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

← →
Neux (2007-09-23 00:53) [0]

Подскажите, пожалуйста, как удалить одинаковые строки в текстовом массиве, который имеет 250 000 строк. Я делаю следующим образом:
1. создаю новый масив
2. читаю строку в массиве с 250 000 строками
3. проверяю нет ли в новом массиве этой строки
4. если нет, то записываю в конец массива новую строку
5. возвращаюсь к пункту 2

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

← →
Zeqfreed © (2007-09-23 02:07) [1]

Отсортировать список нужно. А потом уже искать чем-нибудь типа двоичного поиска. Это принесет наибольший вклад в ускорение работы. Дальнейшие улучшения возможны, но не будут настолько значимы.

← →
DrPass © (2007-09-23 02:29) [2]

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

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

← →
Германн © (2007-09-23 02:52) [3]

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

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

← →
Zeqfreed © (2007-09-23 03:00) [4]

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

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

← →
Riply © (2007-09-23 03:05) [5]

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

← →
Германн © (2007-09-23 03:15) [6]

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

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

← →
DrPass © (2007-09-23 14:52) [7]

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

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

← →
Суслик © (2007-09-23 15:03) [8]

делать можно как угодно, но главное, чтобы алгоритмы поиска одной строки имел сложность C*log(n), а не C*n. (C-константа).

← →
Zeqfreed © (2007-09-23 15:08) [9]

> Германн © (23.09.07 03:15) [6]

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

← →
Johnmen © (2007-09-23 15:58) [10]

Я бы придумал хорошую хеш-функцию, чтобы сам хеш ложился в integer, или хотя бы в int64. Тогда всё делается за один проход массива. Быстро.

← →
Долби (2007-09-23 20:40) [11]

Юзайте Java, там есть HashMap )

← →
palva © (2007-09-23 22:09) [12]

Можно использовать Access. Завести таблицу с одним индексированным полем. Если, конечно, строки приемлемой длины.

← →
Neux (2007-09-23 22:11) [13]

Есть массив с 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:38) [14]

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

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

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

> Для 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 ГГц

> 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 не имеет смысла.

← →
Neux (2007-09-24 00:49) [19]

Всем спасибо, особенно palva
Сделал через TStringList

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

$ cat /tmp/data | wc -l 249999 $ cat /tmp/data | sort | uniq -d | wc -l 60946 $ time cat /tmp/data | sort | uniq > /tmp/data2 real 0m4.681s user 0m4.195s sys 0m0.115s $ ls -l /tmp/data* -rw-r--r-- 1 artem artem 1657995 2007-09-24 02:53 /tmp/data -rw-r--r-- 1 artem artem 1124873 2007-09-24 02:53 /tmp/data2

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

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