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

qqwe

Э, а в сумме это будет меньше 512 метров? Really?

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

 

Просто нужен обычное сравнение в цикле без всяких хешей и пр. муры.

Просто быстро и эффектно.

 

asmlamo

Заявка на победу.

 

не получилось ескейпнуться. не хватило воли.

intel_x128

Код (Text):

1. // значение которым будут помечаться свободные пойнтеры
2. #define NULL ((void*)0)
3. #define ERR -1
4. #define NOT_ERR 1
5.  
6. //-- DATA -------------------------------------------------
7.  
8. // сам массив
9. void* look_up_tab[MAX_N];
10.  
11. // кольцевой индекс пустых;
12. int idx_4_lut[MAX_N];
13. int idx_bot, idx_top;
14.  
15.  
16. //-- CODE -------------------------------------------------
17. void init_lut_and_idx(){
18.   int i;
19.  
20.   for(i = 0; i < MAX_N; i++){
21.     look_up_tab[i] = NULL;
22.     idx_4_lut[i] = i;
23.   }
24.   idx_bot = 0;
25.   idx_top = MAX_N;
26. }
27.  
28.  
29. int aux_pointer_to_index(void* ptr){
30.   int i;
31.  
32.   if((int)ptr & 3)
33.     return ERR;
34.  
35.   i = ((int)look_up_tab - (int)ptr) >> 2;
36.  
37.   if(i < idx_bot || i >= idx_top)
38.     return ERR;
39.    
40.   return i;
41. }
42.  
43.  
44. int is_pointer_empy(void* ptr){
45.   int i = aux_pointer_to_index(ptr);
46.  
47.   if(i == ERR)
48.     return ERR;
49.    
50.   return (look_up_tab[i] == NULL) & NOT_ERR;
51. }
52.  
53.  
54. void* get_new_pointer(){
55.   int i;
56.  
57.   if(idx_bot == idx_top)
58.     return ERR;
59.  
60.   i = idx_4_lut[idx_bot];
61.   idx_bot++;
62.  
63.   look_up_tab[i] = (void*)0xbeefbeef;
64.  
65.   return (void*)&look_up_tab[i];
66. }
67.  
68.  
69. int free_pointer(void* ptr){
70.   int i = aux_pointer_to_index(ptr);
71.  
72.   if(i == ERR)
73.     return ERR;
74.  
75.   if(idx_bot > 0){
76.     idx_bot--;
77.     idx_4_lut[idx_bot] = i;
78.   }else if(idx_top < MAX_N){
79.     idx_4_lut[idx_top] = i;
80.     idx_top++;
81.   }else{
82.     return ERR;
83.   }
84.  
85.   look_up_tab[i] = NULL;
86.  
87.   return NOT_ERR;
88. }

даже без кольца обойтись удалось. одно только НО. значение NULL - особое. вручную оно не должно записываться или стираться по полученной ссылке.

Booster

условие задачи

10 млн * 4 = 40 млн. те немного меньше 40 мегабайт, тк 1000 < 1024.

как вы это будете держать, в виде одного массива/вектора/последовательности или в виде нескольких - значение имеется только для алгоритма, а не для занимаемого объема (хотя, это для асма или С, или простых типов в С++/паса).

 

qqwe
Это по-моему что-то другое. Выделение, освобождение памяти из пула. Вместо самого значения - указателя, возвращается указатель на значение - (void*)&look_up_tab; Ясень пень эти указатели на значения плоского массива расположены в притирку. Но проблему поиска самих значений это не решает.

 

Booster

ась? я чувствую, что мы говорим о разных местах в разных городах.

передо всем делаем инициализацию:

void init_lut_and_idx();

получаем пойнтер (адрес дслова памяти под адрес) типа void* или ERR если кончилось место:

void* get_new_pointer();

проверяем пойнтер на не занятость. 0 - занято, 1 - не занято, ERR - пойнтер не выровнен или вообще не отсюда:

int is_pointer_empy(void* ptr);

освобождаем пойнтер. NOT_ERR - все путем. ERR - не все путем.

int free_pointer(void* ptr);

в пойнтер между получением и освобождением можно использовать и писать как угодно, кроме NULL (0 в данном случае).

---
ЗЫ &array[index] == адрес ячейки массива array по индексу index, те &array[0] == array. вы тоже переработали. весна, май - пару хороших маевок на природе с пивом и девочками прекрасно лечат зимнюю усталость.

 

