Поиск отсутствующего элемента в массиве

пока делаю так:
цифровая сортировка, затем поиск пары с разностью больше единицы.
Например, если рядом стоят 4 и 6, значит 5 нет во всем массиве.

Какие еще варианты чтобы побыстрее?

 

Завести битовый массив, установить соответствующий бит для каждого элемента. Потом искать первый байт, не равный 0xFF и вычислить номер бита.

Код (Text):

1. xmin = min_elem(array);
2. xmax = max_elem(array);
3. delta = xmin;
4. bit_arr = new bit_array(xmax - xmin + 1);
5. for_each(elem in array) bit_arr[elem - delta] = true;
6. result = delta + bit_arr.find(false);

 

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

 

Таак, а если числа 64 битные, и 2^64 бит выделить невозможно?

 

хм, а отсортировать можно?

 

О, вот ещё придумал (хотя, скорее всего, это было подмечено ещё до моего рождения) один алгоритм:
— складываем все числа (хранить весь результат целиком не требуется, нехай себе переполняется), параллельно с этим находим минимальное и максимальное.
— по формуле суммы арифметической прогрессии находим сумму чисел от минимального до максимального (также с переполнением).
— отнимаем одно от другого, и вуаля =)

 

В самом первом посте я сказал, что использую цифровую сортировку. Энто 64 прогона по массиву. С другой стороны, поиск минимального/максимального алимента требует только один прогон. Теперь хочу быстро найти любой отсутствующий элемент...

 

Сумма от 0 до ffffffffffffffff будет 8000000000000000h, очень содержательное число ))

 

persicum,

А что такого в этом числе? FFFF FFFF FFFF FFFF × 1 0000 0000 0000 0000 / 2 = 7FFF FFFF FFFF FFFF 8000 0000 0000 0000.
Откидываем 7FFF FFFF FFFF FFFF, и отнимаем — имеем 0. Что не так?

Наверное, я не до конца объяснил.
Отнимать нужно не только насчитанную по формуле сумму 1…MIN от суммы 1…MAX, но и ещё вдобавок от полученной разности отнимать сумму всех величин в массиве.

ЗЫ.
Вот, закодил вышесказанное.
На вход подаётся массив беззнаковых двойных слов любой длины, завершающийся нулём.
Если в поданном на вход массиве пропущено одно число — на выходе в EAX будет лежать именно оно.
Иначе, туда попадёт сумма пропущенных чисел по модулю 1 0000 0000h.

Код (Text):

1. find proc A: DWORD;
2.  
3.   MOV EAX, A;
4.   XOR ECX, ECX;
5.   MOV EDI, ECX;
6.   LEA ESI, [ECX - 1];
7.   JMP @head;
8.  
9.   @loop:
10.     CMP EDI, EDX;
11.     CMOVB EDI, EDX;
12.     CMP ESI, EDX;
13.     CMOVA ESI, EDX;
14.   @head:
15.     MOV EDX, DWORD PTR [EAX];
16.     ADD EAX, 4;
17.     ADD ECX, EDX;
18.     TEST EDX, EDX;
19.   JNE @loop;
20.  
21.   LEA EAX, [ESI - 1];
22.   MUL ESI;
23.   SHR EAX, 1;
24.   MOV ESI, EAX;
25.  
26.   LEA EAX, [EDI - 1];
27.   MUL EDI;
28.   SHR EAX, 1;
29.   ADD EAX, EDI;
30.  
31.   SUB EAX, ESI;
32.   SUB EAX, ECX;
33.   RET;
34.  
35. find endp;

[UPD:] Оптимизация.

 

Это не переносимо даже на 64хбитные платформы.

Т.е. вы нормально сортируете 2^64 восьмибайтных чисел, и у вас хватает на это памяти?

 

Ну допустим у нас есть сто 64битных чисел, тогда что? Массив битов нужен ведь под размерность содержимого...

 

Скажите, схлифасофский, откуда эта гигантомания? Давайте рассмотрим ваш алгоритм для чисел от 0 до 9 в разрядной сетке в одну цифру. Сумма будет 45, последняя цифра 5. Что дальше делать? Пусть теперь есть массив длины N заведомо меньше 10, набит произвольными цифрами, могут быть и повторения. Если я прибавлю к их сумме еще и 5, то чем это поможет?

 

persicum
Для ста 64битных чисел понадобится ровно 101 бит, если условие задачи ровно такое, как Вы указали, т.е. если из последовательного ряда чисел нехватает ровно одного.

 

persicum

у вас 100 чисел вы нашли минимальное 10 и максимальное ffff'ffff'ffff'ff10. и что?

3 + 5 + 7 = 4 + 5 + 6

 

Где я про это говорил? Задача такая: Есть 100 совершенно левых 64 битных чисел, никакого порядка в них нет, также возможны повторения. Найти любое 64 битное число, которое заведомо НЕ содержится в массиве (то есть среди этой сотни чисел).

легко решить в принципе сортировкой, но хочется за малое число пробегов. Если мы сделаем один пробег и найдем min 10 и max ffff ffff ffff fff0, например, то тогда мы можем легко взять в качестве отсутствующего числа скажем 0,1 или ffff ffff ffff fffe, например.

но в реальной практике там не сто чисел нужно, а миллион например (что отчасти не принципиально, так как и 100 и 1000000 много меньше пространства состояний) и min и max чаще всего находятся как 0,1 и ffff ffff ffff ffff. Лазейка закрывается.

 

0 и -1 очень популярные числа, потому с большой ыероятностью вы будете иметь [0, ffff'ffff'ffff'ffff]
если интересуют не все, а только пару значений из мильена, то можно использовать серию бит полей. младшие биты числа на поле, старшие на счетчик. если выбрать размер поля больший или равный количеству ваших чисел, то вы найдете дыру еще на 1м проходе. в бит поле размером 1гб войдет 2**38 цифер, буфер для которых в 64 варианте займет 2**41 байт. 2тб в озу не влезет. те, если у вас <= 2тб чисел на винте, то найти хоть 1 непопадающее можно 1 чтением с винта и полем 1гб

 

Код (Text):

1. int full=0;
2. for(int i=minelement; i<maxelement;++i)
3. {
4.    full = full ^ i;
5. }
6. int current=0;
7. for(size_t j=0; j<array_size; ++j)
8. {
9.    current = current ^ array[j];
10. }
11. printf("missing number=%i\n",current ^ full);

 

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

 

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

 

Да-да!

(Извините если повторяю уже сказанное).

Если числа действительно совсем разные и их "плотность" невелика, то проще генерить случайное число в диапазоне от 0 до 2^64-1 (если они действительно 64 бита) и искать один раз. Иногда, совсем иногда будет коллизия - но очень редко так. Если планируецца много запросов такого рода то ... ясно что надо делать.

Ваш К.О.