Некоторое время назад мне дали шуточную задачку:
Имеется массив 1000000*1000000 записей, в каждой ячейке целое число. Требуется вывести все не дублирующиеся элементы.
Важно выполнить КАК МОЖНО меньше операций, т.е. нельзя сортировать.
У меня было много разных идей, но все они сводились к сортировке. В общем, без сортировки я не справился, грубо говоря.
Есть у Вас какие-то идеи, как это можно сделать?
Чтобы определить, выводить ли текущий элемент, необходимо знать выводили ли мы уже этот элемент раньше. Для этого нужно просмотреть все выведенные раньше элементы. Основная задача - ускорить процесс просмотра. Наиболее эффективный способ этого добиться - хранить выведенные элементы не в обычном массиве, а в какой-нибудь структуре данных, в которой поиск осуществляется за время, меншее O(N). Это может быть бинарное дерево поиска и его разновидности (AVL-tree, B-tree, RB-tree), хэш-таблицы, списки с пропусками. Такие структуры позволяют ускорить поиск вхождения до O(NlogN). Также может помочь такая структура как фильтр Блума.
Даже если каждое число по 4 байта, то это
1000000 * 1000000 * 4 / 1024/1024/1024/1024 = 3.7 Терабайта.
В оперативку уж точно не вместиться.
Итак, если там однобайтовые числа. Заводим массив на 256 элементов, проходимся последовательно по оригинальному массиву. Используя число как индекс смотрим в первом массиве значение. Если там 0, записываем 1, если единица - пишем 2, если 2 - не трогаем. По окончанию просмотра большого массива смотрим в маленький. Там, где значения нулевые, этих элементов нет, где 1 - для них нет дубликатов. Где двойки - там есть дубликаты. Сложность алгоритма - O(n).
Если числа двухбайтовые, то тут суть та же, 64к массив - это не так много.
Если числа 4-байтовые, то тут придется немного помучаться, так как заводить массив на 4 гигабайта (на каждое число по байту) как-то накладно, можно паковать по 4 числа в байт (на кодирования наличия элемента нужно всего два бита). Это "всего" 1 гигабайт (если нашлось место для 4 терабайт данных, то один гиг найдется). Если памяти мало, то можно попробовать паковать блоки, то есть хранить не одним массивом, а разбить на блоки, к примеру, по 1024 элемента. Если в блоке хранятся одинаковые числа, то можно просто хранить это значение.