Xpoint
   [напомнить пароль]

Удаление одинаковых строк в файле

Метки: [без меток]
2009-08-20 08:40:41 [обр] jkeks Jackson+[досье]

Задачка звучит очень просто, нужно в файле оставить только уникальные строчки.
т.е. повторения нужно удалить.

Какие есть предложения сделать это быстро, файл данных около 100 мегабайт ?
;)))

спустя 37 минут [обр] Роман Чемисов(56/327)[досье]
jkeks Jackson[досье]
Проверяем для каждой строки:
есть ли она в хэше, если нет, то сохраняем её в файл.
спустя 10 часов [обр] Dennis F. Latypoff aka funky_dennis(24/78)[досье]

Роман Чемисов[досье]
:)

jkeks Jackson[досье]
заводим 32 числа, обнуляем их.
читаем по одной строчке, берем crc32() от неё, ну а дальше дело техники (hints: bitwise OR, bitwise AND)
и хоть терабайты перелопачивайте, ли бы винт не сдох.

спустя 4 минуты [обр] Dennis F. Latypoff aka funky_dennis(24/78)[досье]
jkeks Jackson[досье]
а если perl — необязательное условие, то man uniq
спустя 6 часов [обр] Роман Чемисов(56/327)[досье]
Dennis F. Latypoff aka funky_dennis[досье]
Одним из требований было сделать это быстро
спустя 7 часов [обр] Alexander O(122/460)[досье]
Проверяем для каждой строки:
есть ли она в хэше, если нет, то сохраняем её в файл.
Реализация:
perl -ne '$%{$_}++ or print' bigfile > uniqfile
спустя 4 дня [обр] Алексей Севрюков(198/1280)[досье]
Странно, почему никто не упомянул что вариант с хэшем будет кушать очень много памяти при больших размерах файлов. Вариант с crc32() будет кушать поменьше, но работать будет дольше.
спустя 8 часов [обр] Dennis F. Latypoff aka funky_dennis(24/78)[досье]

Алексей Севрюков[досье]
смотря как реализован алгоритм хеширования в перле :)
сдается мне, что вариант с crc32() будет и работать быстрее, и памяти кушать всегда одинаково малое кол-во, независимо от размера файла, а точнее:
память, занимаемая интерпретатором для компиляции и исполнения кода +
память под самую длинную строку, выровненная до размера страницы (обычно 4кб) +
32 * 4 (на 32-битных платформах, для 64-битных — 8) = 128кб или 256кб (64 битная платформа)

:)

спустя 1 минуту [обр] Dennis F. Latypoff aka funky_dennis(24/78)[досье]

Алексей Севрюков[досье]

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

Предполагаю — это очевидно :)

спустя 1 месяц 7 дней [обр] Алексей Севрюков(198/1280)[досье]
Dennis F. Latypoff aka funky_dennis[досье] ошибаетесь. В Основах даже очевидное далеко не всегда очевидно.
спустя 7 дней [обр] German[досье]
интересно, если в файле почти нет одинаковых строк, и 10 мегабайтный файл обрабатывался 10 секунд —
сколько должен обрабытываться 100 мегабайтный файл ??
:)
спустя 1 час 18 минут [обр] Dennis F. Latypoff aka funky_dennis(24/78)[досье]
German[досье]
Это каким методом?
спустя 1 час 55 минут [обр] German[досье]
я имел виду
perl -ne "$%{$_}++ or print" long.txt > uniq.txt
спустя 11 часов [обр] Роман Чемисов(56/327)[досье]
German[досье]
10 секунд безумно много для такого небольшого файла... Что у Вас за машина?
спустя 1 день 7 часов [обр] German[досье]

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

Как зависит время обработки от размера? По моим прикидкам получается, что время должно увеличиваться пропорционально квадрату размера файла.
То есть 100 мегабайтный файл будет обрабатываться примерно в 100 раз дольше чем 10-мегабайтный (если, ничтоже сумняся, предположить что на сравнение строки файла затрачивается одинаковое время) То есть, скажем так, это очень грубая или приблизительная модель, но она должна быть лучше, чем никакая...

Реального эксперимента я не ставил :)
но может и попробую

спустя 4 часа 4 минуты [обр] Alexander O(122/460)[досье]
ccn@asus:~$ time perl -le 'print +($x=rand) . "x" x (80 - length $x) while $i++ < 100*1024*1024/80' >100mb

real   0m3.237s
user   0m2.884s
sys   0m0.352s
ccn@asus:~$ time perl -ne '$seen{$_}++ or print' 100mb > uniq.txt

real   0m4.517s
user   0m3.632s
sys   0m0.880s
ccn@asus:~$ ls -l 100mb uniq.txt 
-rw-r--r-- 1 ccn ccn 106168320 2009-10-11 14:56 100mb
-rw-r--r-- 1 ccn ccn 106168320 2009-10-11 14:57 uniq.txt
ccn@asus:~$
спустя 4 минуты [обр] Dennis F. Latypoff aka funky_dennis(24/78)[досье]
По моим прикидкам получается, что время должно увеличиваться пропорционально квадрату размера файла.
Откуда такие заключения?
спустя 4 часа 12 минут [обр] Алексей Севрюков(198/1280)[досье]
М Это не заключения. Это так, чтобы ляпнуть что-нибудь. Непонятно только зачем ляпать.
German[досье] прежде чем что-то сказать — подумайте. Для этого есть замечательная кнопка "посмотреть, что получится", пользуйтесь, помогает думать.
спустя 13 часов [обр] Дмитрий Кучкин(36/236)[досье]

Dennis F. Latypoff aka funky_dennis[досье]

