Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Neux © (2007-09-23 00:53:00)
Подскажите, пожалуйста, как удалить одинаковые строки в текстовом массиве, который имеет 250 000 строк. Я делаю следующим образом:
1. создаю новый масив
2. читаю строку в массиве с 250 000 строками
3. проверяю нет ли в новом массиве этой строки
4. если нет, то записываю в конец массива новую строку
5. возвращаюсь к пункту 2

Таким образом это занимает очень много времени. Нужен самый быстрый алгоритм работы.

Zeqfreed (2007-09-24 00:57:00) [1]
$ cat /tmp/data | wc -l 249999 $ cat /tmp/data | sort | uniq -d | wc -l 60946 $ time cat /tmp/data | sort | uniq > /tmp/data2 real 0m 4.681s user 0m4.195s sys 0m0.115s $ ls -l /tmp/data* -rw-r--r-- 1 artem artem 16579952007-09-24 02:53 /tmp/data -rw-r--r-- 1 artem artem 11248732007-09-24 02:53 /tmp/data2

Менее пяти секунд стандартными утилитами. Зачем что-то писать? :)

Neux (2007-09-24 00:49:00) [2]
Всем спасибо, особенно palva
Сделал через TStringList

Считает быстро... Процедура объединяет 75 файлов в один, сортируя и удаляя дубликаты. Получается всего 550 000 Ip адресов, после удаления дубликатов - 54 200. Затраты по времени: 25 секунд на все!

Германн (2007-09-24 00:48:00) [3]

> Neux (23.09.07 22:11) [13]

Мой совет.
> Application.ProcessMessages;
не надо вызывать на каждойитерации цикла. Прикинь время выполнения одной итерации

> k:=k+1;
> if IP[k]=IPtmp[i] then check:=false;
> if (k>OriginalProxy) or (check=false) then yes:=false;

и поймёшь, что так часто проверять очередь сообщений Windows не имеет смысла.

DrPass (2007-09-24 00:30:00) [4]

> palva © (23.09.07 23:53) [16]

Мой P-233 считает до сих пор :-Р

palva (2007-09-23 23:53:00) [5]
> Для 250000 строк? Компьтер сепукку на половине этого сделает
Следующий код работал у меня 50 секунд
procedure TForm1.FormCreate(Sender: TObject); var sl: TStringList; begin sl := TStringList.Create; sl.Sorted := True; sl.Duplicates := dupIgnore; sl.LoadFromFile('D:\C\pascal\test.txt'); sl.SaveToFile('D:\C\pascal\test1.txt'); sl.Free; end; test.txt содержал 250000 строк с случайными числами в диапазоне 0..300000 и имел размер 1907433 байта. test1.txt был отсортированный файл без дубликатов и имел размер 1294754 байта. Процессор 2.4 ГГц

DrPass (2007-09-23 23:05:00) [6]

> А если использовать TStringList, установив Sorted = True
> и Duplicates = dupIgnore
> По идее должно быстро сработать.

Для 250000 строк? Компьтер сепукку на половине этого сделает

palva (2007-09-23 22:38:00) [7]
А если использовать TStringList, установив Sorted = True и Duplicates = dupIgnore
По идее должно быстро сработать.

Neux (2007-09-23 22:11:00) [8]
Есть массив с 250 000 прокси. Нужно удалить все повторения. Массив - string

For I:=0 to TotalProxy do begin
check:=true;
k:=0; yes:=true;
proxycount:=i;

repeat
k:=k+1;
Application.ProcessMessages;
if IP[k]=IPtmp[i] then check:=false;
if (k>OriginalProxy) or (check=false) then yes:=false;
until not yes;

If check=true then begin IP[i]:=IPtmp[i]; OriginalProxy:=originalProxy+1;end;
end;

//TotalProxy - общее кол-во прокси (250 000)
//IP - массив с оригинальными адресами прокси
//IPtmp - массив с 250 000 прокси

palva (2007-09-23 22:09:00) [9]
Можно использовать Access. Завести таблицу с одним индексированным полем. Если, конечно, строки приемлемой длины.

Долби (2007-09-23 20:40:00) [10]
Юзайте Java, там есть HashMap )

Johnmen (2007-09-23 15:58:00) [11]
Я бы придумал хорошую хеш-функцию, чтобы сам хеш ложился в integer, или хотя бы в int64. Тогда всё делается за один проход массива. Быстро.

Zeqfreed (2007-09-23 15:08:00) [12]
> Германн © (23.09.07 03:15) [6]

Ну, возможно и так :)
Советовать что-то конкретное здесь не получится в виду скудности предоставленной информации.

Суслик (2007-09-23 15:03:00) [13]
делать можно как угодно, но главное, чтобы алгоритмы поиска одной строки имел сложность C*log(n), а не C*n. (C-константа).

DrPass (2007-09-23 14:52:00) [14]

> Германн © (23.09.07 02:52) [3]

А необязательно нарушать порядок строк. Дубли ж можно выбрасывать не только из результирующего массива, но и из исходного :)
Там уж пущай автор сам разбирается. Если он еще жив...

Германн (2007-09-23 03:15:00) [15]

> Zeqfreed © (23.09.07 03:00) [4]
>
> > Германн © (23.09.07 02:52) [3]
>
> Никто не заставляет нарушать порядок строк. А вот поиск
> в сортированном списке происходит на порядок быстрее — это
> факт.
>

Так кто ж спорит?
Но в "Начинающих" не стоит бросаться "неопределенными" советами. Ты же не сказал, что именно ты советуешь "отсортировать". Я как и DrPass © (23.09.07 02:29) [2], имхо, понял твой совет что нужно сначала отсортировать исходный текст.

Riply (2007-09-23 03:05:00) [16]
> [0] Neux (23.09.07 00:53)
Недавно была ветка постов на сто про это.
Там в результате бесчисленных споров написали искомую функцию.
Ищи по форуму

Zeqfreed (2007-09-23 03:00:00) [17]
> Германн © (23.09.07 02:52) [3]

Никто не заставляет нарушать порядок строк. А вот поиск в сортированном списке происходит на порядок быстрее — это факт.

Германн (2007-09-23 02:52:00) [18]

> Вот как раз сортировка методом вставки здесь и подойдет.
> И без всяких двоичных поисков - т.е. добавляем в условие
> сортировки отбрасывание дублей, и на выходе получаем уже
> готовый массив без одинаковых строк
>

Подойдёт сортировка или нет это автору решать. Ведь для него может быть важен исходный порядок расположения строк в тексте.

DrPass (2007-09-23 02:29:00) [19]

> Отсортировать список нужно

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

Zeqfreed (2007-09-23 02:07:00) [20]
Отсортировать список нужно. А потом уже искать чем-нибудь типа двоичного поиска. Это принесет наибольший вклад в ускорение работы. Дальнейшие улучшения возможны, но не будут настолько значимы.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »