мб пройдёт ещё немного и ты прочитаешь что такое b+ дерево?

Только если время пойдет вспять.

так до сторожа (не путать со storage'ем) и кроссвордов недолго дисквалифицироваться

так до сторожа (не путать со storage'ем) и кроссвордов недолго дисквалифицироваться

Конечно-конечно, как скажешь.

Алгоритмически кэшей в постановке задачи нет вовсе.

Однако в целом это интересно, некое количество вычислений с иерархией кэшэй (бежишь считать эвристики) и нормальной вероятностью попасть мимо них (продолжаешь считать эвристики) против гарантированного одного обращения к RAM.

Тесты проведёшь или тупо сольшёся? Мне интересно, не сливайся просто так.

А чем тебе не нравится вменяемо выбранный hash?

А чем тебе не нравится вменяемо выбранный hash?

Я не уверен, что можно вменяемо выбрать хэш-функцию для таких данных.

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

для таких данных.

А что не так с данными?

Это идея - ровно то, что называется hash. С небольшими усилениями и усложнениями, но именно так.

подобрать функцию распределения и методом монте-карло... шутка

Можно с битовыми векторами попробовать. Есть интересные реализации этого подхода.

А что не так с данными?

Единственное, что я о них знаю - то, что они короткие.

Алгоритмически кэшей в постановке задачи нет вовсе.

Ещё там не сказано, что решение нужно алгоритмическое, верно? Значит нужно учитывать детали реализации. На указанных масштабах чисел всё будет упираться именно в кэши.

Тесты проведёшь или тупо сольшёся? Мне интересно, не сливайся просто так.

Ты же несёшь галиматью на счёт 1-2 тактов, вот иди и сам копайся в песочнице. Для справки, извлечение из L3 уже будет занимать несколько десятков тактов.

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

Значит нужно учитывать детали реализации.

Начинай рассказывать про детали реализации BlueGene'а, готов угорать.

Ты же несёшь галиматью на счёт 1-2 тактов,

Для рисков будет именно так.

А сейчас тебе следует привести эвристики для фильтра Блума и других вариантов для абстрактной иерархии кэшей. Против одного обращения к ОЗУ, само собой.

На хэшах, наверное, можно хорошо выехать,

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

Этого недостаточно?

Для рисков будет именно так.

Неужели так трудно остановиться и пересать нести галиматью?

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

а ты попробуй реализуй этот вариант на практике. Пока это только эврестическое решение существующее не для любой последовательности.

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

Неужели так трудно остановиться и пересать нести галиматью?

Сам удивляюсь.

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

а ты попробуй реализуй этот вариант на практике

Спасибо, я пас, я больше люблю системный подход.

тупой вариант с битовым вектором на 512 мб

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

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

Даже алгоритм с трудом представляю, для которого она понадобится.

Ну ты чё? А просто в цикле перебрать и сравнить с каждым?

см вероятностные фильтры в частности фильтр блума.

это только префильтр, он не отменяет конечной проверки.

Он дает вероятностный ответ что объект принадлежит множеству но совершенно точные что оно не принадлежит. Если топикстартеру достаточно будет такого ответа - то фильтра достаточно. Если нет то фильтр + любой бинарный поиск - так он уменьшит количество поисков только до тех которые не отсутствуют однозначно.

нужно максимально быстро

Judy array

Этого недостаточно?

Для уверенности в том, что можно вменяемо выбрать хэш-функцию - недостаточно. По крайней мере, мне. Если тебе достаточно - обоснуй, почему.

radix tree
//nerdogeek

Это не говоря о том, что у ТС стопудово какая-то встроенная хрень, у которой L2 нифига не гигантский.

пятая панда ;)

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

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

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

И ты всё равно называешь это хэш-таблицей? okay.jpg

Таблица на 4G битов 512 MiB памяти, O(1) по времени
Хеш-таблица O(1) по времени, если хеш-функция обеспечивает нормальное распределение, памяти в идеале 300000 * 4 = 1.2 MB, в реальности примерно 2 MB.
Двоичное дерево не меньше 300000 * (4 + 3 + 3) 3 MB памяти, O(lnN) операций.
Можно сделать 256-ричное дерево по байтам. Будет 4 уровня. Память зависит от элементов. Поиск в 4 операции и неплохо ложится во всякие кеши. Имхо это оптимальный вариант.

баран, l2 отвечает за десяток циклов. l1 за полдесятка.

автор, приближенное решение рулит иногда. еще возможно надо обдумать, что быстрее поступает: цифры которые искомые или сравниваемые.

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

а реально: тебе нужен 1 бит на число!

4гигабита = 512 мегабайт. или по 32 бита можно хешировать.

по хэшу находишь массив битов где ищешь поиском смещения и нужного бита в маске

И ты всё равно называешь это хэш-таблицей? okay.jpg

А как ты предлагаешь это называть? http://docs.enlightenment.org/auto/eina/group__Eina__Hash__Group.html#hashtab...

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

А как ты предлагаешь это называть? http://docs.enlightenment.org/auto/eina/group__Eina__Hash__Group.html#hashtab...

Я предлагаю называть этотак, как называет автор: Eina_Hash. О том, что хэш таблица не предполагает отношения порядка, тебе уже сказали.

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

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

не обязательно, ключ для дерева делают из первичного хэша

слабовато для разрешения коллизий

сразу считают два разных.

а почему бы на основании этого второго хеша в хеш-таблицу не положить ещё одну хеш-таблицу :)

