Алгоритм нахождения distinct значений

← →
dima_shapkin (2004-09-23 17:02) [0]

Уважаемые коллеги!!!
Кто сталкивался с проблемой быстрого нахождения distinct значений, а именно строк, причем очень "типичных и схожих"....
Использую хеш функцию, выдранную в Дельфе,
проблема конечно же в больших коллизиях из-за схожести значений и большой длинны строки.
Кто знает хоть что-нибудь по алгоритмам, методам, что угодно, хоть идею, буду очень признателен.

← →
Sandman25 © (2004-09-23 17:16) [1]

Отсортировать.

← →
Erik1 © (2004-09-23 17:33) [2]

Это целая науа, сортировка тут непоможет. Приведи проблему полностью.
Пример:
Сезам
зам
пр..
Вроде схожи :)

← →
Sandman25 © (2004-09-23 17:35) [3]

сортировка тут непоможет

Сортируем. Проходим с начала до конца, отслеживая изменения. В чем проблема?

← →
Erik1 © (2004-09-23 17:39) [4]

Первые буква могут отличатся, а слова быть похожими. Следовательно они попадут неподряд. Есть конечно возможность создать вычисляемое поле куда записывать фонетическое значение и сортировать по нему. Но помоему это отличается от сортировки

← →
dima_shapkin (2004-09-23 17:41) [5]

Хорошо сортировка допустим....
А каким алгоритмом сортировать?
Если использовать быструю сортировку от Дельфы, это повесится...

← →
Sandman25 © (2004-09-23 17:45) [6]

[4] Erik1 © (23.09.04 17:39)

Мы по разному понимаем задачу автора.

[5] dima_shapkin (23.09.04 17:41)

quicksort. Можно самому написать, можно найти готовый.

← →
dima_shapkin (2004-09-23 17:48) [7]

quicksort, тоже хорошо
Пример, далеко ходить не надо, сортирую в дельфе ее же быстрой сортировкой 30 тысяч строк, получаю полный зависон, Excel тратит на это менее секунды....
Наверняка для строк он использует спец. алгоритм, вот какой?

← →
Sandman25 © (2004-09-23 17:50) [8]

[7] dima_shapkin (23.09.04 17:48)

Код покажите... Может у Вас там перераспределение памяти идет.

> dima_shapkin (23.09.04 17:48)

Да ты что? 30 тысяч? Полный зависон? Конечно делфи виновата... кто же еще... не автор же... со своим странным мировоззрением...
За алгоритмами далеко ходить не надо... Исходники есть... Даже если нет... %Demos%\Threads\

Помимо сортировки с бинарным/интерполяционным поиском есть и другие меоды. Как то - деревья двоичного поиска, нагр. деревья (вот то рекомендую) и т.д. См. Кнут, Вирт, Ахо и др.

> [7] dima_shapkin (23.09.04 17:48)
> quicksort, тоже хорошо
> Пример, далеко ходить не надо, сортирую в дельфе ее же быстрой
> сортировкой 30 тысяч строк, получаю полный зависон

У меня вполне недурственно сортируется и миллион строк. Причем и дельфовой быстрой и моей с рядом изменеий - слегка быстрее.

Алгоритм нахождения distinct значений Найти похожие ветки