Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2010.08.27;
Скачать: CL | DM;

Вниз

алгоритм удаления дубликатов из списка   Найти похожие ветки 

 
tippa ©   (2010-05-14 09:31) [0]

Добрый день. Нужно удалить из списка TStringList дубликаты. Как будет правильнее?

1. Сначала делаем сортировку, а затем в один проход удаляем дубликаты

или

2. Создаем вспомогательный список TstringList, проверяем каждый элемент первого списка на вхожесть во второй(вспомогательный), если не входит - добавляем

или

3. Берем первый элемент, со второго и до конца удаляем совпадающие с ним элементы. Потом берем второй элемент, с третьего и до конца ищем совпадения и удаляем. И так до предпоследнего оставшегося элемента.


 
Anatoly Podgoretsky ©   (2010-05-14 09:34) [1]

> tippa  (14.05.2010 09:31:00)  [0]

TStringList  и так имеет свойство Dublicates


 
tippa ©   (2010-05-14 09:45) [2]

задача - найти возможные алгоритмы, сравнить их, найти самый быстрый. Может еще какие способы имеются?


 
tippa ©   (2010-05-14 09:46) [3]

а можно в делфи посмотреть на реализацию свойства Duplicates?


 
Anatoly Podgoretsky ©   (2010-05-14 09:51) [4]

> tippa  (14.05.2010 09:46:03)  [3]

Конечно можно.


 
MBo ©   (2010-05-14 09:51) [5]

1 способ быстрее (2 и 3 имеют квадратичную сложность)


 
AK-47   (2010-05-14 10:25) [6]


> tippa ©   (14.05.10 09:45) [2]
>
> задача - найти возможные алгоритмы, сравнить их, найти самый
> быстрый. Может еще какие способы имеются?


Можно использовать хешированный список:

последовательно берем элементы из TStringList, проверяем есть ли такой элемент в хешированном списке, если есть удаляем из TStringList, если нет, то оставляем и добавляем его в хешированный список. И так для всех элементов.

Должна получится линейная сложность.


 
RWolf ©   (2010-05-14 10:39) [7]

Удаление из TStringList само по себе не О(1), так что, чтобы получить линейную сложность, надо избавляться от удалений.


 
AK-47   (2010-05-14 11:03) [8]


> RWolf ©   (14.05.10 10:39) [7]
>
> Удаление из TStringList само по себе не О(1), так что, чтобы
> получить линейную сложность, надо избавляться от удалений.
>

Да, не посмотрел как реализовано удаление. Тогда можно завести дополнительный TStringList и добавлять новые значения в него.



Страницы: 1 вся ветка

Текущий архив: 2010.08.27;
Скачать: CL | DM;

Наверх




Память: 0.48 MB
Время: 0.055 c
15-1270759152
Nickola2
2010-04-09 00:39
2010.08.27
Борьба с рекламными баннерами не увенчалась успехом


2-1274454281
Semen
2010-05-21 19:04
2010.08.27
возможно ли открытие документа Word по записи в таблице?


11-1221196936
L`Autour
2008-09-12 09:22
2010.08.27
Проблема с обработкой WM_PAINT в OnMessage


15-1268838645
Дмитрий
2010-03-17 18:10
2010.08.27
IbExpert


2-1270202304
Fr
2010-04-02 13:58
2010.08.27
Локализация программы с помощью Resource DLL Wizard