На главную Наши проекты:
Журнал   ·   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 ... Последняя » все  ( Перейти к последнему сообщению )  
> Быстрый поиск
Guru Jin X
Сообщ. #1 ,

    Законченный оптимист
    *******
    Профиль · PM
    Поощрения: 23 Dgm
    Рейтинг (т): 117
    Имеется очень большой массив слов.
    Необходимо определить - есть ли в нём повторяющиеся слова (эти слова могут находиться в любом месте, даже в противоположных концах массива).
    wormball
    Сообщ. #2 ,
      Unregistered
      сортируй! я думаю за линейное время всё равно не получится
      MeG
      Сообщ. #3 ,
        Profi
        *****
        Профиль · PM
        Поощрения: 1 Dgm
        Рейтинг (т): 38
        Если порядок данных в массиве не имеет значения, построй такое дерево:
         Узел содержит два указателя (и все)
         Глубина --- шестнадцать уровней (от 0 до 15)
         Нижний, пятнадцатый, уровень может указывать на терминатор (такой же узел, но указатели в нем всегда NULL, NULL)
         Каждое число --- это цепочка указателей от вершины дерева до терминатора.
        Количество узлов в полном (все 65536 вариантов) дереве 216, объем занимаемой памяти 2 * 216 указателей. Когда заносишь код который уже существует в дереве, обнаружишь что есть все указатели вплоть до терминатора. Время определения фиксированно, зависит от глубины дерева и не зависит от количества данных в дереве.
        wormball
        Сообщ. #4 ,
          Unregistered
          непонял какое отношение сие дерево имеет к задаче
          MeG
          Сообщ. #5 ,
            Profi
            *****
            Профиль · PM
            Поощрения: 1 Dgm
            Рейтинг (т): 38
            QUOTE (wormball @ 20.09.03, 14:16:26)
            непонял какое отношение сие дерево имеет к задаче

            Быстрый поиск
            Сообщение отредактировано: MeG -
            wormball
            Сообщ. #6 ,
              Unregistered
              ну ты умный! заголовок прочитал, а пост нет. задача то в том, чтобы определить, есть ли в массиве одинаковые слова. к тому же твоё древо будет искать не быстрее, чем двоичный поиск
              MeG
              Сообщ. #7 ,
                Profi
                *****
                Профиль · PM
                Поощрения: 1 Dgm
                Рейтинг (т): 38
                В задаче не указано откуда беруться данные в массиве и как используется массив кроме поиска.
                Время поиска по 'моему' дереву фиксированное и не зависит от количества элементов в нем.
                wormball
                Сообщ. #8 ,
                  Unregistered
                  зато максимальное количество елементов в нём зависит от его глубины ;D
                  так что как ни крути, qsort+двоичный поиск быстрее
                  MeG
                  Сообщ. #9 ,
                    Profi
                    *****
                    Профиль · PM
                    Поощрения: 1 Dgm
                    Рейтинг (т): 38
                    QUOTE (wormball @ 20.09.03, 15:40:16)
                    зато максимальное количество елементов в нём зависит от его глубины ;D
                    так что как ни крути, qsort+двоичный поиск быстрее

                    (хрум) ;D
                    от глубины зависит разрядность хранимых данных
                    Сообщение отредактировано: MeG -
                    wormball
                    Сообщ. #10 ,
                      Unregistered
                      темболее!! строки-то большие!!какправило ;D
                      MeG
                      Сообщ. #11 ,
                        Profi
                        *****
                        Профиль · PM
                        Поощрения: 1 Dgm
                        Рейтинг (т): 38
                        smile.gif
                        смотря что Jin X назвал словом.
                        'мое дерево' хранит WORD  biggrin.gif
                        Сообщение отредактировано: MeG -
                        wormball
                        Сообщ. #12 ,
                          Unregistered
                          ну в таком случае если в массиве больше чем 65536 слов, тогда и думать нечего - как пить дать одинаковые будут ;D
                          MeG
                          Сообщ. #13 ,
                            Profi
                            *****
                            Профиль · PM
                            Поощрения: 1 Dgm
                            Рейтинг (т): 38
                            обычные словари русского языка содержат еще меньше слов :)
                            wormball
                            Сообщ. #14 ,
                              Unregistered
                              зато большой разрядности ;D
                              MeG
                              Сообщ. #15 ,
                                Profi
                                *****
                                Профиль · PM
                                Поощрения: 1 Dgm
                                Рейтинг (т): 38
                                smile.gif
                                можно построить 'мое дерево' и для русских слов (или не русскихsmile.gif ) и глубину не фиксировать, но игра стоит свеч только если "скорость превыше всего"
                                Сообщение отредактировано: MeG -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (4) [1] 2 3 ... Последняя » все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0301 ]   [ 15 queries used ]   [ Generated: 26.04.24, 17:03 GMT ]  
                                Powered by Invision Power Board(U) v1.2 © 2003  IPS, Inc.