LINUX.ORG.RU

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

 


0

3

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

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

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

soomrack ★★★ ()

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

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

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от tailgunner

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

Eddy_Em ☆☆☆☆☆ ()

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

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

schizoid ★★★ ()

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

qnikst ★★★★★ ()

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

anonymous ()

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

ae1234 ★★ ()
Ответ на: комментарий от anonymous

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

anonymous ()
Ответ на: комментарий от anonymous

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

AIv ★★★★★ ()
Ответ на: комментарий от AIv

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

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

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

Тся, блин.

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

День анонимной школоты на ЛОР-е? Даже если у тебя хэш не вырожден, 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

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

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

AIv ★★★★★ ()
Ответ на: комментарий от ae1234

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

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

AIv ★★★★★ ()
Ответ на: комментарий от AIv

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

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

AIv ★★★★★ ()
Ответ на: комментарий от AIv

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

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

А 4/2 = 1.5

anonymous ()
Ответ на: комментарий от AIv

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

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

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

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

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

ae1234 ★★ ()
Ответ на: комментарий от AIv

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

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

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

anonymous ()
Ответ на: комментарий от ae1234

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

anonymous ()
Ответ на: комментарий от ae1234

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

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

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

tailgunner ★★★★★ ()
Ответ на: комментарий от anonymous

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

anonymous ()
Ответ на: комментарий от anonymous

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

ae1234 ★★ ()
Ответ на: комментарий от ae1234

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

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

O02eg ★★★★★ ()
Ответ на: комментарий от ae1234

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

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

anonymous ()
Ответ на: комментарий от ae1234

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

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

tailgunner ★★★★★ ()

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

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

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

AlexCones ★★★ ()
Ответ на: комментарий от tailgunner

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от AlexCones

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

AIv ★★★★★ ()
Ответ на: комментарий от AlexCones

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

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от AIv

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

AlexCones ★★★ ()
Ответ на: комментарий от AlexCones

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

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

AIv ★★★★★ ()
Ответ на: комментарий от Eddy_Em

Вот, пожалуйста: тупой линейный поиск при помощи 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);
}
ищем 100-тысячную запись:
gcc 1.c && time ./a.out 00099999
found str 00099999, num = 99999

real	0m0.013s
user	0m0.012s
sys	0m0.000s
(и это учитывая время на инициализацию). В общем, с частотой герц в 20 искать будет.

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

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

Eddy_Em ☆☆☆☆☆ ()

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

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

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

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

Deleted ()
Ответ на: комментарий от Eddy_Em

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

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

AIv ★★★★★ ()
Ответ на: комментарий от Deleted

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

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

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

AIv ★★★★★ ()
Ответ на: комментарий от Deleted

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

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

tailgunner ★★★★★ ()
Ответ на: комментарий от anonymous

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

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

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

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

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

Deleted ()
Ответ на: комментарий от AIv

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

anonymous ()
Ответ на: комментарий от AIv

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

Eddy_Em ☆☆☆☆☆ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.