Форум: "Начинающим";
Текущий архив: 2007.10.21;
Скачать: [xml.tar.bz2];
ВнизУдаление одинаковых строк Найти похожие ветки
← →
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
По идее должно быстро сработать.
← →
DrPass © (2007-09-23 23:05) [15]
> А если использовать TStringList, установив Sorted = True
> и Duplicates = dupIgnore
> По идее должно быстро сработать.
Для 250000 строк? Компьтер сепукку на половине этого сделает
← →
palva © (2007-09-23 23:53) [16]> Для 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-24 00:30) [17]
> palva © (23.09.07 23:53) [16]
Мой P-233 считает до сих пор :-Р
← →
Германн © (2007-09-24 00:48) [18]
> 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 секунд на все!
← →
Zeqfreed © (2007-09-24 00:57) [20]
$ 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
Менее пяти секунд стандартными утилитами. Зачем что-то писать? :)
Страницы: 1 вся ветка
Форум: "Начинающим";
Текущий архив: 2007.10.21;
Скачать: [xml.tar.bz2];
Память: 0.49 MB
Время: 0.042 c