Как найти уникальные записи в большом наборе данных? - PullRequest
1 голос
/ 06 января 2009

У меня есть 100 миллионов строк данных, данные - это слово длиной не более 15 символов, по одному слову в строке. Эти данные хранятся в нескольких файлах.

Моя цель - найти уникальные слова среди всех файлов.

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

Есть ли более быстрое решение?

Спасибо

Ответы [ 7 ]

3 голосов
/ 06 января 2009

Я не уверен, что будет много более быстрых способов, чем использование базы данных. Лично я обычно использую сценарий оболочки UNIX для этого:

cat * | sort | uniq

Я не знаю, как быстро это будет с 100 000 000 слов, и я не уверен, насколько быстро вы хотите, чтобы это было. (Например, вам нужно запускать его много раз или только один раз? Если бы только один раз, я бы выбрал опцию sort и uniq и позволил бы ему работать всю ночь, если вы можете).

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

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

Ben

1 голос
/ 07 января 2009

Использование базы данных для этого безумно. 100 миллионов записей 15 символов вписываются в оперативную память. Если есть хоть какое-то дублирование, просто создайте trie. Должен быть способен обрабатывать 50 МБ / с или около того на современной машине

0 голосов
/ 06 января 2009

Вы можете сохранить скорость, пространство или здравомыслие. Выберите любые два.

Бросив все это в базу данных, вы потеряли скорость и место, как вы узнали. Но это было легко.

Если пространство является вашей основной проблемой (память, дисковое пространство), то разбейте работу. Отфильтруйте все 1-символьные строки из файлов и используйте одно из указанных выше решений (sort, uniq). Повторите с 2 символьными строками для каждого файла. И так далее. Уникальные решения с каждого прохода образуют ваш набор решений.

Если вашей основной проблемой является скорость, то читайте каждый файл ровно один раз, создавая хеш-таблицу (словарь и т. Д.) Для поиска дубликатов. В зависимости от реализации хэша это может поглотить большие объемы памяти (или диска). Но это будет быстро.

Если вам нужно сохранить скорость и пространство, подумайте о смешении двух техник. Но будьте готовы пожертвовать третьим предметом.

0 голосов
/ 06 января 2009

Если в отдельных файлах имеется значительное дублирование, может быть быстрее сделать это файл за файлом, а затем объединить результаты. Что-то вроде:

{ for n in * ; do sort -u $n ; done } | sort -u

(я предполагаю, что GNU bash и GNU sort)

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


Учитывая разъяснения myhusky (много дуплей, 10 ~ 20 файлов), я определенно предложу это как хорошее решение. В частности, плотное дублирование ускорит sort -u против sort|uniq

0 голосов
/ 06 января 2009

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

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

0 голосов
/ 06 января 2009

Вы можете хранить слова в хеш-таблице. Если предположить, что дубликатов достаточно много, время поиска O (1) значительно увеличит производительность.

  1. Читать строку.
  2. Поиск слова в хеш-таблице.
  3. Если не найдено, добавьте его в таблицу.
0 голосов
/ 06 января 2009

Если вам нужно придерживаться файловой структуры, вам нужен какой-то способ индексации файлов и последующего ведения индекса.

В противном случае я бы порекомендовал перейти к базе данных и перенести все операции с этим файлом для работы с базой данных.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...