Текстовые индексы.

man tsearch

man hsearch

А что, строковые значения не упорядочиваются? Для построения индекса нужно только отношение порядка.

Струкура: хешмассив + индекс по строковому значению.

Но кажется уже сейчас ясно, что это будет глючить и тормозить...

Я так думал совсем недавно о gettext. Однако, работает и не тормозит.

Для ускорения можно небольшое индексирование сделать (хотя бы хранить индексы в строковом массиве, с которых начинаются слова на очередную букву). А можно использовать sqlite, который «сам» все проиндексирует.

Да уж. А я, не зная об этих функциях, когда-то велосипед строил для поиска...

Если алфавитный порядок не важен, тогда хеш, конечно.

А поиск по строковому не будет тормозить, если бинарный.

std::map

деревьями по буковам (общим частям).

man google
google man hash

Только хэш, бинарнопоисковые тормоза в топку.

это стандартный хеш массив
например сделай сумму всех символов ключа - и возми остаток от деления результата на 256
ты получиш хеш строки
вот это и будет - номер для строки в массиве обычьном

Так С же? Можно ли использовать std?

Ну а если строки заранее известны (на момент компиляции и меняются только от версии к версии), то тут gperf просто сам просится. И никаких велосипедов с бинарными говнодеревьями, очень прошу.

велосипедов с бинарными говнодеревьями

сделаем мир чище, а программы быстрее

да-да. Особенно хорош хэш когда записей овер 10^6, а вариантов хэша 256, и то все вырождается в 2-3 варианта. Хоть бы уточнили у ТС-а параметры задачи, прежде чем потрясать ЛОР фееричностью глубины своих знаний...

Поговори мне ещё.

хэш когда записей овер 10^6, а вариантов хэша 256

Бинарные деревья загнуться раньше.

и то все вырождается в 2-3 варианта.

Мне понятна любовь к бинарному поиску у тех, кто нормально хэш не может сделать. Ничего утешительного на это сказать не могу. Люди не виноваты, что у них мозгов тольно на бинарный поиск и хватает.

и то все вырождается в 2-3 варианта.

Берутся за хэш, делают криво, он у них быстро вырождается и работает хуже даже перебора, не то что бинарного поиска. И из этого они делают выводы отнюдь не о своих скудных познаниях, а о ущербности хэша.

даже 256 хеша при 10^6 записей лучше перебора :)

Бинарные деревья загнуться раньше.

Тся, блин.

Твой полуграмотный комментарий даже меня опустил до твоего уровня.

Люди не виноваты, что у них мозгов тольно на бинарный поиск и хватает.

А то пишут, пишут. Хэш, коллизии какие-то. Голова пухнет. Взять всё, да и поделить.

Поговори мне ещё.

День анонимной школоты на ЛОР-е? Даже если у тебя хэш не вырожден, 10^6/256 ~ 4000, log(10^6)/log(2) ~ 20. Считать умеешь?

Бинарные деревья загнуться раньше.

$ cat test.cpp
#include <stdio.h>
#include <stdlib.h>
#include<map>

using namespace std;

int main() {
        map<long,int> table;
        for(int i=0; i<1e7; i++ ) table[random()] = table.size();
        printf("%i\n", table.size() );
        return 0;
}
$ g++ -O3 test.cpp
$ time ./a.out 
9976930

real    0m29.838s
user    0m29.090s
sys     0m0.712s

Ничего утешительного на это сказать не могу.

Научись сначала не хамить незнакомым дядям, потом уже говори. Хотя по делу от тебя вряд ли че то услышать можно, так что лучше уж и правда молчи... Кнута что ли почитай.

даже 256 хеша при 10^6 записей лучше перебора :)

Но хуже бинарного поиска;-)

Кнута что ли почитай.

Вот именно. Сам-то давно читал, или это тебе умные дяди рассказали, что Кнут - это такой крутой авторитет?

