Быстрый поиск ДВОРДА в большом массиве двордов.

Есть большой массив двордов (около 10 млн двордов)
Этот массив - набор указателей. Все указатели уникальны.
Порядок двордов в массиве не критичен. Т.е. массив можно сортировать, дворды менять местами и т.д.
Главное, чтобы эти дворды там были.
Сама программа с массивом ничего не делает, только постепенно в конец добавляет новые указатели.

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

 

Поиск нужно осуществить единожды? Или периодически с разными искомыми элементами?

 

Используй дерево или хеш таблицу.

 

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

 

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

Booster
Я не очень силен в алгоритмах. Как в данном случае применить хеш-таблицу и что с ней делать?

CyberManiac
В массив в хвост добавляются элементы.
А функция поиска элементов вызывается в середине программы, а не в конце.
Т.е. при дихотомии прийдется каждый раз сортировать массив.

 

Сделай таблицу указателей на добавляемые дворды, и указатели вставляй в таблицу так чтобы они указывали на дворды в порядке возрастания значений, адресуемых двордами. Ну и потом как сказал CyberManiac - половинное деление
Сортировать ничего не надо.

 

Попробуйте вот это дерево, если допустимы большие затраты памяти.
http://en.wikipedia.org/wiki/Ternary_search_tree

Если нельзя использовать столько памяти, тогда видимо только
http://en.wikipedia.org/wiki/Hash_table

 

cresta
Указатель размером в двойное слово или четверное. Какой смысл?
Сортировка в лучшем случае - nlogn. Какой смысл?

intel_x128
Какой язык?

 

intel_x128

А тебе нужно именно узнать позицию заданного элемента или просто проверить факт наличия в списке? Если второе - можно сделать битовую карту на полгига (а то и меньше, если повезёт) и добавлять/искать по ней. Установка/проверка бита в общем случае будет во много раз быстрее любого поиска.

 

Booster
Си. Приложение х32 под Win

CyberManiac
Задача: найти элемент и удалить из массива. Чтобы его найти - нужно знать его индекс.
Например: есть функция DeletePointer(PVOID p)
эта функция находит нужный элемент в массиве и удаляет его.

 

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

Указатель размером дворд, у ворда не хватит разрядности для 10 млн. элементов.

P.S.
Немного неправильно выразился, не указатели на указатели, а порядковые номера указателей на дворды

 

вах. это ж указатели. числа. не надо половинных делений. не надо хэштаблиц. просто используйте ваше число как индекс. пустой элемент помечайте 0 или -1. если их сильно много и они на диске - разбейте на несколько таблиц по старшим битам. индекс - младшие. те

DWORD m[<старший_допустимый_дворд> - <младший_допустимый_дворд>] = {0,0,0,0,0,0,0,0,0,0,0,0,0 ...}; //хотя, как я понял это будут не дворды, а указатели на ваши данные

.. <заполняем> ..

if(m[<ваш_дворд> - <младший_допустимый_дворд>]){
.. дворд есть
}else{
.. дворда нет
}

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

 

cresta

Так у тебя сортировка + поиск. ^)

У них разрядность будет меньше чем двойное слово?

intel_x128
Либы есть. К примеру эта.
http://developer.gnome.org/glib/

qqwe

Я смотрю мы так хеш таблицу и изобретём. ^) Только у хеш таблицы распределение то получше будет.

 

Booster

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

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

при чем тут хэши или хэш таблицы? зачем тут нужно хэширование? у чела 10'000'000 ссылок. те < 40 метров памяти на 32х машине. те все прекрасно влазит в память. можно и поизвращаться если охота, но на первый взгляд не обязательно.

 

qqwe

Тут ты прав. ^)

Я где-то писал другое?

В память то оно конечно влезает, вопрос в том как искать.

Ну разобьёшь и что? Каждый каждый массив будет ещё содержать 0xffff динамических массивов? Это и есть зачаток хеш таблицы, но с плохим распределением. Хеш функция в данном случае - значение минус младшее слово.

 

Booster
отбросьте слово "хэш". они тут не нужны. "распределение" тут тоже не нужно. оно нужно только для самого вычисления хэша. просто уменьшает вероятность коллизии на близких данных. в данном случае опасности коллизии нет вообще. и считать "хэш" тоже не надо вообще.
а в чем проблема с поисков в наборе чисел? проверить занято ли по индексу? - задача в 1 действие. найти свободный индекс для заполнения? - при использовании буфера пустых - задача в 1-2 действия (удаление индекса - 2 действия).

вобщем, сам вопрос или шутка, или ТС заработался и ищет хитрый алгоритм зажигания спички.

 

qqwe
Никаких проблем, только отжирать под это дело 512 мегабайт по-моему многовато.

Хеш таблица вроде как общепринятый термин для подобной структуры.
http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0
Я и не настаиваю - просто один их возможных вариантов.

 

Booster

откуда взялись 512 мегабайт? 10000000 4х байтных чисел займут < 40 мегабайт. можно разбить массив на несколько массивов. получится многомерный массив

Type* m[<старшие байты>][<младшие байты>];

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

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

хотя, называйте как хотите. чего это я вообще влез в эту ветку? ескейпнусь-ка.

 

qqwe

ТС пока что данную задачу в лоб решает. В цикле пробегает по массиву и ищет нужный указатель.

Вопрос не шуточный.
Задача действительно есть. И стоит она именно вот так.
Есть две функции.

Первая функция: PVOID CreatePointer();
Она создает указатель и помещает его в глобальный массив двордов. Плюс увеличивает счетчик этих самых двордов.

Вторая функция: BOOL DeletePointer(PVOID p);
Она удаляет указатель из таблицы, уменьшает на единицу счетчик и, грубо выражаясь, освобождает память по указателю p. На самом деле действий там больше, но суть та же.
Удалить указатель не проблема. Просто на его место переместить последний, а счетчик уменьшить на единицу. 2 действия.
А вот найти указатель в массиве, кроме как поиском в лоб, я не могу. Не хватает моих знаний.
Если указателя в массиве нет - никаких действий не производим

функции CreatePointer и DeletePointer вызываются очень много раз. И каждый раз бегать по огромному 10 млн массиву данных для удаления указателя - накладно.

 

Я кажется понял, что хотел qqwe сказать....
Т.е. сделать массив бит.
И включать / выключать бит по индексу, равному p (указателю).
512 метров действительно много (4гб/8). А так решение очень даже ничего...