А мне нравится «информационное» определение энтропии для вероятностного распределения:
E = -∑(p*log p), то есть, энтропия — мат. ожидание минус логарифма вероятности события, или, что то же самое, мат. ожидание количества информации, необходимого, чтобы записать событие.
Например, для игрального кубика события — выпадение чисел 1, 2, 3, 4, 5, 6 с равной вероятностью 1/6; количество инфромации, чтобы передать любое из этих событий -log(1/6) = log(6) ~ 2.6 бит. И энтропия игрального кубика будет
E = -∑(1/6*log(1/6)) ~ 2.6 бит.
Если же кубик у нас не честный, и, например, вероятность выпадения единицы — одна вторая, а остальных чисел — по одной десятой, то энтропия будет
E = -0.5 * log(0.5) — ∑(1/10*log(1/10)) ~ 2.2 бита, то есть, меньше, чем у честного кубика.
В прогрммистских терминах, энтропия даных — это ожидаемый размер зип-архива с этими данными (в предположении, что он сожмет их идеально)!
Если Вы имеете в виду Number theoretic transform, то, возможно, в обработке изображений его не используют. Но, насколько я знаю, это самый быстрый способ перемножить два многочлена с целыми коэффициентами или два целых числа произвольной разрядности, и это имеет приложения, например, в криптографии. И научные статьи о низкоуровневых оптимизациях этого метода регулярно появляются, например, Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography.
Там несколько другая задача, так как считаются остатки не обязательно по модулю простого числа, но кроме практических задач есть еще и научные, и для решения некоторых задач приходится перебирать большие диапазоны чисел, поэтому
>что изменится, если Вы будете считать остатки в 10 раз медленнее или в 10 раз быстрее?
от этого может зависить, напишете вы научную статью через месяц или через год!
Конкретно конвертация числа в текст, может, и не требует особого ускорения, однако, если я правильно понимаю, потобные трюки позволяют ускорить конвертацию числа из одной системы счисления в другую, что уже представляет интерес для задач в теории чисел (например, для вычисления биномиальных коэффициентов по модулю простого числа)
Мне кажется, в этой задаче setDictionary не поможет: он устанавливает начальное значение для sliding window (в котором deflate ищет повторяющиеся последовательности байт); этот метод эффективен для сильно повторяющихся данных. В случае набора коротких слов на разных языках, как мне кажется, основное сжатие в deflate обеспечивается кодировкой Хаффмана, которая от setDictionary не зависит.
В данной задаче могло бы помочь создание специализированных fixed huffman codes для каждого языка, и переключение между ними (стандартный блок deflate compression with fixed huffman codes, скорее всего, не будет самым эффективным), но это решение в любом случае будет сложнее, чем приведенное автором.
Насколько я понимаю, Snappy работает так же, как Lz4 — заменяет повторяющиеся данные ссылками на предыдущие вхождения. В вашем случае очень сомневаюсь, что он даст хоть какое-то преимущество, так как от произвольного набора коротких слов вряд ли стоит ожидать большого количества повторений (кроме префиксов, но ваши строки и так в префиксном дереве)
>К чему формула, если узнать из нее ничего не удасться?
Насколько я видел, вообще определение априорной вероятности в байесовской статистике для практически любой задачи является самым слабым местом: иногда ее можно задать «из общих соображений», но в общем случае непонятно, откуда ее брать. Например, Википедия упоминает deductive reasoning и principle of indifference, что является скорее философией, чем математикой. И для разных распределений можно получить практически произвольные результаты, в этом я с вами согласен.
Но с моей точки зрения, именно в этом ценность формулы: она показывает, что для точного решения задачи необходимо знать это распределение, и без него задачу невозможно формализовать в рамках статистики (но, конечно, можно в других рамках, например, теории игр, как вы делаете)
Если бы мне задали такую задачу, я бы решил, что это классическая задача на применение формулы Байеса: P(N | 17) = P(17 | N) * P(N) / P(17) -> min, то есть вероятность того, что в городе N трамваев при условии того, что мы увидели 17-й, равна вероятности увидеть 17-й трамвай при условии того, что в городе N трамваев, умножить на (априорную) вероятность того, что в городе N трамваев и поделить на вероятность увидеть 17-й трамвай.
Вероятность в знаменателе можно вычислить как P(17) = Sum{ P(17 | n) * P(n) } по всем возможным n, но она от N не зависит, поэтому достаточно найти N, минимизирующее числитель. А условную вероятность можно вычислить как P(17 | N) = Sum { P(17 | city) * P(city) } по всем городам, имеющим N трамваев.
Для сферического города в вакууме P(17 | city) = 1/N, N >= 17, тогда P(N | 17) = P(N)/N. При предположении, что количество городов с N трамваев падает с ростом N, получаем, что оптимальное N=17.
Для города на планете Земля надо в формулу подставить значения из справочника (если такой существует): P(N) — это количество городов, в которых N трамваев, делить на количество городов на Земле; P(17; city), наверно, можно оценить, как количество времени, которое 17-й маршрут проводит в городе за сутки, умножить на количество составов, поделить на общее количество времени, которое все трамваи города проводят за сутки.
Спасибо, интересная задача!
Я применил некоторые оптимизации, результат ускоряется очень сильно. Понятно, что 20x20 будет работать быстро и без опnимизаций, поэтому я мерил производительность на двух случаях: 1) матрица 10,000x10,000, заполненная случайными значениями, и 2) матрица 1,000x1,000, заполненная «наихудшими» значениями так, чтобы максимальное произведение четырех соседних элементов было в самом конце.
Без оптимизаций первый вариант я не дождался, когда закончит вычисления, а второй вариант — 30 секунд.
Оптимизация, которую нашел vesper-bot, — пропускать числа, умножение которых на 99*99*99 будет меньше уже найденного результата, улучшает сильнее всего — «случайный» вариант ускоряется до 8 секунд, наихудший — никак не ускоряется (так как я специально подбирал для него значения!)
Кроме этого, если текущее значение = 99*99*99*99, то можно дальше не искать, так как это максимально возможный результат. Это ускоряет случайный вариант до 6 секунд.
Далее, так как перебирать всех соседей всех клеток на каждом шаге дорого, то до начала работы можно вычислить уникальные пути из четырех клеток. Их оказалось всего 102. Это ускоряет случайный вариант до 3 секунд, а наихудший — с 30 до 2 секунд.
При этом в случайном варианте заполнение матрицы случайными значениями занимает больше времени, чем решение задачи. Поэтому последня оптимизация — не создавать всю матрицу с нуля, а создать первые 4 строчки, а потом сдвигать их вверх, вычисляя четвертую строчку на каждом шаге. Также, на данном этапе проверка выхода за границу матрицы уже дает ощутимый вклад, поэтому еще одна оптимизация — расширить матрицу на три клетки во все стороны, заполненные нулями. Это ускоряет случайный вариант до 0.2 секунд, а наихудший — до 1 секунды, больше я ускорить не смог. Еще я проверил идею заменить произведение суммой логарифмов, но особо результат не ускорился (но и не замедлился).
Интересно, что хотя сложность задачи совершенно явно O(n*n), но для случайной матрицы, если она достаточно большая, рано или поздно найдется максимальное произведение (99*99*99*99), и дальше можно будет не искать. Учитывая, что оптимизированная версия создает матрицу построчно, скорость работы в среднем случае для случайной матрицы, похоже, будет O(n). Именно поэтому «случайный» вариант работает в 10 раз быстрее на большей матрице.
Насколько я понимаю, уже упоминавшийся выше Roaring Bitmap примерно так и работает: разбивает диапазон на под-диапазоны, и хранит только младшие биты в каждом, но у него (в оригинальном варианте) только один уровень вложенности: 64K страниц по максимум 64K элементов, причем каждая страница сжимается своим способом (битовый массив или набор чисел, в зависимости от количества элементов).
Да, спасибо, это интересный трюк — вести вычисления не для n, а для (n-1)/2.
Хочу только уточнить, что избавление от повторных вычеркиваний не полное — например, число 45 = 5 * 9 все равно вычеркивается дважды: (n-1)/2 = 22 = i + j + 2ij для {i=1, j=7}, а также для {i=2, j=4}.
Если я правильно понимаю, практически любая оптимизация решета Эратосфена делает аналогичную вещь: в коде вместо
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
надо 1 заменить на 2 в двух местах:
for (long i = 7; i * i < Length; i += 2)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += 2 * i) ClearPrime(d);
}
и получится полный аналог алгоритма Сундарама в плане избавления от повторных вычеркиваний.
Но вы правы, можно перевести все вычисления в (n-1)/2, код получится даже проще (хотя, конечно, для понимания сложнее, чем интуитивно понятное решето Эратосфена)
А если не секрет, какого рода задача и какое распределение чисел получается?
Хороший пример решения задачи такого рода — исходный код Люсены: ее индекс, собственно, это набор файлов, в котором хранятся числа разных распределений. Соответственно, для каждого типа файлов они придумывают свой собственный кодек, их можно посмотреть, например, здесь.
Мне приходилось решать похожие задачи (хотя, скорее, для оптимизации хранения), я использовал комбинацию уже упоминавшихся тут приемов:
— отсортировать числа
— взять разницу между соседними (если числа разные, можно отнять 1)
— закодировать Varint encoding (7 бит на значение, восьмой бит — флаг последнего байта)
— разделить на куски и каждый кусок сжать deflate-ом (либо lz4, если нужна скорость).
Да, действительно, факторизация по трем первым простым числам мне тоже показалась «оптимальной» именно из-за восьми бит на период.
Хочу только отметить, что если взять достаточно большое количество простых чисел, можно добиться произвольно большого сжатия. Я когда-то подсчитал, что для факторизации по первым четырем миллиардам простых чисел потребуется примерно 0.0225 бит на натуральное число. Однако на практике, конечно, этот алгоритм неприменим, потому что выгода начнется только для простых чисел, состоящих из триллионов (десятичных) знаков. Кроме того, размер таблицы INDEX_TO_BIT будет больше количества атомов во вселенной.
Вроде бы чисто теоретически должно сработать, но затрудняюсь сказать, насколько это усложнит код. Кроме того, размер поля 1 мегабайт, а размер линии — 1 килобайт (по 4бита на клетку), так что экономия на одной линии не особо должна повлиять на производительность. Вот действительно где можно было бы сильно сэкономить, — это хранить клетки не в 4 битах, а в одном бите, и распаковывать только для подсчетов, примерно как это делается в этой статье. К сожалению, чтобы биты расширить в байты более-менее эффективно, нужен десяток AVX-инструкций; я пытался делать, но производительность только ухудшилась. В AVX512 будет специальная инструкция для этого, тогда можно будет попробовать, но пока процессоры не особо его поддерживают.
Спасибо за комментарий, это действительно отличная идея, я ее проверил уже после написания статьи.
Тут есть техническая проблема: в AVX невозможно сдвинуть на 4 бита весь регистр как одно 256-разрядное число, минимум нужно делать два сдвига и одно сложение, так что ускорение будет немного меньше, чем в два раза, и код сильно усложняется, но выигрыш в скорости все равно получается существенный.
Вкупе с еще одной идеей: избавиться от временного буффера вообще, и хранить дополнительно только три линии поля (текущую, выше, и ниже) получается суммарно ускорение в 330 раз от начальной версии, от 25 до 7400 шагов в секунду!
Можно код посмотреть на гитхабе: AdvancedLifeExtensionsInLineCompressed.cs.
Спасибо за статью!
По поводу превосходства GPU: я когда-то пытался делать неоптимизированную реализацию на CUDA, и она оказалась сильно медленнее, чем я ожидал (медленнее вашей версии). Потом я наткнулся на эту статью, в которой утверждается, что ключ к оптимизации — расположение данных в GPU-памяти правильного типа (в идеале, в регистровой памяти).
Их производительность — 0.16 секунд на 1024 итераций на поле 16K на 16K на видеокарте GeForce GTX TITAN X. Эта разница из-за того, что видеокарты несопоставимы по производительности, или Вашу версию еще можно ускорить, если применить аналогичные трюки?
E = -∑(p*log p), то есть, энтропия — мат. ожидание минус логарифма вероятности события, или, что то же самое, мат. ожидание количества информации, необходимого, чтобы записать событие.
Например, для игрального кубика события — выпадение чисел 1, 2, 3, 4, 5, 6 с равной вероятностью 1/6; количество инфромации, чтобы передать любое из этих событий -log(1/6) = log(6) ~ 2.6 бит. И энтропия игрального кубика будет
E = -∑(1/6*log(1/6)) ~ 2.6 бит.
Если же кубик у нас не честный, и, например, вероятность выпадения единицы — одна вторая, а остальных чисел — по одной десятой, то энтропия будет
E = -0.5 * log(0.5) — ∑(1/10*log(1/10)) ~ 2.2 бита, то есть, меньше, чем у честного кубика.
В прогрммистских терминах, энтропия даных — это ожидаемый размер зип-архива с этими данными (в предположении, что он сожмет их идеально)!
Там несколько другая задача, так как считаются остатки не обязательно по модулю простого числа, но кроме практических задач есть еще и научные, и для решения некоторых задач приходится перебирать большие диапазоны чисел, поэтому
>что изменится, если Вы будете считать остатки в 10 раз медленнее или в 10 раз быстрее?
от этого может зависить, напишете вы научную статью через месяц или через год!
В данной задаче могло бы помочь создание специализированных fixed huffman codes для каждого языка, и переключение между ними (стандартный блок deflate compression with fixed huffman codes, скорее всего, не будет самым эффективным), но это решение в любом случае будет сложнее, чем приведенное автором.
Насколько я видел, вообще определение априорной вероятности в байесовской статистике для практически любой задачи является самым слабым местом: иногда ее можно задать «из общих соображений», но в общем случае непонятно, откуда ее брать. Например, Википедия упоминает deductive reasoning и principle of indifference, что является скорее философией, чем математикой. И для разных распределений можно получить практически произвольные результаты, в этом я с вами согласен.
Но с моей точки зрения, именно в этом ценность формулы: она показывает, что для точного решения задачи необходимо знать это распределение, и без него задачу невозможно формализовать в рамках статистики (но, конечно, можно в других рамках, например, теории игр, как вы делаете)
P(N | 17) = P(17 | N) * P(N) / P(17) -> min, то есть вероятность того, что в городе N трамваев при условии того, что мы увидели 17-й, равна вероятности увидеть 17-й трамвай при условии того, что в городе N трамваев, умножить на (априорную) вероятность того, что в городе N трамваев и поделить на вероятность увидеть 17-й трамвай.
Вероятность в знаменателе можно вычислить как P(17) = Sum{ P(17 | n) * P(n) } по всем возможным n, но она от N не зависит, поэтому достаточно найти N, минимизирующее числитель. А условную вероятность можно вычислить как P(17 | N) = Sum { P(17 | city) * P(city) } по всем городам, имеющим N трамваев.
Для сферического города в вакууме P(17 | city) = 1/N, N >= 17, тогда P(N | 17) = P(N)/N. При предположении, что количество городов с N трамваев падает с ростом N, получаем, что оптимальное N=17.
Для города на планете Земля надо в формулу подставить значения из справочника (если такой существует): P(N) — это количество городов, в которых N трамваев, делить на количество городов на Земле; P(17; city), наверно, можно оценить, как количество времени, которое 17-й маршрут проводит в городе за сутки, умножить на количество составов, поделить на общее количество времени, которое все трамваи города проводят за сутки.
Я применил некоторые оптимизации, результат ускоряется очень сильно. Понятно, что 20x20 будет работать быстро и без опnимизаций, поэтому я мерил производительность на двух случаях: 1) матрица 10,000x10,000, заполненная случайными значениями, и 2) матрица 1,000x1,000, заполненная «наихудшими» значениями так, чтобы максимальное произведение четырех соседних элементов было в самом конце.
Без оптимизаций первый вариант я не дождался, когда закончит вычисления, а второй вариант — 30 секунд.
Оптимизация, которую нашел vesper-bot, — пропускать числа, умножение которых на 99*99*99 будет меньше уже найденного результата, улучшает сильнее всего — «случайный» вариант ускоряется до 8 секунд, наихудший — никак не ускоряется (так как я специально подбирал для него значения!)
Кроме этого, если текущее значение = 99*99*99*99, то можно дальше не искать, так как это максимально возможный результат. Это ускоряет случайный вариант до 6 секунд.
Далее, так как перебирать всех соседей всех клеток на каждом шаге дорого, то до начала работы можно вычислить уникальные пути из четырех клеток. Их оказалось всего 102. Это ускоряет случайный вариант до 3 секунд, а наихудший — с 30 до 2 секунд.
При этом в случайном варианте заполнение матрицы случайными значениями занимает больше времени, чем решение задачи. Поэтому последня оптимизация — не создавать всю матрицу с нуля, а создать первые 4 строчки, а потом сдвигать их вверх, вычисляя четвертую строчку на каждом шаге. Также, на данном этапе проверка выхода за границу матрицы уже дает ощутимый вклад, поэтому еще одна оптимизация — расширить матрицу на три клетки во все стороны, заполненные нулями. Это ускоряет случайный вариант до 0.2 секунд, а наихудший — до 1 секунды, больше я ускорить не смог. Еще я проверил идею заменить произведение суммой логарифмов, но особо результат не ускорился (но и не замедлился).
Интересно, что хотя сложность задачи совершенно явно O(n*n), но для случайной матрицы, если она достаточно большая, рано или поздно найдется максимальное произведение (99*99*99*99), и дальше можно будет не искать. Учитывая, что оптимизированная версия создает матрицу построчно, скорость работы в среднем случае для случайной матрицы, похоже, будет O(n). Именно поэтому «случайный» вариант работает в 10 раз быстрее на большей матрице.
Хочу только уточнить, что избавление от повторных вычеркиваний не полное — например, число 45 = 5 * 9 все равно вычеркивается дважды: (n-1)/2 = 22 = i + j + 2ij для {i=1, j=7}, а также для {i=2, j=4}.
Если я правильно понимаю, практически любая оптимизация решета Эратосфена делает аналогичную вещь: в коде вместо
надо 1 заменить на 2 в двух местах:
и получится полный аналог алгоритма Сундарама в плане избавления от повторных вычеркиваний.
Но вы правы, можно перевести все вычисления в (n-1)/2, код получится даже проще (хотя, конечно, для понимания сложнее, чем интуитивно понятное решето Эратосфена)
Хороший пример решения задачи такого рода — исходный код Люсены: ее индекс, собственно, это набор файлов, в котором хранятся числа разных распределений. Соответственно, для каждого типа файлов они придумывают свой собственный кодек, их можно посмотреть, например, здесь.
Мне приходилось решать похожие задачи (хотя, скорее, для оптимизации хранения), я использовал комбинацию уже упоминавшихся тут приемов:
— отсортировать числа
— взять разницу между соседними (если числа разные, можно отнять 1)
— закодировать Varint encoding (7 бит на значение, восьмой бит — флаг последнего байта)
— разделить на куски и каждый кусок сжать deflate-ом (либо lz4, если нужна скорость).
Хочу только отметить, что если взять достаточно большое количество простых чисел, можно добиться произвольно большого сжатия. Я когда-то подсчитал, что для факторизации по первым четырем миллиардам простых чисел потребуется примерно 0.0225 бит на натуральное число. Однако на практике, конечно, этот алгоритм неприменим, потому что выгода начнется только для простых чисел, состоящих из триллионов (десятичных) знаков. Кроме того, размер таблицы INDEX_TO_BIT будет больше количества атомов во вселенной.
Тут есть техническая проблема: в AVX невозможно сдвинуть на 4 бита весь регистр как одно 256-разрядное число, минимум нужно делать два сдвига и одно сложение, так что ускорение будет немного меньше, чем в два раза, и код сильно усложняется, но выигрыш в скорости все равно получается существенный.
Вкупе с еще одной идеей: избавиться от временного буффера вообще, и хранить дополнительно только три линии поля (текущую, выше, и ниже) получается суммарно ускорение в 330 раз от начальной версии, от 25 до 7400 шагов в секунду!
Можно код посмотреть на гитхабе: AdvancedLifeExtensionsInLineCompressed.cs.
По поводу превосходства GPU: я когда-то пытался делать неоптимизированную реализацию на CUDA, и она оказалась сильно медленнее, чем я ожидал (медленнее вашей версии). Потом я наткнулся на эту статью, в которой утверждается, что ключ к оптимизации — расположение данных в GPU-памяти правильного типа (в идеале, в регистровой памяти).
Их производительность — 0.16 секунд на 1024 итераций на поле 16K на 16K на видеокарте GeForce GTX TITAN X. Эта разница из-за того, что видеокарты несопоставимы по производительности, или Вашу версию еще можно ускорить, если применить аналогичные трюки?