а почему бы на основании этого второго хеша в хеш-таблицу не положить ещё одну хеш-таблицу :)

Это один из способов разрешения коллизий.

слабовато для разрешения коллизий

зависит исключительно от битности хэша. И в любом случае это лучше чем бегать по листу в плохих кейсах.

Это идея - ровно то, что называется hash. С небольшими усилениями и усложнениями, но именно так.

Таки надо быть альтернативно одаренным, чтобы называть это hash.

hash + bitset на 300000 элементов = O(1) на test/update и ~37 Кб памяти

зависит исключительно от битности хэша.

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

чудесный способ, только он опять не гарантирует, что в худшем случае поиск не займет O(n).

чудесный способ, только он опять не гарантирует, что в худшем случае поиск не займет O(n).

Просто я не сказал, что там генерируется perfect hash.

в плохом случае хеши совпадают и у тебя будет дерево с одним узлом в списком в нём

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

ничем не лучше, чем просто список

скажи уж сразу, что хэш таблица ничем не лучше неупорядоченного списка, т.к. вероятность 100% коллизии больше нуля. Намёк понятен?

Мальчики, а вычисление самого хеша у вас случайно не займёт больше тактов, чем поиск в дереве, которое помещается в кеш CPU целиком?

Отсортируй, проиндексируй и дальше уже либо тупым перебором, либо дихотомией.

А зачем индекс для перебора или дихотомии?

Для начала. Но он, оказывается, и не нужен-то: от силы спасет на 1-2 сравнения.

Я предлагаю называть это так, как называет автор: Eina_Hash.

Я гуглил наглядную картинку, чтобы показать тебе во избежание недоразумений. Это первое, что нагуглилось. Аналогичных реализаций как собак нерезаных, благо идея заменить классический линейный список на что-нибудь более шустрое лежит на поверхности.

О том, что хэш таблица не предполагает отношения порядка, тебе уже сказали.

Потрясающе, капитан! Это как-то мешает тому, что написано тут: посоветуйте быстрый алгоритм установления принадлежности числа к множеству (комментарий) ?

Используй битовые поля соответствующей размерности.

Мальчики, а вычисление самого хеша у вас случайно не займёт больше тактов, чем поиск в дереве, которое помещается в кеш CPU целиком?

Хаотичные обращения в память, которые характерны для поиска по дереву, стоят очень дорого (тут выше уже срались про тайминги L2). Если хеш не слишком упорот криптостойкостью, то не займет.

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

Сравнивается Btree, Hash и qsort/bsearch. Btree и hash из Berkeley DB, без тюнинга, я только увеличил размер cachesize, поставил на всякий случай 100М.