qqwe
Ну так всё тоже самое я и описал. ^) Задача-то несколько иная, чем пул. Задача определения числа в массиве, а не получения указателя на элемент массива(или указателя на значение в массиве, что суть одно и тоже).

Ещё раз повторю, задача не найти поинтер, а найти значение в массиве, которое может быть поинтером и должно быть уникальным. Если данное решение подходит ТС-у, то тогда нормально, но по-моему это нечто другое. У вас ключ это указатель на элемент массива, а значение в массиве это значение. Ключом же должно быть само значение в массиве.

З.Ы. Конечно переработал и уже давно, но переработать придётся ещё больше.

 

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

 

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

 

>Не надо изобретать велосипеды, хэш-таблица идеально подходит для этой задачи.

В данной задаче она нафиг не нужна.

хэш-таблица нужна когда идет поиск болших значений длинной десятки байт и больше.

Сравнивать каждое ресурсоемко поэтому имеет смысл хэш-таблица.

В нашей задаче значение dword короткое и замечательно влазит в регистр процессора EAX, EBX целиком без всяких преобразований типа хеша и пр.

Посему простое сравнение рулит.

 

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

 

asmlamo
Дело не в сравнении, а в экономии памяти.

 

Где сложность-то?

Код (Text):

1. stdext::hash_map<DWORD> m;

Но если ставить задачу максимально быстрого поиска, то по-любому надо писать свою реализацию хэш-таблицы. Естественно, хэш-функция будет выглядеть так: f(x)=x, потому что все значения уникальные. А в остальном, нужно сделать обычную хэш-таблицу на ~10 млн. ячеек, коллизии разрешать при помощи списков, сделать свой аллокатор памяти, заточенный под работу с фиксированными блоками, и все будет просто летать.

 

прочитал топик, челюсть отвисла.
для более менее нерандомных данных:
http://ru.wikipedia.org/wiki/Двоичное_дерево_поиска

а для надёжности декартово дерево (оно же рандомизированное дерево поиска). (http://e-maxx.ru)

 

А теперь вспоминаем самое первое предложение

ИМХО, экономией памяти автор топика не очень озабочен - уже изначально сырых данных 40 метров. А вот накладные расходы на "деревянную" организацию такого размера (со всеми указателями дочерних ветвей) увеличат аппетит в несколько раз, как минимум в три (само значение, указатель на левую ветку, указатель на правую ветку) - уже 120 метров. Половина от требуемых 256 метров битовой карты (если работа только с указателями на пользовательскую память).

Интересно, что за задача, нейросети чтоль автор обсчитывает?

 

Dmitry_Milk
Лишние данные не нужны, нужно лишь изначально организовывать данные в "правильном" виде.
Первый элемент - корень дерева, следующие два - его преемники, далее два преемника первого и второго узлов и т.д.

 

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

А неудачное распределение практически однозначно будет, когда прога только-только запустится и начнет получать память - с очень большой вероятностью в начаое работы программы память будет выделяться последовательно, значения каждого следующего указателя будет больше предыдущего, и дерево будет расти только в сторону старших ветвей A[1],A[3],A[7],A[15],A[31] и.т.д, оставляя массу неиспользованного места.

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

 

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

А теперь о накладных расходах на память:
Размер дерева = O(размер массива).

А вот размер хештаблицы для 10млн чисел — это огого

 

Dmitry_Milk
Уже давно используется 64 bit, так что 256 метровая карта устарела.

 

Блин, я, кажется, понял. Если я понял правильно, то не нужно никаких ни хэшей, ни деревьев быстрого поиска. Вообще не нужно поиска!

Автор, intel_x128, отойди назад и посмотри на свою задачу более абстрактно.

Если я правильно понял, у тебя есть какие-то объекты, адресуемые указателями. Из этих объектов тебе надо организовать множество. То есть, над объектами тебе надо осуществлять такие операции:
- выполнение каких-либо действий над всеми объектами, принадлежащими множеству
- проверка принадлежности объекта множеству
- добавление объектов к множеству
- удаление объекта из множества

Ты решаешь эту задачу таким путем: организовал указатели на объекты в отдельном массиве и вышеуказанные операции над адресуемыми объектами фактически изначально проводишь над содержимым этого массива указателей. И мы тут все выше думали над вариантами работы именно с этими отделенными указателями.

Зачем тебе отдельный массив указателей? Внеси информацию об образовании множества в сами адресуемые объекты.

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