На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (4) [1] 2 3 ... Последняя » все  ( Перейти к последнему сообщению )  
> Быстрый поиск
    Имеется очень большой массив слов.
    Необходимо определить - есть ли в нём повторяющиеся слова (эти слова могут находиться в любом месте, даже в противоположных концах массива).
      сортируй! я думаю за линейное время всё равно не получится
        Если порядок данных в массиве не имеет значения, построй такое дерево:
         Узел содержит два указателя (и все)
         Глубина --- шестнадцать уровней (от 0 до 15)
         Нижний, пятнадцатый, уровень может указывать на терминатор (такой же узел, но указатели в нем всегда NULL, NULL)
         Каждое число --- это цепочка указателей от вершины дерева до терминатора.
        Количество узлов в полном (все 65536 вариантов) дереве 216, объем занимаемой памяти 2 * 216 указателей. Когда заносишь код который уже существует в дереве, обнаружишь что есть все указатели вплоть до терминатора. Время определения фиксированно, зависит от глубины дерева и не зависит от количества данных в дереве.
          непонял какое отношение сие дерево имеет к задаче
            QUOTE (wormball @ 20.09.03, 14:16:26)
            непонял какое отношение сие дерево имеет к задаче

            Быстрый поиск
            Сообщение отредактировано: MeG -
              ну ты умный! заголовок прочитал, а пост нет. задача то в том, чтобы определить, есть ли в массиве одинаковые слова. к тому же твоё древо будет искать не быстрее, чем двоичный поиск
                В задаче не указано откуда беруться данные в массиве и как используется массив кроме поиска.
                Время поиска по 'моему' дереву фиксированное и не зависит от количества элементов в нем.
                  зато максимальное количество елементов в нём зависит от его глубины ;D
                  так что как ни крути, qsort+двоичный поиск быстрее
                    QUOTE (wormball @ 20.09.03, 15:40:16)
                    зато максимальное количество елементов в нём зависит от его глубины ;D
                    так что как ни крути, qsort+двоичный поиск быстрее

                    (хрум) ;D
                    от глубины зависит разрядность хранимых данных
                    Сообщение отредактировано: MeG -
                      темболее!! строки-то большие!!какправило ;D
                        smile.gif
                        смотря что Jin X назвал словом.
                        'мое дерево' хранит WORD  biggrin.gif
                        Сообщение отредактировано: MeG -
                          ну в таком случае если в массиве больше чем 65536 слов, тогда и думать нечего - как пить дать одинаковые будут ;D
                            обычные словари русского языка содержат еще меньше слов :)
                              зато большой разрядности ;D
                                smile.gif
                                можно построить 'мое дерево' и для русских слов (или не русскихsmile.gif ) и глубину не фиксировать, но игра стоит свеч только если "скорость превыше всего"
                                Сообщение отредактировано: MeG -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0411 ]   [ 15 queries used ]   [ Generated: 21.05.24, 08:23 GMT ]