December 8th, 2007

with Cat The Cat

Антропометрические замеры языков программирования.

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

Мы с gaperton поспорили, что монадические парсеры при разборе битовых потоков не будут сильно отставать от встроенных в Эрланг паттернов разбора битовых шаблонов на битовых строках.

Он пообещал мне дать разобрать формат упакованных котировок, я же попросил его научиться разбирать целые числа в кодировке Голомба.

Собственно, кодировка Голомба:
Битовая последовательностьЧисло
10
011
0011x
00011xx
000011xxx


Все достаточно просто: сперва идет N+1 нулей, затем единичка, затем остаток битового представления.

Есть представление, в котором длина кодируется кодом Голомба, а потом читается только битовый остаток, но и так уже неплохо.

На данный момент накропал что-то. 1.9с на раскодирование 2 миллионов чисел в диапазоне от 0 до 224. Это, получается, по 3000 команд на число (3.2GHz*2.02с/2000000).

Данные читаются из файла, и размножаются 2000 раз. Это чтобы не тормозить на вводе-выводе.

Теоретический предел, пожалуй, находится в районе пары десятков команд, я думаю. Соответственно,
по прикидке с корнем квадратным из крайних значений, Эрланг будет находится в районе 244 команд на число и мое отставание составит 3000/244=12 раз.

Это попадает в предсказанный gaperton диапазон. Он предсказал, что я отстану не более, чем в 15 раз, и не менее, чем в пять или семь (тут меня память подводит).