LINUX.ORG.RU

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

 


0

3

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

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

Почему? ... Недочет только в том, что на хранение этого дерева на больших строках уйдет много памяти.

Вот поэтому. А накладные расходы сильно зависят, в том числе, и от используемого алфавита. И насчет сложность O(len(word)) ты как следует приврал. Почему-то ты считаешь, что выбор нужного узла, соответствующего заданной букве, осуществляется за константное время. Это так только в том случае, если ты используешь индексацию по символам алфавита, что дает гигантский оверхед по памяти.

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

Во-первых, n_k << N — это твоя нездоровая фантазия.

n_k - число хэш значений, N - число элементов в таблице. Если НЕ выполняется n_k<<N то бинарный поиск в букете вообще бессмысленное действо. Если выполняется, и таблица хорошо сбалансирована - то тем более бессмысленное, потому что эффективный бинарный поиск в букете это готовое дерево, и нафига тогда тут хэш таблица?

AIv ★★★★★
()
Ответ на: комментарий от AIv
#include "uthash.h"
#include <sys/time.h>
#include <stdio.h>

int main( int argc, const char** argv ) {
int i,i2;
double alpha;
float N,sz;
struct timeval tv1,tv2;

struct elem{
int id;
int v;
UT_hash_handle hh;
};
struct elem *p0,*p1;
struct elem *elems = NULL;

N = atof(argv[1]), sz = 0;
alpha = N/RAND_MAX;

for(i=0; i<N; i++ ){
p0=malloc(sizeof(struct elem));
p0->id=i; p0->v=i;
HASH_ADD_INT(elems, id, p0);
}

gettimeofday(&tv1,NULL);
for(i=0; i<1e6; i++,i2=random()*alpha) HASH_FIND_INT(elems, &i2, p1);
gettimeofday(&tv2,NULL);
printf( "%g %g\n", N, tv2.tv_sec-tv1.tv_sec+(tv2.tv_usec-tv1.tv_usec)/1e6 );
return 0;
}
125000 0.18728
250000 0.246063
500000 0.282247
1e+06 0.315836
2e+06 0.285915
4e+06 0.357568
8e+06 0.31575
1.6e+07 0.338424
3.2e+07 0.362088
6.4e+07 0.382202
ae1234 ★★
()
Ответ на: комментарий от Deleted

O(logN) в худшем случае для вставки, удаления, поиска элемента

Забыл добавить, что «в худшем» совпадает со «в среднем».

а также поиск следующего и предыдущего

Хэш-таблица не требует задания отношения порядка, так что говорить «о следующем» и «предыдущем» элементе как-то странно.

В дереве нет свободных ячеек

Уж что-что, а накладные расходы на поддержание древовидной структуры очень некислые: 3 * sizeof(pointer_type), что обычно выливается в 24 байта в современном 64-битном мире. Это эквивалентно 12-символьному русскому слову в utf-8.

Данные, лежащие в бинарном дереве, отсортированы.

А толку-то? Все равно последовательного (с точки зрения адресации памяти) доступа к ним нет.

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

Да я видел... ну опять таки, какой размер хэша (сколько допустимо значений)? Если MAX_INT... значит опять бинарный поиск (по тесту похоже).

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

n_k - число хэш значений

Число допустимых значений хэш-функции? Тогда у тебя «меньше» с «больше» перепутано. Или имеется в виду «количество различных значений хэш-функции, попадающих в одну ячейку хэш-таблицы»?

Если выполняется, и таблица хорошо сбалансирована

Понятие «сбалансированности» к хэш-таблице неприменимо.

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

Число допустимых значений хэш-функции?

да. И нет, не перепутано. В среднем, по одному хэш значению N/n_k элементов. Под «сбалансированностью» я имел ввиду такую хэш ф-ю, которая равномерно распределяет элементы по хэшам ключей.

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

Делает видимо... ну так и выходит то на то, просто вместо less от ключей less от хэшей? Хотя для интов можно че та более эффективное сделать, наверное это в unordered_map и сделано, не зря же она на порядок шустрее.

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

надо было сказать TRIE :)

чо уж мелочиться, поехали - hash array trie

ps на самом деле зависит от задачи, у trie свои недостатки

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

Но и профиты от дерева очевидны.

ну тут как раз у хеша свои преимущества, у дерева свои - в хеше удобнее lookup делать, в дереве search

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

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

ну-ну, посмотрим как ты сделаешь аналог перебора всех веток поддерева с использованием хеша и с какой скоростью это всё у тебя будет работать :)

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

в файловых системах и СУБД применяют B-деревья, которые являются дальнейшим развитием идеи бинарных деревьев поиска

не развитием, а частным случаем

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

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

поиск (понимаем здесь процесс перебора ключей по заданному критерию) по дереву быстрее

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

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

не развитием, а частным случаем

Именно развитием (B-деревья появились позже), и, поскольку двоичные деревья могут быть получены из B-деревьев, именно двоичные являются частным случаем B :)

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

Анонимус-то прав :)

#include <stdio.h>
#include <stdlib.h>
#include <unordered_map>

