Форум: "Начинающим";
Текущий архив: 2010.08.27;
Скачать: [xml.tar.bz2];
Внизалгоритм удаления дубликатов из списка Найти похожие ветки
← →
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;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.067 c