На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Правила раздела:
1. Название темы - краткое описание кто/что против кого/чего
2. В первом сообщении - список параметров, по которым идет сравнение.
3. Старайтесь аргументировать свои высказывания. Фразы типа "Венда/Слюникс - ацтой" считаются флудом.
4. Давайте жить дружно и не доводить обсуждение до маразма и личных оскорблений.
Модераторы: Модераторы, Комодераторы
Страницы: (4) 1 [2] 3 4  все  ( Перейти к последнему сообщению )  
> Язык программирования для представления алгоритмов
    Цитата korvin @
    Есть же всякие сайты с разными алгоритмами и их реализациями на разных языках. Смотри — сравнивай.

    Так а холиварить-то как? Давайте сюда что-то притащим.
      LZW. Дёшево и в меру сердито.
        Ну и? Мне начинать, что ли?
          Цитата Qraizer @
          Ну и? Мне начинать, что ли?

          Было бы неплохо :rolleyes:

          Добавлено
          Хотелось бы сравнить с Петоном :whistle: Тьфу на него )))
            Цитата Qraizer @
            Ну и? Мне начинать, что ли?

            Конечно! Инициатива наказуемапоощряема. Мне лично не очень интересны байто-бито-дрочерские вещи, и судя по описанию в вике, какой-то заметной разницы между языками тут не будет. Как и во многих алгоритмах. Во всяком случае, навскидку, я не вижу здесь точки отличий. Так что я не знаю, что тут можно сравнивать.
              Цитата korvin @
              Так что я не знаю, что тут можно сравнивать.

              Ты просто Бейсика не видел, или Пасквиля ... с их излишествами в синтаксисе.
              А лутше ознакомься с синтаксисом PL/1. Просто чтобы ознакомится с глубинами ихних глубин.
                Цитата Majestio @
                Ты просто Бейсика не видел, или Пасквиля

                С чего ты это взял?

                Цитата Majestio @
                А лутше ознакомься с синтаксисом PL/1

                Бессмысленно.
                  Скрытый текст
                  Не, про Пасквиля я мало чего могу сказать плохого - хорошо продуманный язык. Если не брать учебу, а именно практическое программирование, я с него начинал. Вспоминания только хорошие. Особенно впечатляла скорость сборки. Речь идет о Turbo Pascal 5.0/5.5 и какого-то установленного сбоку Microsoft C (версии не помню). Все это было на нативном компе IBM 8086 с 512Kb оперативной памяти... Но потом слишком "многосимвольный" синтаксис задостал. И пришлось уходить на Perl, параллельно на Си. А вот про PL/1 скажу только плохое - пришлось его выучить только для того, чтобы в институте получить "отлично" по прикладному программированию. Перфокарты, шоколадки операторшам, ацкий ад.


                  Цитата korvin @
                  С чего ты это взял?

                  Вообще-то это сарказм был :-?

                  Добавлено
                  Цитата Qraizer @
                  Ну и? Мне начинать, что ли?

                  Кстати ... есть тема. Я как-то в "Алгоритмах" предлагал интересный линк. Зацени тему!
                  Если тебя это зацепит, и ты сможешь это отразить изящно-алоритмически, твой опыт будет просто бесценен!!! Я серьёзно, без стеба!
                    Цитата korvin @
                    Ага. Хорошо, что этого никто не предлагает.

                    Цитата korvin @
                    Scheme
                      Цитата applegame @
                      Scheme

                      Тот же Брэйнфак, но только с помощью скобочек.
                        Цитата Majestio @
                        Perl и чистый Си

                        :wub:
                        Сообщение отредактировано: Gonarh -
                          applegame, Scheme не AST.
                            Цитата korvin @
                            Мне лично не очень интересны байто-бито-дрочерские вещи, и судя по описанию в вике, какой-то заметной разницы между языками тут не будет. Как и во многих алгоритмах. Во всяком случае, навскидку, я не вижу здесь точки отличий. Так что я не знаю, что тут можно сравнивать.
                            Ну не я ж топик начал-то. Так-то и мне непонятно, чем таким кардинальным могут отличаться реализации одного алгоритма на разных языках, окромя внешнего вида. Кардинально может отличаться архитектура реализации, т.к. зависит от парадигм языка... и то не факт. А так-то, пиши, на чём тебе будет читать удобно.
                            Я тут случайно чуть архиватор не написал. Начал вот с такого:
                            кодер
                            ExpandedWrap disabled
                              /* LZW кодирование
                                 стартовая ширина кодирования 9 бит, максимальная 16 */
                              int main()
                              {
                                std::string   buffer;
                                char          ch;
                                std::ifstream inFile ("in.txt", std::ios::binary);
                                std::ofstream outFile("out.txt",std::ios::binary);
                                Bits          bitBuffer(outFile);
                                // лямбда чтения очередного кода
                                auto getCh = [&inFile]{
                                                        char ch;
                               
                                                        inFile.read(&ch, 1);
                                                        return ch;
                                                      };
                               
                                initDict();
                                ch = getCh();                                 // прочитать первый символ
                                if (inFile.good()) buffer = ch;               // и запомнить как текущую цепочку
                                while (inFile.good())
                                {
                                  ch = getCh();                               // прочитать следующий символ
                                  if (inFile.gcount() == 0) continue;         // конец потока или ошибка чтения
                                  if (lastCode == curDictSize-1)              // если очередной код достиг предельного значения,
                                  {                                           // следующий код должен быть на бит длиннее
                                    if (lastCode == dictSize-1)               //   если только он не максимальный,
                                    {
                                      toOut(bitBuffer, dict[buffer]);         //   тогда вывести код текущей цепочки,
                                      toOut(bitBuffer, reset);                //   вывести код сброса словаря,
                                      initDict();                             //   переинициализировать
                                      buffer = ch;                            //   и запомнить текущий символ как текущую цепочку
                                      continue;
                                    }
                                    else ++curDictBit, curDictSize *= 2;      //   иначе просто расширить характристики кодирования
                                  }
                               
                                  std::string newBuf = buffer + ch;           // новая цепочка
                                  auto        token  = dict.find(newBuf);     // попытаться найти в словаре код для неё
                               
                                  if (token != dict.end())                    // если нашли,
                                  {
                                    buffer = newBuf;                          // то просто запомнить новую цепочку как текущую
                                    continue;
                                  }
                                  toOut(bitBuffer, dict[buffer]);             // иначе вывести код текущей цепочки,
                                  dict[newBuf] = from_ulong(++lastCode);      // дополнить словарь кодом для новой
                                  buffer = ch;                                // и запомнить текущий символ как текущую цепочку
                                }
                                // финализация кодирования
                                toOut(bitBuffer, dict[buffer]);               // вывести код для текущей цепочки
                                toOut(bitBuffer, end);                        // вывести код конца потока
                                bitBuffer.flush();                            // сбросить битовый буфер в поток вывода
                              }
                            и потихонечку дописал к нему ( :jokingly: )
                            фреймворк
                            ExpandedWrap disabled
                              #include <map>
                              #include <bitset>
                              #include <string>
                              #include <fstream>
                              #include <cmath>
                              #include <limits>
                               
                              // максимальная ширина элементов словаря в битах
                              const unsigned dictBit = 16;
                              // максимальный размер словаря
                              const unsigned dictSize= std::pow(2, dictBit);
                               
                              // тип битового набора
                              using bitset = std::bitset<dictBit>;
                               
                              // текущие битность и размер словаря и последний использованный в нём код
                              unsigned curDictBit;
                              unsigned curDictSize;
                              unsigned lastCode;
                              // символы окончания потока и сброса словаря
                              bitset end;
                              bitset reset;
                              // словарь[строка символов] = битовый набор
                              std::map<std::string, bitset> dict;
                               
                              /* преобразовать код в битовый набор */
                              bitset from_ulong(unsigned long val)
                              {
                                return bitset(val);
                              }
                               
                              /* преобразовать битовый набор в код */
                              unsigned long to_ulong(const bitset& buf)
                              {
                                return buf.to_ulong();
                              }
                               
                              /* инициализация словаря и рабочих характеристик кодирования символов */
                              void initDict()
                              {
                                int i;
                               
                                curDictBit = 9;                               // стартовая ширина кода
                                curDictSize= std::pow(2, curDictBit);         // стартовый размер словаря
                               
                                // заполнить словарь базовыми кодами
                                dict.clear();
                                for (i = 0; i <= std::numeric_limits<unsigned char>::max(); ++i)
                                  dict[std::string(1, static_cast<char>(i))] = from_ulong(i);
                                // добавить два спец.кода
                                end  = from_ulong(++i);
                                reset= from_ulong(++i);
                                // последний использованный код
                                lastCode = to_ulong(reset);
                              }
                               
                              // прокси-класс для битового вывода в байтовый поток
                              template <typename Ch, typename Tr>
                              struct Bits
                              {
                                using os_type = std::basic_ostream<Ch, Tr>;
                               
                                static constexpr size_t charBits = std::numeric_limits<Ch>::digits +
                                                                   std::numeric_limits<Ch>::is_signed;
                                std::bitset<charBits> bufChar;        // буфер ввода
                                size_t                curBit;         // текущая позиция бита в буфере
                                os_type              &os;
                               
                                /* переполнение буфера: вывести в поток */
                                void overflow()
                                {
                                  Ch ch = Tr::to_char_type(bufChar.to_ulong());
                               
                                  os.write(&ch, sizeof(ch));          // ошибки вывода остаются на совести вызывающей стороны; тут
                                  curBit = 0;                         // всё равно неизвестно, что делать, а там проверить os::good()
                                }                                     // ничего не стоит, та и исключения никто не отменял
                               
                                Bits(const Bits&)            = delete;
                                Bits(Bits&&)                 = default;
                                Bits& operator=(const Bits&) = delete;
                                Bits& operator=(Bits&&)      = default;
                               
                              public:
                                explicit Bits(os_type &osRef): bufChar(), curBit(0), os(osRef) {}
                               
                                /* вывести бит
                                   ошибки потока не обрабатываются: базовая гарантия */
                                void outBit(bool b)
                                {
                                  bufChar[curBit++] = b;
                                  if (curBit == bufChar.size()) overflow();
                                }
                                /* сбросить буфер досрочно
                                   недозаписанные в буфере биты неопределены */
                                void flush() { overflow(); }
                              };
                               
                              /* функция вывода очередного кода, шириной curDictBit, в поток */
                              template <typename Ch, typename Tr>
                              void toOut(Bits<Ch, Tr> &bos, const bitset& bits)
                              {
                                for (int i = 0; i < curDictBit; ++i)  // записать младшие биты битового набора в количестве,
                                  bos.outBit(bits[i]);                // равном текущей ширине
                              }
                            Быстро, за вечер где-то. Или два, не помню. Но вот с декодером вышло далеко не так шоколадно. Поди отладься, когда непонятно, а кто, собстна, бажит. Понятно, что скорее всего оба, но... отлаживаться-то как?
                            В общем на вот это безобразие
                            декодер
                            ExpandedWrap disabled
                              /* LZW декодирование
                                 стартовая ширина кодирования 9 бит, максимальная 16 */
                              int main()
                              {
                                std::ifstream inFile ("out.txt", std::ios::binary);
                                std::ofstream outFile("res.txt", std::ios::binary);
                                Bits          bitBuffer(inFile);
                               
                                std::string buffer;                           // ранее декодированный код
                                bitset      ch;                               // ранее прочитанный код (пока пуст)
                                // лямбда инициализации процесса декодирования
                                auto start = [&]{                             // кто сказал, что в Плюсах нет локальных функций?
                                                  initDict();
                                                  ch = fromIn(bitBuffer);     // прочитать первый код для декодирования
                                                  if (inFile.good())
                                                  {
                                                    buffer = dict[ch];        // декодировать (первый код всегда будет найден)
                                                    outFile << buffer;        // и вывести
                                                  }
                                                };
                               
                                // инициализировать словарь, прочить первый код, декодировать его и вывести
                                start();
                                while (inFile.good())
                                {
                                  bitset nextCh = fromIn(bitBuffer);          // прочитать следующий код
                               
                                  if (!inFile.good()) continue;               // конец потока или ошибка чтения
                                  if (nextCh == end)  break;                  // если символ конца потока кодов, всё
                                  if (nextCh == reset)                        // если символ сброса словаря, переинициализация
                                  {
                                    start();
                                    continue;
                                  }
                               
                                  auto        token = dict.find(nextCh);      // попытаться найти код в словаре
                                  std::string decCh = dict[ch];               // декодированный код предыдущего кода (всегда будет найден)
                                  std::string newBuf;                         // декодированный код нового символа
                               
                                  if (token != dict.end())                    // если новый код найден,
                                  {                                           // то его декодированный код определяется содержимым
                                    newBuf = decCh + token->second.front();   // словаря, осталось его только вывести и сформировать
                                    outFile << token->second;                 // его декодированный код, как это делало кодирование
                                  }
                                  else                                        // а если не найден (декодирование отстаёт на один
                                  {                                           // код от кодирования, поэтому иногда такое происходит),
                                    newBuf = decCh + decCh[0];                // то его декодированый код однозначно определяется
                                    outFile << newBuf;                        // алгоритмом кодирования, просто следуем ему
                                  }
                                  dict[from_ulong(++lastCode)] = newBuf;      // пополнить словарь новым кодом
                                  /* если до конца кодов словаря у нас осталось два символа, то у кодера уже один, т.к. декодер
                                     отстаёт от него на шаг, поэтому следующий символ уже будет закодирован кодом с шириной на бит
                                     больше, но не при максимальном размере: в этом случае ожидается символ сброса той же ширины */
                                  if (lastCode == curDictSize-2 && curDictBit != dictBit)
                                    ++curDictBit, curDictSize *= 2;           // расширяем рабочие характеристики кодирования
                                  ch = nextCh;                                // новый код на следующем шаге становится предыдущим
                                }
                              }
                            с собственным фреймворком ( :lol: )
                            он самый
                            ExpandedWrap disabled
                              #include <map>
                              #include <bitset>
                              #include <string>
                              #include <cmath>
                              #include <fstream>
                              #include <limits>
                               
                              // максимальная ширина элементов словаря в битах
                              const unsigned dictBit = 16;
                              // максимальный размер словаря
                              const unsigned dictSize= std::pow(2, dictBit);
                               
                              // тип битового набора
                              using bitset = std::bitset<dictBit>;
                               
                              // текущие битность и размер словаря и последний использованный в нём код
                              unsigned curDictBit;
                              unsigned curDictSize;
                              unsigned lastCode;
                              // символы окончания потока и сброса словаря
                              bitset end;
                              bitset reset;
                              // словарь[битовый набор] = строка символов
                              auto comp = [](const bitset& l, const bitset& r) { return l.to_ulong() < r.to_ulong(); };
                              std::map<bitset, std::string, decltype(comp)> dict(comp);
                               
                              /* преобразовать код в битовый набор */
                              bitset from_ulong(unsigned long val)
                              {
                                return bitset(val);
                              }
                               
                              /* преобразовать битовый набор в код */
                              unsigned long to_ulong(const bitset& buf)
                              {
                                return buf.to_ulong();
                              }
                               
                              /* инициализация словаря и рабочих характеристик кодирования символов */
                              void initDict()
                              {
                                int i;
                               
                                curDictBit = 9;                               // стартовая ширина кода
                                curDictSize= std::pow(2, curDictBit);         // стартовый размер словаря
                               
                                // заполнить словарь базовыми кодами
                                dict.clear();
                                for (i = 0; i <= std::numeric_limits<unsigned char>::max(); ++i)
                                  dict[from_ulong(i)] = std::string(1, static_cast<char>(i));
                                // добавить два спец.кода
                                end  = from_ulong(++i);
                                reset= from_ulong(++i);
                                // последний использованный код
                                lastCode = to_ulong(reset);
                              }
                               
                              // прокси-класс для битового ввода из байтового потока
                              template <typename Ch, typename Tr>
                              struct Bits
                              {
                                using is_type = std::basic_istream<Ch, Tr>;
                               
                                static constexpr size_t charBits = std::numeric_limits<Ch>::digits +
                                                                   std::numeric_limits<Ch>::is_signed;
                                std::bitset<charBits> bufChar;        // буфер ввода
                                size_t                curBit;         // текущая позиция бита в буфере
                                is_type              &is;
                               
                                /* опустошение буфера: ввести из потока */
                                void underflow()
                                {
                                  Ch ch;
                               
                                  is.read(&ch, sizeof(ch));           // ошибки ввода остаются на совести вызывающей стороны; тут
                                  curBit = bufChar.size();            // всё равно неизвестно, что делать, а там проверить is::good()
                                  bufChar= Tr::to_int_type(ch);       // ничего не стоит, та и исключения никто не отменял
                                }
                               
                                Bits(const Bits&)            = delete;
                                Bits(Bits&&)                 = default;
                                Bits& operator=(const Bits&) = delete;
                                Bits& operator=(Bits&&)      = default;
                               
                              public:
                                explicit Bits(is_type &isRef): bufChar(), curBit(0), is(isRef) {}
                               
                                /* ввести бит
                                   ошибки потока не обрабатываются: базовая гарантия */
                                bool inBit()
                                {
                                  if (curBit == 0) underflow();
                                  return bufChar[bufChar.size() - curBit--];
                                }
                              };
                               
                              /* функция ввода очередного кода, шириной curDictBit, из потока */
                              template <typename Ch, typename Tr>
                              bitset fromIn(Bits<Ch, Tr> &bis)
                              {
                                bitset bits;
                               
                                for (int i = 0; i < curDictBit; ++i)  // читать битовый набор текущей ширины, старшие биты сброшены
                                  bits[i] = bis.inBit();
                                return bits;
                              }
                            я чуть не забил. Зато когда-таки отладился, такие планы наполеоновские попёрли... включая параметризирование битовых границ словаря.
                            В общем, берите это, а то не остановлюсь. Вам будет проще, алгоритм надо будет просто перевести, а не реализовывать.
                            Сообщение отредактировано: Qraizer -
                              Цитата Qraizer @
                              и потихонечку дописал к нему фреймворк

                              https://habr.com/ru/post/153225/
                                Цитата korvin @

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


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0478 ]   [ 14 queries used ]   [ Generated: 14.08.22, 10:04 GMT ]