Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск дубликатов / 18 сообщений из 18, страница 1 из 1
03.09.2010, 21:08
    #36829258
Hett
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Потребовалось сейчас найти в большом массиве строк дубликаты.
Самое простое что пришло в голову:

Код: plaintext
1.
2.
for i =  1  to length(mas) -  2 
    for j = i +  1  to length(mas) -  1  
        if (mas[i] != null and mas[i] == mas[j]) mas[j] = null

Но полагаю есть что-то эффективнее?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 21:09
    #36829260
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
есть, отсортировать массив а потом сравнивать соседние элементы
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 21:09
    #36829261
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
сортировать естественно нужно квик сорт, иначе оптимизация в трубу
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 21:20
    #36829266
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Если изменять массив (сортировать) нежелательно, то используется вспомогательный объект - map, реализованный в виде хэш-таблицы или сбалансированного дерева.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 21:31
    #36829273
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Сбалансированное дерево -- по сути та же сортировка, только с б о льшим расходном памяти.
Хеш-таблицы на больших массивах могут быть не эффективны, смотря что такое "большой" массив.
Сортировка -- в подавляющем большинстве случаев оптимальный вариант.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 21:45
    #36829284
Hett
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
3кк записей.
Сортировка, тогда какая? Я только пузырек и пирамидальную помню.
Можно тогда при добавлении элемента проверять.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 21:52
    #36829287
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Hett3 кк записей.3 миллиона что-ли?

что за язык используется? Квик-сорт есть готовый много где.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 22:05
    #36829295
Hett
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Да 3 млн. Там в каждом элементе одно слово.
Язык - Delphi.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 22:11
    #36829299
fd00ch
fd00ch
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
HettЯзык - Delphi.По первому посту не заметно :-)

Решение: создаете TStringList, выставляете Sorted=True и добавляете свои 3 млн. строк. После этого в списке автоматически будут только уникальные значения. Анализируя число, возвращаемое методом Add, и свойство Count, можно сделать вывод о том, являлась ли добавляемая строка дублем.
При желании можно поиграться свойством CaseSensitive.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 22:12
    #36829300
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
HettЯ только пузырек и пирамидальную помню.
Пузырёк лучше забыть. Пирамидальная прокатит.
Но если массив достаточно беспорядочен, то quicksort ощутимо лучше (да она и проще в реализации, чем пирамидальная).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 22:26
    #36829310
Hett
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
А такой вопрос, если сначала заполнить TStingList а потом sorted = true сделать, то он отсортирует? И как это по скорости будет? Быстрее чем сначала выставить и добавлять?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 22:32
    #36829316
fd00ch
fd00ch
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Hett, а попробовать самому религия не позволяет?..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 22:38
    #36829323
Hett
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Уже пошел.
Работает довольно быстро этот стрингЛист, устраивает. Спасибо за подсказку.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.09.2010, 15:28
    #36829631
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Три миллиона строк - в ТСтрингЛист это сурово. Главное чтобы завтра не пришло три миллиарда. А то выйдет конфуз.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.09.2010, 11:19
    #36831100
manitor
manitor
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
Можно Поиск дубликатов при помощи разного бесплатного софта. Скачай отсюда, например.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.09.2010, 00:46
    #36833076
Hett
Hett
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
maytonТри миллиона строк - в ТСтрингЛист это сурово. Главное чтобы завтра не пришло три миллиарда. А то выйдет конфуз.
Нынче память не 640 килобайт, однако =) Да и там в каждой записи - одно слово.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.09.2010, 01:19
    #36833086
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
HettНынче память не 640 килобайт, однако =) Да и там в каждой записи - одно слово.
Это типичные рассуждения "плохого" девелопера. Не забудь указать в ТЗ что твой софт отбирает всю свободную память.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.09.2010, 02:44
    #36833113
Denis.
Denis.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск дубликатов
я так сортировал во времена когда вместо строк юзал TMemo(кажется так называлось)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск дубликатов / 18 сообщений из 18, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 499ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1343478]:
 0ms
get settings:
 9ms
get forum list:
 11ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 173ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 50ms
get tp. blocked users:
 1ms
others: 238ms
total:  499ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]