Всякий знает, что вычисление чисел Фибоначчи - важнейшая задача программирования, поэтому именно с нее нередко начинают обучение. Некоторые языки программирования, похоже, были созданы специально для решения этой задачи (prooflink). Однако не все еще нашли применение этим чудесным числам в быту.

Понадобилось мне тут недавно уметь компактно представить набор целых чисел: при проверке на наличие новых версий а также при деинсталляции программа передает на сервер номер своей версии, а заодно кое-какую статистику, вроде числа запусков, количества дней с момента установки и т.п. Передавать нужно GET'ом, ибо при деинсталляции это делает не сама программа, а скрипт установщика, к тому же хочется сразу иметь эти данные в логах апача. Чисел получилось много, в явном виде запрос получился бы сильно длинным и некрасивым. Решил применить какое-нибудь простое сжатие.

Числа все неотрицательные, сверху не ограниченные, и вероятность встречи числа быстро уменьшается с ростом самого числа. Для таких данных есть семейство кодов переменной длины, называемое универсальными кодами. Большинство из них сначала кодируют некоторым образом число битов (например, унарно), а затем сами биты кодируемого числа. Но длина таких кодов растет довольно быстро. Зато есть более интересный и для нужных мне значений более эффективный способ представления - коды Фибоначчи. Они основаны на теореме одного зубного врача из бельгийской армии, которая говорит, что всякое натуральное число можно уникальным образом представить в виде суммы чисел Фибоначчи, причем в такой сумме никогда не будет двух последовательных членов ряда. Ряд начинается так: 1, 2, 3, 5, 8, 13, 21... Тогда 6 = 1+5, 15 = 2+13, 31 = 2+8+21. Чтобы закодировать число последовательностью битов, достаточно пройтись по ряду Фибоначчи до требуемого числа и проставить единицы напротив входящих в сумму членов и нули напротив невходящих. Поскольку по построению у нас не может быть подряд двух единиц, этот факт используется для маркировки конца числа: после последней единицы ставим еще одну и код готов, длину числа хранить нигде не надо. Примеры:

Fib: 1 2 3 5 8 13 21 34  | Code
  1: *                   | 11
  2:   *                 | 011
  3:     *               | 0011
  4: *   *               | 1011
 10:   *     *           | 010011
 16:     *      *        | 0010011
 42:         *        *  | 000010011

В итоге у меня требуемый набор чисел превращается в такую битовую последовательность, которая затем кодируется по пять цифрами и буквами в Base32. Получается обычно по 12-15 символов на 24 исходных инта.

А вот и сам автор теоремы - полковник Эдуард Цекендорф:

Недавно обнаружил в своей программе, что при отображении в окошке текущего обрабатываемого видео иногда цвета не совсем такие, как надо. Это было видно, если исходное видео в формате YV12, а в процессе преобразуется в RGB32. Причем в получающемся файле все нормально, проблема только в отображении на экране в процессе. И на многих видео проблема была не заметна, а заметна лишь чуть-чуть на некоторых видеофайлах. Стал разбираться, и выяснилось, что в коде преобразования цветов из цветового пространства YUV в RGB было две грубых ошибки: сначала перепутаны местами цветовые плоскости U и V, а потом перепутаны позиции красного и синего цветов в четверке RGBA. В результате две этих ошибки друг друга почти компенсировали:



Слева - что получалось при таком двойном путании компонент, а справа - правильная картинка.

Про сравнение флоатов:


Из резюме кандидата:
Language: English, Thai, Hindi, Punjabi
Application: Microsoft Words, Excel, Power Point, Adopt Photoshop

Давно хотел предложить общественности порешать такую вот задачку и собрать свежую статистику по языкам.





Дана такая таблица соответствий букв и цифр:

E | J N Q | R W X | D S Y | F T | A M | C I V | B K U | L O P | G H Z
e | j n q | r w x | d s y | f t | a m | c i v | b k u | l o p | g h z
0 |   1   |   2   |   3   |  4  |  5  |   6   |   7   |   8   |   9

Мы хотим использовать ее для записи телефонных номеров словами, чтобы их проще было запоминать.

Функциональные требования

