Чтобы получить ровно 64Кб, достаточно использовать 19-битный хеш — тупо обрезаем один бит с начала или с конца. Немного магии архиватора и получим дополнительно пару Кб места для кода. Правда на сколько процентов при этом пострадает результат сложно сказать, но могу предположить 2-3 процента от текущего результата.
Имея 20 бит на хеш, получим 1.048.576 (2^20) возможных комбинаций ~ 128Kb, которые ещё нужно ужать до 60-62Кб, т.к. не нужно забывать про место и для кода, который должен эти данные обрабатывать.
Если получится всё уместить в 64Кб, то дальше будет борьба за каждые сотые доли процента ;)
Моя идея была в том, чтобы сгенерировать вначале словарь локально и, если натыкаюсь на коллизию, продолжать генерировать дальше, запомнив количество колизий, которое нужно пропустить до генерации нужной строки. Это как один из вариантов. Но похоже, что число коллизий, которые нужно будет пропустить, хотя и на много порядков меньше 2^34533917, но всё же довольно большое.
Если использовать чисто хеш — да, из-за коллизий. Но можно уменьшить вероятность коллизий практически до 0 задав исходный размер строки и, при необходимости, ещё какие-либо дополнительные параметры. И, конечно же, протестировать решение до того, как отправлять. Т.к. строка будет генерироваться в той же последовательности, это гарантирует факт, что решение, протестированное локально, будет работать так же и на тестовом сервере.
Не знаю как Вы, но мне было бы интересно посмотреть на решение, занимающее 256Кб. Зип жмёт словарь в 1.62Мб. С использованием префиксного дерева мне удалось сжать решение до 825Кб, и верю, что это не предел. Т.е. тут влияет не только архиватор, но и способ хранения. В любом случае, решать не мне, и, скорее всего, я предложил слишком поздно.
Мой коллега предложил гениально-простое самое маленькое возможное решение, которое будет давать 100% результат — это сгенерировать md5 хеш от словаря, и затем восстановить весь словарь перебором. Жаль, что ограничение по времени — 1 неделя :)
Полностью поддерживаю ограничение в 64Кб — задача поставлена очень интересно и требует много размышлений и проб. Поэтому я и не предлагаю назначить какой-либо из главных призов, чтобы большинство программистов продолжало пытаться уложиться в 64Кб, но в то же время интересно было бы посмотреть сколько места может занять программа, выдающая 100% результат.
Или можно будет где-то организовать доску с результатами попыток сжатия, но уже без финансовой мотивации — чисто ради интереса.
ИМХО, было бы неплохо ради спортивного интереса, если бы один из спец призов достался тому, кто сумел бы упаковать решение, дающее 100% результат, в наименьшее количество байт. Только через форму данное решение не отправить, т.к. подобное решение наверняка превысит 64Кб
Я тоже долго не мог допереть. Логичеки вроде понимаю отдельные куски, а сложить в целую картинку не получалось. Может поможет https://www.jasondavies.com/bloomfilter/ — тут наглядно визуализировали работу фильтра Блума.
Думал об этом, но не получилось — ужимается дерево в памяти за счёт повторного использования узлов, но есть 2 «но»:
1. дерево ужимается в памяти, но не при сериализации (главный аргумент)
2. последние уровни усечённого дерева настолько разные, что смысла ужимать нет
Также думал о побитовом сжатии — использовать биты вместо 26 букв и апострофа, тогда вместо потенциальных 27 байтов можно использовать 4 (3 при усечении алфавита). И это действительно даёт преимущество в сериализации 2-3 первых уровней, где используются практически все буквы из алфавита, но на на последних уровнях, которые заканчиваются на 1-2 возможные буквы, это преимущество оказывается избыточным. Усечённое дерево, обычно сжимаемое до 60Кб, с использованием битовой маски превращается в 200Кб
Добавление подобной проверки не дало ощутимой разницы при тестировании на 12К случайных слов, но ради интереса я проверил в словаре «неверных» слов и результаты интересны:
Total words: 598216
Words with 5 consonants: 68502 or 11.45%
Words with 3 same letters: 2835 or 0.47%
Против статистики «верных» слов:
Total words: 630404
Words with 5 consonants: 1053 or 0.17%
Words with 3 same letters: 109 or 0.02%
Так что я ошибался — проверка на 5 согласных подряд должна добавить несколько процентов.
Добавлю сюда результат проверки для 4 гласных подряд:
Correct words with 4 vowels: 2447 or 0.39%
Incorrect words with 4 vowels: 6467 or 1.08%
Добавлю немного своих размышлений и результатов исследований:
1. Используя префиксное дерево, дающего 100% результат удалось добиться размера 845Кб
2. То же префиксное дерево, но с результатом 98% весит уже 784Кб
3. 89% — 474Кб
4. 85% — 356Кб
и т.д…
Данная статистика наглядно показывает зависимость размера от результата.
Использование фильтрации по неиспользуемым сочетаниям букв даёт нулевой результат — 3-х буквенные неиспользуемые сочетания занимают 12Кб места, а толку от них 0, т.к. в выборке сгенерированных «неправильных» слов размером в 500тыс слов (ссылка в комментах выше) ни одно из этих сочетаний не используется.
Попытки найти какой-либо шаблон в словах, который бы использовался в словаре, но не использовался бы в сгенерированных словах, не удались. Сгенерированные слова слишком похожи на слова из словаря, а слова из словаря слишком разные. Например, слова с 5 согласными буквами подряд встречаются в словаре 1053 раза, а слова с одной и той же буквой 3 раза подряд встречаются 109 раз. При этом данная статистика бесполезна.
Следующим шагом была попытка использования масок для слов, например, 010101100 — где 0 — гласные, 1 — согласные, либо маски, сгруппированные по буквам, например, проверка одного и того же слова сразу по нескольким маскам, использующим различные группировки букв. Толку от подобного подхода слишком мало — опять же из-за сильной схожести сгенерированных слов со словами из словаря.
Наибольший результат достигается использованием фильтрации по первым буквам слов — для 3 букв при размере 17.5Кб результат — 57%, для 4 букв — 89Кб и 64%, для 5 букв — 73% (размер не смотрел). Использование префиксного дерева позволяет уменьшить размер — 3.5Кб для 3 букв, 24Кб — для 4 букв, 89Кб — для 5. Отсекая малоиспользуемые префиксы для 5 букв можно добиться результата в 71% при размере 60Кб (мой лучший результат). Попытка дополнительно учитывать длину слова и/или конечные буквы значительно увеличивает размер, при этом мало влияя на результат. Например, попытка использовать 2 префиксных дерева по 4 буквы для отсечения слов и с начала и с конца, даёт 66% при размере 58Кб, 5 с начала и 3 с конца — 71% при размере 67Кб. Выводы можете сделать сами.
Думаю, что нейронные сети могут найти более хороший подход к решению данной задачи, однако каким образом можно будет запихнуть результат обучения подобной сети в 64 Кб — не имею ни малейшего представления.
P.S. когда я увидел возможность упаковки 6.3Мб словаря в 100Кб, я был очень удивлён, но у меня появился стимул. Очень жаль, что это оказалось усечённое префиксное дерево :(.
Я не вижу ваш код, поэтому сложно сказать, что именно происходит не так. Но могу предположить, что проблема в наследовании. Чтобы грид в админке заработал, основной блок должен наследоваться от класса Mage_Adminhtml_Block_Widget_Grid_Container, тогда грид будет вызываться автоматически.
Из этих строчек получилось dsnews/adminhtml_news, после чего добавилось хардкорное значение _grid, в результате получилось dsnews/adminhtml_news_grid.
По названию dsnews определяется класс blocks/dsnews/class, в вашем случае My_Module_Block, а дальше просто добавляется то, что имеется в пути — adminhtml_news_grid преобразуется в _Adminhtml_News_Grid, которое добавляется к названию вашего класса. Итого имеем название класса My_Module_Block_Adminhtml_News_Grid
Идеальных конкурсов не бывает, но организаторы очень старались. Большое спасибо организаторам за конкурс, а участникам — за интересные решения. Критерии и способы оценки у всех разные, в данном конкурсе способы и результаты тестирования видны всем, а не являются «черным ящиком».
Лично мне понравилось решение Sergey Golub — при высокой скорости обработки такой код понятен с первого взгляда, и в дальнейшем его поддержка и доработка будет простой, что порой имеет большее значение, чем выигрыш в несколько мс.
Могу привести реальный пример пересылки денег из Кореи в Узбекистан. Т.к. у нас имеется проблема ограничения вывоза баксов, то система пересылания гастарбайтерами денег из Кореи в Узбекистан очень даже оправдана как для пересылающих, так и для «брокеров» — деньги пересылаются с 0% комиссией. Суть в том, что торговцы, привозящие товары из Кореи, не могут вывезти большие суммы денег из страны, поэтому им выгодно, если кто-то заплатит в Корее поставщику, а местный «продавец» уже тут рассчитается с получателем в счёт будущих покупок.
В моих примерах и описаниях в квадратных скобках приведены [изменяемые переменные], т.е в данном случае стоит package rwd и theme default, т.е. шаблоны нужно класть по пути /app/design/frontend/rwd/default, а скрипты и стили — /skin/frontend/rwd/default
Если получится всё уместить в 64Кб, то дальше будет борьба за каждые сотые доли процента ;)
А жаль, идея выглядела такой перспективной :)))
Мой коллега предложил гениально-простое самое маленькое возможное решение, которое будет давать 100% результат — это сгенерировать md5 хеш от словаря, и затем восстановить весь словарь перебором. Жаль, что ограничение по времени — 1 неделя :)
Или можно будет где-то организовать доску с результатами попыток сжатия, но уже без финансовой мотивации — чисто ради интереса.
1. дерево ужимается в памяти, но не при сериализации (главный аргумент)
2. последние уровни усечённого дерева настолько разные, что смысла ужимать нет
Также думал о побитовом сжатии — использовать биты вместо 26 букв и апострофа, тогда вместо потенциальных 27 байтов можно использовать 4 (3 при усечении алфавита). И это действительно даёт преимущество в сериализации 2-3 первых уровней, где используются практически все буквы из алфавита, но на на последних уровнях, которые заканчиваются на 1-2 возможные буквы, это преимущество оказывается избыточным. Усечённое дерево, обычно сжимаемое до 60Кб, с использованием битовой маски превращается в 200Кб
— теоретически проверка 5 согласных подряд даёт дополнительно несколько процентов
— практически результат улучшился всего на 0.08%
Total words: 598216
Words with 5 consonants: 68502 or 11.45%
Words with 3 same letters: 2835 or 0.47%
Против статистики «верных» слов:
Total words: 630404
Words with 5 consonants: 1053 or 0.17%
Words with 3 same letters: 109 or 0.02%
Так что я ошибался — проверка на 5 согласных подряд должна добавить несколько процентов.
Добавлю сюда результат проверки для 4 гласных подряд:
Correct words with 4 vowels: 2447 or 0.39%
Incorrect words with 4 vowels: 6467 or 1.08%
1. Используя префиксное дерево, дающего 100% результат удалось добиться размера 845Кб
2. То же префиксное дерево, но с результатом 98% весит уже 784Кб
3. 89% — 474Кб
4. 85% — 356Кб
и т.д…
Данная статистика наглядно показывает зависимость размера от результата.
Использование фильтрации по неиспользуемым сочетаниям букв даёт нулевой результат — 3-х буквенные неиспользуемые сочетания занимают 12Кб места, а толку от них 0, т.к. в выборке сгенерированных «неправильных» слов размером в 500тыс слов (ссылка в комментах выше) ни одно из этих сочетаний не используется.
Попытки найти какой-либо шаблон в словах, который бы использовался в словаре, но не использовался бы в сгенерированных словах, не удались. Сгенерированные слова слишком похожи на слова из словаря, а слова из словаря слишком разные. Например, слова с 5 согласными буквами подряд встречаются в словаре 1053 раза, а слова с одной и той же буквой 3 раза подряд встречаются 109 раз. При этом данная статистика бесполезна.
Следующим шагом была попытка использования масок для слов, например, 010101100 — где 0 — гласные, 1 — согласные, либо маски, сгруппированные по буквам, например, проверка одного и того же слова сразу по нескольким маскам, использующим различные группировки букв. Толку от подобного подхода слишком мало — опять же из-за сильной схожести сгенерированных слов со словами из словаря.
Наибольший результат достигается использованием фильтрации по первым буквам слов — для 3 букв при размере 17.5Кб результат — 57%, для 4 букв — 89Кб и 64%, для 5 букв — 73% (размер не смотрел). Использование префиксного дерева позволяет уменьшить размер — 3.5Кб для 3 букв, 24Кб — для 4 букв, 89Кб — для 5. Отсекая малоиспользуемые префиксы для 5 букв можно добиться результата в 71% при размере 60Кб (мой лучший результат). Попытка дополнительно учитывать длину слова и/или конечные буквы значительно увеличивает размер, при этом мало влияя на результат. Например, попытка использовать 2 префиксных дерева по 4 буквы для отсечения слов и с начала и с конца, даёт 66% при размере 58Кб, 5 с начала и 3 с конца — 71% при размере 67Кб. Выводы можете сделать сами.
Думаю, что нейронные сети могут найти более хороший подход к решению данной задачи, однако каким образом можно будет запихнуть результат обучения подобной сети в 64 Кб — не имею ни малейшего представления.
P.S. когда я увидел возможность упаковки 6.3Мб словаря в 100Кб, я был очень удивлён, но у меня появился стимул. Очень жаль, что это оказалось усечённое префиксное дерево :(.
Из этих строчек получилось dsnews/adminhtml_news, после чего добавилось хардкорное значение _grid, в результате получилось dsnews/adminhtml_news_grid.
По названию dsnews определяется класс blocks/dsnews/class, в вашем случае My_Module_Block, а дальше просто добавляется то, что имеется в пути — adminhtml_news_grid преобразуется в _Adminhtml_News_Grid, которое добавляется к названию вашего класса. Итого имеем название класса My_Module_Block_Adminhtml_News_Grid
Лично мне понравилось решение Sergey Golub — при высокой скорости обработки такой код понятен с первого взгляда, и в дальнейшем его поддержка и доработка будет простой, что порой имеет большее значение, чем выигрыш в несколько мс.