наверняка есть, так как есть глобальная база, в которую все исследователи кладут «интересные» шаблоны (найденные брутфорсом на GPU).
Или можно еще скачать программу Golly, в ней есть пара сотен шаблонов (в простом текстовом формате)
fuggy
Примерно так и работает алгоритм Hashlife, который может работать в тысячи и миллионы раз быстрее, его придумал американский програмист Bill Gosper в 1983 году. Мне не удалось достать его оригинальную статью, так что не ручаюсь за достоверность, но я слышал, что его оригинальная версия была написана на лиспе.
Это другой тип оптимизации, который может сильно ускорить «хорошие» сценарии, но сильно замедлить «плохие».
Если живых клеток на поле мало, то этот подход даст огромный эффект — можно получить ускорение и в 100 и в 1000 раз. Но если живых клеток много, то время, потраченное на проход их соседей, да еще и не в cache-friendly порядке, может замедлить алгоритм в десятки раз.
Например, на поле 1920x1080 примерно два миллиона клеток, и алгоритм, сканирующий все поле, делает два миллиона итераций.
Для какого-нибудь глайдера, в котором не больше 10 точек, алгоритм со списком будет обрабабывать за итерацию 10 + 8*10 < 100 точек, то есть, будет быстрее в 20000 раз!
Но если в начальной конфигурации поля половина клеток живая, то алгоритм со списком будет делать 9 миллионов итераций, то есть, в 4.5 раза медленнее (на самом деле, еще медленней из-за cache misses). И это только в сравнении с неоптимизированным алгоритмом.
Да, конечно, думаю, тут можно (и даже нужно!) использовать многопоточность, если мы хотим добиться максимальной производительности.
Это не отменяет пользу от однопоточной оптимизации, но согласен, про многопоточность, наверно, следовало упомянуть.
Я точно не знаю, но возможно, что так как она была придумана в 1970 году, когда персональных компьютеров не было, требовался игрок, который должен был вручню гонять симуляцию на листке в клеточку.
Я на ноутбуке (Windows 10, Intel Core i7-6700HQ) скачал Firefox и проверил количество итераций в секунду на всех скоростях на всех трех браузерах:
Я так понимаю, у них разные движки, но все равно такая разница удивительна.
Спасибо за фидбек, у меня нет опыта в UI, и для меня такие вещи не очевидны.
2х-50х примерно на одинаковой скорости работают
А какой у Вас браузер? У меня в Хроме на скорости 2x — 120 итераций в секунду, на 50x — 220. В Edge и на мобильном телефоне на всех 1x-50x скорость одинаковая — примерно 17 итераций в секунду, но, думаю, это из-за движка яваскрипта.
Я, когда готовил статью и искал интересные шаблоны, работал с Golly, но в основном на Hashlife. Я сейчас мельком посмотрел на код qlifealgo.cpp, и там тоже огромное количество оптимизаций, при чем они все равно используют quadtree, так что его скорость тоже растет с улучшением регулярности. Хотя SIMD они не используют. Я сейчас запустил его на рандомно заполненном поле размера 1920x1080 с коэффициентом 0.5 (то есть, примерно половина клеток — живые, половина — мертвые), и за первую секунду он обработал 1000 итераций, за вторую — уже 10000, и на статической картинке скорость стабилизировалась где-то на 50000 в секунду. На картинке из КПДВ он работает стабильно примерно со скоростью 5000 в секунду.
Согласен, это тоже классическая оптимизация, которую было бы неплохо применить. Я, честно говоря, поленился: суммарно оба массива не превышают одного мегабайта, и должны помещаться в кеш третьего уровня, так что копирование должно быть быстрым по сравнению с довольно большим количеством логических операций. Но так как эта оптимизация не усложняет код, то кажется логичным ее применить, даже если она даст только 10% выигрыша.
А как лучше эту проблему решить? Просто уменьшить размер поля на высоту панели? или скриптом проверять размер экрана и скейлить канвас? или можно как-то подобрать значение meta name=«viewport», чтобы браузер сам все за нас сделал? Я имеюю в виду даже не технический аспект, а юзабилити — какой способ даст наиболее логичное с точки зрения пользователя поведение?
да, это тот самый Hashlife, я его упомянул в статье. Интересно было бы попробовать применить вышеописанные оптимизации к нему (исключительно для саморазвития: эту игру люди исследуют уже 50 лет, и все, что можно было оптимизировать, думаю, уже давно соптимизировали)
Или можно еще скачать программу Golly, в ней есть пара сотен шаблонов (в простом текстовом формате)
Доказано, что плотность может превышать 50%
Примерно так и работает алгоритм Hashlife, который может работать в тысячи и миллионы раз быстрее, его придумал американский програмист Bill Gosper в 1983 году. Мне не удалось достать его оригинальную статью, так что не ручаюсь за достоверность, но я слышал, что его оригинальная версия была написана на лиспе.
Если живых клеток на поле мало, то этот подход даст огромный эффект — можно получить ускорение и в 100 и в 1000 раз. Но если живых клеток много, то время, потраченное на проход их соседей, да еще и не в cache-friendly порядке, может замедлить алгоритм в десятки раз.
Например, на поле 1920x1080 примерно два миллиона клеток, и алгоритм, сканирующий все поле, делает два миллиона итераций.
Для какого-нибудь глайдера, в котором не больше 10 точек, алгоритм со списком будет обрабабывать за итерацию 10 + 8*10 < 100 точек, то есть, будет быстрее в 20000 раз!
Но если в начальной конфигурации поля половина клеток живая, то алгоритм со списком будет делать 9 миллионов итераций, то есть, в 4.5 раза медленнее (на самом деле, еще медленней из-за cache misses). И это только в сравнении с неоптимизированным алгоритмом.
Это не отменяет пользу от однопоточной оптимизации, но согласен, про многопоточность, наверно, следовало упомянуть.
Я так понимаю, у них разные движки, но все равно такая разница удивительна.
Вы имеете в виду с целью выяснить умение пользоваться JOIN, или в данном случае у него есть преимущества над EXCEPT?
А в данном случае нельзя использовать EXCEPT?
А какой у Вас браузер? У меня в Хроме на скорости 2x — 120 итераций в секунду, на 50x — 220. В Edge и на мобильном телефоне на всех 1x-50x скорость одинаковая — примерно 17 итераций в секунду, но, думаю, это из-за движка яваскрипта.