Лучший способ определить уникальность и повторяемость в текстовом файле - PullRequest
Новая
       10

Лучший способ определить уникальность и повторяемость в текстовом файле

3 голосов
/ 13 марта 2009

У меня есть текстовый файл около 20 миллионов строк. Каждая строка длиной 25 символов. По моим оценкам, существует около 200–300 тыс. Уникальных линий. Я хочу выяснить, сколько именно существует уникальных строк и сколько вхождений каждой строки (я ожидаю, что результат будет степенным).

Я мог бы сделать это: 

sort bigfile|uniq -c |sort -nr > uniqcounts
wc -l uniqcounts

но это ужасно неэффективная память и время.

Какое решение этой проблемы для вашей командной строки является лучшим?

Ответы [ 5 ]

6 голосов
/ 14 марта 2009

Я склоняюсь к Perl, когда у меня возникают подобные проблемы с обработкой текста, тем более что Perl установлен на большинстве систем Unix. (Возможно, вы могли бы сделать то же самое с awk, который, возможно, немного более доступен.)

Нечто подобное должно сработать: 

#!/usr/bin/perl

while(<>) {
    chomp;
    $lines{$_}++;
}

print "Total unique lines: ", scalar(keys %lines), "\n";
foreach my $line (sort {$lines{$b} <=> $lines{$a}} keys %lines) {
    printf "%6d  %s\n", $lines{$line}, $line;
}

(Вы можете сделать это как однострочник, но разбитый текст облегчает чтение.)

Для этого требуется O (n) памяти для хеш-ключей, где n - количество уникальных строк. Эффективность времени выполнения зависит от поиска хеша, но будет где-то между O (n) (если у вас нет коллизий хешей) и O (n * log n) (для сбалансированного дерева) Последняя, ​​необязательная сортировка может занять O (n ^ 2) в худшем случае и может доминировать во время выполнения, если число уникальных строк велико.

2 голосов
/ 14 марта 2009

Я принимаю на себя риск быть сочтенным не по теме и пониженным, но я должен разглагольствовать об этом.

20 миллионов * 25 символов = 500000000 байт (при условии, что вы не имеете в виду Unicode)

Это менее 500 МБ ОЗУ. Это не так уж много для современного компьютера.

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

Использовать базу данных (например, sqlite) вместо простого файла.

Используйте таблицу типа 

CREATE TABLE lines (line VARCHAR(25), occurences INTEGER)

для хранения уникальных линий и их появления.

Если этот текстовый файл генерирует не ваше приложение, пожаловайтесь разработчикам об этом!

1 голос
/ 14 марта 2009

С awk (используйте nawk или / usr / xpg4 / bin / awk на Solaris : 

awk 'END {
  for (k in _)
    print k, _[k]
    }
{ _[$0]++ }
' infile
1 голос
/ 14 марта 2009

Убедитесь, что вы делаете это перед тестированием решения sort и uniq: 

export LC_ALL=C

Было бы хорошо, если бы вы могли сравнить это и время решения perl по крайней мере.

0 голосов
/ 13 марта 2009

Я не уверен, что есть лучшее решение, чем вы опубликовали: O (n log (n) + n). Упомянутая вами мелкая "sort -nr" не является строго необходимой, учитывая формулировку проблемы, но облегчает вывод результатов для людей.

Мне было бы очень интересно, если бы кто-то мог придумать решение, которое быстрее, чем это (по сложности). Конечно, написание специальной программы для этой же задачи, вероятно, будет быстрее, чем использование sort и uniq.

...