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

hash

Если других ограничений нет, то можно все числа в базу данных загнать.

тоесть использование таблицы на 4G елементов. не канает.

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

А так: таблица на 4G/8 элементов и вперёд.

не совсем представляю как его здесь применить. можешь ткнуть в какой нибуть пример?

Какое-нибудь дерево. B+, наверное.

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

не, туплю, лучше бинарное дерево :)

(4 байта + 3 указателя по 4 байта (если 32 битная платформа)) * 300000 = 4.5 мегабайта памяти

если множество константно, то сортированный вектор (~ 1.2 мб) + бинарный поиск

из STL - std::set

Из велосипедостроения - поиск методом половинного деления.

Придумываешь хэш функцию из 8^4 в такое количество памяти, сколько тебе не жалко, заводишь массив на это количество памяти, в нём ссылка на linked list для разрешения коллизий.

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

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

Кстати, да: BST тут хорошо бы проканало, если б не одно "но" — у него же чуть ли не O(n^3) сложность!

а я всегда думал что O(logN)

Кстати тоже хорошая мысль, если они там есть (скажем непрерывные участки, или участки с фиксированной скважностью).

отсортируй сраное множество

ищи двоичным поиском

если множество постоянно (крайне редко меняется), то можно вычислить мат.функцию f(x) принадлежности множеству. Вряд-ли 300000 элементов равномерно распределены по 2^24. Обрывки воспоминаний о теории информации говорят об алгоритмах подобных DH, LZV

то что нужно. *THANKS*

Это поиск. А ты повставляй-ка элементы, да сбалансируй! Мне drbatty ( emulek) рассказывал про красно-черные деревья, я почитал — да, вполне себе шустрая реализация по сравнению с моим собственным велосипедом, но все равно на таких количествах данных это будет жутко скрипеть.

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

фильтр Блума?

При бинарном поиске первая пара десятков сравнений гарантированно даст результат;-)

При сложности log_2(N) на таком массиве всякая индексация (Вы небось имели ввиду что то вроде разбиения на подмножетсва по хэш-значениям?) ИМНО только ухудшит дело.

на таких количествах данных это будет жутко скрипеть

А если в дерево запихивать векторы чисел, типа от х до у?

фильтр Блума?

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

Дык, тогда получится моя индексация. AIv считает, что дело только ухудшится. А я думаю, что надо проверять. Но мне влом. Тут делов-то на полчаса. Может, кто напишет?

Для числовых массивов оно как раз самое то, при выборе правильного размера можно количество ложных срабатываний минимизировать. Вообще целесообразность его применения зависит от задачи и входных данных.

Те же яйца, что и хэширование, только хуже.

Б-г мой, чего тут проверять??? 3е5*4б==>1.2Мб, это почти влазит в L2. 3e5 это порядка 2^18-2^19, т.е. 18-19 сравнений.

Одно сравнение это неск. тактов макс, т.е. один поиск будет занимать порядка 50-100 тактов. И куда Вы это решили ускорять О_О?

Если бы у ТСа было 16гб памяти, то один поиск будет занимать 1-2 такта.

Те же яйца, что и хэширование, только хуже.

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

Хотя можно уменьшить до 2-х, количество тактов увеличится на один сдвиг.

64**8 = 16 гб. - пространство значений исходных чисел Выделяем 2 гб на битовую строчку, содержащую 1 если элемент есть, 0 если нет. Проверка - всего лишь проверка элемента строки. Что может быть лучше?

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

И как, по-твоему, будут вести себя кэши L2/L3 и TLB на 16 Гб?

кстати - классная идея. надо подумать смогу ли я ее себе применить.

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

Не уточнил язык. В скале для этого битсет подошел бы.

C

какой язык? если python, то set(). если php, то array. если c++, то unordered_map. если сишечка - читай кнута

http://ru.wikipedia.org/wiki/Фильтр_Блума

Можно сначала им фильтровать лишнее, это быстро.

Одно сравнение это неск. тактов макс, т.е. один поиск будет занимать порядка 50-100 тактов.

Это если весь массив уже в кэше.

Красно-черное дерево, АВЛ-дерево

В принципе можно смотреть на это множество как на массив из 2^32 бит (нолик -нет числа, 1 - есть число). Это 2^29 байт, т.е. 512Мб. В этом случае, в идеале (если соотв. страница уже в кэше), скорость поиска неск. тактов - скажем массив uint64 (2^8 бит) т.е. 2^24 чисел. Сначала от проверяемого числа откусываем первые 24 бита, находим число, затем проверяем соотв. бит.

Но если доступ рандомный и страницы в кэше нет.... от железа зависит, скажем латентность 10нс (оптимистично, я не помню конкретных цифирей) при 3ГГц это 30 тактов (если я не проврался)? Т.е. по памяти проигрыш в 500 раз, по времени сравнимо с бинарным поиском.

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

1.2Мб - можно считать что он кэше?

Да с чего бы? Вряд ли единственная задача программы - искать в массиве числа.

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

Ну от шелезяки зависит... в L2/3 может и все время висеть, ежели туда стучаться часто. А если нечасто, то неважно где оно;-)

Скажи лучше какая латентность будет при рандоном доступе к чему то большому, я забыл;-(

1.2Мб - можно считать что он кэше?

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

Т.е. сначала идёт корень, потом второй уровень (т.е. два элемента), длаее 3ий (4 штуки) и т.д. Значительно улучшится кеширование первых уровней дерева.

Еще немного, и ты изобретешь B+-дерево %)

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