Comments 43
Прямо сейчас я с интересом смотрю на программиста, который писал-писал REST, и, вдруг, обнаружил, что ему для работы нужно построить граф (услуги), построить остовной граф из него и найти изолированные подграфы, не связанные с предпочтительными вершинами. Правда, это хороший программист, потому что ещё до появления графов там были деревья и монадки.
Я задумался как я бы реализовывал эту задачу, и мне придумалось вот такое: полезных значений мало (1 бит), и мы можем себе позволить хранить несколько их в массиве, не увеличивая размер массива (я предполагаю, что значения хранятся в int-подобном значении, а не в bitarray, потому что битовая распаковка - это то ещё упражнение).
Используем два бита: бит 0 и бит 1 (маска 1 и маска 2). Для выбора с какой "эпохой" мы работаем, будет per-board переменные new_epoch и current_epoch (которые маски содержат). В конце "хода" мы их меняем местами.
Мы записываем значения с использованием маски new_epoch, а читаем - с использованием current_epoch.
... хотя, попрограммировав на rust, я могу сказать, что это будет не очень быстро. read-write цикл одного значения из памяти полностью сносит все предсказания процессора.
Видимо, running window с небольшим кешем - самое разумное. ... А вот эффективная реализация двухмерного кольцевого буффера - это, даже интересно. Нам нужен буффер 3x3, так что его можно сделать на чистой арифметике...
оставляя без внимания мастерство, мягкие навыки
под мягкими навыками что скрывается? Soft skills?
Я бы для этой задачи использовал бы 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.
Вы серьезно потащили бы костыли городить, чтобы сэкономить память на копии массива? На мой взгляд спорное архитектурное решение. Что даст это переусложнение? Потребление памяти будет в 2 раза больше. То есть память не по экспоненте не по полному будет расти а всегда ровно в 2 раза. Как мне кажется такие проблемы надо решать докупкой памяти один раз, зато потом легко поддерживать и актуализировать по. Иначе мы тут капельку сэкономим, а потом в 1000 раз больше потратим на разгребание проблем с модификациями программы.
Ну так, чтобы на собеседовании поспрашивать об этом можно, а в продакшне не надо нарушать принцип kiss там, где его можно не нарушать.
Было бы интересно замерять время на 1 обновление с перерисовкой и, скажем, на 1000 обновлений с единственной перерисовкой в конце.
Вот да. Потому что когда я это всё писал в универе (на яве, плюс ох и давно это было) — затык начинался очевидно в рендере, причем еще и настолько выдающийся, что даже минимальнейшие оптимизации прорисовки позволяли наращивать поле до размеров всего экрана.
Понятно, что какие-нибудь там триллионы на триллионы клеток поля уже бы начали тормозить и по рассчётам, но их не визуализировать, и "мотивации невооруженным взглядом" уже не будет.
500x500 это 250 000. Не знаю когда вы учились в универе, но когда я участвовал в студенческих олимпиадах, мы брали грубую оценку 10^6 "операций" в секунду. Соответственно грубо такое поле можно позволить себе обновлять 4 раза в секунду без всяких оптимизаций.
обошелся копией поля,
Зачем его вообще копировать? Храните два указателя — новое поле и старое поле. Используйте для построения нового поля данные от старого поля. Потом указатели меняете местами.
Да-да, конечно, указатели были, это было очевидным улучшением)
Производительность будет одинаковая при любом подходе. Меняется только потребление памяти ровно в 2 раза.
<минуткаЭмоций>
Я очень надеюсь, что в том аду, в котором обязательно окажутся все сторонники подобного подхода, температура в котле будет всего-то в два раза выше, чем у соседей.
</минуткаЭмоций>
Но если серьезно, то, во-первых, при неудачном стечении обстоятельств два массива могут просто-напросто не влезть в кэш процессора, что вызовет проблемы не только по памяти, но и по производительности.
Во-вторых, размышляя подобным образом и поощряя такой подход, мы со временем как раз и пришли к тому, что какой-нибудь несчастный мессенджер жрет полтора гигабайта оперативки. Базовая культура все-таки должна быть: на улицах не мусорить, в подол рубашки не сморкаться, память лишнюю не занимать.
В общем и целом - вы правы.
Но в некоторых случаях (и это как раз такой) быстрее сразу реализовать более оптимальное решение, чем спрашивать, философствовать, дожидаться ответа и переносить из-за этого имплементацию на следующий спринт :)
микроконтроллер с 8K RAM
скорее всего должен быть в описании условия задачи. И тогда тут либо спросить, возможна ли ситуация с > 3 000 живых клеток, либо изучать возможности использования другого микроконтроллера со 128К RAM, либо узнавать про наличие накопителя и предлагать решение, использующее страничный подход, либо объяснить заказчику, что он хочет странного.
обычный ПК
точно не будет против, если удастся сэкономить чуток памяти.
если нужно очень быстро
то смотреть в сторону параллелизма, а то и вообще расчетов на GPU. При этом выделение памяти в любом случае придется оптимизировать.
поле здоровенное
обычно означает, что наивная имплементация в реальной жизни по скорости никого не устроит, как бы это ни декларировалось в постановке задачи.
Подпишусь.
Когда память начинает измеряться в терабайтах оптимизация по памяти в два раза за счёт усложнения алгоритма того стоит.
А таких случаев, чтобы при накате патча ломался какой то старый функционал, потому что программа написана мудрено и разработчик патча не смог до конца понять некоторых аспектов, таких случаев не бывало?
Я упоминаю об этом вскользь, но на самом деле, то, что кандидат способен опознать и разделить эти два этапа, уже говорит в его пользу. Некоторые рубят сплеча и пытаются решить обе задачи одновременно – это не то чтобы плохо, но гораздо труднее. Здесь есть парадоксальный момент: разделение на две задачи упрощает имплементацию, но на практике оказывается сложнее, потому что требует концептуального рывка, который должен подсказать опыт.
Я все-таки не понял, почему эту задачу нельзя решить за один проход всего массива, сохраняя старые значения для тех клеток где они изменились.
Если старое значение сохранять для всех, то по затратам памяти это то же самое, что 2 полных массива. Если старое сохранять только для изменённых - то оптимизация алгоритма по памяти будет сложнее, чем кеширование 2 строк, и, возможно, придётся сразу решать п.3
Я, если память не изменяет, еще на спектруме, делал за один проход. Значения «старого поля» сохранял в промежуточном массиве 3х3, затем сдвигая его, этакое своеобразное «скользящее окно». А в дальнейшей модификации тупо вообще игрался битами, кодируя текущее состояние в нулевом, а новое в первом )))
Написать про игру "Жизнь" и не упомянуть Джона Конвея - както совсем неправильно по моему...
На хабре прошлым летом была пара хороших статей про дальнейшие ускорения алгоритма:
А вообще есть альтернативный путь решения задачи через динамическое программирование - https://en.wikipedia.org/wiki/Hashlife Идея в его основе такая:
Допустим, у нас есть квадрат
. Тогда через
шагов состояние внутреннего квадрата 
зависит только от исходного состояния клеток большого квадрата.Допустим, у нас есть большая хэш-таблица, в которой мы умеем быстро искать по квадратам
.Тогда задача определения состояния квадрата
через 
шагов решается делением квадрата на четвертинки и четырьмя обращениями к хэш-таблице.Последовательно отращивая поле или удваивая время получим логарифмическую сложность.
Мне вот интересно сам этот сотрудник решит задачку поиска кратчайшего пути с учетом загрузки за 40 минут? А напишет алгоритм flood fill для произвольного полигона? А алгоритм поиска оптимального пира в п2 сети с учётом исходящей и входящей полосы? Может алгоритм парсинга бинарных выражений? Конечно же максимум за 40-50 минут. Если нет, то у меня вопрос что он делает в реддите?
2. BFS
3. Хз что это
4. Если парсить то автомат, если вычислять то ОП нотация
Думаю что на пишет без проблем если будет знать что на собесе нужны вызубренные алгоритмы а не опыт работы. А если можно гуглить то и зубрить не надо.
А потом он проходит этот собес и пишет на реакте новый UI для reddit, который тормозит на шестнадцатиядерном десктопе.
Предлагаю ЖизньЕнтерпрайзЕдишн (по аналогии)
Каждая клетка - отдельный класс, реализующий интерфейс:
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. не воспринимайте серьёзно, просто идея за обеденной чашкой кофе.
высчитать своё следующее состояние
(Удивленного, с недоумением и оттенками презрения во вгляде) что, сама? Помилуйте, голубчик, это же просто POD, а вы в него логику пихаете, да еще с такими букетом зависимостей! Тут отдельный сервис требуется, а то и три!
О! Вас бы с радостью взяли в целую кучу компаний, где меня безуспешно пытались собеседовать! Могу дать все явки. Мне - процент от первой ЗП.
Опубликуйте лучше список зарегистрированных в СНГ компаний, в которых на собеседовании дают "типовые задачи на алгоритмы", чтоб сразу в спам офферы с их доменов кидать фильтром.
Пробежался по тексу, возможно что-то упустил. Да я и не программист совсем. Но есть вопрос, а нельзя делать не массив, а связку клеток. Т.е. есть клетка, у нее указатель на соседа сверху, снизу, справа, слева и т.д. ?
Шаг 1: строим вторую матрицу, содержащую сумму соседей для каждой клетки
Шаг 2: изменяем первую матрицу, фильтруя количество соседей по алгоритму, пробегаясь по второй матрице
Если памяти недостаточно - режем вспомогательную матрицу, превращаем в буфер, работаем по принципу скользящего окна.
Если вычислительной мощности недостаточно - распараллеливаем процесс на ядра, GPU, кластер.
Давно уже не сталкивался с задачами, для которых недостаточно оперативной или дисковой памяти. А вот с задачами, в которых узкое место - процессор, сталкиваюсь постоянно.
Задача, которую предлагали разработчикам на собеседованиях в Reddit: разбор и решение от сотрудника компании