Язык программирования для представления алгоритмов

[D_KEY]

Цитата korvin @ 11.07.22, 11:49

Есть же всякие сайты с разными алгоритмами и их реализациями на разных языках. Смотри — сравнивай.

Так а холиварить-то как? Давайте сюда что-то притащим.

[Qraizer]

LZW. Дёшево и в меру сердито.

[Qraizer]

Ну и? Мне начинать, что ли?

[Majestio]

Цитата Qraizer @ 12.07.22, 12:43

Ну и? Мне начинать, что ли?

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

Добавлено 12.07.22, 14:28
Хотелось бы сравнить с Петоном Тьфу на него )))

[korvin]

Цитата Qraizer @ 12.07.22, 12:43

Ну и? Мне начинать, что ли?

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

[Majestio]

Цитата korvin @ 12.07.22, 17:48

Так что я не знаю, что тут можно сравнивать.

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

[korvin]

Цитата Majestio @ 12.07.22, 18:24

Ты просто Бейсика не видел, или Пасквиля

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

Цитата Majestio @ 12.07.22, 18:24

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

Бессмысленно.

[Majestio]

Скрытый текст

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

Цитата korvin @ 12.07.22, 18:25

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

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

Добавлено 12.07.22, 18:44

Цитата Qraizer @ 12.07.22, 12:43

Ну и? Мне начинать, что ли?

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

[applegame]

Цитата korvin @ 11.07.22, 11:49

Ага. Хорошо, что этого никто не предлагает.

Цитата korvin @ 09.07.22, 18:17

Scheme

[Majestio]

Цитата applegame @ 13.07.22, 05:32

Scheme

Тот же Брэйнфак, но только с помощью скобочек.

[Gonarh]

Цитата Majestio @ 09.07.22, 12:01

Perl и чистый Си

Сообщение отредактировано: Gonarh - 13.07.22, 08:11

[korvin]

applegame, Scheme не AST.

[Qraizer]

Цитата korvin @ 12.07.22, 17:48

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

Ну не я ж топик начал-то. Так-то и мне непонятно, чем таким кардинальным могут отличаться реализации одного алгоритма на разных языках, окромя внешнего вида. Кардинально может отличаться архитектура реализации, т.к. зависит от парадигм языка... и то не факт. А так-то, пиши, на чём тебе будет читать удобно.
Я тут случайно чуть архиватор не написал. Начал вот с такого:

кодер

/* 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();                            // сбросить битовый буфер в поток вывода
}

и потихонечку дописал к нему ( )

фреймворк

#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]);                // равном текущей ширине
}

Быстро, за вечер где-то. Или два, не помню. Но вот с декодером вышло далеко не так шоколадно. Поди отладься, когда непонятно, а кто, собстна, бажит. Понятно, что скорее всего оба, но... отлаживаться-то как?
В общем на вот это безобразие

декодер

/* 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;                                // новый код на следующем шаге становится предыдущим
  }
}

с собственным фреймворком ( )

он самый

#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 - 19.07.22, 03:33

[korvin]

Цитата Qraizer @ 19.07.22, 03:13

и потихонечку дописал к нему фреймворк

https://habr.com/ru/post/153225/

[Majestio]

Цитата korvin @ 19.07.22, 06:52

https://habr.com/ru/post/153225/

Как же долго я это безуспешно искал! Эту тему я когда-то видел в виде видосика.
Всегда ее вспоминаю, когда заходит речь о шаблонах проектирования.