Ваша задача состоит в написании программы, которая для заданного телефонного номера находит все возможные его записи словами и выводит их. Телефонный номер - это произвольная(!) строка из цифр, дефисов (-) и слэшей (/). Дефисы и слэши при переводе в слова не кодируются. Все слова берутся из словаря, который дан в отсортированном по алфавиту ASCII файле (одно слово на строку).
( Read more...Collapse )

Один добрый человек поделился архивами, в которых имена файлов были на русском в кодировке UTF-8, что в его ОС в порядке вещей. Когда открываю их своим старым винраром, имена превращаются в мусор типа "01 ¦Э¦-TБTВTА¦-¦¬¦Ж¦¦¦- ¦¬¦-TГ¦¦¦-". Если же распаковываю 7-zip'ом, то гораздо лучше: "01 ╨Э╨░╤Б╤В╤А╨╛╨╕╠Ж╨║╨░ ╨╖╨▓╤Г╨║╨░". В 7-zip есть замечательная опция для задания кодировки, вот только она не работает - что с ней, что без нее получается совершенно одинаково. Решил поискать решение в инете, но мое гугл-фу оказалось недостаточно хорошим. Скачал пару утилит. Первая - какая-то суперпрограмма с описанием на чешском, в которой можно загрузить список файлов и нажать Ок, после чего ровным счетом ничего не происходит. Вторая - сурьезный ренеймер за 50 баксов, умеющий делать с именами файлов абсолютно все кроме того, что мне нужно.
Тогда я решил сделать все сам, в результате получилась такая штука на F#:

#light 
open System.IO 
open System.Text 
 
let conv s = 
  let u16 = Encoding.Unicode 
  let bytes = Encoding.Convert(u16, Encoding.GetEncoding(866), u16.GetBytes(s:string)) 
  Encoding.Convert(Encoding.UTF8, u16, bytes) |> u16.GetString  
   
Directory.GetFiles(".") |> Seq.iter (fun fname -> File.Move(fname, conv fname)) 

Смысл процесса в том, что когда архиватор распаковывает файлы, имя в UTF-8 он считает набором 8-битных символов в текущей кодировке (cp866). Винда же имена файлов хранит в 16-битном юникоде. Программа из юникода получает обратно исходную последовательность байт, трактует ее как UTF-8 и из него уже конвертит в привычный двухбайтный юникод.

Бинарник (4096 байт) можно взять тут.
Это мой самый первый опыт с F#, языка я еще не знаю, наверняка можно сделать лучше.

Отдельный прикол с буквой "й". Похоже, в какой-то из юникодных кодировок она представлена не одной буквой "й", а буквой "и" со значком наверху, навроде немецкого умляута или восточных огласовок. Для неюникодных программ это выглядит как два символа, причем второй какой-то странный. Юникодные программы такие файлы показывают и открывают нормально, а неюникодные затрудняются. Нафига нужно было так изгаляться? В русском алфавите "и" и "й" - разные буквы.

> You forget that people are quite happily programming in very slow languages like Perl, Python, Ruby and Visual Basic, and those people vastly outnumber the ones using F#, Haskell, OCaml, SML etc. (They don't even have static safety, dammit!).

Should we tell them that using CPU for nothing (side-effect for using a "slow language") has a bad effect on global warming? Could it be a wake-up call? :-p

half-kidding,

Philippe Wang

Из недр одного мейллиста.

Когда делаю для себя на Окамле что-то интерактивное, то обычно делаю веб-интерфейс. Нашел в интернетах простенький веб-сервер в 200 строк (из них половина - перечисление кодов ошибок HTTP) - thumper, портировал под винду (реализовав нехватавшую функцию из модуля Unix), дописал разбор параметров и POST запросов. Устроено там все было очень просто и по-функциональному: для нужных путей регистрируются обработчики, являющиеся вполне себе чистыми функциями - параметры запроса на входе, заголовки и тело ответа на выходе. Этого вполне хватало, но вот пришел день, когда понадобилось обрабатывать много данных и выводить прогресс выполнения. И тут всплыл закон дырявых абстракций.
( Read more...Collapse )
Т.е. обработчик запроса возвращает веб-серверу последовательность отложенных вычислений. Веб-сервер последовательно по ней проходится, отдавая результаты пользователю, в результате прогрессбар ползет по мере обработки данных. Все работает, но благодаря тому, что само вычисление стало побочным эффектом. Вот мне интересно, а как такая задача решается в православном чистом ФП?

