нахождение числа, появляющегося снова среди чисел, сохраненных в файле

Question

Скажем, у меня есть 10 миллиардов чисел, хранящихся в файле. Как мне найти номер, который уже появился однажды ранее?

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

Как бы вы подошли к этой проблеме?

Заранее спасибо:)

Answer 1

У меня было это как вопрос для собеседования.

Вот алгоритм O (N)

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

Автор Редактировать:

Ниже @Phimuemue подчеркивает, что 4-байтовые целые имеют фиксированную границу, прежде чем столкновение гарантировано; это 2 ^ 32 или ок. 4ГБ. При рассмотрении в беседе, сопровождающей этот ответ, потребление памяти в худшем случае по этому алгоритму значительно уменьшается.

Кроме того, использование битового массива, как описано ниже, может снизить потребление памяти до 1/8, 512 МБ. На многих машинах это вычисление теперь возможно без учета или постоянного хэша, или менее производительной стратегии сортировки в первую очередь.

Теперь более длинные числа или числа с двойной точностью являются менее эффективными сценариями для стратегии битового массива.

Phimuemue Редактировать:

Конечно, нужно взять немного "специальной" хеш-таблицы:

Возьмите хеш-таблицу, состоящую из 2 ^ 32 бит. Поскольку вопрос касается 4-байтовых целых чисел, их может быть не более 2 ^ 32, то есть один бит для каждого числа. 2 ^ 32 бит = 512 МБ.

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

Answer 2

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

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

Вместо этого перейдите к вероятностным решениям , которые использовались в большинстве практических применений этой проблемы (в сетевом анализе вы пытаетесь найти мышей , элементы, которые очень редко появляются в большом наборе данных).

Возможное решение, которое может быть найдено для получения точных результатов: используйте достаточно высокое разрешение Фильтр Блума . Либо используйте фильтр, чтобы определить, был ли элемент уже виден, либо, если вы хотите идеальной точности, используйте (как предложил kbrimington использовать стандартную хеш-таблицу), чтобы отфильтровать элементы, которые вы, возможно, не можете увидели и во втором проходе определите элементы, которые вы на самом деле видите дважды.

И если ваша проблема немного отличается - например, вы знаете, что у вас есть как минимум 0,001% элементов, которые повторяются дважды, и вы хотели бы узнать, сколько их приблизительно, или вы хотели бы получить случайная выборка таких элементов, а затем целый набор вероятностных потоковых алгоритмов, в духе Flajolet & Martin , Alon et al., существуют и очень интересны (не говоря уже о высокой эффективности).

Answer 3

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

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

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

Это все еще O (n), всего в два раза медленнее, чем за один проход.

Answer 4

Поиск дубликатов

Обратите внимание, что 32-разрядное целое число означает, что у вас будет большое количество дубликатов, поскольку 32-разрядное целое число может представлять только 4,3 миллиарда различных чисел, а у вас "10 миллиардов".

Если бы вы использовали плотно упакованный набор, вы могли бы представить, все ли возможности в 512 МБ, что может легко вписаться в текущие значения ОЗУ. Это довольно просто для начала, чтобы вы могли распознать тот факт, дублируется номер или нет.

Подсчет дубликатов

Если вам нужно знать, сколько раз число дублируется, вы получаете хэш-карту, содержащую только дубликаты (используя первые 500 МБ памяти оперативной памяти, чтобы эффективно определить, должно ли оно быть на карте или нет). В худшем случае с большим спредом вы не сможете вписать это в баран.

Другой подход, если числа будут иметь одинаковое количество дубликатов, заключается в использовании плотно упакованного массива с 2-8 битами на значение, что занимает около 1-4 ГБ ОЗУ, что позволяет подсчитывать до 255 экземпляров каждого числа.

Будет взломом, но выполнимо.

Answer 5

Как насчет:

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

Answer 6

