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

Тема в разделе "WASM.A&O", создана пользователем persicum, 13 окт 2011.

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    пока делаю так:
    цифровая сортировка, затем поиск пары с разностью больше единицы.
    Например, если рядом стоят 4 и 6, значит 5 нет во всем массиве.

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

    Ezrah Member

    Публикаций:
    0
    Регистрация:
    22 мар 2011
    Сообщения:
    411
    Завести битовый массив, установить соответствующий бит для каждого элемента. Потом искать первый байт, не равный 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);
     
  3. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    Ezrah,
    кстати, если уж на то пошло, лучше изначально иметь битовый массив единиц, а при обнаружении обращать их в нули, т.к. потом можно сразу получать номер бита с помощью BSF/BSR.
     
  4. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Таак, а если числа 64 битные, и 2^64 бит выделить невозможно?
     
  5. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    хм, а отсортировать можно?
     
  6. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    О, вот ещё придумал (хотя, скорее всего, это было подмечено ещё до моего рождения) один алгоритм:
    — складываем все числа (хранить весь результат целиком не требуется, нехай себе переполняется), параллельно с этим находим минимальное и максимальное.
    — по формуле суммы арифметической прогрессии находим сумму чисел от минимального до максимального (также с переполнением).
    — отнимаем одно от другого, и вуаля =)
     
  7. persicum

    persicum New Member

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

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Сумма от 0 до ffffffffffffffff будет 8000000000000000h, очень содержательное число ))
     
  9. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    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:] Оптимизация.
     
  10. Ezrah

    Ezrah Member

    Публикаций:
    0
    Регистрация:
    22 мар 2011
    Сообщения:
    411
    Это не переносимо даже на 64хбитные платформы.
    Т.е. вы нормально сортируете 2^64 восьмибайтных чисел, и у вас хватает на это памяти?
     
  11. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Ну допустим у нас есть сто 64битных чисел, тогда что? Массив битов нужен ведь под размерность содержимого...
     
  12. persicum

    persicum New Member

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

    Ezrah Member

    Публикаций:
    0
    Регистрация:
    22 мар 2011
    Сообщения:
    411
    persicum
    Для ста 64битных чисел понадобится ровно 101 бит, если условие задачи ровно такое, как Вы указали, т.е. если из последовательного ряда чисел нехватает ровно одного.
     
  14. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    persicum
    у вас 100 чисел вы нашли минимальное 10 и максимальное ffff'ffff'ffff'ff10. и что?
    3 + 5 + 7 = 4 + 5 + 6
     
  15. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Где я про это говорил? Задача такая: Есть 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. Лазейка закрывается.
     
  16. qqwe

    qqwe New Member

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

    100gold New Member

    Публикаций:
    0
    Регистрация:
    26 фев 2010
    Сообщения:
    165
    Код (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);
     
  18. persicum

    persicum New Member

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

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    вы описываете особенности своей задачи нам абсолютно неизвестные.
    а о вашем утверждении - возьмите символы уникода или обычный счет. первый байт гораздо востребованей чем все остальные. особенно последние.
    но это зависит от условий задачи, которые вы не описали.
     
  20. PSR1257II

    PSR1257II New Member

    Публикаций:
    0
    Регистрация:
    25 июн 2011
    Сообщения:
    228
    Да-да!

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

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

    Ваш К.О.