Быстрый поиск

помоему наоборот, так двоичным поиском быстрее

я же говорю, скорость поиска не зависит (совсем!) от количества

так думаю нагляднее

Сообщение отредактировано: MeG - 07.11.03, 15:50

ну так правильно, с помощью твоего дерева можно выразить только числа не больше ворда, а русские слова куда больше, придётся глубину увеличивать.

к тому же можно обойтись вобще без дерева. заводим массиф [0..65535] оф боолеан, ну и сей боолеан будет обозначать присутствие данного ворда в исходном массиве. так время поиска вобще не будет зависеть от колва данных (при етом сократится до трёх операций: индексации, обращения к памяти и сравнения), да и памяти в десятки раз (особенно если биты использовать) меньше потребуется. только чтобы все русские слова выразить всё равно много памяти уйдёт.

Сообщение отредактировано: wormball - 20.09.03, 13:24

используй хеш-функцию.

заводишь массив хешей. каждый элемент этого массива - ссылка на список элементов, имеющих такой хеш.

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

и пример. хеш - первая  буква слова

хеш-массив
а,б,в,г,д, ...  (ну числе ессно, )

for(int i=0;i<N;i++)
{
   if(hash[array[i][0]]!=0)
    {
         list_pointer* lp=hash[array[i][0]];
          while(lp)
            {
                if(strcmp(lp->data,array[i])==0) goto out;
                 lp=lp->next;
             }

    }
}

естественно, что хеш функция должна быть получше. а хеш массив побольше.

как пример хеш-функции - что-нить на тему суммы элементов. возможно не всех элементов, а  только первого, среднго и последнего.

Сообщение отредактировано: Demo_S - 20.09.03, 16:50

дерево для словаря строим так



Чем больше слов в дереве, тем эффективнее используется память. Для русского (33 буквы) словаря из 60 тысяч слов, по ориентировочной оценке, потребуется около 5000 узлов, требуемый объем памяти менее 1,5 МБайт. Этот же словарь в виде массива займет, примерно, 600кБайт.

В этом же дереве можно хранить и словарь английских слов, добавляем еще один терминатор и по другому интерпретируем связи. Дополнительные затраты будут мизерными.

Еще раз. Время поиска по такому дереву не зависит от количества слов в нем, и зависит от длины слова.

Очевидно, что вариантов решения может быть много. И известна старая проблема: если мы сокращаем затраты памяти, то увеличивается время обработки, Если уменьшаем время обработки, то возрастают затраты памяти.  Каждый выбирает сам, что ему больше подходит.

2 Jin X, ты где пропал, открой секрет, что тебе нужно?

Сообщение отредактировано: MeG - 07.11.03, 15:51

Jin X молчит как партизан

продолжу
в узлы нужно добавить признак конца слова, для разных языков разные флаги


Динамически выделять память для каждого узла не выгодно: дополнительные затраты памяти, потери времени для нескольких тысячь new/delete (или что там вам больше нравится), алгоритм удаления всего дерева сложный. Проще и быстрей выделить память для всего дерева сразу, удалять одним махом, или статически.

что-то в этом духе

Сообщение отредактировано: MeG - 07.11.03, 15:51

Цитата MeG, 21.09.03, 11:52:34

дерево для словаря строим так

Круто! Я раньше где-то о таком слышал, но тогда не врубился.

всёравно в данной конкретной задаче quicksort работает быстрее. если уж ты не веришь моим словам, можно поспорить: я напишу qsort, ты напишешь дерево, jin x предоставит массив и мы посмотрим, кто быстрее. а потом я объясню, почему. ;D

зы. желательно на паскале

Сообщение отредактировано: wormball - 22.09.03, 13:27

Ого!
Имеется в виду поиск одинаковых слов в словаре русских и иностранных слов.
Задача 1: удалить совпадения.
Задача 2: быстро найти слово.

2 MeG: Интересный метод, но у него есть один недостаток: в твоё дерево нельзя заложить, например, слова "мир" и "мираж". Но если его немного модифицировать: добавить булевскую переменную "ТакоеСловоЕсть", то всё будет пучком. А вот памяти это будет жрать много, т.к. представь: есть, например, слово "компьютер"... ветвь, идущая от буквы "е" будет содержать 33 указателя (по 4 байта, даже по 5, если добавить bool), хотя использоваться будет только один.

2 wormball: Кол-во слов в словаре может быть несоклько сот тысяч. Для 200000 слов бинарный поиск будет достигать 18 итераций (сравнение + арифметические операции). Тормозным моментом здесь является создание хэшей (один раз для всего словаря) или сравнение целого слова (если не строить хэши). В методе MeG'а тормозным моментом является выделение памяти под каждое слово и инициализация таблицы указателей (но это тоже только 1 раз для всего словаря). Но твой метод менее ресурсоёмок.
Ты всё-таки объясни, почему твой метод быстрее...

Вообще, я надеялся, что можно как-нибудь организовать это дело (решение задачи 1) так, чтобы не искать каждое слово в словаре.

Но это тоже неплохо.
Всем спасибо!

Сообщение отредактировано: 7in - 22.09.03, 16:45

моим методом искать слово не придётся. надо будет просто после сортировки просматривать подряд массив и удалять слово, если оно такое же, как идущее до него.

я тут подумал и решил, что если букв больше 2х, то метод mega всётаки должен быть побыстрее. но всёже я думаю стоит сравнить в натуре.

ивобще у моего метода сложность n log n, а у mega n log m, где m - колво букв в слове.

Сообщение отредактировано: wormball - 22.09.03, 17:00

Цитата wormball, 22.09.03, 20:54:31

а у mega n log m, где m - колво букв в слове

Ты хотел сказать n*m ?

2 wormball
давай сравним  ;D
до выходных подождешь?
для начала словарь один.
(где ты там n нашел ?)

2 Jin X я сказал о флагах в 21 сообщении

Цитата Jin X, 22.09.03, 22:52:22

Ты хотел сказать n*m ?

скорее да, чем нет

я тут на досуге подумал ;D и решил, что у моего метода (т е у qsorta) будет m*n*log(n), ибо при сравнении строк в худшем случае придётся произвести m операций.

похоже мне придётся признать своё поражение ;D

Цитата MeG, 22.09.03, 23:20:46

2 Jin X я сказал о флагах в 21 сообщении

Sorry, упустил.
2 wormball: Это уже "Память vs Скорость". Большая ли у вас с MeG'ом разница в скорости будет?