declarative
Dec. 25th, 2012 01:34 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonПериодически встречаю словосочетание "декларативное программирование", которое противопоставляют императивному, сопровождая формулой "описывается, что должно быть получено, а не как оно должно быть получено". Известный пример декларативного языка - SQL. Еще к декларативщине частенько относят хаскель и другие ФЯ, но вот с ними проблема: сколько кода я на них видел, (практически) везде было явное описание процесса вычисления, т.е. код был все же императивным по сути (создать список такой-то, свернуть его так-то, построить дерево такое-то и т.д. - это все про "как"). Вопрос к залу: покажите максимально декларативное решение (на любом языке, в том числе еще не существующем и чисто гипотетическом) следующей задачи.
Есть последовательность байтов (фиксированный массив/список или потенциально бесконечный поток - на ваш выбор), нужно их сжать RLE методом по мотивам формата PCX: в выходном потоке байт Х <= 192 обозначает сам себя, а байт Х > 192 означает Х-192 повторений следующего за ним байта. Т.е. последовательность
1, 1, 2, 3, 2, 2, 2, 200, 0, 200, 200, 200, 200
должна превращаться в
194, 1, 2, 3, 195, 2, 193, 200, 0, 196, 200
Есть последовательность байтов (фиксированный массив/список или потенциально бесконечный поток - на ваш выбор), нужно их сжать RLE методом по мотивам формата PCX: в выходном потоке байт Х <= 192 обозначает сам себя, а байт Х > 192 означает Х-192 повторений следующего за ним байта. Т.е. последовательность
1, 1, 2, 3, 2, 2, 2, 200, 0, 200, 200, 200, 200
должна превращаться в
194, 1, 2, 3, 195, 2, 193, 200, 0, 196, 200
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-01-04 10:22 am (UTC)Неэффективно, но должно работать, вроде бы. Можно для незваисимых тестов использовать.
Будет время - набросаю в коде, на словах не очень понятно, наверное.
no subject
Date: 2013-01-04 02:19 pm (UTC)Сжатие касается только цепочек одинаковых байт. Значит, можно рассматривать цепочки одинаковых байт по отдельности. Цепочка 2..63 байта минимально записывается 2 байтами; если ваш алгоритм так и делает, значит, он генерирует минимальное представление.
Цепочка 65..126 байт всегда записывается 4 байтами. Главное, не делать глупостей, вроде записывать любые 64 байта с помощью 4 байт: если ваш алгоритм умеет записывать 64 байта X <= 192 с помощью 3 байт, значит, он генерирует минимальное представление.
Далее по индукции показываем, что представление 63+n байт равно 2+(представление n байт). Отсюда вытекает рекурсия и одно минимальное представление. Поскольку оно уже минимально, незачем хранить N решений в надежде найти ещё лучшее.
no subject
Date: 2013-01-04 03:57 pm (UTC)no subject
Date: 2013-01-04 07:39 pm (UTC)Пусть нам нужно найти Y <- f(X), если у нас есть функция g, такая что x <- g(Y). Здесь X и Y - последовательнсти байт.
Предположим что X = '0123456789'.
Предположим, что g('a') = '0123', g('0') = '0'.
Если бы рассматривать только greedy solutions, мы должны однозначно выбрать 'a' как первый байт выхода. Но может оказаться, что единственным решением, которое начинается с 'a', будет 'a456789'. В то время как другим решением может быть '0c' (то есть 'c' преодбразуется в '123456789'). Более того, решения, которое начинается с 'a', может вообще не существовать.
То есть нужен какой-то backtracking, или какой-то другой поиск решения.
Beam search не универсален, но удобен при работе с потоками - например, не нем так имплементированы многие известные алгоритмы OCR и speech recognition.
no subject
Date: 2013-01-04 03:55 pm (UTC)no subject
Date: 2013-01-04 07:44 pm (UTC)