💻 Coding interviews in a nutshell

Продолжаю читать Programming Pearls. Интересно про перформанс.

Автор рассказывает про Андрея Аппеля, который работал над симуляцией какого-то движения 10K планет. И пришлось ему закопаться в перфоманс и программирование, отвлечься от физики, потому что просто цикл в цикле на три строки работал бы год.

Он сделал табличку с замерами (фотка дальше). Где конкретно и во сколько раз улучшился рантайм.

Переписал самую нагружённую функцию на ассемблере — ускорился в 2.5 раза. Запустили на компе с приблудной для ускорения плавающей точки, заплатив за оборудование кучу денег — ускорился в 2 раза.

Переписал с O(N^2) на O(N * log N) — ускорился в 12 раз 😃 В тему про где закопаны 80% результата. Но у всего есть цена.

Тут же как. Вот есть эти 10K планет и милое дело их все циклом в цикле пробежать. Откуда логарифм у него? Построил дерево поиска. Как? Оно само по себе ниоткуда не возьмётся.

Ему пришлось сделать хорошие предположения о том как можно планеты сгруппировать так, чтобы засунуть все это в дерево — очевидно, симуляция уже как бы не та, то есть не совсем точная. Но он смог показать насколько она не точная в новой модели, по мелочи вышло. Явно стоит того, чтобы не ждать год 😃

Вывод такой, что структуры данных это на самом деле про выдумать хорошую модель и показать, что она довольно точна в определённом случае, то есть про трейдофы. Системы ж не в вакууме существуют, а отражают реальные процессы в жизни.

И олимпиадные задачки на самом деле про это, только в миниатюре. То есть выучил ты алгосики и что с ними дальше делать? Никто не ставит задачу как «напиши мне бинарный поиск», лол, что там писать. А вот построить удачную модель — могут не только лишь все, нужна тренировка (по большей части не пугаться неизвестной задачи и не умереть со скуки пока бьешься головой о задачу).

Если эту мысль продолжать, то «синьорность» тоже где-то рядом. В синьора можно сгрузить неведомую никому херню и на выходе получить модель, с хорошим приближением, и так чтобы можно было запрограммировать (ведь компьютер не понимает «сделать красиво»), в идеале ещё и оценкой куда надо приложить 20% усилий чтобы все заиграло. Красота. Можно нарезать на таски в джире 😊

www.tgoop.com/coding_interviews/169

2.28K viewsJul 10, 2021 at 15:24

Продолжаю читать Programming Pearls. Интересно про перформанс.

Автор рассказывает про Андрея Аппеля, который работал над симуляцией какого-то движения 10K планет. И пришлось ему закопаться в перфоманс и программирование, отвлечься от физики, потому что просто цикл в цикле на три строки работал бы год.

Он сделал табличку с замерами (фотка дальше). Где конкретно и во сколько раз улучшился рантайм.

Переписал самую нагружённую функцию на ассемблере — ускорился в 2.5 раза. Запустили на компе с приблудной для ускорения плавающей точки, заплатив за оборудование кучу денег — ускорился в 2 раза.

Переписал с O(N^2) на O(N * log N) — ускорился в 12 раз 😃 В тему про где закопаны 80% результата. Но у всего есть цена.

Тут же как. Вот есть эти 10K планет и милое дело их все циклом в цикле пробежать. Откуда логарифм у него? Построил дерево поиска. Как? Оно само по себе ниоткуда не возьмётся.

Ему пришлось сделать хорошие предположения о том как можно планеты сгруппировать так, чтобы засунуть все это в дерево — очевидно, симуляция уже как бы не та, то есть не совсем точная. Но он смог показать насколько она не точная в новой модели, по мелочи вышло. Явно стоит того, чтобы не ждать год 😃

Вывод такой, что структуры данных это на самом деле про выдумать хорошую модель и показать, что она довольно точна в определённом случае, то есть про трейдофы. Системы ж не в вакууме существуют, а отражают реальные процессы в жизни.

И олимпиадные задачки на самом деле про это, только в миниатюре. То есть выучил ты алгосики и что с ними дальше делать? Никто не ставит задачу как «напиши мне бинарный поиск», лол, что там писать. А вот построить удачную модель — могут не только лишь все, нужна тренировка (по большей части не пугаться неизвестной задачи и не умереть со скуки пока бьешься головой о задачу).

Если эту мысль продолжать, то «синьорность» тоже где-то рядом. В синьора можно сгрузить неведомую никому херню и на выходе получить модель, с хорошим приближением, и так чтобы можно было запрограммировать (ведь компьютер не понимает «сделать красиво»), в идеале ещё и оценкой куда надо приложить 20% усилий чтобы все заиграло. Красота. Можно нарезать на таски в джире 😊

BY 💻 Coding interviews in a nutshell