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

Брысь, читать про хэш-таблицы с прямой адресацией.

Просто другой механизм разрешения коллизий. Разумеется это хэш-таблица.

См. выше.

Если множество не меняется в процессе, можно тупо сделать switch - case для всех чисел, доступных в множестве. Компиляторы достаточно хорошо умеют оптимизировать такое. Можно тут об этом почитать http://www.insidepro.com/kk/031/031r.shtml

Хэши тоже нужно делать руками

Попробовал хэш руками. Все по инструкции, 2**16 бакетов, хэш = число >> 16. Но я не эксперт в хэшах, мог что-то неправильно сделать.

Результат (10000000 выборок):

bsearch ... ok, 0.500542 secs
hash ... ok, 0.730773 secs

Вот код, хэш с открытой адресацией:

#define HTSIZE (1 << 16)

struct hbucket
{
        size_t nent;
        ITEMTYPE *entries;
};

static void
hhash_test(ITEMTYPE *set)
{
        size_t i;
        struct timeval begin, end;
        struct hbucket hash_table[HTSIZE];

        memset(hash_table, 0, HTSIZE * sizeof(struct hbucket));

        for (i=0; i<SETSIZE; i++) {
                uint16_t idx;

                idx = set[i] >> 16;
                hash_table[idx].entries = realloc(hash_table[idx].entries, (hash_table[idx].nent + 1) * sizeof(ITEMTYPE *));
                hash_table[idx].entries[hash_table[idx].nent] = set[i];
                hash_table[idx].nent++;
        }

        printf("hash ... ");

        gettimeofday(&begin, NULL);
        for (i=0; i<NRUNS; i++) {
                ITEMTYPE sample;
                uint16_t idx;
                size_t j;

                sample = rand();
                idx = sample >> 16;

                for (j=0; j<hash_table[idx].nent; j++) {
                        if (hash_table[idx].entries[j] == sample) break;
                }
        }
        gettimeofday(&end, NULL);
        printf("ok, %f secs\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0);

        for (i=0; i<HTSIZE; i++) {
                if (hash_table[i].nent > 0) free(hash_table[i].entries);
        }
}

на твоём сете выигрывает таблица

Это ты кагбэ теоретически так написал или как-то проверил?

Это ты кагбэ теоретически так написал или как-то проверил?

И то, и другое. У меня хеш раза в два работает быстрее в указанных условиях с бинарным и линейным поисками по бакету, примерно как ожидал.

Мб у тебя получилось медленнее из-за того, что берёшь для хэша старшие байты. Т.к. rand() не всё заполняет в 2**32, то средняя длинна бакета выходит большей. Т.е. минимум половина таблицы не используется.

man универсальное семейство хеш-функций

А, понял. У меня неправильно вызывался bsearch. Надо было «bsearch(&sample, set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);», перепутал порядок аргументов. Начал внимательно смотреть, недоумевать, и увидел. Да, на таком размере и хэш = число & 0x0000ffff получается так:

bsearch ... ok, 2.526986 secs
hash ... ok, 0.892438 secs

Т.е. хэш быстрее чем bsearch почти в 3 раза.

bsearch начинает обгонять хэш только на массиве где-то в 50 млн. элементов (ну, это если я опять где-то не перепутал).

Результаты BDB тогда тоже не так грустны - bdb-шный хэш всего где-то на порядок медленнее написанного руками.

Но в любом случае, вариант с qsort/bsearch самый компактный и быстрый в изготовлении, я бы не парился и делал так, по-простому, а потом уже оптимизировал если нужно

Если у тебя хеш таблица с хеш-функцией id, то это таки не хеш-таблица.

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

вероятность совпадения хэшей (допустим 64 битный хэш) значительно меньше вероятности коллизии в таблице (log2(размер_таблицы) бит).

изначально речь шла о

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

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

Любопытство не отпустило, написал еще немного тестов (уже не поленился, делал с проверками):

Judy array: 0.341420 secs
Битмап: 0.424979 secs *
Хэш вручную с линейным поиском: 0.461485 secs
Интерполирующий поиск: 0.685202 secs
bsearch вручную: 0.798197 **
bsearch: 1.069592 secs
bdb btree: 7.752924 secs
bdb hash: 6.879257 secs

* производительность битмапа довольно сильно плавает, иногда бывает хуже чем у хэша вручную

** вдохновение черпал здесь: http://schani.wordpress.com/tag/c-optimization-linear-binary-search-sse2-simd/ но без ассемблерных cmov

Это все на rand(), конечно, делать какие-то худшие/лучшие наборы не хочется.

Выводы неутешительные: верить в наше время нельзя никому, порой даже самому себе

Пошарь сырец - я допишу свои варианты и почекаю твои.

Уже давно пора понять, что всё готовое - говно, особенно то, что связанно с БД.

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

В бревне ты получаешь 100% фейл на каждый свич ветвей.

То, что О-питушки, как и ООП-питушка, так и БД-питушки - бесполезное и безрукое говно, которое нихрена в этой жизни не знаю, кроме «ко-ко-ко в худжеш случае там Oпоменьше», «слишком лень пилить кастыль, который пилить 5минут», «Лучшие умы писали бдб и bsearch() в сишке - ты не можешь написать лучше». - тоже не удивил.

Пошарь сырец

http://pastebin.com/sKunxDYk

питушки

Вот это вот что-то знакомое. Царь? Впрочем, какая разница

студент, полегче

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

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

Такая техника работает только на маленьких наборах. Я попробовал на твоих 300000 чисел (пробовал if и switch/case) и не смог дождаться пока gcc эту портянку скомпилирует. Уменьшил до 30000, gcc как-то прожевал (без -O, с -O3 тоже долго, я не дождался), clang вывалился с ошибкой.

Ну и функция работала медленнее всех, компилятор ничего особо умного там не сделал.

Но вообще идея интересная. Не обязательно знать массив на этапе компиляции приложения. Можно программно генерировать С-код, делать из него динамическую библиотеку, потом dlopen/dlsym и вот у нас есть быстрая функция. Если бы у тебя был небольшой набор, интересно было бы сравнить производительность

Такая техника работает только на маленьких наборах. Я попробовал на твоих 300000 чисел (пробовал if и switch/case) и не смог дождаться пока gcc эту портянку скомпилирует. Уменьшил до 30000, gcc как-то прожевал (без -O, с -O3 тоже долго, я не дождался), clang вывалился с ошибкой.

Один из лоровцев решил эту прооблему несколько лет назад. Если интересно - попробуй порытся по форуму. там явно форсировалась компиляция gcc с -O0 или -O1. с -O2 уже не взлетало.

Но вообще идея интересная. Не обязательно знать массив на этапе компиляции приложения. Можно программно генерировать С-код

Ужоснах. AFAIK, gcc генерирует perfect hash для всего набора case, и ты тоже можешь его генерировать во время исполнения (это одна из техник разрешения коллизий, дает константное время поиска).

студент, полегче

Это не студент. Так, гений-самоучка.

Ужоснах

Ну вот везде пишут что сейчас на маленьких массивах самый быстрый поиск - линейный. Поиск кодом у меня отрабатывает раза в два-три быстрее чем линейный. Вот тест с генерацией С-кода, деланием из него библиотеки и dlopen/dlsym: http://pastebin.com/sP5gAei5 .

AFAIK, gcc генерирует perfect hash для всего набора case

gcc для if (с -O3) генерирует что-то типа такого:

cmp    $0x6b8b4567,%eax
je     58 <set_test+0x58>
cmp    $0x327b23c6,%eax
je     58 <set_test+0x58>
cmp    $0x643c9869,%eax
je     58 <set_test+0x58>
...

И иногда разбавляет nop/xchg %ax,%ax.То есть вообще в лоб.

Для switch/case там уже что-то сложное http://pastebin.com/zLBiGGY2 , я с наскока и не понял что это, но не похоже на хэш, больше похоже на какие-то хитрые сравнения. switch/case получается медленнее чем if.

clang на if тоже умничает:

cmp    $0x238e1f28,%eax
jg     16 <set_test+0x16>
cmp    $0x19495cff,%eax
jne    82 <set_test+0x82>
jmp    8d <set_test+0x8d>
cmp    $0x74b0dc50,%eax
jg     7b <set_test+0x7b>
cmp    $0x2ae89449,%eax
jg     2d <set_test+0x2d>
...

И тоже получается медленнее чем gcc-шный if. Но все еще быстрее линейного поиска «в данных»

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

Возможно (а возможно и нет) если генерировать не С, а ассемблерный код, то можно будет захардкодить весь поиск. Скажем, тем же интерполирующим поиском. Но это тоже надо думать, проверять, и тоже лень

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

А что такое «маленький массив», в этом везде пишут?

gcc-шный if
быстрее линейного поиска

Просто интересно - зачем ты это пишешь?

Просто интересно - зачем ты это пишешь?

Что именно «это»? Мне интересно, какими приемами можно достичь хорошей производительности. Я же написал - интересующийся диваный теоретик.

Способов узнать что-то не так уж много - читать статьи, код или интересоваться у знающих людей. Статьи могут быть бессмысленными, а могут содержать ценную информацию. Знающие люди могут имитировать знание, а могут действительно знать. Проверить это сложно, можно проверить (и то очень условно) только какую-то часть утверждений. Вот mashina пишет: «на твоём сете выигрывает таблица на 2**16 бакетов» и это кажется вполне разумным. А выигрывают Judy-массивы. И битовые карты.

Ты пишешь «gcc генерирует perfect hash для всего набора case, и ты тоже можешь его генерировать во время исполнения». Подразумевая (наверное) что это работает быстрее остальных способов. Я беру массив из 8 элементов и делаю тест: генерирую switch/case, скармливаю его gcc. Потом генерирую набор if-ов и тоже скармливаю gcc. Сравниваю все с линейным поиском. Набор if-ов оказывается быстрее всех. Потом делаю такой же тест с clang-ом. То что сгенерировал gcc на наборе if-ов опять оказывается быстрее всех.

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

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

Просто интересно - зачем ты это пишешь?

Что именно «это»?

Стену текста про if и линейный поиск.

Я беру массив из 8 элементов
Набор if-ов оказывается быстрее всех

Я правильно понял - поиск в массиве из 8 элементов? Ты это серьезно?

И если ты знаешь быстрый способ найти принадлежность числа к массиву

В этом топике перечислили много способов, которые быстрее линейного поиска.

Я правильно понял - поиск в массиве из 8 элементов? Ты это серьезно?

Да. Уже давал ссылку http://schani.wordpress.com/tag/c-optimization-linear-binary-search-sse2-simd/ , там аффтар пишет что до 50-60 элементов линейный поиск быстрее чем bsearch, и ему хочется верить. Ну и поиск кодом на таком размере быстрее линейного. То есть, с большой вероятностью, на маленьких массивах (до 60 элементов) поиск кодом будет быстрее всех.

mashina предложил хороший вариант с хэшем, если допустить что числа распределены более-менее равномерно, в каждом бакете будет 300000/65536 элементов, т.е. 4-5. Если коллизии получится разрешать в 2-3 раза быстрее, то и весь алгоритм слегка ускорится (это гипотеза, конечно)

В этом топике перечислили много способов, которые быстрее линейного поиска.

Ясно

с большой вероятностью, на маленьких массивах (до 60 элементов) поиск кодом будет быстрее всех.

На массивах, которые быстро подкачиваются в кэш. Но в условии задачи дан массив на 1.2М и (неявно) встроенный процессор. Поэтому рассуждения о «поиске кодом» вызывают у меня недоумение (предложение вызывать компилятор на стадии исполнения - тоже).

(неявно) встроенный процессор.

добавил железку в топик явно

Лучше бы ты добавил частоту и размер кэшей :)

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