Тест работает так: заполняем массив rand(), подготавливаем и делаем 1000000 поисков (ищем тоже rand()). Замеряется только время выборки. Результаты:

bsearch ... ok, 0.052041 secs
Btree db ... ok, 1.945713 secs
Hash db ... ok, 1.586483 secs

bsearch почти в 40 раз быстрее чем bdb-шный btree.

Скорее всего можно как-то потюнить BDB, или попробовать LMDB, или написать btree/hash руками, но вот на таком наборе данных я бы не парился, qsort/bsearch хороший выбор.

#include <assert.h>
#include <db_185.h>

#include <fcntl.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <sys/types.h>

typedef uint32_t ITEMTYPE;
#define SETSIZE 300000

#define NRUNS   1000000


static void
bdb_test(ITEMTYPE *set, DBTYPE dbtype, void *dbinfo)
{
        size_t i;
        DB *db;
        DBT key, data;
        ITEMTYPE sample;

        struct timeval begin, end;

        db = dbopen(NULL, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR, dbtype, dbinfo);

        data.data = NULL;
        data.size = 0;
        key.size = sizeof(ITEMTYPE);
        for (i=0; i<SETSIZE; i++) {
                key.data = &set[i];
                db->put(db, &key, &data, 0);
        }

        printf("db ... ");

        gettimeofday(&begin, NULL);
        key.data = &sample;
        for (i=0; i<NRUNS; i++) {
                sample = rand();
                db->get(db, &key, &data, 0);
        }
        gettimeofday(&end, NULL);
        printf("ok, %f secs\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0);
        db->close(db);
}

static int
cmp_func(const void *p1, const void *p2)
{
        ITEMTYPE *a = (ITEMTYPE *)p1;
        ITEMTYPE *b = (ITEMTYPE *)p2;
        return *a - *b;
}

static void
bsearch_test(ITEMTYPE *setsample)
{
        size_t i;
        ITEMTYPE *set;
        struct timeval begin, end;

        set = malloc(SETSIZE * sizeof(ITEMTYPE));
        assert(set != NULL);
        memcpy(set, setsample, SETSIZE * sizeof(ITEMTYPE));

        qsort(set, SETSIZE, sizeof(ITEMTYPE), &cmp_func);

        printf("bsearch ... ");

        gettimeofday(&begin, NULL);
        for (i=0; i<NRUNS; i++) {
                ITEMTYPE sample, *res;

                sample = rand();
                res = bsearch(&sample, set, sizeof(ITEMTYPE), SETSIZE, &cmp_func);
        }
        gettimeofday(&end, NULL);
        printf("ok, %f secs\n", ((double)((end.tv_sec - begin.tv_sec)*1000000 + end.tv_usec - begin.tv_usec)) / 1000000.0);
        free(set);
}

int
main()
{
        ITEMTYPE *set;
        size_t i;

        BTREEINFO btree_info;
        HASHINFO  hash_info;

        set = malloc(SETSIZE * sizeof(ITEMTYPE));
        assert(set != NULL);

        for (i=0; i<SETSIZE; i++) {
                set[i] = rand();
        }

        bsearch_test(set);

        printf("Btree ");
        memset(&btree_info, 0, sizeof(BTREEINFO));
        btree_info.cachesize = 100 * 1024 * 1024;
        bdb_test(set, DB_BTREE, &btree_info);

        printf("Hash ");
        memset(&hash_info, 0, sizeof(HASHINFO));
        hash_info.cachesize = 100 * 1024 * 1024;
        bdb_test(set, DB_HASH, &hash_info);

        free(set);
        return EXIT_SUCCESS;
}

На хабре, что ли, статьи херачишь? Ещё бы сравнил бинарный поиск на си с хэшами на питоне.

Хэши тоже нужно делать руками. В частности на твоём сете выигрывает таблица на 2**16 бакетов и хэш в виде любых двух байтов из числа.

Это как-то мешает тому, что написано тут: посоветуйте быстрый алгоритм установления принадлежности числа к множеству (комментарий) ?

Да, но не только это. И перестань уже прикидываться шлангом.