заводим 32 числа, обнуляем их.
читаем по одной строчке, берем crc32() от неё, ну а дальше дело техники (hints: bitwise OR, bitwise AND)
и хоть терабайты перелопачивайте, ли бы винт не сдох.

Можно подробнее про технику? Или ссылку на более подробное описание алгоритма, а то для "основ" слишком мало информации.
Я, например, этот алгоритм раньше не встречал, а по такому описанию самостоятельно его реализовать не получается.

спустя 15 часов [обр] German[досье]

Алексей Севрюков[досье], вы делитесь опытом, в ляпании чего-нибудь?
вполне естественно предположить, что время работы скрипта зависит от числа сравнений строк друг с другом

число таких сравнений примерно пропорционально квадрату строк

n*(n-1)/2

И совсем неплохо иметь такого рода представление, прежде чем начинать эсксперименты, которые естественно могут сильно отличаться от предварительных вычислений. Как я и говорил, предполагается что одинаковых строк почти нет.

спустя 40 минут [обр] Alexander O(122/460)[досье]
German[досье] В этой задаче не нужно сравнивать строки. Нужно каждую запоминать при просмотре, и игнорировать уже виденные. Количество операций пропорционально количеству строк, O(n), время растет линейно.
спустя 13 часов [обр] German[досье]

Alexander O[досье] мы переходим к следующей строке файла — чтобы понять уникальна эта строка или нет, мы должны сравнить ее со всеми предыдущими уникальными строками. Если колличество повторяющихся строк пернебрежимо мало, то число сравнений (как вы их не называйте) растёт примерно пропорционально квадрату

Число сравнений при двух строкак - одна операция, при трех - 3 операции сравнения. Как я писал n*(n-1)/2 Время, наверно, серьезно будет отличаться и от линейного, да и квадратным не станет. Но более правильное представление о ресурсоёмкости задачи создаёт квадрат — а не линия.

спустя 16 минут [обр] Dennis F. Latypoff aka funky_dennis(24/78)[досье]

German[досье]

мы должны сравнить ее со всеми предыдущими уникальными строками

Это если бы мы все считанные строки хранили в массиве.

Мы должны выяснить существует она в хеше или нет. Поиск в хеше это O(1). В итоге получается O(n). Если бы мы уникальные строки хранили не в хеше, а в бинарном дереве — O(log n), то итоговое время было бы O(n log n).

спустя 1 день 3 часа [обр] German[досье]

Dennis F. Latypoff aka funky_dennis[досье] да, может быть, здесь не все у меня продуманно :)
но не с потолка же я предложил этот квадрат?

Благодарю, Dennis[досье] за пояснения.

спустя 2 месяца 18 дней [обр] Saboteur[досье]
сообщение промодерировано

прошу сильно не пинать, я новичок в Перле.
у меня заработал вот такой код:

open IN, "test.txt";
open OUT, ">results.txt";
foreach (<IN>){$lines{$_} = $_;}
print OUT keys %lines;

чем не годится?

спустя 10 часов [обр] Lynn «Кофеман»(3/571)[досье]
Он описан во первом же комментарии словами и чуть ниже кодом.
Причём ваша версия не сохраняет порядок строк (хотя этого и нет в требованиях).
спустя 1 день 9 часов [обр] Алексей Севрюков(198/1280)[досье]
Saboteur[досье] как минимум нет смысла присваивать хэшу саму строку. Лучше пусть это будет единица, или, как в первоначальном примере — количество строк ($hash{$_}++). Память то она не резиновая, зачем зря разбазаривать.
спустя 17 часов [обр] Евгений Седов aka KPbIC(38/176)[досье]
как минимум нет смысла присваивать хэшу саму строку
Хранить в ключе вместо контрольной суммы саму строку — тоже смысла немного.
спустя 6 часов [обр] Алексей Севрюков(198/1280)[досье]
Евгений Седов aka KPbIC[досье] Это уже обсуждалось выше в теме, поэтому я и не стал говорить.
спустя 1 год 4 месяца [обр] !Serg[досье]
сообщение промодерировано

Код отлично работает на небольших массивах:

open IN, "test.txt";
open OUT, ">results.txt";
foreach (<IN>){$lines{$_} = $_;}
print OUT keys %lines;

У меня два строковых массива, один 12Гб, другой 24Гб. Попробовал на 64х перле запускать и безрезультатно. Свап увеличился до 43Гб после нескольких дней работы на 12Гб массиве. Запись промежуточных результатов несколько бы упростило работу.
Что-то стал сомневаться, что можно на перле решить мою задачу.

Кто докажет обратное?

спустя 19 часов [обр] Евгений Седов aka KPbIC(38/176)[досье]
сообщение промодерировано

!Serg[досье]
Может, стоит все-таки:

  1. Не хранить строку в значении хеша, а хранить там undef.
  2. В ключе хеша хранить не строку, а контрольную сумму.
  3. Вместо хеша использовать бинарное дерево.

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

спустя 1 месяц 23 дня [обр] !Serg[досье]
Спасибо за интерес, но я на перле в последний раз программировал 12 лет назад, все подзабыл (будет время\желание с удовольствием потренируюсь).
Сделал апргрейд машины (i7/24Gb/SSD80), теперь код (perl -ne '$%{$_}++ or print' bigfile > uniqfile) расправляется с данными 2Гб за два часа, а дальше 1Мб в минуту. 24Гб массив сделает за 2-3 недели, если не будет сбоев по питанию.
спустя 12 минут [обр] Евгений Седов aka KPbIC(38/176)[досье]
!Serg[досье] man screen вам в помощь.
Powered by POEM™ Engine Copyright © 2002-2005