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

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

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

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

tippa © (2010-05-14 09:31:00)
Добрый день. Нужно удалить из списка TStringList дубликаты. Как будет правильнее?

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

или

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

или

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

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

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

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

RWolf (2010-05-14 10:39:00) [2]
Удаление из TStringList само по себе не О(1), так что, чтобы получить линейную сложность, надо избавляться от удалений.

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

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

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

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

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

Anatoly Podgoretsky (2010-05-14 09:51:00) [4]
> tippa (14.05.2010 09:46:03) [3]

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

MBo (2010-05-14 09:51:00) [5]
1 способ быстрее (2 и 3 имеют квадратичную сложность)

tippa (2010-05-14 09:46:00) [6]
а можно в делфи посмотреть на реализацию свойства Duplicates?

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

Anatoly Podgoretsky (2010-05-14 09:34:00) [8]
> tippa (14.05.2010 09:31:00) [0]

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

Наверх

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