На главную Наши проекты:
Журнал   ·   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] 4  все  ( Перейти к последнему сообщению )  
> Быстрый поиск
wormball
Сообщ. #31 ,
    Unregistered
    мерять надо! ведь n сравнений (особенно с cmpsb) и n переходов по ссылке - не одно и то же! похоже всётаки придётся написать qsort. только на с++е мне чото не хочется писать, да и в сети qsortов полно, и помнится в стандартной библиотеке qsort есь. остаётся написать только то, что должно быть после сортировки, т е собственно выбрасывание одинаковых строк. если не знаешь, как ето сделать без одалживания памяти - я тебе напишу, только надо будет знать, в каком формате строки.
    Visitor
    Сообщ. #32 ,

      Profi
      *****
      Профиль · PM
      Поощрения: 1 Dgm
      Рейтинг (т): 22
      А если весь массив со строками существенно больше, чем размер доступной оперативной памяти? У MeG метод более универсальный :)

      P.S. Еще можно вспомнить алгоритм сжатия LZW -- структуру словаря етого алгоритма :)
      wormball
      Сообщ. #33 ,
        Unregistered
        Цитата Visitor, 25.09.03, 18:45:05
        А если весь массив со строками существенно больше, чем размер доступной оперативной памяти? У MeG метод более универсальный :)

        вопервых если массив не умещается в память, то даже и думать нечего, а вовторых уменя насколько я понимаю меньше памяти тратится.
        Цитата Visitor, 25.09.03, 18:45:05
        P.S. Еще можно вспомнить алгоритм сжатия LZW -- структуру словаря етого алгоритма :)

        тыбы ещё рар предложил ;D
        Visitor
        Сообщ. #34 ,

          Profi
          *****
          Профиль · PM
          Поощрения: 1 Dgm
          Рейтинг (т): 22
          Вот RAR, с его алгоритмом LZ, как раз не подойдет :)

          А словарь-дерево из LZW или такое как у MeG, в случае слов естественного языка большим не будет. Вот представь себе такую задачу: некое собрание сочинений (например, Билиотека Мошкова) в електронном виде. Нужно из него сделать список всех форм всех имеющихся там слов русского языка. Читать слова придется из какого-то потока, а хранить словарь можно и в памяти.

          Хотя я бы, в етом случае, хранил слова просто в балансированном двоичном дереве. :)
          Сообщение отредактировано: Visitor -
          Guru Jin X
          Сообщ. #35 ,

            Законченный оптимист
            *******
            Профиль · PM
            Поощрения: 23 Dgm
            Рейтинг (т): 118
            В LZW происходит то же самое: сравнение слова со всеми словами из словаря. К тому же, я что-то не совсем понимаю, какое LZW имеет отношение к делу.

            2 wormball: qsort, создание дерева и т.п. нужно использовать только 1 раз, в самом начале. Так что, если qsort будет быстрее создания дерева, а двоичный поиск медленнее создания дерева (а мне почему-то кажется, что именно так и будет), то что быстрее - нужно рассчитывать уже по кол-ву поисков.
            wormball
            Сообщ. #36 ,
              Unregistered
              Цитата Jin X, 26.09.03, 23:37:42
              Так что, если qsort будет быстрее создания дерева, а двоичный поиск медленнее создания дерева (а мне почему-то кажется, что именно так и будет), то что быстрее - нужно рассчитывать уже по кол-ву поисков.

              ещё раз объясняю: двоичного поиска не будет! после сортировки надо будет за линейное время сравнивать слова с идущими за ними словами.
              Guru Jin X
              Сообщ. #37 ,

                Законченный оптимист
                *******
                Профиль · PM
                Поощрения: 23 Dgm
                Рейтинг (т): 118
                Да, точно... прогон :)
                Но тогда при поиске (не совпадений, а просто слова) будет :)
                MeG
                Сообщ. #38 ,
                  Profi
                  *****
                  Профиль · PM
                  Поощрения: 1 Dgm
                  Рейтинг (т): 38
                  подведем итоги обсужденияsmile.gif

                  предложенные методы поиска и удаления дубликатов:
                  • сортировка + двоичный поиск
                  • MeGTree smile.gif
                  • хеш-функция
                  • балансированное двоичное дерево
                  • прямой перебор

                  Предлагаю сравнить все эти методы живьем. Смысл? Оценить предложенные методы с различных сторон.
                  Требования к реализации достаточно свободные, любой язык, любые библиотеки. В общем, можно использовать все что вам доступно и удобно, в том числе готовые решения.

                  Проверяем на одном словаре.

                  Оцениваем:
                  • объем памяти занимаемый данными (в готовом к поиску состоянии)
                  • время подготовки структуры словаря к работе (исходный словарь берем из файла)
                  • время поиска заданного набора слов
                  • время уничтожения структуры словаря в памяти
                  и еще личная оценка сложности, универсальности ...


                  Jin X, wormball, Demo_S, Visitor прошу участвовать
                  Сообщение отредактировано: MeG -
                  wormball
                  Сообщ. #39 ,
                    Unregistered
                    как всё сложно ;D
                    MeG
                    Сообщ. #40 ,
                      Profi
                      *****
                      Профиль · PM
                      Поощрения: 1 Dgm
                      Рейтинг (т): 38
                      я грубо ошибся при оринтировочной оценке требуемого количества узлов  в моем дереве для словаря, размер намного больше.
                      если кому нужен исходник, вышлю
                      Sazabis
                      Сообщ. #41 ,

                        Master
                        ******
                        Профиль · PM
                        Поощрения: 9 Dgm
                        Рейтинг (т): 122
                        если всеравно что использовать, может попробуешь Perl, у него единица языка - слово. Для определения одинаковых слов очень подходит.
                        Производительность высокая, можешь сравнить со своей производительностью, результаты были бы интересны rolleyes.gif

                        пишется на перле для такого дела всего несколько строчек smile.gif
                        Visitor
                        Сообщ. #42 ,

                          Profi
                          *****
                          Профиль · PM
                          Поощрения: 1 Dgm
                          Рейтинг (т): 22
                          Ну вот ориентировочные результаты: с помощью обычного (не балансированного) двоичного дерева из 100M текстов RFCxxxx словарь (слова состоящие из символов, у которых isalpha != 0) строится 17 сек на PIII-700 smile.gif
                          Sazabis
                          Сообщ. #43 ,

                            Master
                            ******
                            Профиль · PM
                            Поощрения: 9 Dgm
                            Рейтинг (т): 122
                            CODE
                            #!/usr/bin/perl

                            use CGI       qw (:standard);              
                            $table = $ARGV[0];


                            %seen_kwords = ();
                            @uniq_kwords = ();

                            $filename = $table . ".txt";

                            open( FILE, "$filename" );


                            $time = localtime;
                            print $time . "\n\r";
                            while( <FILE> ){
                             foreach( split( / / ) ){
                               push(@uniq_kwords, $_) unless $seen_kwords{ $_ }++;
                             }
                            }
                            $time = localtime;
                            print $time . "\n\r";
                            close( FILE );

                            $filename = $table . ".ukw";
                            open(FILE, "+>$filename");
                            foreach( @uniq_kwords ){
                             print FILE $seen_kwords{ $_ } . " - " . $_ . "\n\r";
                            }
                            close(FILE);


                            код на Perl, без какой либо оптимизации правда, читает прямо из файла smile.gif файл - текстовый - слова с пробелами. Слово это то, что ограничено пробелами или концом-началом строки.

                            CODE
                            while( <FILE> ){
                             foreach( split( / / ) ){
                               push(@uniq_kwords, $_) unless $seen_kwords{ $_ }++;
                             }
                            }


                            Это собственно вся сортировка wink.gif
                            если бы каждое слово было на новой строчке было еще быстрей. А так как видно еще перебор каждой строки происходит.

                            2Visitor
                            сравните, будет, конечно, не 17 сек, но результат интересен.

                            запускается как perl название_скрипта файл_для_сортировки_без_расширения

                            входной файл подразумевается .txt
                            Visitor
                            Сообщ. #44 ,

                              Profi
                              *****
                              Профиль · PM
                              Поощрения: 1 Dgm
                              Рейтинг (т): 22
                              rfcs.txt: 107 857 600 bytes
                              CODE
                              Mon Nov 10 13:50:24 2003
                              Mon Nov 10 13:52:40 2003

                              Тоже недолго...

                              Вот только памяти он почему-то 120M сожрал в прцессе выполнения???
                              Сообщение отредактировано: Visitor -
                              Sazabis
                              Сообщ. #45 ,

                                Master
                                ******
                                Профиль · PM
                                Поощрения: 9 Dgm
                                Рейтинг (т): 122
                                Да smile.gif память он любит, я тоже заметил.

                                2.16 неплохо, если память под массивы выделить сразу на все эл-ты, и сделать так, что слово есть 1 строчка. Можно будет еще время выграть, но это уже для фанатов.
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (4) 1 2 [3] 4  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0.1118 ]   [ 14 queries used ]   [ Generated: 23.10.26, 08:57 GMT ]  
                                Powered by Invision Power Board(U) v1.2 © 2003  IPS, Inc.