samolevich / test-labsystech

test-labsystech

Task

Есть множество (массив, где порядок не важен) целых чисел в диапазоне от 1 до 300.
Количество чисел - до 1000. Напишите функцию сериализации / десериализации в строку, чтобы итоговая строка была компактной.
Цель задачи - максимально сжать данные относительно простой сериализации без алгоритма сжатия (хотя бы 50% в среднем).
Сериализованная строка должна содержать только ASCII символы. Можно использовать любой язык программирования.
Вместе с решением нужно прислать набор тестов - исходная строка, сжатая строка, коэффициент сжатия.
Примеры тестов: простейшие короткие, случайные - 50 чисел, 100 чисел, 500 чисел, 1000 чисел, граничные - все числа 1 знака, все числа из 2х знаков, все числа из 3х знаков, каждого числа по 3 - всего чисел 900.

Solution descrition

Запуск файла через NodeJS node [path]/zip.js В консоль выведет результат.

Суть решения:

Способы сократить запись.

• Числа из десятичной системы переводятся в систему более высокой разрядности. В моём случае в 91-ричную систему счисления. Ограничился ASCII символами.
• Числа идущие по порядку (1,2,3,4) записываются в виде 1-4.
• Повторяющиеся числа записываются в виде num * count

Вывод:

Алгоритм работает тем лучше

• числа большие (10+)
• числа идут подряд (n, n+1...)
• числа повторяются

Работает не так эффективно, если

• числа меньше 10
• числа максимально разрознены
• нет повторений

---

seedSet

Функция принимает три аргумента (числа), возращает строку со случайными числами в диапазоне через запятую.

• from - начало диапазона чисел включительно
• to - конец диапазона чисел не включительно
• len - количестве чисел в строке

notationSystem

Функция по сути являет собой систему счисления, в которой будут кодироваться данные. Изспользуются ряд символо ASCII, начиная с 35 символа и заканчивая 125.

#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}

Возвращает массив из двух значений

• строку с знаками, которыми будут заменяться числа
• длину строки - разрядность системы счисления

convertDec

Принимает число в десятичной системе счисления.
Возвращает строку в новой системе счисления.
Засчёт увеличенной разрядности используется меньше чисел для записи.
Среднее значение сжатия, используя лишь этот метод записи - ~70%.

serialize

Функция принимает и возвращает строку.

• Поскольку в задании указано, что на даётся множество где порядок не важен, то первым делом числа упорядочиваются по возрастанию.
• Повторяющиеся числа считаются.
• Числа идущие по порядку записываются в виде от-до
• Переводятся в 91-ричную систему счисления.
• Собираются в строку.

В консоль выводится

• строка, которая пришла изначально.
• строка, которая получилась в результате
• степень сжатия (соотношение длин полученной и результативной строк)

deSerialize

Получает и возвращает строку. Разматывает в обратном порядке алгоритм.

---

Несколько тестов работы.

• простейшие короткие
• случайные
  • 50 чисел
  • 100 чисел
  • 500 чисел
  • 1000 чисел
• граничные
  • все числа 1 знака
  • все числа из 2х знаков
  • все числа из 3х знаков
  • каждого числа по 3 - всего чисел 900