Алгоритм выбора уникальных значений из нескольких "крупных" (1-2Мб) массивов?

[Camillo]

Алгоритм выбора уникальных значений из нескольких "крупных" (1-2Мб) массивов?

Привет.

Есть несколько массивов. Каждый ~ 1-2Мб и хранится в отдельном файле.

Задача: Выбрать из всех этих массивов только уникальные комбинации ключ > значение. (т.е. если в первом массиве есть 'masha' => 'sasha', то этой пары уже не должно быть в остальных массивах).

Сложность задачи в том, что таких файлов с массивами окол 30-40 штук, т.е. склеивание массива не катит в этом случае.

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

Подскажите пожалуйста более рациональное решение.

Спасибо.

 

[sage]

а как у тебя хранятся массивы в файлах?

 

[Camillo]

ну допустим, они хранятся в формате
key|value
key1|value2
....
keyn|valuen
и т.д.

 

[Loshadka]

Camillo
А если их переложить в базу, в таком же виде: key|value
А после DISTINCT

 

[bkonst]

Может, использовать "ленточную" сортировку (позволит получить слитый отсортированный файл без больших затрат памяти), а потом ещё раз пройтись уже по отсортированному файлу?

 

[Camillo]

Loshadka, я уже думал об этом. Но я думаю, что INSERT 1-2 млн. строк длиной 18-20байт займет очень много времени.

-~{}~ 31.01.06 12:38:

bkonst, а где можно внятно почитать про "ленточную" сортировку?

 

[Loshadka]

Camillo
Зато поиск, однозначно, будет быстрее...

А чтобы скрипт не вылетел по timeout - у, разбей задачу на несколько, т.е. каждый скрипт загружает в базу всего один файл...

-~{}~ 31.01.06 12:40:

+ любые другие операции с этими данными будут выполнятся так же быстро... ;-)

 

[Camillo]

Loshadka, окей - сейчас попробую.

bkonst, почитал вот тут про несколько алгоритмов сортировки массивов http://rusdoc.ru/articles/9817/

Но они все подходят только для случая, когда весь массив находится в памяти...

Сейчас попробую в БД загнать, как сказала Loshadka и опубликую результаты.

 

[vovik]

С базой - совсем уж извращение. Не такие уж большие объемы данных.

Навскиду делаем так:
1. Файлы читаем с помощью `sort -u < file1`
2. Присоединяем к массиву уникальных значений и делаем array_unique() после каждого файла.

Можно всячески еще заморочиться, но этого должно хватить.

 

[Loshadka]

vovik
Не факт, что у php хватит памяти на весь этот массив.

Арифметика: 1-2Мб * 30-40Мб = 30-80Мб....

Т.е. достаточно 1/3 уникальных значений для того, чтобы php не хватило 8мб по-умолчанию...

 

[bkonst]

Camillo
У Кнута в третьем томе очень хорошо расписано.
В электронном виде (правда, не совсем внятно) на русском можно почитать на http://www.emanual.ru/download/9792.html, например. Если английский - не проблема, на википедии есть хорошая статья по этой теме: http://en.wikipedia.org/wiki/Merge_sort

Эта же сортировка называется "merge sort" или "сортировка слиянием"

~~~

Как раз предназначена для случая, когда весь объем данных не помещается в памяти.

 

[Andreika]

$unique = array();
$output = array();

for(; {

$s = fgets ($f);
$crc = crc32($s);

if (!in_array($crc, $unique)) { $unique[] = $crc; $output[] = $s; }
}

1000000*4(int32) ~1Mb ?

 

[vovik]

Автор оригинала: Loshadka
vovik
Т.е. достаточно 1/3 уникальных значений для того, чтобы php не хватило 8мб по-умолчанию...

Я не претендую на истину в последней инстанции, просто предлагаю один из вариантов.

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

 

[Camillo]

vovik, точно!
Про shell то я забыл что-то Спасибо что напомнил.

Я тогда вообще сделаю просто.
Сперва sort с output'ом в файл, а потом uniq.

-~{}~ 31.01.06 13:09:

bkonst
Спасибо за ссылки! Обязательно почитаю.

-~{}~ 31.01.06 13:16:

Сделал вот так на ~10Мб файле (~15-20% неуникальных строк):

date;
sort -u -o file.txt myfile.log;
uniq -u file.txt uniq.txt;
date;

Результат:
Tue Jan 31 13:12:13 MSK 2006
Tue Jan 31 13:12:20 MSK 2006

Ну что я могу сказать - меня результат порадовал очень.
vovik, спасибо тебе!

 

[vovik]

Пожалуйста

Только отмечу, что sort -u уже оставляет только уникальные значения.

 

[Camillo]

Автор оригинала: vovik
Пожалуйста

Только отмечу, что sort -u уже оставляет только уникальные значения.

а я просто не стал ман читать и влоб написал.
посмотрел:

-u, --unique
with -c, check for strict ordering; without -c, output only the first of an equal run

и правда
Ну что я могу сказать - тогда еще быстрее будет.