Я точно не знаю, но возможно, что так как она была придумана в 1970 году, когда персональных компьютеров не было, требовался игрок, который должен был вручню гонять симуляцию на листке в клеточку.

Я бы из них тогда попробовал ILGPU — она OpenSource и, вроде как, не требует сложной настройки.

Вроде пока еще на стадии proposal

Я на ноутбуке (Windows 10, Intel Core i7-6700HQ) скачал Firefox и проверил количество итераций в секунду на всех скоростях на всех трех браузерах:

Я так понимаю, у них разные движки, но все равно такая разница удивительна.

попрошу переделать на JOIN

Вы имеете в виду с целью выяснить умение пользоваться JOIN, или в данном случае у него есть преимущества над EXCEPT?

Правильный ответ будет, разумеется, содержать не просто JOIN, но LEFT JOIN со сравнением значения на NULL.

А в данном случае нельзя использовать EXCEPT?

(select id from groups) except (select group_id from students)?

Спасибо за фидбек, у меня нет опыта в 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 лет, и все, что можно было оптимизировать, думаю, уже давно соптимизировали)

Можно даже дальше пойти: разбить плоскость на квадраты и кешировать результат итераций для каждого квадрата. Собственно, эта идея лежит в основе того самого Hashlife.

Сейчас проверил (deflate, normal compression) сжался с 3.2 гб до 2.1, я, честно говоря, не ожидал

А исполнялась программа под 64-битную ява машину или 32-битную? В 32-битных процессах длинная арифметика медленнее, так как 64-битные регистры процессора недоступны.
Хотя я согласен, битовая арифметика будет замедляет алгоритм в любом случае.
Теоретически, если искать простые числа не в одном большом массиве на гигабайты, а разделить его на куски по несколько мегабайт, чтобы весь битовый массив поместился в кеш третьего уровня, может, тогда ускорение доступа к памяти может исправить замедление от битовых операций.

Можете подробнее про Ваш вариант рассказать?
Оптимизация таких числодробилок иногда бывает очень нетривиальна. У меня, например, скорость увеличивается в полтора раза, только если закомментарить строку if (n >= Length) throw new ArgumentException(«Number too big»);
Возможно, она как-то препятствует jit-у инлайнить метод, не изучал вопрос.

Кстати, получить итератор по всем простым числам в возрастающем порядке (самый частый use-case) можно эффективнее, чем проверять на простоту числа последовательно от 1 до ста миллионов (используя, как раз, массив BIT_TO_INDEX), просто я старался сделать код как можно проще, даже ценой ухудшения производительности.

В первой задаче про аналитика дроби же сокращаются:
1) P = 1 — ( 1/2 * 2/3 * 3/4 *… * 89/90 * 90/91 ) = 1 — 1/91 = 90/91 ~ 0.989
2) P = 1 — ( (1*3)/(2*2) * (2*4)/(3*3) * (3*5)/(4*4) *… * (89*91)/(90*90) * (90*92)/(91*91) ) = 1 — 1/2 * 92/91 = 45/91 ~ 0.495

Можно сжать, если проверять на простоту с помощью МТФ — хранить только те, которые не являются простыми но проходят проверку.

Нашел в Викпедии, что Baillie–PSW primality test, который является комбинацией двух вероятностных тестов на простоту (Ферма и Лукаса), вообще не имеет исключений для 64-битных чисел. Больше того, даже для произвольно больших чисел за сорок лет ни одного исключения так и не нашли. Так что Ваша идея тут кстати: размер базы будет нулевой практически всегда. А если вдруг кто-нибудь найдет составное число, проходящее этот тест, он даже получит премию в 30 долларов!
А из более поздних исследований нашел эту статью 2015 года — они утверждают, что их алгоритм самый быстрый (скорость проверки — чуть больше миллиона 64-битных чисел в секунду) из класса алгоритмов, не требующих предварительных вычислений.
Забавно, но я у них нашел такую цитату:

If we expect that we’ll need to test a significantly large number of small integers for primality, the best solution might be precomputing all possible answers
and then answering each query in constant time. The canonical implementation
uses one bit for each odd number, i.e., 2b/16 bytes of memory if the valid inputs are b-bit integers

То есть, они тоже считают, что для некоторых случаев битовая таблица — лучшее решение, но даже они говорят о бите на каждое нечетное число! Хотя Wheel factorization широко известен, почему-то даже ученые его игнорируют при практическом применении

Вы абсолютно правы, у меня в изначальной версии был именно ulong[]. Просто я не упомянул еще некоторые неудобства:
1) массив байт можно сохранить в файл одним вызовом File.Write
2) в .NET Framerork массив ulong-ов все равно просто так не создать
3) если мы захотим считать простые числа, например, до триллиона (вдруг у нас есть 30 гб памяти), массив ulong сам станет больше двух миллиардов элементов.

логичнее использовать RAM-машину

Понятно, спасибо. Я почему-то думал, что MT — это обобщенное название класса машин, эквивалентных классической MT с одномерной лентой.

Верхняя планка чисел всегда ограничена количеством памяти на компьютере и разрядностью. Поправьте меня, если я ошибаюсь, но стандартная de-facto вычислительная модель, если не оговорено обратное — машина Тьюринга, что эквивалентно компьютеру с бесконечным количеством памяти.