кстати, малость оффтоп, но есть ли наилучший алгоритм реализации этой штуковины (я про алгоритм самой "Жизни")?
varnie Блин, я дал линку прежде всего таким как я, которые не до конца понимают силу ком.строки никсов, что не зачем писать приложения, когда можно и через ком. строку! Меня лично поразило!
Nothing, в смысле наиболее оптимизированный и грамотный. ну, вы меня поняли EvilsInterrupt, это я усек.
varnie самый-самый, говорите... Сам алгоритм уже давно свели к табличным преобразованиям. В смысле, что и число соседей и новое поколение просто вычисляется по большой таблице, а основной цикл состоит в линейном чтении очередной строки ячеек и по таблице вычисления их новых значений. Соседи при этом корректно подсчитываются начиная с 3-ей обработанной строки и дальше с каждой новой. Размер таблицы зависит от максимальной длины строки, как ее строить - я думаю примерно понятно. Ну и соответственно преобразования параллелят (по 2 или 4 ячейки за раз, это зависит от доступной памяти). Чтобы не обрабатывать все поле, размеры которого обычно огромны, обрабатывают лишь те места, где еще теплится "жизнь" плюс по одной клетке со всех сторон как минимум (перечень таких "областей" хранится в 2d-дереве, причем области эти могут распадаться и объединяться, что с помощью 2d-дерева и организуется). Дальнейшие оптимизации включают в себя детектирование наиболее часто встречающихся комбинаций и/или предварительное преобразование поля (прямо как в сжатии) и исключение каких-то частей из обработки, т.к. их эволюция очевидна до момента столкновения с другими объектами. Чаще всего в этот список попадают простые флип-флопы с периодом 2, неподвижные объекты и планеры. Ес-но, как и в сжатии, предварительные преобразования тоже стараются делать табличными и линейными. Кстати, иногда таким образом удается перепрыгнуть не на 1 итерацию вперед, а сразу на несколько. Низкоуровневых оптимизаций для современных P4/Athlon я не видал, хотя говорят можно что-то с помощью SSE2 замутить (последнее что я видел использовало только MMX). Вобщем сам алгоритм примерно таков. Хотя у меня где-то валялась игра жизнь (с выводом на экран) в 72 байтах
перевод. может не достаточно красивый, но суть передаёт: http://amty.narod.ru/rootless-root.pdf [add] О! поставил latex2html поновее, он сожрал это, вроде правильно, так что можно и http://amty.narod.ru/rootless-root/index.html
