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

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

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    да все я описал, сказав, что числа левые. Это могут быть хеши, а могут... ошметки видеофильмов. Первый байт он конечно востребованный, но где взять байты с кучей лидирующих нулей??? Т.е. 0000 0000 0000 0001, затем 0000 0000 0000 00002 и так далее? Похоже на UTF64 =)))

    Идея генерить случайное число и сравнивать тоже интересная...
     
  2. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    короче, сделал так, что сначала идет массивчик 256 элементов, если облом то 1024, потом 4096, потом 16К =))) 256 действительно иногда обламывается на некоторых данных, но остальные рогатки не дають врагу шанса... Один массивчик - один проход - это быстрее полной сортировки.
     
  3. qqwe

    qqwe New Member

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

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    А теперь рассмотрим, что среди этих чисел от 0 до 9, не хватает, скажем, восьмёрки.
    45 мы посчитали, найдя 0 и 9: 9×(9+1)/2 = 45. Сложив же весь массив, имеем 37. Вычитая 37 из 45, имеем 8.
    Но, да — у нас нет 37 и 45, а есть только 7 и 5. Вычитаем 7 из 5, выходит –2.
    Однако, учитывая, что числа у нас беззнаковые, и, по правилам машинной арифметики, «заворачиваются» при переполнении, получаем 100 – 2 = 98. Как обычно, выкидываем 9. Так или иначе, остаётся 8.

    Магия! =)
     
  5. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    странно. то не было поста. то появился. чудеса. дубликат убран
     
  6. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Лан, забабахал массивчик чуть побольше и оставил один проход. В реальной практике он почти пустой. Где взять подряд стока малых чисел среди 64-битного хлама если только не вводить их преднамеренно?

    Это шаманизм... Вот если бы все числа переXORить, тогда волшебство...
     
  7. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    Если битовая маска не лезет можно цифры группами считать.
    Например массив: первая ячейка это цифры от 0-511, вторая 512-1024...
    т.е. первый поход находим в каком диапазоне не достаёт числа, второй находим само число.

    Или половинки от чисел посчитать, а по ним потом решить что на втором проходе искать.. (такой способ наверное даже к повторам устойчив)
    Хотя тут и похитрее мысли есть, но их надо немного обдумать..
     
  8. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    но это так, к слову: думаю, если родится какая-нибудь действительно революционная идея, автор добавит её в свой алгоритм =)

    и, кстати, qqwe прав.
    надо бы конкретизировать распределение величин.
    проще говоря, каковы типичные значения: (1) длины массива; (2) разности минимального и максимального элементов?
     
  9. persicum

    persicum New Member

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

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

    революционное решение тоже было найдено - превратить алгоритм битовых зарубок из детерминированного в вероятностный и таким образом искать в неупорядоченном случайном массиве. Какова вероятность что в случайных данных представлены непременно все числа скажем от 0 до 1024? Тут и без распределения Пуассона ясно, что ноль на массу. Поэтому ценой очень скромной памяти задача почти наверняка решается в один проход.
     
  10. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Если в массиве N целых чисел (неважно какой разрядности), то хотя бы одно число из интервала 0...N включительно будет в этом массиве отсутствовать. Потому что в этом интервале содержится ровно N+1 число. То есть достаточно битовой маски из N+1 бита, что уже вполне приемлемо. И задача решается за один проход по массиву и один проход по получившейся битовой маске.
     
  11. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Atlantic
    Спасибо за точное гарантированное решение задачи.
    Я и сам частенько употреблял метод голубиных задниц
    http://en.wikipedia.org/wiki/Pigeonhole_principle
    Но тут испугался элементов массива большой разрядности...

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