Реализуйте BitArray таким образом, чтобы i-й индекс этого массива соответствовал числам от 8 * i +1 до 8 * (i + 1) -1. т.е. первый бит i-го числа равен 1, если мы уже видели 8 * i + 1. Второй бит i-го числа равен 1, если мы уже видели 8 * i + 2 и т. Д.

Инициализируйте этот битовый массив размером Integer.Max / 8, и всякий раз, когда вы видели число k, установите бит k% 8 индекса k / 8 как 1, если этот бит уже равен 1, значит, вы уже видели это число.

Answer 7

Это простая проблема, которая может быть решена очень легко (несколько строк кода)и очень быстро (несколько минут выполнения) с правильными инструментамимой личный подход заключается в использовании MapReduce MapReduce: упрощенная обработка данных на крупных кластерах Прошу прощения за то, что не буду вдаваться в подробности, но как только вы ознакомитесь с концепцией MapReduce, станет ясно, как нацелить решение.в основном мы собираемся реализовать две простые функции

1. Карта (ключ, значение)
2. Уменьшение (ключ, значения [])

, всего всего:

• открыть файл и перебрать данные
• для каждого числа -> Карта (число, индекс_строки)
• в сокращении мы получим число в качестве ключа и общее число вхождений в качестве числазначений (включая их позиции в файле)
• , поэтому в Reduce (key, values ​​[]), если число значений> 1 превышает его повторное число
• , выведите дубликаты: number, line_index1, line_index2, ...Опять же, этот подход может привести к очень быстрому выполнению, в зависимости от того, как настроена ваша инфраструктура MapReduce, масштабируемой и очень надежной, существует множество различных реализаций для MapReduce на многих языках.Есть несколько ведущих компаний, представляющих уже созданные среды облачных вычислений, такие как Google, Microsoft Azure, Amazon AWS, ...или вы можете создать свой собственный и настроить кластер с любыми провайдерами, предлагающими виртуальные вычислительные среды, платящие очень низкие затраты на часудачи :)
  • Еще один более простой подход - использование фильтров Блума. AdamT

Answer 8

#include <stdio.h>
#include <stdlib.h>
/* Macro is overly general but I left it 'cos it's convenient */
#define BITOP(a,b,op) \
 ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a))))
int main(void)
{
    unsigned x=0;
    size_t *seen = malloc(1<<8*sizeof(unsigned)-3);
    while (scanf("%u", &x)>0 && !BITOP(seen,x,&)) BITOP(seen,x,|=);
    if (BITOP(seen,x,&)) printf("duplicate is %u\n", x);
    else printf("no duplicate\n");
    return 0;
}

Answer 9

Пришлось сделать это давным-давно. Что я сделал ... Я отсортировал числа настолько, насколько мог (имел ограничение по времени) и выстроил их так, сортируя:

1-10, 12, 16, 20-50, 52 станет ..

[1,10], 12, 16, [20,50], 52, ...

Поскольку в моем случае у меня были сотни «очень близких» чисел ($ a- $ b = 1), из нескольких миллионов наборов у меня было очень низкое использование памяти

p.s. другой способ их хранения

1, -9, 12, 16, 20, -30, 52,

когда у меня не было чисел ниже нуля

После этого я применил различные алгоритмы (описанные другими авторами) здесь к сокращенному набору данных

Answer 10

Я должен согласиться с Кбримингтоном и его идеей хеш-таблицы, но прежде всего я хотел бы узнать диапазон чисел, которые вы ищете.По сути, если вы ищете 32-битные числа, вам понадобится один массив из 4,294,967,296 бит.Вы начинаете с установки всех битов на 0, и каждый номер в файле будет устанавливать определенный бит.Если бит уже установлен, то вы нашли число, которое встречалось ранее.Вам также нужно знать, как часто они происходят?Тем не менее, потребуется 536 870,912 байт как минимум.(512 МБ.) Это много и потребует некоторых хитрых навыков программирования.В зависимости от вашего языка программирования и личного опыта, для его решения найдутся сотни решений.