>К чему формула, если узнать из нее ничего не удасться?
Насколько я видел, вообще определение априорной вероятности в байесовской статистике для практически любой задачи является самым слабым местом: иногда ее можно задать «из общих соображений», но в общем случае непонятно, откуда ее брать. Например, Википедия упоминает 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. Эта разница из-за того, что видеокарты несопоставимы по производительности, или Вашу версию еще можно ускорить, если применить аналогичные трюки?
Вы имеете в виду, фигура, как на КПДВ? Вообще-то это твердый знак (ну, по крайней мере задумывался).
Нету смысла искать оптимальную стратегию в обычном тетрисе — известно, что он проходится до момента, пока не встретится какое-то количество z- и s- фигурок в определенной последовательности. Вот я и добавил фигурку, которая все «портит», чтобы вручную его тоже было сложно пройти — я, например, дальше компьютера не смог.
Спасибо! Было бы интересно, чего можно достичь на не-топовых FPGA.
Вообще интересно, чего можно достичь на разных технологиях за разные деньги. Я по сумме всех комментариев понял примерно так (плюс-минус порядок):
— процессор ($1'000) — 50'000 итераций в секунду
— видеокарта ($1'500) — 500'000 итераций в секунду
— FPGA ($15'000) — 50 миллионов итераций в секунду
— ASIC ($1'500'000) — 1 миллиард итераций в секунду
А это чисто физически можно сделать на двумерной схеме? Ведь у каждой клетки будет свой сумматор, и надо будет к нему тянуть линию от всех восьми ее соседей.
Круто! Получается, скорость будет ограничена только пропускной способностью канала памяти? После Вашего комментария полез искать, пользуются ли FPGA для ресёрча, и нашел, что пользуются, но, похоже, это единичные случаи.
Два вопроса по этому поводу (чисто теоретических):
1) Нашел в гугле, что есть FPGA Virtex-7 2000T с двумя миллионами ячеек; в нем можно сделать симуляцию игры не в памяти, а напрямую в этих ячейках? Или топология не позволяет?
2) Может быть, можно сделать специализированную микросхему с двумя мегабайтами SRAM, и к каждой ячейке прикрутить трехбитный сумматор? Тогда теоретически можно добиться по одной итерации на такт?
Ваш комментарий верен в общем случае, но при обходе двумерного массива внутренний цикл должен быть по второму индексу, так что в данном случае этот порядок правильный, можете поменять местами и проверить. Тут скорее проблема в том, что массив определялся как new bool[WIDTH, HEIGHT], хотя надо было бы длину и ширину поменять местами.
Насколько я видел, вообще определение априорной вероятности в байесовской статистике для практически любой задачи является самым слабым местом: иногда ее можно задать «из общих соображений», но в общем случае непонятно, откуда ее брать. Например, Википедия упоминает 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. Эта разница из-за того, что видеокарты несопоставимы по производительности, или Вашу версию еще можно ускорить, если применить аналогичные трюки?
Нету смысла искать оптимальную стратегию в обычном тетрисе — известно, что он проходится до момента, пока не встретится какое-то количество z- и s- фигурок в определенной последовательности. Вот я и добавил фигурку, которая все «портит», чтобы вручную его тоже было сложно пройти — я, например, дальше компьютера не смог.
Вообще интересно, чего можно достичь на разных технологиях за разные деньги. Я по сумме всех комментариев понял примерно так (плюс-минус порядок):
— процессор ($1'000) — 50'000 итераций в секунду
— видеокарта ($1'500) — 500'000 итераций в секунду
— FPGA ($15'000) — 50 миллионов итераций в секунду
— ASIC ($1'500'000) — 1 миллиард итераций в секунду
Два вопроса по этому поводу (чисто теоретических):
1) Нашел в гугле, что есть FPGA Virtex-7 2000T с двумя миллионами ячеек; в нем можно сделать симуляцию игры не в памяти, а напрямую в этих ячейках? Или топология не позволяет?
2) Может быть, можно сделать специализированную микросхему с двумя мегабайтами SRAM, и к каждой ячейке прикрутить трехбитный сумматор? Тогда теоретически можно добиться по одной итерации на такт?
Если кому интересно, простой поиск по коду Linux находит дофига и переменных temp, и копирования в и из них