В свете этой отсылки к авторитету на разбор твоего кода и проверки утверждений нет никакого желания. Ты уж извини, но ты мерзок. Не хочешь, чтобы тебе хамили - сначала заслужи это, воздерживаясь от написания бреда.

Знаешь такую поговорку - полчи, за умного сойдёшь? Ну так вот, это про тебя.

Из такой кучи букв ни одной по делу... ожидаемо;-)

Но хуже бинарного поиска;-)

Да-да-да, дебилушка. Ну конечно хуже.

А 4/2 = 1.5

и тут мы вспоминаем - что доступ к памяти - не такой простой
если грубо то - рандомный доступ к памяти это задержка на 30-50микросекунд а дальше данные льются на фулл скорости памяти

и в случае с хешем - это 1 рандомный доступ к памяти + еще один рандомный с чтением блока
в случае с мапой - это 20 рандомных доступа к памяти

если в среднем - 4тонны элементов во вторичном массиве при условии хеша 256занчного
и если взять элемент - ну 32 байта - это эти 128 кбайт прочитаються последовательно за 26микросекунд (5гбайт чтение из памяти)

получаем - при случае хеша 50+50+26
при случае мапы 50*20
;)

(цифры почти с потолка)

Кто бы говорил. Ах да, у тебя же хэш хуже бинарного поиска, как я мог забыть.

Ну, _твоя реализация_ хуже, в этом ты меня убедил. Хэщ функция-то какая, сумма элементов по модулю?

И да, сортируешь-то, небось, пузырьками, как тебя на первом курсе учили? Или старшые товарищи показали что по-лучше?

По-моему для него это (цена доступа к памяти) слишком высокие материи. Бесполезно.

если грубо то - рандомный доступ к памяти это задержка на 30-50микросекунд

30-50микросекунд

Куясе. Это где так?

Он живёт в стране розовых бинарных деревьев и нежно-голубого Кнута. Которого, я уверен, сам он не читал, иначе бы не писал такой бред.

ну - бинарный поиск он действительно быстрее и надежнее - но реальность свои коррективы вносит

ой сори - нано секунд - обшибся

http://cdn.erodov.net/portal/reviews/ram/gskill-ripjaws/ripjaws-aida64-2133.jpg

и в случае с хешем - это 1 рандомный доступ к памяти + еще один рандомный с чтением блока

Воистину, кто-то не осилил коллизии.

Он простой как пробка - это да, потому что там ломаться нечему. Как я уже цитировал: «взять всё, да и поделить».

Но реальность штука грубая, да. Всё время конфликтует с идеальными представленими о мире и тем, чему в институте учили (это кого учили).

все колизии во вторичном массиве - шонетак ?

ой сори - нано секунд - обшибся

Понятно. А теперь объясни, почему ты считаешь, что в случае хэша уложишься в одну операцию доступа к памяти %)

Уууу, колько всего понасоветовали.

Уточняю условия задачи: элементов в 99% случаев не более 1000, длина строки постоянна - 8 символов.

