подскажите алгоритм

[Termin@L]

Народ подскажите, как считать большой текстовый файл(допустим словарь) и очистить его от повторов или наоборот, например найти элемент повторяющийся наибольшее кол-во раз, какой самый быстрый способ (желательно на php)?

[Helios]

Убирал совпадения из фалика в 200000 строк таким макаром:


<?php

$data_in = file("numbers.txt");


$data2 = file("base_final.txt");

$data_in = array_merge($data_in, $data2);

sort(&$data_in);


$t = count($data_in);

$iterator = 0;

$data_out = array();

$data_out[] = $data_in[0];

for($i = 1; $i < $t; $i++)
{
if($data_in[$i] != $data_in[$iterator])
{
$data_out[] = $data_in[$i];
$iterator = $i;
}
}

file_put_contents("base_final.txt", join("", $data_out));

echo "Done! Total " . count($data_out) . " items";
?>

[Srg]

А еще бы комментов :)......

[ZaCo]

>>Народ подскажите, как считать большой текстовый файл
2Helios мало того что алгоритм неэффективен так он еще и под заданную задачу не подходит.

[Helios]

Комменты:
После считывания файла все его строки сортирую, при этом одинаковые окажутся рядом. На это совпадение и проверяю. При желании можно прикрутить strtoupper/strtolower дабы не обращать внимания на регистр.

2ZaCo Напиши эффективнее, ты ж чингачкук.

[ZaCo]

2Helios я напишу вот только задачи не вижу.

[genom--]

Комменты:
После считывания файла все его строки сортирую, при этом одинаковые окажутся рядом. На это совпадение и проверяю. При желании можно прикрутить strtoupper/strtolower дабы не обращать внимания на регистр.

2ZaCo Напиши эффективнее, ты ж чингачкук.

понимаешь твоя ошибка в том что при сортировке тебе полюбому придется заносить все в массив и они будут немеренно жрать оперативы о-- особенно если словарь метров на 300 ---

[nerezus]

понимаешь твоя ошибка в том что при сортировке тебе полюбому придется заносить все в массив и они будут немеренно жрать оперативы о-- особенно если словарь метров на 300 --- Либо память, либо скорость.
Т.к. память безгранична за счет раздела подкачки, то... ;)

[Termin@L]

2 ZaCo задача - находить повторяющиеся элементы в текстовом файле и производить с ними различные действия

[Helios]

Скрипт ентот исполняться будет не сотню раз одновременно, а в один поток, поэтому на ОЗУ жаловаться ИМХО нет смысла. А насчет того, что считывать нужно весь файл сразу - в другом случае прогонять поиск совпадений по циклу и сортировку пришлось бы после каждого считывания => время исполнения увеличилось бы в разы.

З.Ы.: Кто знает другие варианты - пишите, а то и самому интерессно)

[k1b0rg]

Helios

твой код можно заменить одной функцией array_unique которуая удалит все дубликаты из массива.


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

[KSURi]

Это по тому что, написал киба (perl, портировать на php не составит труда)
foreach(@tmp) { push(@unqie,$_) if !$seen{$_}; $seen{$_}=1; }
@tmp - список в который считывается файл
@unique - список в котором окажутся все уникальные строки
%seen - хэш, в котором будут повторы (key=>имя_повтора, value=>всегда 1)
Хотя я не совсем уверен, что это есть оптимальный алгоритм... Хотя хз...

UPD:
E:\>perl unique.pl
All: 1008176; Unique: 1000000; Time: 17 secs
E:\>

Oбрабатывался файл размером 25 284 608 байт (1008176 строк)

[k1b0rg]

Написал аналог php'шной функции


sub array_unique(@)
{
@input=@_;
%temp=();
foreach $item (@input) {
push(@output, $item) unless $temp{$item}++;
}
return @output;
}

использовать так:

@arr=array_unique(@arr);

[KSURi]

Я модифицировал функцию от кибы и получилось вот что:

sub array_unique
{
my $input=shift;
my %seen;
my $i=0;
foreach(@{$input})
{
delete @{$input}[$i] if $seen{$_};
$seen{$_}=1;
$i++;
}
}

Работает теперь вот так:

E:\>perl unique.pl
All: 1008176; Unique: 1000000; Time: 8
E:\>

Вызывать ее теперь вот так: array_unique(\@arr);