Фибоначчи в народном хозяйстве

[thedeemon]

Всякий знает, что вычисление чисел Фибоначчи - важнейшая задача программирования, поэтому именно с нее нередко начинают обучение. Некоторые языки программирования, похоже, были созданы специально для решения этой задачи (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 исходных инта.

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

Comments

[thedeemon.livejournal.com]

А если в след. версии один счотчик исчезнет (причом не последний, а тот шо посередине), и появятся 2 новых?

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

Я не спорю, можно было сделать и так, как ты говоришь. Но все же мне идея хранения и передачи статистики в явном виде не очень симпатична, а сжатие кодами Фибоначчи это фан. Могу позволись себе совместить приятное с полезным. :)

[soonts.livejournal.com]

OK, если для тебя фан, тогда конечно.
Лично меня бы заебало это программировать только ради фана.

Формула Бине какая-то сука сложная.
Забил в Maple, он тоже не смог её обратить.
Значит скорее всего "быстрого" решения не существует.

Тогда насколько я понимаю, для кодирования надо одновременно искать по двум фибоначчи-рядам (сначала по одному вверх до упора, потом по нему вниз и одновременно по второму вверх).

Подобные алгоритмы обычно занимают как минимум полтора экрана плохо поддерживаемого кода.

И потом ещё надо клеить биты: или склеивать строчки из '0' и '1' (очень неэффективно), или ебаццо самому с битовыми операциями (снова трудно поддерживаемый код: в первой реализации шансы где-нить перепутать >> с << стремятся к 100%).

Причом судя по тому что ты живёшь не в мире Windows (где было бы достаточно один раз закодить на C# сразу для всех платформ, включая xbox, zune и телефоны), тебе это нужно делать минимум два раза: в windows приложении, и для твоего оп.сорсного apache.

P.S. Конечно, я и не такие извращения придумывал и успешно реализовывал, но как минимум в половине случаев это было оправдано экономией ценных ресурсов :-)

[thedeemon.livejournal.com]

Не, че-то ты усложняешь. Одновременно по двум точно не надо. Обычно достаточно одного прохода сверху вниз.

bool started = false;
res.push_front(1);
for(std::vector::reverse_iterator it = fibs.rbegin(); it != fibs.rend(); it++) {
  if (*it <= x) {
    res.push_front(1);
    x -= *it;
    started = true;
  } else {
    if (started) res.push_front(0);
  }
}
return res;

Перед этим проверяется, достаточно ли у нас посчитанных членов ряда в fibs, если нет - досчитываются недостающие.

Эффективность в этой задаче на стороне клиента вообще не требуется, ибо кодируются числа один-два раза за сессию работы с программой. Поэтому вместо возни с битами можно использовать списки интов. Упаковка в строку:

int tn = digits.size() % 5;
if (tn > 0)
  digits.insert(digits.end(), 5-tn, 0);
CString out;
for(int dn = 0; dn < digits.size()/5; dn++) {
  int v = digits[dn*5]*16 + digits[dn*5+1]*8 + digits[dn*5+2]*4 + digits[dn*5+3]*2 + digits[dn*5+4];
  out += enc[v];
}

Причом судя по тому что ты живёшь не в мире Windows (где было бы достаточно один раз закодить на C# сразу для всех платформ, включая xbox, zune и телефоны), тебе это нужно делать минимум два раза: в windows приложении, и для твоего оп.сорсного apache.

Данный продукт как раз чисто виндовый, а вот на хостинге у меня действительно линукс. Использовать C# тут нельзя, ибо а) это shareware-утилита для широкого круга пользователей, не у всех был .net framework нужной версии, когда она начиналась, и б) там жосткий number crunching - обработка видео между отнюдь не managed кодеками.

[soonts.livejournal.com]

Точно, про кодирование я чо-то проебал.
Я думал теорема про "сумму одного или двух чисел" - три взятых наугад числа, и твои примеры этому не противеречили.
Не мог что ли 41 вместо 42 написать? :-)))

>на хостинге у меня действительно линукс
Бросай ты эти open source поделки, и переходи на Windows Server 2008 - не пожалеешь.
godaddy.com: неограниченный трафик, medium trust level, $50 в год - там web site шо я сделал для своего клиента.
aspdiscount.net: 80 GB/month, full trust = можно звать unmanaged API, $120 в год - там const.me.

[thedeemon.livejournal.com]

Не мог что ли 41 вместо 42 написать? :-)))

Нет, конечно. :)

переходи на Windows Server 2008

Пока не вижу смысла. Тот хостинг у меня уже лет 10 и вполне всем устраивает: места хватает, трафик неограничен, бинарники свои запускаю любые, логи, бэкапы и безопасность устроены неплохо, аптайм 99.8, а админ - мой друг.

[kisa-i-osya.livejournal.com]

Хи-хи, вот из-за таких моральных индусов-шарпейщиков пользоваться совтом на .NET (а точнее, от всего современного MS) и невозможно.