Макс, опять проблемы с ЛОРом - любая клавиша - переход в другую тему. Набирал в gedit`е.

А вдруг он сразу же попадет в нужное слово? ☺

Какие то ограничения на скорость поиска есть?

не более 1000
8 символов

Тут и тупым strcmp шустро будет. Если, конечно, не надо миллион-другой операций в секунду выполнять.

Желательно побыстрей, но чтобы сейчас на этапе написания кода было меньше геморроя и возможностей отстрелить себе выпирающие части.

1000 это по любому мало, почти ничего. Можно сделать хоть в лоб как Вы планировали, хоть сваять структуру из строки и числа и с ними уже плясать (это в принципе более Ъ) - хоть тем же перебором, хоть хэш таблицей, хоть половинным делением. Из простых фенек - можно запоминать посл результат поиска и потом проверять его, для повторяющихся обращений помогает;-)

А строки произвольные или в них есть какая то закономерность? Сколько занчений может принимать каждая буква? Опять поди мол. биология;-)

Вот, пожалуйста: тупой линейный поиск при помощи strcmp

#include <stdio.h>
#include <string.h>

#define SZ 100000

int main(int argc, char **argv){
	char symbols[SZ][9];
	char *key;
	int numbers[SZ];
	int i;
	if(argc != 2){
		printf("Usage: %s string\n", argv[0]);
		return(-2);
	}
	key = strdup(argv[1]);
	for(i = 0; i < SZ; i++){
		sprintf(symbols[i], "%08d", i);
		numbers[i] = i;
	}
	for(i = 0; i < SZ; i++)
		if(strcmp(symbols[i], key) == 0){
			printf("found str %s, num = %d\n", key, numbers[i]);
			return(0);
		}
	printf("not found str %s\n", key);
	return(-1);
}

gcc 1.c && time ./a.out 00099999
found str 00099999, num = 99999

real	0m0.013s
user	0m0.012s
sys	0m0.000s

А если мы сделаем бинарное дерево, поиск вполне может ускориться.

Ну, а ежели еще и индексирование добавить…

И да, таки именно С или С++?

Самыми популярными решениями подобных задач являются хэш-таблицы и сбалансированные деревья поиска. Я предпочитаю именно деревья, т.к. с ними для поиска значения нужно гарантировано O(logN) операций сравнения, а хэш-таблица при правильно подобранных ключах может заставить тебя потратить на поиск O(N) сравнений. Все эти алгоритмы реализованы 100500 раз в разных библитеках. Стандартный плюсовый map реализует дерево, нестандартизованный, но вездесущий hash_map - отображение на основе хэш-таблицы.

Однако, такие решения для строк неоптимальны. Намного лучше будет сделать дерево по буквам. Т.е., есть корень дерева и от него ветки, соответствующие возможным буквам, и от каждого дочернего узла так же. Чтобы найти значение, соответствующее некой строке «string», ты из корня переходишь по переходу 's', потом из вершины, в которую перешел - по ветке 't', потом - по ветке 'r', 'i', 'n', 'g', в результате ты доберешьсядо вершины, соответствующей искомому числу.

Вставка в такое дерево и удаление из него являются очевидными. Сложность поиска - O(N), где N - длина строки. Лучше тебе вряд ли удастся достичь.

PS. ЛОР, ты меня расстраиваешь. Уровень вопросов падает все ниже и ниже. Доки не читают даже по самым базовым вещам.

ищем 100-тысячную запись:

Там основное время не поиск а набивание массива snprintf-ами;-)

Дерево по буквам хорошО, я над ним мельком думал... но оно может (в самом общем случае) потребовать значительно больше памяти - веток много, и тупики тоже надо обозначать. Кроме того оно нестандартное (ну я не встречал), асилит ли ТС?;-) Хотя для его размера с т.з. производительности это наверное оптимально, поскольку нету лишних телодвижений со сравнением строк.

PS. ЛОР, ты меня расстраиваешь. Уровень вопросов падает все ниже и ниже.

Зато анонимусы хамят как встарь;-)

ЛОР, ты меня расстраиваешь. Уровень вопросов падает все ниже и ниже

Кхм. Ну, тогда и уровень ответов тоже падает - надо было сказать TRIE :)

Бинарные деревья загнуться раньше.

Бинарным деревьям ничего не случится на миллиардах записей. Т.к. на миллионе это около 20 сравнений, а на миллиарде - около 30, и чем дальше, чем медленнее растет (ибо O(logN)).

В отличии от этих ваших деревянных хэшей...

Мне понятна любовь к бинарному поиску у тех, кто нормально хэш не может сделать.

Нормальное сбалансированное бинарное дерево сделать намного проще, чем написать жалкий хэш. Но и профиты от дерева очевидны.

А регистранты всё так же с гордостью жидко какаются и пытаются потом отшутиться, типа я не я и лошадь не моя. Молчал бы, дерево-лучше-хэша.

Вот и я о том же: на таком малом количестве данных даже не оценишь скорость. Разве что миллион-другой раз поиск вызывать...