Подробности

    ЦифроМахИгры и ГоловоломкиГоловоломки → Как ускорить темп "жизни"?

    Как ускорить темп "жизни"?

    что такое жизнь

    Чтобы не обременять читателя, в дальнейшем условимся называть этот автомат просто игрой Жизнь. О правилах этой игры написано немало, поэтому мы не будем останавливаться на них, а сразу перейдём непосредственно к теме этой статьи. Тем же, кто либо не знает правил, либо просто хочет прочитать ещё раз о них, можем порекомендовать книгу [1], с которой, пожалуй, начинали все “жизнелюбы”, или книгу [4].

    Идея применения вычислительных машин для слежения за ходом игры – не нова. Сам Джон Хортон Конвей использовал компьютер для наблюдения за причудливыми конфигурациями своего детища. Без моделирующих программ увидеть большинство интереснейших превращений, происходящих по ходу игры, было бы просто невозможно. Некоторым вопросам написания таких программ и посвящена данная статья.

    Итак, с точки зрения программирования, Жизнь – трудоёмкая, для компьютера, задача, так как требует довольно больших ресурсов машины на непрерывный пересчёт состояний моделируемого мира (под “миром”, здесь и далее, будет пониматься плоскость, разбитая на клетки, на которой рассматривается колония). В чём же этот пересчёт заключается? Фактически, на каждой итерации нужно разрешать отношение соседства между конкретными объектами, то есть, уметь узнавать, сколько у него соседних клеток. Эта статья и посвящена именно тому, как это сделать максимально эффективно (ясно, что вариант полного перебора мест гипотетической дислокации клеток мы рассматривать не будем, тем более, что его применение проблематично на “бесконечных” полях, которые и представляют основной интерес при моделировании процесса Жизни). Далее под “местами” будем понимать позиции, на которых могут стоять клетки, элементарную область в рассматриваемом мире (“A” на рисунке 1), а под “клетками” – места, в которых есть жизнь (“B” на том же рисунке).

    “Объектами” будем называть “клетки” и “места”. Эту терминологию лучше запомнить, так как она будет постоянно использоваться.

    Конечно, приведённые здесь методы не претендуют на то, чтобы быть истиной в высшей инстанции, и автор с удовольствием будет общаться с людьми, которые поделятся с ним своими мыслями по этому поводу.

    Любой мало-мальски серьёзный проект начинается с продумывания и организации структур данных, необходимых при решении задачи. Первая дилемма, встающая перед нами – хотим мы использовать динамические или статические структуры для хранения информации о клетках. Под статическими структурами имеется в виду, конечно, массив. Очевидно, недостатков у этого метода представления данных – более чем достаточно. Хватит даже одного: размеры популяции (число клеток в ней) неизбежно будут ограничены. Зачем же он нужен? Метод, основанный на использовании массива, программируется, пожалуй, проще, чем любой другой. Иногда Жизнь реализуют в декоративных целях: неплохая экранная заставка – развитие случайно сгенерированной популяции на поле, скажем, в 1024 на 768 мест, то есть, по пикселю на место. Зачем в такой программе трудиться над списками или другими динамическими структурами? Кроме того, здесь – тривиальный способ ускорения разрешения отношения соседства – сортировка.

    1. Сортировка

    Итак, пусть нам дан массив на m элементов некоторой структуры, LifeCell, содержащей два информационных поля. Допустим, такой структуры:

    struct LifeCell

    {

    int x, y;

    };

    Будем хранить в нём информацию о существующих клетках на данный момент времени. То есть, если место с координатами x0 и у0 является клеткой, то в массиве должен присутствовать элемент, имеющий поля со значениями x0 и y0. Пусть на данном шаге моделирования у нас будет заполнено n элементов. Так как размеры популяции, как правило, не постоянны во времени, то n будет меняться от итерации к итерации. Вот вам и очевидное ограничение: n не может превосходить m!

    Как происходит разрешение отношения соседства для объекта с координатами x0, y0? Для него нам нужно найти в массиве все соседние клетки (смотрите рисунок 2), тогда остальные его соседи являются местами. Обращаем Ваше внимание на то, что такой поиск нужно производить не только для n клеток, которые содержатся в массиве, но и для всех окружающих их объектов, то есть именно, для ближайших восьми соседей, так как это – места гипотетического возникновения жизни. Таким образом, на каждой итерации придётся разрешать отношение соседства для 9*n объектов (n клеток, у каждой – 8 соседей).

    Как сделать это максимально эффективно? Конечно, отсортировав массив по возрастанию (или по убыванию) одной из координат, скажем, по y. Тогда будет достаточно только пробежать в массиве интервал ячеек, для которых значения y-координат элементов будут заключены между y0-2 и y0+2. Остальные клетки рассматривать уже бессмысленно, так как они слишком далеки от нашего объекта. Затем нужно перейти к следующему объекту или следующей ячейке массива. Разрешать отношения соседства в строгом порядке, установленном расположением ячеек в массиве – очень рационально. Поступаем так: рассмотрели соседей клетки, содержащейся в ячейке массива с номером i, рассмотрели соседей её соседей – перешли к следующей (к (i+1)-ой). Тогда счётчик (индекс) обрабатываемой ячейки i поможет нам рассмотреть весь вышеописанный интервал и будет достаточно просто “пройтись” от i-ой ячейки вправо и влево по массиву до тех пор, пока y-координаты клеток не будет отличаться от y-координаты рассматриваемого объекта на два.

    Здесь, вообще говоря, нужно организовать просмотр так, чтобы не приходилось по несколько раз учитывать одни и те же клетки, ведь любая из них – соседка своего соседа, но в рамках этой статьи методы преодоления этой проблемы мы рассматривать не будем, так как она имеет лишь косвенное отношение к непосредственной тематике статьи.

    После того, как с соседями станет всё ясно, вносим в массив необходимые изменения, и, перед переходом на следующую итерацию, лишь сортируем его. Для этого можно использовать, например, алгоритм QuickSort, предложенный в 1962 году английским математиком Чарльзом Хоаром (его ещё можно встретить под названием “быстрая сортировка”). Для его изучения, можем порекомендовать книгу [2], где есть много интересной информации об алгоритмах сортировки вообще (на самом деле – и не только сортировки, а практически всех базовых алгоритмов, в том числе и упоминаемых далее в этой статье) и QuickSort, в частности.

    Опыт показывает, что сортировка внутри групп с одинаковыми y-координатами по x-координатам даст ощутимый эффект лишь при достаточно больших размерах популяции. Тем не менее, иногда, это всё же имеет смысл и тогда по x-координатам стоит проводить поиск дихотомией (“двоичным поиском”). Описание этого алгоритма, как, кстати, и алгоритма QuickSort, можно найти, например, в книге [3].

    От статических структур переходим к динамическим. Как Вы понимаете, сортировать список – не лучшая идея. Несмотря на то, что существует множество алгоритмов для этого, но сочетать динамические структуры, с тем же методом, который мы использовали для статических – не разумно, так как его реализация будет намного более сложной. Однако, справедливости ради, необходимо отметить, что трудоёмкость “ленточной сортировки” (метода упорядочивания списков) такая же, как и у QuickSort’а, то есть O(N*ln(N)), где N – число сортируемых элементов. Но к динамическим структурам применимо такое мощнейшее средство, как хеширование.

    2. Стандартные принципы хеширования и их применение к Жизни

    Хеширование (от английского “hash” – “размешивать”) служит для оптимизации задач обработки информации, а конкретнее, преимущественно, для интересующего нас поиска (для нас важна именно эта операция, ведь как бы мы не организовали хранение информации, по всему её объёму, придётся искать соседей некоторого объекта).

    Метод хеширования позволяет производить это более эффективно. Его принцип заключается в разбиении всего набора данных на маленькие группы, с которыми быстрее оперировать. Для этого информационным полям конкретной структуры, сопоставляется значение некой функции. Так называемой, хеш-функции. Разбиение на группы, “размешивание” информации, происходит по признаку равенства этого значения (оно ещё называется ключом). Нужно стремиться к тому, чтобы группы были приблизительно одинаковыми по величине. Когда мы знаем содержимое полей структуры, которую хотим найти и можем произвести подсчёт ключа для неё, то после этого, искать точное совпадение требуемых полей нужно уже не по всему набору данных, а лишь в рамках группы, отвечающей конкретному полученному значению хеш-функции. В худшем случае, хеширование приведёт к обычному поиску полным перебором (справедливости ради надо отметить, что так будет лишь с точки зрения трудоёмкости, на практике получится ещё медленнее из-за “холостого прокручивания” механизма хеширования). Но для этого нужна поразительно неудачная хеш-функция, выдающая одинаковые значения ключа для всех объектов-структур, содержащихся в наборе данных, по которому производится поиск. Подробности об этом методе можно найти в, уже упоминавшейся в этой статье, книге [2].

    Достаточно эффективный способ применения такого метода – организация массива указателей на списки. Каждый из этих списков содержит структуры, значения хеш-функции для которых одинаково (это – вышеописанные группы), а индекс ячейки массива, содержащей указатель на данный список, равен её значению (этот способ будет широко использоваться в следующих параграфах). Также, вполне благоприятен вариант, когда индекс равен некоей функции от её значения. Ведь, например, в языках C/C++ массивы индексируются от нуля, и если наша хеш-функция принимает целые значения от 7, то функция преобразования индекса должна будет вычитать из получающегося ключа семёрку. Впрочем, эту функцию преобразования, в таком случае, имеет смысл включить в процедуры подсчёта хеш-функции.

    Итак, возвращаясь к нашему примеру, продолжим рассмотрение данных, хранящихся в объектах вышеописанного типа LifeCell. Теперь, когда нам понадобится посмотреть, является ли клеткой место (x0+1;y0-1), мы сосчитаем хеш-функцию от данных значений полей, а потом поищем информацию о ней не среди всех клеток, а среди лишь членов списка, для которых она имеет то же значение.

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

    Очень часто в качестве хеш-функций применяются битовые операции. Пусть x, y и ключ занимают по одному байту, тогда последний можно по битам составить так, как показано на рисунке 3. Если целого байта под ключ жалко, то можно использовать четыре бита, как предложено на рисунке 4 (для обоих рисунков будем считать, что младший бит – слева). Конечно, эффективность этого метода зависит от набора данных, на котором он используется. Скажем, точки (255;0), (150;45), (166;37), (200;139) размешаются хеш-функцией, изображённой на рисунке 3 хорошо, все – в разные списки, а точки (85;239), (117;238), (87;171), (213;170) – все в один.

    На самом деле, нет никаких принципиальных ограничений на используемые хеш-функции, кроме границ здравого смысла. Помимо побитовых преобразований, это могут быть просто математические функций или композиции тех и других. Но не надо слишком мудрствовать. Надеемся, например, синус суммы x и y вряд ли кто-нибудь будет использовать в качестве хеш-функции, по крайней мере, применительно к Жизни.

    Ключ должен быть достаточно короток, чтобы расходы на него были позволительны и в то же время, достаточно длинен, чтобы хорошо “размешивать” данные (чем больше мощность множества значений ключа, тем больше разных групп можно составить, тем меньше в них будет элементов (но хотелось бы, чтобы они всё же были в каждой группе и, чтобы их количество для всех групп было почти одинаковым или хотя бы одного порядка) и тем быстрее по ним будет производиться поиск).

    Изображённые на рисунках 3 и 4 модели получения ключа по полям LifeCell используют некие общие соображения теории хеш-функций, абстрагируясь от специфики задачи. Как было указано выше, есть наборы клеток, которые эти функции размешают крайне плохо. Давайте всё-таки вспомним, что мы моделируем именно Жизнь.



  • Первое решение

    Если бы мы с самого начала воспользовались этим рецептом, то смогли бы сразу же поставить единицу в четвертый столбец, двойку - в четвертую строку, седьмой столбец и правый средний квадратик 3x3, а цифру 9 - в первый столбец и левый средний квадратик

     
  • Источник: http://arbuz.uz