using namespace std;

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

real    0m13.342s
user    0m12.833s
sys     0m0.351s
$ g++ -O3 -std=c++0x unordered_map_test.cpp && time ./a.out
9976930

real    0m6.135s
user    0m5.832s
sys     0m0.235s

legolegs ★★★★★
()
Ответ на: Анонимус-то прав :) от legolegs

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

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

В общем вот http://a-iv.ru/trash/map-vs-hash.png

Во первых, поведение map и hash (которая unordered_map) совпадают с точностью до множителя, hash на порядок быстрее - лучше реализован бинарный поиск, поскольку заранее известно что ключ uint64_t.

Во вторых, если ограничивать число хэш-значений чиселкой H (кривые вида hash=H) то за счет коллизий сложность алгоритма меняется с O(log(N)) на O(N), как и положено по теории, и ес-но при больших N хэш мапу сливает, ну и чем шире хэш тем быстрее поиск.

В третьих, все кривые делают скачОк при N~10^6. Смотрим:

aiv@node-01:~> less /proc/cpuinfo
...
model name      : Intel(R) Core(TM)2 Quad  CPU   Q9450  @ 2.66GHz
...
cache size      : 6144 KB
Что и следовало ожидать;-)

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

ЗЫ точнее скачок начинается при N~2e5, кэш 6МБ, т.е. 32 байта на ячейку, а в ячейке должно быть long key, int value, long hash + указатель (28 байт в сумме), ну и выравнивание ес-но... картинку можно вставлять в учебник;-)

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

кстати - мерить надо не в тактах - а скорее в колличествах доступа к памяти
один доступ к памяти это 50ns например

алгоритмической сложности то нету - расчитывать особо нечего - одно только общение с памятью

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

Именно что в тактах, приходящихся на один доступ - это единственная объективная характеристика, и пользователю интересна именно она.

алгоритмической сложности то нету - расчитывать особо нечего - одно только общение с памятью

В смысле О_О? Про общение с памятью можно мне не рассказывать - мы как раз занимаемся алгоритмами для числодробилок, оптимальных с т.з. общения с памятью;-)

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

А зачем мне _перебирать_ ветки? Хэш вообще-то для того, чтобы быстро искать.

Посмотрим, как ты бинарным поиском будешь искать по словарю, где 10^6 (любимое местное число) записей и 80% из них начинаются с одинаковой последовательности, допустим, 6 символов. Что там кто балансировать собрался?

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

Тогда как для хэша выбираем 1к начальных ключей, а на следующем уровне идут любимые бинарные деревья.

Сорри за К.О.

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

идут любимые бинарные деревья

Но куда лучше без них

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

нене - тут определенная подмена понятий

2ггрц и 4 ггрц интел - сидя на одной и тойже памяти - в случае больших массивах примерно одно и тоже время покажем - по транзакциям в секунду

а в тактах - будет странная картина - что более быстрый тормазнее более медленного

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

Пока все в кэш ложится, в тактах все будет одинаково. А вот когда уперся в память... в тактах это сразу видно (для алгоритма есть теор. оценка, отсюда считается эффективность), - и падение эффективности как раз повод задуматься и что то поменять, если не в жизни то хотя бы в коде;-)

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

Посмотрим, как ты бинарным поиском будешь искать по словарю, где 10^6 (любимое местное число) записей и 80% из них начинаются с одинаковой последовательности, допустим, 6 символов. Что там кто балансировать собрался?

Так Кнута и не прочел? Балансировка как раз для таких задач и придумана, корень дерева будет в середине словаря, и пофик скока записей имеют совпадающее начало. А вот хэш таблица, с хэшем по первым буквам...

AIv ★★★★★
()

ну как - заюзал чегонить ? :)

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

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

не развитием, а частным случаем

Именно развитием (B-деревья появились позже), и, поскольку двоичные деревья могут быть получены из B-деревьев, именно двоичные являются частным случаем B :)

с логической цепочкой и хронологией полностью согласен, но насчёт развития... можно, конечно, говорить, что бранч является развитием транка, но майнлайн от этого не стопается

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

Таки развитием.

я бы всё же это назвал веткой эволюции

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

А зачем мне _перебирать_ ветки? Хэш вообще-то для того, чтобы быстро искать.

ну и теперь, для полноты картины, поясни что есть поиск

Посмотрим, как ты бинарным поиском будешь искать по словарю, где 10^6 (любимое местное число) записей и 80% из них начинаются с одинаковой последовательности, допустим, 6 символов. Что там кто балансировать собрался?

а в чём проблема? и почему именно бинарный поиск?

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

перебор - это самый плохой вариант поиска
это когда тупо перебирают компоненты

а поиск - это хочу вот это -> так вот оно !
хеши и по комбинации параметров могут быть

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

а поиск - это хочу вот это -> так вот оно !

ок, вот пример - хочу достать все строки из словаря соответствующие шаблону «сам***н», как будем решать?

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

атличаеться

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

в моей - сортировка по возрастанию непомогет

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

да суть не в этом, а суть в том что хэш на обоих задачах сольёт

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