На днях доделывал новый кодек, в одном месте занятная загогулина получилась.
Нужно, чтобы незарегистрированная версия при кодировании через N кадров или M секунд после начала работы (что произойдет раньше) рисовала на видео похабную надпись большими красивыми буквами, тем самым побуждая к регистрации. Рисовать надпись обычными средствами GDI плохо - векторным шрифтом это делать медленно, да и нужного шрифта у пользователя может не быть. Быстрый вариант - накладывать картинку с прозрачностью. Но ее слишком легко заменить на полностью прозрачную, сам так делал с одним скринсейвером. :) К тому же, хочется какой-то защиты от взлома - чтобы так просто надпись было не убрать.
Воспользовался привычным решением, которое успешно применял в предыдущих продуктах - функциональность, которую хочется защитить от взлома, пишется на моем DSEL, который компилится в байткод простенькой регистровой виртуальной машины. Получилось следующее. Нарисовал нужную картинку нужным шрифтом в графическом редакторе, превратил в монохромную, сохранил. Дальше моя программка на Окамле прочитала картинку и прошлась по ней чем-то вроде RLE, превратив в такой примерно текст:

[[
  [119,5]
],
[
  [117,3], [3,4]
],
[
  [67,1], [56,4], [69,1], [9,19], [3,19], [4,5], [7,5], [5,5], [17,5]
],
[
  [11,2], [6,2], [9,2], [6,2], [8,2], [6,2], [7,4], [5,3], [3,3], [17,5], [2,6], [15,5]
],
[
  [11,2], [5,3], [8,3], [5,3], [8,3], [5,3], [6,5], [4,3]
],
...
]

Каждая строка картинки кодируется последовательностью пар чисел - число прозрачных точек, число непрозрачных. Записаны данные намеренно в синтаксисе Руби. А дальше происходит вот что.
Код, который будет выполняться в ВМ, у меня пишется на С-образном язычке, являющимся DSEL Руби. Т.е. синтаксически это код на Руби, который в результате выполнения порождает скомпилированный код ВМ. А раз это код на Руби, то у меня есть полная свобода действий во время компиляции - Руби выступает в качестве мета-языка. И вот, во время такой компиляции я читаю из файла описание картинки в виде того массива и прохожусь по нему, на каждой итерации цикла порождая кусочек кода для ВМ:

____________________________________________________
def drawwm(x, y, pSrc, stride, lines, bpp)
  sy = _int(y/2 - 30)
  sx = _int(x/2 - 128)
  pPic = _pbyte
  j = _int
  for ny in 0...lines.length
    if lines[ny].length > 0
      pPic.point(pSrc + (sy+ny)*stride + sx*bpp)
      for pair in lines[ny]
        pPic.add(bpp * pair[0])
        _for(j <= 0, j < bpp * pair[1], j.inc) {
          pPic <= 81
          pPic.inc
        }
      end
    end
  end
end

lines = open('lines.rb') {|f| eval(f.read) }
_if(draw > 0) {
  _if(bytespp.eq(2)) {
    drawwm(x, y, pSrc, stride, lines, 2)
  }.else {
    drawwm(x, y, pSrc, stride, lines, 3)
  }
}
____________________________________________________

Здесь синим обозначены конструкции, которые генерят код для ВМ, это как бы run-time, а черным - то, что происходит в compile-time, в частности, выражения типа bpp * pair[0] превращаются в сгенеренном коде в константы. Compile-time функция drawwm вызывается дважды - с разными значениями числа байт на пиксел, что приводит к генерации двух рисующих кусков кода, отличающихся лишь конкретными значениями констант. Т.е. налицо partial evaluation. В итоге, для каждой пары чисел из того массива, например [4,5], генерится такой вот код (bpp=3):

ADD|RV, 23, 12,  # перепрыгиваем через 4 точки
MOV|RV, 24, 0,   # обнуляем счетчик цикла
LE|RV, 24, 15,   # цикл на 5 точек - 15 байт
JZ, 13,
MOVB|PV, 23, 81, # пишем в картинку 
ADD|RV, 23, 1,   # увеличиваем указатель на место рисования и счетчик цикла
ADD|RV, 24, 1,
JMP, -14,        # конец цикла

И, как ни удивительно, все это даже работает, и надпись рисуется как надо в разных цветовых режимах.