Сейчас всё уже немного иначе. Когда я стал разработчиком, то сам задавал вопросы и оценивал ответы. Потом меня перевели на руководящую должность, и теперь моё дело – выслушивать впечатления разработчиков после собеседования и принимать решение о найме. Так что я видел процесс со всех возможных сторон, и в этой статье хотел бы поделиться частью своего опыта.
Для этой цели я разберу реальную задачу, которую мы раньше предлагали желающим присоединиться к Reddit, пока не решили, что ей пора на покой. Объяснив решение, я расскажу о том, что учитывалось при оценке и почему это задание кажется мне подходящим для собеседований. Надеюсь, к концу статьи вы подойдете с чувством, что узнали больше о механизмах отбора и стали лучше подготовлены к процессу найма.
Игра «Жизнь»
Представьте, что у вас есть поле с клетками размером M на N клеток, и каждая клетка находится в одном из двух состояний: живая или мертвая. Распределение клеток на поле называется состоянием, и наша задача – просчитать расположение клеток в следующем состоянии исходя из следующего набора правил:
- Соседи: у каждой клетки может быть восемь соседей (сверху, снизу, справа, слева и по диагонали).
- Изоляция: живая клетка, у которой только один живой сосед или они вообще отсутствуют, погибнет в следующем состоянии поля.
- Выживание: живая клетка, у которой ровно два или три живых соседа, выживет в следующем состоянии поля.
- Перенаселение: живая клетка, у которой четыре и больше живых соседей, погибнет в следующем состоянии поля.
- Воспроизводство: мертвая клетка, у которой ровно три живых соседа оживет в следующем состоянии поля.
По часовой стрелке: воспроизводство — перенаселение — изоляция — выживание
Если повторять эти вычисления раз за разом, становится всё более и более интересно.
Целая ветвь информатики посвящена изучению подобных схем. Но давайте сейчас сосредоточимся на имплементации.
Задача у кандидата такая: у него есть массив массивов, представляющий состояние поля (где 'x' обозначает состояние живая, а ' ' – состояние мертвая), и нужно рассчитать следующее состояние.
Мне очень нравится эта задача. Как мы потом увидим, с точки зрения алгоритмов она не такая сложная, как некоторые другие, которые я описывал ранее. Сложность заключается по большей части в имплементации, и я полагаю, что любой, кто имеет представление о массивах и управляющих структурах с ней справится. Это отличное задание для стажеров, и довольно незатейливое для тех, кто идет на полную ставку.
Решение: часть первая
Давайте разберемся со сложностями имплементации. Задачу можно разбить на две части: сначала мы вычисляем состояние каждой новой отдельной клетки (живая или мертвая), а потом с опорой на эти расчеты просчитываем состояние всего поля.
Я упоминаю об этом вскользь, но на самом деле, то, что кандидат способен опознать и разделить эти два этапа, уже говорит в его пользу. Некоторые рубят сплеча и пытаются решить обе задачи одновременно – это не то чтобы плохо, но гораздо труднее. Здесь есть парадоксальный момент: разделение на две задачи упрощает имплементацию, но на практике оказывается сложнее, потому что требует концептуального рывка, который должен подсказать опыт.
Так или иначе, первая часть решения выглядит примерно так:
LIVE_CELL = 'x'
DEAD_CELL = ' '
def update_cell(board, row, col):
# Счётчик соседних живых клеток
neighbor_count = 0
for row_offset in (-1, 0, 1):
for col_offset in (-1, 0, 1):
if row_offset == 0 and col_offset == 0:
continue
new_row = row + row_offset
if new_row < 0 or new_row >= len(board):
continue
# Исходя из предположения, что у всех рядов одинаковая
# длина, проверяем выход за границы поля.
new_col = col + col_offset
if new_col < 0 or new_col >= len(board[0]):
continue
if board[new_row][new_col] == LIVE_CELL:
neighbor_count += 1
elif board[new_row][new_col] != DEAD_CELL:
raise ValueError('invalid cell value')
if board[row][col] == LIVE_CELL:
# Нет ни перенаселенности, ни изоляции
if not (neighbor_count <= 1 or neighbor_count >= 4):
return LIVE_CELL
elif neighbor_count == 3:
# Воспроизводство
return LIVE_CELL
return DEAD_CELLТут часто допускают несколько ошибок:
- Не проводят проверку границ при пересчете соседей и уходят за пределы поля. Этого можно избежать путем проверки номера ряда, который подвергается оценке на текущем этапе: он должен быть больше нуля и строго меньше предельного значения для размеров поля.
- По ошибке определяют клетку как своего собственного соседа. Этого можно избежать, если пропускать клетки, у которых смещение равно нулю и в пределах столбца, и в пределах ряда.
- Допускают логические ошибки при реализации логики. Здесь может помочь только практика.
Решение: часть вторая (неверная)
Теперь нам нужно вызвать метод, чтобы осуществить обновление. И вот здесь-то и кроется подвох. Самое наивное решение – итерировать на одной клетке за другой, определять для каждой, будет ли она живая или мертвая на следующем этапе, и тут же обновлять состояние.
def update_state_wrong(board):
for row in range(len(board)):
for col in range(len(board[0])):
board[row][col] = update_cell(board, row, col)
return board«Что здесь не так?» – спросите вы. Проблема в том, что в ходе обновления у вас перемешиваются значения, которые относятся к старому состоянию доски, и значения, которые относятся к новому состоянию. По сути, значения из нового состояния попросту уничтожают информацию: старое состояние больше для вас недоступно, потому что вы только что заменили исходное значение новым!
Только что обновленные — Еще не обновленные
Решение: часть третья (верно, но накладно)
Самое простое решение оказывается и самым нехитрым: вы попросту создаете копию поля в его старом состоянии, считываете данные оттуда и вписываете на новое поле. На Python можно использовать модуль copy, чтобы без лишних сложностей сделать дубликат.
def update_state_slow(board):
import copy
old_board = copy.deepcopy(board)
for row in range(len(board)):
for col in range(len(board[0])):
board[row][col] = update_cell(old_board, row, col)
return boardЭто нормальное решение, верное и рабочее. Однако давайте попристальнее взглянем на паттерны доступа к старому полю в процессе вычислений. Допустим, мы рассчитываем состояние клетки, отмеченной звездочкой.
Старое поле — Новое поле
Для нас имеют значение только те клетки, которые выделены на рисунке красным цветом. Те клетки, которые закрашены серым, вообще никогда больше не будут рассматриваться. Для вычислений они абсолютно бесполезны. Остальные клетки, которые мы еще не прочитывали, дублируются со старого поля на новое. Большая часть памяти, которая используется для хранения данных о старом поле, тратится впустую: эти данные либо никогда не понадобятся в будущем, либо их можно получить из другого источника.
Можно сказать, что это не слишком существенно, и, честно говоря, если бы кандидат здесь остановился, я бы не стал считать это за минус. То, что он сумел дойти до этого этапа в стрессовых условиях собеседования – уже неплохой знак. Но в реальности неоптимальные решения такого рода сказываются. Когда объем входных данных достигает определенного уровня, ненужный расход ресурсов может подорвать работоспособность системы, которая во всех остальных отношениях сделана верно и качественно. Я ставлю плюс кандидатам, которые отмечают это расточительство и хотя бы в общих чертах описывают, что с ним делать.
Решение: часть четвертая (верно и более-менее оптимально)
Если присмотреться, то всё, что нам действительно необходимо копировать – это текущий ряд, и тот, который идёт перед ним: данные из более «старых» рядов уже не будут прочитываться, более «новые» ряды пока что не нужны. Один из способов имплементации такого подхода – брать данные только со старого поля, переписывание осуществлять во временной локации, а на поле замену клеток производить только в тех рядах, которые совершенно точно больше читаться не будут.
Ряды с нового поля — Ряды со старого поля — Временные ряды, которые вскоре заменят ряды в той же позиции на старом поле
Имплементация этого подхода выглядит приблизительно так:
def update_state_correct(board):
# Сохраняем предыдущий ряд, чтобы обновить его позже.
previous_row = None
for row in range(len(board)):
current_row = []
# Записываем все обновления во временный ряд.
for col in range(len(board[0])):
current_row.append(update_cell(board, row, col))
# Если в предыдущем ряду появились изменения, переносим новую версию на поле.
if previous_row:
board[row - 1] = previous_row
# Записываем все изменения в текущем ряду,
# чтобы произвести замену в следующей итерации.
previous_row = current_row
# Не забываем обновить последний ряд!
# Это очень распространенная ошибка.
if len(board) > 1:
board[-1] = previous_row
return boardЭто решение приближается к оптимальному: временные данные ограничиваются двумя рядами вместо целого поля. Строго говоря, оно всё-таки недотягивает до идеала, так как мы храним данные в переменной previous_row, которая гипотетически может быть изменена при обходе. Однако данное решение, в целом, удовлетворяет требованиям, а альтернативное сопряжено с большими сложностями, так что оставляю усовершенствования на откуп читателям.
Дополнительная часть: отрываемся по полной
На этом можно было бы остановиться, но с какой стати? Предлагаю читателям еще одну задачу со звездочкой: задумайтесь о проблеме до смешного огромных полей. Что если у вас на поле не несколько сотен клеток, а триллионы? Что если только очень небольшой процент клеток в каждый конкретный момент имеет состояние живая? Что вы тогда измените в решении? На ум приходят несколько дополнительных соображений:
- Имплементации, которые я предлагал, предполагают плотную матрицу, то есть в них представлены в виде значений и живые, и мертвые клетки. Если большая часть поля пуста, прописывание пустых клеток будет отнимать неоправданно много ресурса. Как бы вы спроектировали разреженную матрицу, в которой прописаны только живые клетки?
- Входные данные замкнуты в границы, за которыми нельзя ни считывать, ни прописывать состояние клеток. Сможете продумать имплементацию без границ, чтобы можно было прописывать состояние клеток, которые располагаются на любом участке поля независимо от его удаленности?
- Предположим, вы проводите вычисления для такого количества клеток, что одной машине с ними справится нереально. Как бы вы равномерно разделили вычисления по узлам? Имейте в виду, что в ходе многочисленных итераций, мертвые клетки, которые раньше располагались в отдалении от живых, могут тоже «оживать» по мере сближения.
Примечания
Ну, вот и вся задача. Если за сорок пять минут собеседования вы дошли до третьей части, я бы, вероятно, решительно вас рекомендовал на должность стажера и определил как подходящего кандидата на полную ставку. Забавно, но когда я проходил одно из собеседований в Google, куда устраивался на стажировку, мне дали эту самую задачу. Я быстро дошел до третьей части имплементации; уже не помню, реализовал ли четвертую или просто перечислил ее преимущества, но в итоге меня приняли.
Задача нравится мне как раз тем, что она не слишком сложная с точки зрения алгоритмов. Среди тех, кто занимается наймом, да и в IT-сообществе в целом, сейчас ведутся конструктивные дискуссии о том, какой уровень сложности следует выдерживать на собеседованиях. Использование задач такого типа, по сути, косвенно выражает мою позицию (и позицию Reddit) по этому вопросу.
Точки зрения в этой дискуссии обычно озвучиваются такие. С одной стороны, более сложные задания позволяют отобрать, самых способных кандидатов, а значит, и команда будет сильная. Если кандидат даже в стрессовых условиях может справиться со сложным заданием, значит, у него, скорее всего, достаточно знаний и интуиции и для любых рабочих ситуаций. Тут работает логика в духе «если пробился сюда, значит, и здесь пробьешься».
С другой стороны, со сложными задачами можно слишком зациклиться на одном знании алгоритмов, оставляя без внимания мастерство, мягкие навыки и интуицию в программировании, которая с трудом поддается измерению. К тому же, так мы рискуем захлопнуть двери перед людьми, у которых пришли в IT нетрадиционными путями, предлагая им задания, по сути, требующие академических знаний.
Мне кажется, задачи вроде этой выдерживают разумный баланс между двумя позициями: они просты для понимания, но трудны, когда дело до доходит до решения. Здесь нужны развитые навыки имплементации и оптимизации, а не просто озарение, какие из алгоритмов применить. Кроме того, в процессе найма кандидату часто предлагается несколько заданий, и каждое из них нацелено на проверку определенных умений. Результатов какого-то одного собеседования недостаточно, чтобы принять решение о найме, а вот целая серия откликов в духе «подходит» и «надо брать» показывает, что у кандидата обширный опыт и стоит подумать о том, чтобы предложить ему работу.
Комментарии (43)
amarao
24.08.2021 14:36Я задумался как я бы реализовывал эту задачу, и мне придумалось вот такое: полезных значений мало (1 бит), и мы можем себе позволить хранить несколько их в массиве, не увеличивая размер массива (я предполагаю, что значения хранятся в int-подобном значении, а не в bitarray, потому что битовая распаковка - это то ещё упражнение).
Используем два бита: бит 0 и бит 1 (маска 1 и маска 2). Для выбора с какой "эпохой" мы работаем, будет per-board переменные new_epoch и current_epoch (которые маски содержат). В конце "хода" мы их меняем местами.
Мы записываем значения с использованием маски new_epoch, а читаем - с использованием current_epoch.
... хотя, попрограммировав на rust, я могу сказать, что это будет не очень быстро. read-write цикл одного значения из памяти полностью сносит все предсказания процессора.
Видимо, running window с небольшим кешем - самое разумное. ... А вот эффективная реализация двухмерного кольцевого буффера - это, даже интересно. Нам нужен буффер 3x3, так что его можно сделать на чистой арифметике...
kompilainenn2
24.08.2021 14:41+3оставляя без внимания мастерство, мягкие навыки
под мягкими навыками что скрывается? Soft skills?
alec_kalinin
24.08.2021 14:48+1Я бы для этой задачи использовал бы scientfic python с использованием свертки
import numpy as np from scipy.ndimage import convolve board = np.zeros(shape=(height, width), dtype=np.uint8) kernel = np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]], dtype=np.uint8) board_state = convolve(board, kernel, mode="wrap")Для огромных досок используем sparse matrix representation, а для быстрых сверток можно использовать какой-нибудь deep learning framework.
GospodinKolhoznik
24.08.2021 14:54Вы серьезно потащили бы костыли городить, чтобы сэкономить память на копии массива? На мой взгляд спорное архитектурное решение. Что даст это переусложнение? Потребление памяти будет в 2 раза больше. То есть память не по экспоненте не по полному будет расти а всегда ровно в 2 раза. Как мне кажется такие проблемы надо решать докупкой памяти один раз, зато потом легко поддерживать и актуализировать по. Иначе мы тут капельку сэкономим, а потом в 1000 раз больше потратим на разгребание проблем с модификациями программы.
Ну так, чтобы на собеседовании поспрашивать об этом можно, а в продакшне не надо нарушать принцип kiss там, где его можно не нарушать.
TheGodfather
24.08.2021 15:59+1Я в универе писал лабораторную на Qt, и могу заметить, что когда размер поля становится достаточно большим (точных цифр не помню, но условно 500*500), то производительность уже начинает заметно падать (естественно, мы не говорим о разовом обновлении, а о нажатии кнопки типа «плей», которая обновляет несколько раз в секунду). В лабораторной я, конечно, кэша рядов не делал, обошелся копией поля, но все-таки мотивация видна невооруженным взглядом
DirectoriX
24.08.2021 16:32+1Возможно, дело не столько в копировании, сколько в долгой перерисовке?
Было бы интересно замерять время на 1 обновление с перерисовкой и, скажем, на 1000 обновлений с единственной перерисовкой в конце.
JustDont
24.08.2021 17:26Вот да. Потому что когда я это всё писал в универе (на яве, плюс ох и давно это было) — затык начинался очевидно в рендере, причем еще и настолько выдающийся, что даже минимальнейшие оптимизации прорисовки позволяли наращивать поле до размеров всего экрана.
Понятно, что какие-нибудь там триллионы на триллионы клеток поля уже бы начали тормозить и по рассчётам, но их не визуализировать, и "мотивации невооруженным взглядом" уже не будет.
farafonoff
24.08.2021 17:19500x500 это 250 000. Не знаю когда вы учились в универе, но когда я участвовал в студенческих олимпиадах, мы брали грубую оценку 10^6 "операций" в секунду. Соответственно грубо такое поле можно позволить себе обновлять 4 раза в секунду без всяких оптимизаций.
da-nie
24.08.2021 17:50+2обошелся копией поля,
Зачем его вообще копировать? Храните два указателя — новое поле и старое поле. Используйте для построения нового поля данные от старого поля. Потом указатели меняете местами.DirectoriX
24.08.2021 18:00+3Такая же мысль при чтении статьи: зачем вообще что-то копировать, когда достаточно 1 раз сделать второе поле такого же размера и отрефакторить функцию так, чтоб она брала данные с первого поля и клала во второе, а на следующей итерации — обратно (см. «двойная буферизация»). Так будет около 0 расходов на копирование данных и даже на выделение памяти, которые неизбежны в «оптимизированном» варианте с его append'ами.
GospodinKolhoznik
24.08.2021 17:57Производительность будет одинаковая при любом подходе. Меняется только потребление памяти ровно в 2 раза.
t13s
24.08.2021 17:42+6<минуткаЭмоций>
Я очень надеюсь, что в том аду, в котором обязательно окажутся все сторонники подобного подхода, температура в котле будет всего-то в два раза выше, чем у соседей.
</минуткаЭмоций>Но если серьезно, то, во-первых, при неудачном стечении обстоятельств два массива могут просто-напросто не влезть в кэш процессора, что вызовет проблемы не только по памяти, но и по производительности.
Во-вторых, размышляя подобным образом и поощряя такой подход, мы со временем как раз и пришли к тому, что какой-нибудь несчастный мессенджер жрет полтора гигабайта оперативки. Базовая культура все-таки должна быть: на улицах не мусорить, в подол рубашки не сморкаться, память лишнюю не занимать.
DrGluck07
25.08.2021 13:59Поэтому я бы начал свой ответ на вопрос с вопроса «а что у нас с ресурсами». В зависимости от ответа стал бы предлагать решение.
t13s
25.08.2021 14:04В общем и целом - вы правы.
Но в некоторых случаях (и это как раз такой) быстрее сразу реализовать более оптимальное решение, чем спрашивать, философствовать, дожидаться ответа и переносить из-за этого имплементацию на следующий спринт :)
DrGluck07
25.08.2021 14:06+2Вот у нас микроконтроллер с 8K RAM. Заказчик хочет поле 1000х1000. Ну и какой метод оптимальнее? А если не контроллер, а обычный ПК и поле то же самое? А если пофиг на память, но нужно очень быстро? Или наоборот, поле здоровенное, а скорость не очень важна?
t13s
25.08.2021 14:25микроконтроллер с 8K RAM
скорее всего должен быть в описании условия задачи. И тогда тут либо спросить, возможна ли ситуация с > 3 000 живых клеток, либо изучать возможности использования другого микроконтроллера со 128К RAM, либо узнавать про наличие накопителя и предлагать решение, использующее страничный подход, либо объяснить заказчику, что он хочет странного.
обычный ПК
точно не будет против, если удастся сэкономить чуток памяти.
если нужно очень быстро
то смотреть в сторону параллелизма, а то и вообще расчетов на GPU. При этом выделение памяти в любом случае придется оптимизировать.
поле здоровенное
обычно означает, что наивная имплементация в реальной жизни по скорости никого не устроит, как бы это ни декларировалось в постановке задачи.
DrGluck07
25.08.2021 15:09+2Вот и я об этом. А потом уже отвечать в зависимости от условий.
Единственное в чём я не уверен, что стоит экономить на спичках при реализации на ПК поля 1000х1000 (условно 1 мегабайт * 2). Если только у нас не сервер, на котором одновременно считается 1000000 таких партий.
0xd34df00d
24.08.2021 18:06+3У меня на одной работе был случай, когда именно разница в два раза по потреблению памяти отличала «можем посчитать за следующую неделю» от «надо либо повышать сложность реализации и делать ее распределенной, либо вносить новое железо в бюджет на следующий год, ждать январских закупок через полгода, настраивать железо, и так далее».
BugM
24.08.2021 19:51Подпишусь.
Когда память начинает измеряться в терабайтах оптимизация по памяти в два раза за счёт усложнения алгоритма того стоит.
GospodinKolhoznik
24.08.2021 21:24+2А таких случаев, чтобы при накате патча ломался какой то старый функционал, потому что программа написана мудрено и разработчик патча не смог до конца понять некоторых аспектов, таких случаев не бывало?
0xd34df00d
25.08.2021 01:31+3Такие случаи тоже были, конечно. Правда, чаще всего программа была написана мудрёно потому, что недавно обчитавшийся паттернов разработчик решал её хорошенько future-proof'нуть и обмазать слоями абстракций, а не потому, что с оптимизациями перемудрили.
micho1973
24.08.2021 15:43+2Я упоминаю об этом вскользь, но на самом деле, то, что кандидат способен опознать и разделить эти два этапа, уже говорит в его пользу. Некоторые рубят сплеча и пытаются решить обе задачи одновременно – это не то чтобы плохо, но гораздо труднее. Здесь есть парадоксальный момент: разделение на две задачи упрощает имплементацию, но на практике оказывается сложнее, потому что требует концептуального рывка, который должен подсказать опыт.
Я все-таки не понял, почему эту задачу нельзя решить за один проход всего массива, сохраняя старые значения для тех клеток где они изменились.
Srgun
24.08.2021 16:04Если старое значение сохранять для всех, то по затратам памяти это то же самое, что 2 полных массива. Если старое сохранять только для изменённых - то оптимизация алгоритма по памяти будет сложнее, чем кеширование 2 строк, и, возможно, придётся сразу решать п.3
RA-NGR
25.08.2021 10:54+1Я, если память не изменяет, еще на спектруме, делал за один проход. Значения «старого поля» сохранял в промежуточном массиве 3х3, затем сдвигая его, этакое своеобразное «скользящее окно». А в дальнейшей модификации тупо вообще игрался битами, кодируя текущее состояние в нулевом, а новое в первом )))
Telmah
24.08.2021 15:45+9Написать про игру "Жизнь" и не упомянуть Джона Конвея - както совсем неправильно по моему...
anatolii_kostrygin
24.08.2021 16:29+1На хабре прошлым летом была пара хороших статей про дальнейшие ускорения алгоритма:
А вообще есть альтернативный путь решения задачи через динамическое программирование - https://en.wikipedia.org/wiki/Hashlife Идея в его основе такая:
Допустим, у нас есть квадрат
. Тогда через
шагов состояние внутреннего квадрата 
зависит только от исходного состояния клеток большого квадрата.Допустим, у нас есть большая хэш-таблица, в которой мы умеем быстро искать по квадратам
.Тогда задача определения состояния квадрата
через 
шагов решается делением квадрата на четвертинки и четырьмя обращениями к хэш-таблице.Последовательно отращивая поле или удваивая время получим логарифмическую сложность.
Druj
24.08.2021 16:40+3Серьёзно? В 2021 году в очередной раз писать(!!! переводить!!) на хабр про простейшую реализацию «жизни» да ещё и в максимально простом варианте? Думаю что большая часть читателей просто клюнула на байт с «задачей из Reddita». Фу.
zim32
24.08.2021 16:45+1Мне вот интересно сам этот сотрудник решит задачку поиска кратчайшего пути с учетом загрузки за 40 минут? А напишет алгоритм flood fill для произвольного полигона? А алгоритм поиска оптимального пира в п2 сети с учётом исходящей и входящей полосы? Может алгоритм парсинга бинарных выражений? Конечно же максимум за 40-50 минут. Если нет, то у меня вопрос что он делает в реддите?
Druj
24.08.2021 16:561. Если загрузка это вес ребра то Дейкстра/Флойд
2. BFS
3. Хз что это
4. Если парсить то автомат, если вычислять то ОП нотация
Думаю что на пишет без проблем если будет знать что на собесе нужны вызубренные алгоритмы а не опыт работы. А если можно гуглить то и зубрить не надо.
kasthack_phoenix
24.08.2021 17:17+4А потом он проходит этот собес и пишет на реакте новый UI для reddit, который тормозит на шестнадцатиядерном десктопе.
M0rdecay
24.08.2021 16:56+6Предлагаю ЖизньЕнтерпрайзЕдишн (по аналогии)
Каждая клетка - отдельный класс, реализующий интерфейс:
type Cell interface { GetState() state NextState() error UpdateState() error }Где state - специальный отдельный тип, под капотом маппящий 1 как "жив" и 0 как "мёртв", чтоб можно было расширяться и добавлять новые состояния.
При вызове NextState() каждая клетка должна сходить в один из апи-сервисов, узнать состояние соседей, высчитать своё следующее состояние и приготовиться обновиться по вызову UpdateState().
Создаем сервис-менеджер, который может хранить в себе кусочек поля:
type CellManager struct { Cells []Cell } func (m *CellManager) Initialize(from, to int64) error {} func (m *CellManager) Next() error {} func (m *CellManager) Update() error {}Менеджеры клеток можно разделить по нескольким дата-центрам, каждый из менеджеров может обслуживать свой кусочек поля. Next() и Update(), конечно, асинхронные.
Для большей ентерпрайзности можно положить всё в кубер, а каждый менеджер пусть хранит данные в выделенной базёнке, и чтоб всё масштабировалось налету в зависимости от изначально заданного размера поля.
Теперь нам нужен апи-сервис. Апи-сервис должен знать о расположении всех менеджеров (допустим, что эта информация хранится в кластере Consul). Когда апи получает команду на обновление, он асинхронно кидает команду на менеджеры о вычислении следующего состояния. Когда все вычисления завершаются, отдаётся команда на обновление.
К апи-сервису прилагается какой-нибудь веб-сервер с фронтом, который отображает красивую картинку.
P.S. не воспринимайте серьёзно, просто идея за обеденной чашкой кофе.
t13s
24.08.2021 17:52+3высчитать своё следующее состояние
(Удивленного, с недоумением и оттенками презрения во вгляде) что, сама? Помилуйте, голубчик, это же просто POD, а вы в него логику пихаете, да еще с такими букетом зависимостей! Тут отдельный сервис требуется, а то и три!
Femistoklov
24.08.2021 19:16О! Вас бы с радостью взяли в целую кучу компаний, где меня безуспешно пытались собеседовать! Могу дать все явки. Мне - процент от первой ЗП.
pavelsc
24.08.2021 19:15+1Опубликуйте лучше список зарегистрированных в СНГ компаний, в которых на собеседовании дают "типовые задачи на алгоритмы", чтоб сразу в спам офферы с их доменов кидать фильтром.
t13s
25.08.2021 13:49А как вы предпочитаете демонстрировать потенциальным работодателям свою компетентность?
net_racoon
25.08.2021 10:13Пробежался по тексу, возможно что-то упустил. Да я и не программист совсем. Но есть вопрос, а нельзя делать не массив, а связку клеток. Т.е. есть клетка, у нее указатель на соседа сверху, снизу, справа, слева и т.д. ?
t13s
25.08.2021 13:40Т.е. вместо одного бита (ну или байта - в зависимости от реализации) на состояние клетки предлагаете хранить 64*4+1 = 257 бит? :)
petropavel
25.08.2021 17:30Ну, вообще-то он предлагает вместо 1е6х1е6=1е12 бит, хранить 257*N бит. Одну глайдерную пушку так считать наверняка лучше.
t13s
25.08.2021 17:41Тогда 257 не хватит. Надо же как-то уметь еще обрабатывать пересечения из различных кластеров точек, т.е. координаты каждой точки хранить, видимо.
Zoomerman
10.09.2021 14:03Шаг 1: строим вторую матрицу, содержащую сумму соседей для каждой клетки
Шаг 2: изменяем первую матрицу, фильтруя количество соседей по алгоритму, пробегаясь по второй матрице
Если памяти недостаточно - режем вспомогательную матрицу, превращаем в буфер, работаем по принципу скользящего окна.
Если вычислительной мощности недостаточно - распараллеливаем процесс на ядра, GPU, кластер.
Давно уже не сталкивался с задачами, для которых недостаточно оперативной или дисковой памяти. А вот с задачами, в которых узкое место - процессор, сталкиваюсь постоянно.
ProstakovAlexey
Мне эта задача очень нравится еще со школы. Тогда впервые прочитал про нее и реализовал имплементацию с дублирование поля. Она очаровательно работала, визуализация была на экране с помощью спрайтов, был даже расширенный вариант - у клеток было состояние не только жив/мертв, но и "счастье" (оно завило от кол-ва соседей, не помню уже формулу). С этим "счастьем" картинка была цветной и иногда очень красивой. Не знаю, что за задачи в Reddit, но в своей работе ничего подобного не встречал. Вообще за годы работы был только один проект в котором пригодилась математика и мышление - расчет прыжка в фигурном катании, а остальном REST, примитивная логика (хоть и с множеством условий и требующая большой внимательности) и ковыряние с чужими framework, database и прочими поделками.
amarao
Прямо сейчас я с интересом смотрю на программиста, который писал-писал REST, и, вдруг, обнаружил, что ему для работы нужно построить граф (услуги), построить остовной граф из него и найти изолированные подграфы, не связанные с предпочтительными вершинами. Правда, это хороший программист, потому что ещё до появления графов там были деревья и монадки.