Фибоначчи в народном хозяйстве
Sep. 18th, 2010 12:57 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonВсякий знает, что вычисление чисел Фибоначчи - важнейшая задача программирования, поэтому именно с нее нередко начинают обучение. Некоторые языки программирования, похоже, были созданы специально для решения этой задачи (prooflink). Однако не все еще нашли применение этим чудесным числам в быту.
Понадобилось мне тут недавно уметь компактно представить набор целых чисел: при проверке на наличие новых версий а также при деинсталляции программа передает на сервер номер своей версии, а заодно кое-какую статистику, вроде числа запусков, количества дней с момента установки и т.п. Передавать нужно GET'ом, ибо при деинсталляции это делает не сама программа, а скрипт установщика, к тому же хочется сразу иметь эти данные в логах апача. Чисел получилось много, в явном виде запрос получился бы сильно длинным и некрасивым. Решил применить какое-нибудь простое сжатие.
Числа все неотрицательные, сверху не ограниченные, и вероятность встречи числа быстро уменьшается с ростом самого числа. Для таких данных есть семейство кодов переменной длины, называемое универсальными кодами. Большинство из них сначала кодируют некоторым образом число битов (например, унарно), а затем сами биты кодируемого числа. Но длина таких кодов растет довольно быстро. Зато есть более интересный и для нужных мне значений более эффективный способ представления - коды Фибоначчи. Они основаны на теореме одного зубного врача из бельгийской армии, которая говорит, что всякое натуральное число можно уникальным образом представить в виде суммы чисел Фибоначчи, причем в такой сумме никогда не будет двух последовательных членов ряда. Ряд начинается так: 1, 2, 3, 5, 8, 13, 21... Тогда 6 = 1+5, 15 = 2+13, 31 = 2+8+21. Чтобы закодировать число последовательностью битов, достаточно пройтись по ряду Фибоначчи до требуемого числа и проставить единицы напротив входящих в сумму членов и нули напротив невходящих. Поскольку по построению у нас не может быть подряд двух единиц, этот факт используется для маркировки конца числа: после последней единицы ставим еще одну и код готов, длину числа хранить нигде не надо. Примеры:
В итоге у меня требуемый набор чисел превращается в такую битовую последовательность, которая затем кодируется по пять цифрами и буквами в Base32. Получается обычно по 12-15 символов на 24 исходных инта.
А вот и сам автор теоремы - полковник Эдуард Цекендорф:
Понадобилось мне тут недавно уметь компактно представить набор целых чисел: при проверке на наличие новых версий а также при деинсталляции программа передает на сервер номер своей версии, а заодно кое-какую статистику, вроде числа запусков, количества дней с момента установки и т.п. Передавать нужно 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 исходных инта.
А вот и сам автор теоремы - полковник Эдуард Цекендорф:
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-09-18 12:46 am (UTC)no subject
Date: 2010-09-18 03:22 pm (UTC)Например пишешь 10 строк C# кода, который, если запрошен файл "Uninstall.aspx?s=...", сохраняет Request.QueryString["s"] в Session["s"], после чего отправляет клиенту HTTP 301 на Uninstall.aspx без параметров.
Все параметры на месте + чистый URL.
>это же представление используется для хранения статистики
А если в след. версии один счотчик исчезнет (причом не последний, а тот шо посередине), и появятся 2 новых?
>не возникнет желания ее выборочно попортить
IMO чувак, который открывает RegEdit и правит непонятные для него значения - весьма редкий use-case.
Когда на сайте support.microsoft.com есть инструкции по правке реестра, они всегда сопровождаются warning "serious problems might occur if you modify the registry incorrectly".
Где-то мне попадался warning даже страшнее, о том шо "вы можете сломать систему так шо потребуется её переустановка".
Несмотря на то что удалив единственный ключ (например из ветки HKCR), можно поиметь очень разнообразные проблемы, Microsoft не делает попыток защититься от таких чуваков.
Точнее, делает только если пиздец: "Restore last known good configuration".
no subject
Date: 2010-09-18 05:21 pm (UTC)Новые добавятся в конец. Ненужное значение не будет использоваться, по умолчанию там будет ноль, который тут кодируется двумя битами.
Я не спорю, можно было сделать и так, как ты говоришь. Но все же мне идея хранения и передачи статистики в явном виде не очень симпатична, а сжатие кодами Фибоначчи это фан. Могу позволись себе совместить приятное с полезным. :)
no subject
Date: 2010-09-18 11:29 pm (UTC)Лично меня бы заебало это программировать только ради фана.
Формула Бине какая-то сука сложная.
Забил в Maple, он тоже не смог её обратить.
Значит скорее всего "быстрого" решения не существует.
Тогда насколько я понимаю, для кодирования надо одновременно искать по двум фибоначчи-рядам (сначала по одному вверх до упора, потом по нему вниз и одновременно по второму вверх).
Подобные алгоритмы обычно занимают как минимум полтора экрана плохо поддерживаемого кода.
И потом ещё надо клеить биты: или склеивать строчки из '0' и '1' (очень неэффективно), или ебаццо самому с битовыми операциями (снова трудно поддерживаемый код: в первой реализации шансы где-нить перепутать >> с << стремятся к 100%).
Причом судя по тому что ты живёшь не в мире Windows (где было бы достаточно один раз закодить на C# сразу для всех платформ, включая xbox, zune и телефоны), тебе это нужно делать минимум два раза: в windows приложении, и для твоего оп.сорсного apache.
P.S. Конечно, я и не такие извращения придумывал и успешно реализовывал, но как минимум в половине случаев это было оправдано экономией ценных ресурсов :-)
no subject
Date: 2010-09-19 05:15 am (UTC)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 кодеками.
no subject
Date: 2010-09-20 09:12 pm (UTC)Я думал теорема про "сумму одного или двух чисел" - три взятых наугад числа, и твои примеры этому не противеречили.
Не мог что ли 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.
no subject
Date: 2010-09-21 01:28 am (UTC)Нет, конечно. :)
переходи на Windows Server 2008
Пока не вижу смысла. Тот хостинг у меня уже лет 10 и вполне всем устраивает: места хватает, трафик неограничен, бинарники свои запускаю любые, логи, бэкапы и безопасность устроены неплохо, аптайм 99.8, а админ - мой друг.
no subject
Date: 2010-09-25 01:55 pm (UTC)