Слияние кода завершено, страница обновится автоматически
Написание и оптимизация кода на Go
В этом документе представлены рекомендации по написанию высокопроизводительного кода на Go.
Хотя некоторые обсуждения будут посвящены тому, как сделать отдельные сервисы быстрее (кэширование и т. д.), проектирование эффективных распределённых систем выходит за рамки этой работы. Уже есть хорошие тексты о мониторинге и проектировании распределённых систем. Оптимизация распределённых систем включает в себя совершенно другой набор исследований и компромиссов в дизайне.
Весь контент будет лицензирован под CC-BY-SA.
Эта книга разделена на разные разделы:
Мы можем резюмировать эти три раздела так:
Я ставлю это на первое место, потому что это действительно самый важный шаг. Стоит ли вообще этим заниматься?
Каждая оптимизация имеет свою цену. Как правило, эта стоимость выражается в терминах сложности кода или когнитивной нагрузки — оптимизированный код редко бывает проще неоптимизированной версии.
Но есть и другая сторона, которую я назову экономикой оптимизации. Как программист, ваше время ценно. Существует альтернативная стоимость того, над чем ещё вы могли бы работать для своего проекта, какие ошибки исправлять, какие функции добавлять. Оптимизировать вещи весело, но это не всегда правильная задача. Производительность — это функция, но также важны доставка и корректность.
Выберите наиболее важную задачу для работы. Иногда это не фактическая оптимизация процессора, а оптимизация пользовательского опыта. Что-то такое простое, как добавление индикатора выполнения или повышение отзывчивости страницы путём выполнения вычислений в фоновом режиме после рендеринга страницы.
Иногда это будет очевидно: ежечасный отчёт, который завершается через три часа, вероятно, менее полезен, чем тот, который завершается менее чем за один час.
То, что что-то легко оптимизировать, не означает, что это стоит оптимизировать. Игнорирование низко висящих плодов — это действенная стратегия разработки.
Думайте об этом как об оптимизации вашего времени.
Вы можете выбирать, что оптимизировать и когда оптимизировать. Вы можете перемещать ползунок между «Быстрое программное обеспечение» и «Быстрое развёртывание».
Люди слышат и бездумно повторяют «преждевременная оптимизация — корень всех зол», но упускают полный контекст цитаты.
«Программисты тратят огромное количество времени на размышления или беспокойство о скорости некритических частей своих программ, и эти попытки повысить эффективность фактически оказывают сильное негативное влияние, если учитывать отладку и обслуживание. Мы должны забыть о небольших улучшениях эффективности, скажем, в 97% случаев: преждевременная оптимизация — это корень всех зол. Тем не менее мы не должны упускать возможности в этих критических 3%».
— Кнут
Добавьте: https://www.youtube.com/watch?time_continue=429&v=3WBaY61c9sE
Стоит ли оптимизировать?
Да, но только если проблема важна, программа действительно слишком медленная, и есть некоторые ожидания, что её можно ускорить, сохраняя при этом корректность, надёжность и ясность».
— Практика программирования, Керниган и Пайк
Преждевременная оптимизация также может навредить вам, связав вас с определёнными решениями. Оптимизированный код может быть сложнее изменить, если требования изменятся, и его может быть труднее выбросить (ошибка невозвратных затрат), если это необходимо.
Оценка производительности BitFunnel содержит некоторые цифры, которые делают этот компромисс явным. Представьте себе гипотетический поисковый движок, которому требуется 30 000 машин в нескольких центрах обработки данных. Эти машины стоят примерно 1 000 долларов США в год. Если вы сможете удвоить скорость программного обеспечения, это может сэкономить компании 15 миллионов долларов США в год. Даже один разработчик, потративший целый год на улучшение производительности всего на 1%, окупит себя. В подавляющем большинстве случаев размер и скорость программы не являются проблемой.
Самая простая оптимизация — это её отсутствие. Вторая по простоте оптимизация — просто купить более быстрое оборудование.
Если вы решили изменить свою программу, продолжайте читать.
Прежде чем мы перейдём к деталям, давайте поговорим об общем процессе оптимизации. Оптимизация — это форма рефакторинга. Но каждый шаг вместо улучшения какого-либо аспекта исходного кода (дублирование кода, ясность и т. д.) улучшает какой-либо аспект производительности: снижает использование ЦП, памяти, задержку и т. д. Это улучшение обычно достигается за счёт читаемости. Это означает, что помимо полного набора модульных тестов (чтобы убедиться, что ваши изменения ничего не сломали), вам также нужен хороший набор бенчмарков, чтобы убедиться, что изменения оказывают желаемый эффект на производительность. Вы должны быть в состоянии проверить, действительно ли ваше изменение снижает нагрузку на ЦП. Иногда изменение, которое, как вы думали, улучшит производительность, на самом деле оказывается нулевым или даже отрицательным. Всегда проверяйте, что в таких случаях вы можете отменить своё исправление.
Что является лучшим комментарием в исходном коде, который вы когда-либо встречали? — Stack Overflow:
// // Dear maintainer: // // Once you are done trying to 'optimize' this routine, // and have realized what a terrible mistake that was, // please increment the following counter as a warning // to the next guy: // // total_hours_wasted_here = 42 //
Используемые вами бенчмарки должны быть правильными и давать воспроизводимые числа для репрезентативных рабочих нагрузок. Если отдельные прогоны имеют слишком большую дисперсию, будет сложнее заметить небольшие улучшения. Вам нужно будет использовать benchstat или эквивалентные статистические тесты, и вы не сможете просто оценить их визуально. (Обратите внимание, что использование статистических тестов в любом случае является хорошей идеей.) Шаги для запуска бенчмарков должны быть задокументированы, а любые пользовательские скрипты и инструменты должны быть зафиксированы в репозитории с инструкциями по их запуску. Помните о больших наборах бенчмарков, которые занимают много времени для выполнения: это замедлит итерации разработки.
Также обратите внимание, что всё, что можно измерить, можно оптимизировать. Убедитесь, что вы измеряете то, что нужно.
Следующий шаг — решить, для чего вы оптимизируете. Если цель состоит в том, чтобы улучшить работу ЦП, какое приемлемое ускорение? Хотите ли вы улучшить текущую производительность в 2 раза? В 10 раз? Можете ли вы сформулировать это как «задача размера N менее чем за время T»? Пытаетесь ли вы уменьшить использование памяти? Насколько? Насколько медленнее допустимо для какого изменения использования памяти? Чем вы готовы пожертвовать ради снижения требований к пространству?
Оптимизировать задержку обслуживания сложнее. Целые книги были написаны о том, как тестировать производительность веб-серверов. Основная проблема заключается в том, что для одной функции производительность довольно стабильна для данного размера проблемы. Для веб-сервисов у вас нет одного числа. Правильный набор тестов для веб-сервиса предоставит распределение задержки для заданного уровня запросов в секунду. Этот доклад даёт хороший обзор некоторых проблем: «Как НЕ измерять задержку» Гила Тене.
TODO: См. следующий раздел об оптимизации веб-сервисов.
Цели производительности должны быть конкретными. Почти всегда вы сможете сделать что-то быстрее. Оптимизация часто представляет собой игру с уменьшающейся отдачей. Вы должны знать, когда остановиться. Сколько усилий вы собираетесь приложить, чтобы получить последний кусочек работы? Насколько уродливее и труднее в обслуживании вы готовы сделать код?
В ранее упомянутом докладе Дэна Луу о оценке производительности BitFunnel показан пример использования грубых расчётов для определения того, являются ли ваши целевые показатели производительности разумными.
У Саймона Эскилдсена есть доклад с SRECon, охватывающий эту тему более подробно: Продвинутая математика на салфетке: оценка производительности системы. Наконец, в книге Джона Бентли «Programming Pearls» есть глава под названием «На обратной стороне конверта», посвящённая задачам Ферми. К сожалению, подобные навыки оценки получили плохую репутацию из-за их использования в «головоломных вопросах на собеседованиях» в Microsoft в 1990-х и начале 2000-х годов.
При разработке с нуля не стоит оставлять все измерения производительности и бенчмаркинг до конца. Легко сказать: «Мы исправим это позже», но если производительность действительно важна, она будет учитываться при проектировании с самого начала. Любые значительные архитектурные изменения, необходимые для исправления проблем с производительностью, будут слишком рискованными ближе к дедлайну. Обратите внимание, что во время разработки основное внимание следует уделять разумному проектированию программы, алгоритмам и структурам данных. Оптимизация на более низких уровнях стека должна подождать до более поздних этапов цикла разработки, когда будет доступно более полное представление о производительности системы. Любые профили всей системы, которые вы создаёте, пока система неполна, дадут искажённое представление о том, где будут узкие места в готовой системе.
TODO: Как избежать/обнаружить «смерть от тысячи порезов» из-за плохо написанного программного обеспечения. Решение: «Преждевременная пессимизация — корень всех зол». Это соответствует моему Правилу 1: Действуйте обдуманно. Вам не нужно писать каждую строку кода быстро, но и не следует по умолчанию делать расточительные вещи.
«Преждевременная пессимизация — это когда вы пишете код, который работает медленнее, чем должен, обычно запрашивая ненужную дополнительную работу, тогда как эквивалентно сложный код был бы быстрее и должен просто естественно вытекать из ваших пальцев».
— Херб Саттер
Бэнчмаркинг как часть CI сложен из-за шумных соседей и даже разных CI-боксов, если это только вы. Трудно ориентироваться на метрики производительности. Хорошая золотая середина — проводить тесты разработчиками (на соответствующем оборудовании) и включать результаты в сообщение о фиксации для коммитов, специально посвящённых производительности. Для тех, которые являются просто общими патчами, попробуйте выявить ухудшение производительности «на глаз» при проверке кода.
TODO: как отслеживать производительность с течением времени?
Пишите код, который можно протестировать. Профилирование можно выполнить на больших системах. Бэнчмаркинг нужен для тестирования изолированных частей. Вы должны быть в состоянии извлечь и настроить достаточный контекст, чтобы тесты были репрезентативными и тестировали достаточно.
Разница между вашей целью и текущей производительностью также даст вам представление о том, с чего начать. Если вам нужно всего лишь улучшение производительности на 10–20%, вы, вероятно, сможете добиться этого с помощью некоторых изменений в реализации и небольших исправлений. Если вам нужен коэффициент 10x или больше, то простое замена умножения на сдвиг влево не поможет. Вероятно, это потребует изменений вверх и вниз по вашему стеку, возможно, перепроектирования больших частей системы с учётом этих целей производительности.
Хорошая работа по повышению производительности требует знаний на многих различных уровнях, от системного проектирования, сетей, оборудования (ЦП, кэши, хранилище), алгоритмов, настройки и отладки. Имея ограниченные время и ресурсы, подумайте, какой уровень даст наибольшее улучшение: это не всегда будет алгоритм или настройка программы.
В целом, оптимизация должна идти сверху вниз. Оптимизации на системном уровне окажут большее влияние, чем оптимизации на уровне выражений. Убедитесь, что вы решаете проблему на соответствующем уровне.
Эта книга в основном будет говорить о снижении использования ЦП, снижении использования памяти и снижении задержки. Стоит отметить, что очень редко можно сделать всё три одновременно. Может быть, процессорное время ускоряется, но теперь ваша программа использует больше памяти. Возможно, вам нужно уменьшить объём памяти, но теперь программа будет работать дольше.
Закон Амдала говорит нам сосредоточиться на узких местах. Если вы удвоите скорость работы процедуры, которая занимает всего 5% времени выполнения, это всего лишь ускорение на 2,5% в общей сложности. С другой стороны, ускорение процедуры, занимающей 80% времени, всего на 10% улучшит время выполнения почти на 8%. Профили помогут определить, куда на самом деле уходит время. Оптимизация: вы хотите уменьшить объём работы, которую должен выполнять процессор.
Quicksort работает быстрее, чем пузырьковая сортировка, потому что решает ту же задачу (сортировку) за меньшее количество шагов. Это более эффективный алгоритм. Вы уменьшили объём работы, который должен выполнить процессор для выполнения той же задачи.
Настройка программы, как и оптимизация компилятора, обычно даёт лишь небольшое улучшение общего времени выполнения. Значительное улучшение почти всегда достигается за счёт алгоритмических изменений или изменений структуры данных, фундаментального изменения в организации вашей программы. Технология компиляторов улучшается, но медленно. Закон Пробстинга гласит, что производительность компиляторов удваивается каждые 18 лет, что резко контрастирует с (немного неправильно понятой интерпретацией) закона Мура, согласно которому производительность процессоров удваивается каждые 18 месяцев. Алгоритмические улучшения работают в больших масштабах. Алгоритмы для смешанного целочисленного программирования улучшились в 30 000 раз в период с 1991 по 2008 год. В качестве более конкретного примера рассмотрим разбивку замены алгоритма грубой силы геопространственного анализа, описанного в блоге Uber, на более специализированный, более подходящий для представленной задачи. Не существует переключателя компилятора, который даст вам эквивалентное повышение производительности.
TODO: Оптимизация различий алгоритмов FFT и MMM с плавающей точкой в gttse07.pdf
Профилировщик может показать, что много времени тратится на определённую процедуру. Может быть, это дорогостоящая процедура, а может быть, дешёвая процедура, которая просто вызывается много-много раз. Вместо того чтобы сразу пытаться ускорить эту процедуру, посмотрите, можно ли уменьшить количество её вызовов или полностью исключить её. Более конкретные стратегии оптимизации мы обсудим в следующем разделе.
Три вопроса оптимизации:
Работа Джона Бентли «Написание эффективных программ» 1982 года рассматривала оптимизацию программы как инженерную проблему: бенчмарк. Анализ. Улучшение. Проверка. Итерация. Ряд его советов теперь выполняется автоматически компиляторами. Задача программиста — использовать преобразования, которые компиляторы не могут сделать.
Есть резюме книги:
и правила настройки программы:
Когда вы думаете об изменениях, которые вы можете внести в свою программу, есть два основных варианта: вы можете либо изменить свои данные, либо вы можете изменить свой код.
Изменение ваших данных означает либо добавление, либо изменение представления данных, которые вы обрабатываете. С точки зрения производительности некоторые из них в конечном итоге изменят O(), связанную с различными аспектами структуры данных. Это может даже включать предварительную обработку входных данных в другом, более полезном формате.
Идеи для расширения вашей структуры данных:
Дополнительные поля
Классический пример этого — сохранение длины связанного списка в поле в корневом узле. Требуется немного больше работы, чтобы поддерживать его в актуальном состоянии, но затем запрос длины становится простым поиском поля вместо обхода O(n). Ваша структура данных может дать аналогичную выгоду: немного бухгалтерии во время некоторых операций в обмен на более высокую производительность в типичном сценарии использования.
Аналогично, сохранение указателей на часто необходимые узлы вместо выполнения дополнительных поисков. Это охватывает такие вещи, как «обратные» ссылки в двусвязном списке, чтобы сделать удаление узла O(1). Некоторые списки пропуска содержат «поисковый палец», где вы сохраняете указатель на то место, где вы только что были, предполагая, что это хорошая отправная точка для вашей следующей операции. Поисковые индексы
Большинство структур данных предназначены для одного типа запросов. Если вам нужны два разных типа запросов, то наличие дополнительного «представления» ваших данных может быть значительным улучшением. Например, набор структур может иметь первичный идентификатор (целое число), который вы используете для поиска в срезе, но иногда вам нужно искать с помощью вторичного идентификатора (строка). Вместо того чтобы перебирать срез, вы можете дополнить свою структуру данных картой либо от строки к идентификатору, либо непосредственно к самой структуре.
Дополнительная информация об элементах
Например, сохранение фильтра Блума всех вставленных элементов позволит вам быстро вернуть «нет совпадения» для поиска. Они должны быть небольшими и быстрыми, чтобы не перегружать остальную часть структуры данных. (Если поиск в вашей основной структуре данных дешёвый, стоимость фильтра Блума перевесит любую экономию.)
Если запросы дорогие, добавьте кэш
На более высоком уровне может помочь внутренний или внешний кэш (например, memcache). Это может быть излишним для одной структуры данных. Мы подробнее рассмотрим кэши ниже.
Все эти изменения полезны, когда данные, которые вам нужны, дёшево хранить и легко поддерживать в актуальном состоянии.
Это всё наглядные примеры того, как «меньше работать» на уровне структуры данных. Все они требуют места. В большинстве случаев, если вы оптимизируете для процессора, ваша программа будет использовать больше памяти. Это классический компромисс между пространством и временем.
Важно изучить, как этот компромисс может повлиять на ваши решения — это не всегда прямолинейно. Иногда небольшой объём памяти может дать значительную скорость, иногда компромисс линейный (удвоение использования памяти == удвоение ускорения производительности), иногда он значительно хуже: огромный объём памяти даёт лишь небольшое ускорение. То, где вам нужно находиться на этой кривой памяти/производительности, может повлиять на выбор алгоритма. Не всегда можно просто настроить параметр алгоритма. Разные варианты использования памяти могут быть совершенно разными алгоритмическими подходами.
Таблицы поиска также попадают в этот компромисс между пространством и временем. Простая таблица поиска может быть просто кешем ранее запрошенных вычислений.
Если область достаточно мала, весь набор результатов можно предварительно вычислить и сохранить в таблице. Примером этого может служить подход, используемый для быстрой реализации popcount, где количество установленных битов в байте хранится в таблице из 256 записей. Более крупная таблица может хранить биты, необходимые для всех 16-битных слов. В этом случае они хранят точные результаты.
Ряд алгоритмов для тригонометрических функций использует таблицы поиска в качестве отправной точки для расчёта.
Если ваша программа использует слишком много памяти, вы также можете пойти другим путём. Сократите использование пространства в обмен на увеличенные вычисления. Вместо того чтобы хранить вещи, рассчитывайте их каждый раз. Вы также можете сжимать данные в памяти и распаковывать их на лету, когда они вам понадобятся.
Если данные, которые вы обрабатываете, находятся на диске, вместо загрузки всего в оперативную память вы можете создать индекс для нужных фрагментов и хранить его в памяти или предварительно обработать файл на более мелкие рабочие фрагменты.
Книга Small Memory Software доступна онлайн и охватывает методы сокращения пространства, используемого вашими программами. Хотя изначально она была написана для разработчиков встраиваемых систем, идеи применимы и для программ на современном оборудовании, работающих с огромными объёмами данных.
Переупорядочьте свои данные
Устраните заполнение структуры. Удалите лишние поля. Используйте меньший тип данных.
Измените на более медленную структуру данных
Простые структуры данных часто имеют более низкие требования к памяти. Например, переход от тяжёлой по указателям древовидной структуры к использованию среза и линейного поиска.
Пользовательский формат сжатия для ваших данных
Алгоритмы сжатия сильно зависят от того, что сжимается. Лучше выбрать тот, который подходит вашим данным. Если у вас []byte, то что-то вроде snappy, gzip, lz4 работает хорошо. Для данных с плавающей запятой существует go-tsz для временных рядов и... FPC для научных данных
Было проведено множество исследований по сжатию целых чисел, обычно для поиска информации в поисковых системах. Примеры включают дельта-кодирование и varints до более сложных схем, включающих кодированные по Хаффману xor-разности. Вы также можете придумать собственные форматы сжатия, оптимизированные именно под ваши данные.
Вам нужно проверять данные или они могут оставаться сжатыми? Вам нужен произвольный доступ или только потоковая передача? Если вам нужен доступ к отдельным записям, но вы не хотите распаковывать всё целиком, вы можете сжать данные небольшими блоками и вести индекс, указывающий, какой диапазон записей находится в каждом блоке. Для доступа к отдельной записи достаточно проверить индекс и распаковать меньший блок данных.
Если ваши данные не просто обрабатываются, а будут записаны на диск, что насчёт миграции данных или добавления/удаления полей? Теперь вы будете иметь дело с необработанными байтами вместо хорошо структурированных типов Go, поэтому вам понадобится unsafe и придётся рассмотреть варианты сериализации.
Мы поговорим о макетах данных позже.
Современные компьютеры и иерархия памяти делают компромисс между пространством и временем менее ясным. Очень легко, чтобы таблицы поиска были «далеко» в памяти (и поэтому доступ к ним стоит дорого), что делает быстрее просто пересчитывать значение каждый раз, когда это необходимо.
Это также означает, что бенчмаркинг часто будет показывать улучшения, которые не реализуются в производственной системе из-за конкуренции за кэш (например, таблицы поиска находятся в кэше процессора во время бенчмаркинга, но всегда сбрасываются «реальными данными», когда используются в реальной системе).
Google в своей статье Jump Hash фактически рассмотрел это напрямую, сравнив производительность как на конкурентном, так и на неконкурентном кэше процессора. (См. графики 4 и 5 в статье Jump Hash.)
TODO: как смоделировать конкурентный кэш, показать дополнительные затраты.
Ещё один аспект, который следует учитывать, — это время передачи данных. Обычно сетевой и дисковый доступ очень медленный, и поэтому возможность загрузить сжатый фрагмент будет намного быстрее, чем дополнительное процессорное время, необходимое для распаковки данных после их получения. Как всегда, проведите бенчмарк. Двоичный формат обычно будет меньше и быстрее для анализа, чем текстовый, но ценой того, что он больше не будет читаться человеком.
Для передачи данных перейдите на менее разговорчивый протокол или дополните API, чтобы разрешить частичные запросы. Например, инкрементный запрос вместо того, чтобы принудительно извлекать весь набор данных каждый раз.
Если вы не меняете данные, другой основной вариант — изменить код.
Наибольшее улучшение, вероятно, произойдёт благодаря алгоритмическим изменениям. Это эквивалентно замене пузырьковой сортировки ($O(n^2)$) быстрой сортировкой ($O(n log n)$) или замене линейного сканирования по массиву ($O(n)$) бинарным поиском ($O(log n)$) или поиском по карте ($O(1)$).
Вот как программное обеспечение становится медленным. Структуры, изначально предназначенные для одного использования, перепрофилируются для чего-то, для чего они не были предназначены. Это происходит постепенно.
Важно иметь интуитивное представление об уровнях сложности big-O. Выбирайте правильную структуру данных для вашей задачи. Вам не обязательно всегда экономить циклы, но это просто предотвращает глупые проблемы с производительностью, которые могут быть замечены гораздо позже.
Основные классы сложности:
Ссылка: http://bigocheatsheet.com.
Допустим, вам нужно выполнить поиск в несортированном наборе данных. «Я должен использовать двоичный». Поиск «ты думаешь, зная, что двоичный поиск — это O(log n), который быстрее, чем O(n) линейный поиск. Однако двоичный поиск требует, чтобы данные были отсортированы, а это значит, что вам нужно сначала их отсортировать, что займёт O(n log n) времени. Если вы выполняете много поисков, то первоначальные затраты на сортировку окупятся. С другой стороны, если вы в основном выполняете поиск, возможно, массив был неправильным выбором, и вам лучше заплатить O(1) стоимость поиска для карты вместо этого.
Возможность анализировать вашу проблему с точки зрения нотации big-O также означает, что вы можете
выяснить, достигли ли вы предела того, что возможно для вашей проблемы,
и нужно ли вам изменить подходы, чтобы ускорить процесс. Например,
нахождение минимума несортированного списка — это O(n), потому что вам приходится просматривать
каждый элемент. Невозможно сделать это быстрее.
Если ваша структура данных статична, то обычно вы можете добиться гораздо большего, чем в динамическом случае. Становится проще построить оптимальную структуру данных, настроенную именно под ваши шаблоны поиска. Здесь могут иметь смысл такие решения, как минимальное идеальное хеширование или предварительно вычисленные фильтры Блума. Это также имеет смысл, если ваша структура данных «статична» достаточно долго, и вы можете амортизировать первоначальные затраты на построение через множество поисков.
Выберите самую простую разумную структуру данных и двигайтесь дальше. Это CS 101 для написания «немедленного программного обеспечения». Это должен быть ваш режим разработки по умолчанию. Если вы знаете, что вам нужен произвольный доступ, не выбирайте связанный список. Если вы знаете, что вам нужна последовательная навигация, не используйте карту. Требования меняются, и вы не всегда можете угадать будущее. Сделайте разумное предположение относительно рабочей нагрузки.
http://daslab.seas.harvard.edu/rum-conjecture/
Структуры данных для похожих задач будут различаться в том, когда они выполняют часть работы. Двоичное дерево сортирует понемногу при каждом вставке. Несортированный массив быстрее для вставки, но он несортирован: в конце, чтобы «завершить», вам нужно выполнить сортировку сразу.
При написании пакета для использования другими избегайте соблазна оптимизировать заранее для каждого отдельного случая использования. Это приведёт к нечитаемому коду. Структуры данных по своей сути одноцелевые. Вы не можете ни читать мысли, ни предсказывать будущее. Если пользователь говорит: «Ваш пакет слишком медленный для этого варианта использования», разумным ответом может быть: «Тогда используйте этот другой пакет здесь». Пакет должен «хорошо делать одну вещь».
Иногда гибридные структуры данных обеспечат необходимое улучшение производительности. Например, разделив данные на сегменты, вы можете ограничить свой поиск одним сегментом. Это всё равно будет стоить теоретических затрат O(n), но константа будет меньше. Мы вернёмся к этим видам настроек, когда перейдём к настройке программы.
Две вещи, которые люди забывают при обсуждении нотации big-O:
Во-первых, существует постоянный коэффициент. Два алгоритма, имеющие одинаковую алгоритмическую сложность, могут иметь разные постоянные коэффициенты. Представьте себе цикл по списку 100 раз против одного раза. Хотя оба они O(n), один имеет постоянный коэффициент, который в 100 раз выше.
Эти постоянные факторы являются причиной того, что хотя сортировка слиянием, быстрая сортировка и пирамидальная сортировка все O(n log n), все используют быструю сортировку, потому что она самая быстрая. У неё наименьший постоянный коэффициент.
Вторая вещь заключается в том, что big-O говорит только «по мере того, как n стремится к бесконечности». Он говорит о тенденции роста: «По мере увеличения чисел этот фактор роста будет доминировать во времени выполнения». Он ничего не говорит о фактической производительности или о том, как она ведёт себя при малых значениях n.
Часто существует точка отсечки, ниже которой более глупый алгоритм работает быстрее. Хороший пример из стандартного пакета сортировки библиотеки Go. Большую часть времени он использует быструю сортировку, но у него есть проход сортировки по оболочке, а затем сортировка вставками, когда размер раздела падает ниже 12 элементов.
Для некоторых алгоритмов постоянный коэффициент может быть настолько большим, что эта точка отсечения может быть больше, чем все разумные входные данные. То есть алгоритм O(n^2) быстрее, чем алгоритм O(n) для всех входных данных, с которыми вы, вероятно, будете иметь дело.
Это также означает, что вам необходимо знать репрезентативный ввод». Выбор подходящего алгоритма и написание хороших тестов производительности важны как для выбора наиболее подходящего алгоритма, так и для написания хороших тестов производительности.
10 элементов? 1000 элементов? 100 000 элементов?
Это работает и в обратную сторону: например, выбор более сложной структуры данных, которая даёт масштабирование O(n), вместо O(n^2), даже если тесты для небольших входных данных стали медленнее. Это также относится к большинству структур данных без блокировок. Они обычно медленнее в однопоточном случае, но более масштабируемы, когда их используют многие потоки.
Иерархия памяти в современных компьютерах немного усложняет ситуацию, поскольку кэши предпочитают предсказуемый доступ при сканировании среза по сравнению с фактически случайным доступом при отслеживании указателя. Тем не менее лучше всего начать с хорошего алгоритма. Мы поговорим об этом в разделе, посвящённом аппаратному обеспечению.
TODO: расширение последнего абзаца, упоминание нотации O() — это модель, где каждая операция имеет фиксированную стоимость. На современном оборудовании это неверное предположение.
Борьба может идти не всегда за сильнейшего, а гонка — не всегда за быстрейшего, но именно на них стоит ставить. — Редьярд Киплинг
Иногда лучший алгоритм для конкретной задачи — это не один алгоритм, а набор алгоритмов, специализированных для слегка разных классов входных данных. Этот «полиалгоритм» быстро определяет, с каким типом ввода ему нужно работать, а затем переходит к соответствующему пути кода. Именно это делает упомянутый выше пакет сортировки: определяет размер проблемы и выбирает другой алгоритм. Помимо объединения быстрой сортировки, сортировки Шелла и вставки, он также отслеживает глубину рекурсии быстрой сортировки и при необходимости вызывает пирамидальную сортировку. Пакеты string и bytes делают нечто подобное, определяя и специализируясь для разных случаев. Как и в случае сжатия данных, чем больше вы знаете о том, как выглядит ваш ввод, тем лучше может быть ваше индивидуальное решение. Даже если оптимизация не всегда применима, усложнение вашего кода путём определения того, что его безопасно использовать, и выполнения различной логики может стоить того.
Это также относится к подзадачам, которые должен решить ваш алгоритм. Например, возможность использовать сортировку по основанию может значительно повлиять на производительность или использование быстрого выбора, если вам нужна только частичная сортировка.
Иногда вместо специализации для вашей конкретной задачи лучше всего абстрагировать её в более общее пространство задач, которое хорошо изучено исследователями. Затем вы можете применить более общее решение к своей конкретной проблеме. Отображение вашей проблемы в область, в которой уже есть хорошо проработанные реализации, может стать значительным преимуществом.
Аналогично, использование более простого алгоритма означает, что компромиссы, анализ и детали реализации, скорее всего, будут более изучены и понятны, чем более эзотерические или экзотические и сложные.
Простые алгоритмы также могут быть быстрее. Эти два примера не являются изолированными случаями. https://go-review.googlesource.com/c/crypto/+/169037 https://go-review.googlesource.com/c/go/+/170322/
TODO: заметки о выборе алгоритма
TODO: улучшение поведения в худшем случае при незначительных затратах на среднее время выполнения линейное сопоставление регулярных выражений
Хотя большинство алгоритмов детерминированы, существует класс алгоритмов, использующих случайность как способ упростить сложное принятие решений. Вместо того чтобы иметь код, который делает правильные вещи, вы используете случайность для выбора, вероятно, не плохой вещи. Например, треп — это вероятностно сбалансированное бинарное дерево. Каждому узлу присвоен ключ, но также назначается случайное значение. При вставке в дерево следует обычный путь вставки бинарного дерева, но узлы также подчиняются свойству кучи на основе веса каждого узла, назначенного случайным образом. Этот более простой подход заменяет сложные решения для вращения деревьев (например, AVL и красно-чёрные деревья), но всё же поддерживает сбалансированное дерево с O(log n) вставкой/поиском «с высокой вероятностью». Пропускаемые списки — ещё одна подобная простая структура данных, которая использует случайность для создания «вероятно» O(log n) вставок и поисков.
Точно так же выбор случайного поворота для быстрой сортировки может быть проще, чем более сложный подход медианы медиан. Поиск хорошего опорного элемента и вероятность того, что плохие опорные элементы постоянно (случайно) выбираются и ухудшают производительность quicksort до O(n^2), исчезающе мала.
Рандомизированные алгоритмы классифицируются как алгоритмы «Монте-Карло» или «Лас-Вегас», в честь двух известных игорных заведений. Алгоритм Монте-Карло рискует корректностью: он может выдать неправильный ответ (или, в данном случае, несбалансированное бинарное дерево). Алгоритм Лас-Вегаса всегда выдаёт правильный ответ, но может выполняться очень долго.
Ещё один известный пример рандомизированного алгоритма — это алгоритм тестирования простоты Миллера-Рабина. Каждая итерация выдаст либо «не простое число», либо «возможно, простое». В то время как «непростое число» определено точно, «возможно, простое» верно с вероятностью не менее 1/2. То есть существуют непростые числа, для которых всё равно будет выведено «возможно, простое». Выполнив множество итераций Миллера-Рабина, мы можем сделать вероятность ошибки (то есть вывод «возможно, простого» для составного числа) настолько малой, насколько захотим. Если пройдёт 200 итераций, то можно сказать, что число составное с вероятностью максимум 1/(2^200).
Другая область, где играет роль случайность, называется «Сила двух случайных выборов». Изначально исследование применялось к балансировке нагрузки, но оказалось широко применимо ко многим задачам выбора. Идея заключается в том, чтобы вместо поиска наилучшего выбора из группы элементов случайно выбрать два и выбрать лучший из них. Возвращаясь к балансировке нагрузки (или цепям хеш-таблиц), сила двух случайных выборов уменьшает ожидаемую нагрузку (или длину цепи хеширования) с O(log n) элементов до O(log log n) элементов. Для получения дополнительной информации см. «The Power of Two Random Choices: A Survey of Techniques and Results» (https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf).
Рандомизированные алгоритмы:
TODO: пакетирование для уменьшения накладных расходов: https://lemire.me/blog/2018/04/17/iterating-in-batches-over-data-structures-can-be-much-faster/.
TODO:
Реальные входные данные редко соответствуют теоретическому «худшему случаю». Бенчмаркинг важен для понимания поведения вашей системы в производстве.
Вам нужно знать, какой класс входных данных будет видеть ваша система после развёртывания, и ваши бенчмарки должны использовать экземпляры из того же распределения. Как мы видели, разные алгоритмы имеют смысл при разных размерах входных данных. Если ожидаемый диапазон входных данных <100, то ваши бенчмарки должны отражать это. В противном случае выбор алгоритма, оптимального для n=10^6, может быть не самым быстрым.
Уметь генерировать репрезентативные тестовые данные. Разные распределения данных могут вызывать разное поведение вашего алгоритма: вспомните классический пример «quicksort — это O(n^2) при отсортированных данных». Аналогично, интерполяционный поиск — это O(log log n) для равномерно распределённых случайных данных, но O(n) в худшем случае. Знание того, как выглядят ваши входные данные, является ключом как к репрезентативным бенчмаркам, так и к выбору лучшего алгоритма. Если данные, которые вы используете для тестирования, не являются репрезентативными для реальных рабочих нагрузок, вы можете легко оптимизировать их для одного конкретного набора данных, «переобучив» свой код для работы с одним конкретным набором входных данных.
Это также означает, что ваши данные бенчмарка должны быть репрезентативны для реального мира. Использование чисто случайных входных данных может исказить поведение вашего алгоритма. Алгоритмы кэширования и сжатия используют искажённые распределения, отсутствующие в случайных данных, и поэтому будут работать хуже, в то время как бинарное дерево будет лучше работать со случайными значениями, поскольку они будут стремиться поддерживать дерево сбалансированным. (Кстати, это идея трепа.)
С другой стороны, рассмотрим случай тестирования системы с кешем. Если... Если бенчмарк состоит только из одного запроса, то каждый запрос будет попадать в кэш, что потенциально может дать очень нереалистичное представление о том, как система будет вести себя в реальном мире с более разнообразным шаблоном запросов.
Также обратите внимание, что некоторые проблемы, которые не очевидны на вашем ноутбуке, могут проявиться после развёртывания в продакшн и обработки 250 тысяч запросов в секунду на 40-ядерном сервере. Аналогично, поведение сборщика мусора во время бенчмаркинга может исказить реальное воздействие. Бывают (редкие) случаи, когда микробенчмарк показывает замедление, но реальная производительность улучшается. Микробенчмарки могут помочь направить вас в правильном направлении, но лучше всего иметь возможность полностью протестировать влияние изменения на всю систему.
Написание хороших бенчмарков может быть сложным.
Используйте геометрическое среднее для сравнения групп бенчмарков.
Оценка точности бенчмарка:
Настройка программы раньше была искусством, но потом компиляторы стали лучше. Так что теперь оказывается, что компиляторы могут оптимизировать простой код лучше, чем сложный. Компилятору Go ещё предстоит пройти долгий путь, чтобы сравняться с gcc и clang, но это означает, что вам нужно быть осторожным при настройке и особенно при обновлении версий Go, чтобы ваш код не стал «хуже». Определённо бывают случаи, когда уловки для обхода отсутствия конкретной оптимизации компилятора становились медленнее после улучшения компилятора.
Моя реализация шифра RC6 ускорилась на 10% для внутреннего цикла, просто переключившись на encoding/binary и math/bits вместо моих собственных версий.
Аналогично, пакет compress/bzip2 был ускорен путём перехода на более простой код, который компилятор мог лучше оптимизировать.
Если вы работаете над конкретной проблемой генерации кода во время выполнения или компилятором, всегда документируйте свои изменения со ссылкой на исходную проблему. Это позволит вам быстро вернуться к оптимизации, как только ошибка будет исправлена.
Боритесь с искушением использовать фольклорные «советы по производительности» или даже обобщать свой собственный опыт. К каждой ошибке производительности нужно подходить исходя из её собственных достоинств. Даже если что-то работало раньше, обязательно профилируйте, чтобы убедиться, что исправление всё ещё применимо. Ваш предыдущий опыт может направлять вас, но не применяйте предыдущие оптимизации слепо.
Настройка программы — это итеративный процесс. Продолжайте пересматривать свой код и видеть, какие изменения можно внести. Убедитесь, что вы добиваетесь прогресса на каждом этапе. Часто одно улучшение позволяет сделать другие. (Теперь, когда я не делаю A, я могу упростить B, делая C вместо этого.) Это означает, что вы должны продолжать смотреть на общую картину и не слишком увлекаться одним небольшим набором строк.
Как только вы определились с правильным алгоритмом, настройка программы — это процесс улучшения реализации этого алгоритма. В нотации Big-O это процесс уменьшения констант, связанных с вашей программой.
Вся настройка программы заключается либо в том, чтобы сделать медленное быстрым, либо делать медленное реже. Алгоритмические изменения также попадают в эти категории, но мы будем рассматривать меньшие изменения. То, как именно вы это делаете, зависит от того, как меняются технологии.
Сделать медленное быстрым можно, заменив SHA1 или hash/fnv1 более быстрой хеш-функцией. Делать медленное реже можно, сохраняя результат расчёта хеша большого файла, чтобы не приходилось делать это несколько раз.
Сохраняйте комментарии. Если что-то не нужно делать, объясните почему. Часто при оптимизации алгоритма вы обнаружите шаги, которые не нужно выполнять при некоторых обстоятельствах. Документируйте их. Кто-то другой может подумать, что это ошибка и её нужно вернуть.
Пустые программы дают неправильный ответ в мгновение ока.
Легко быть быстрым, если не нужно быть правильным.
«Правильность» может зависеть от проблемы. Эвристические алгоритмы... Кэширование общих случаев:
Мы все знакомы с memcache, но есть также кэши в процессе работы программы. Использование кэша в процессе работы экономит стоимость как сетевого вызова, так и стоимость сериализации. С другой стороны, это увеличивает нагрузку на сборщик мусора (GC), поскольку нужно отслеживать больше памяти. Также необходимо учитывать стратегии вытеснения, аннулирования кэша и потокобезопасность. Внешний кэш обычно обрабатывает вытеснение за вас, но аннулирование кэша остаётся проблемой. Потокобезопасность также может быть проблемой для внешних кэшей, поскольку они становятся эффективно общим изменяемым состоянием либо между разными горутинами в одном сервисе, либо даже между разными экземплярами сервиса, если внешний кэш является общим.
Кэш сохраняет информацию, которую вы только что вычислили, в надежде, что сможете использовать её снова в ближайшее время и сэкономить время вычислений. Кэшу не обязательно быть сложным. Даже сохранение одного элемента — самого последнего увиденного запроса/ответа — может быть большим преимуществом, как видно на примере time.Parse().
При использовании кэшей важно сравнить стоимость (с точки зрения фактического времени работы и сложности кода) вашей логики кэширования с простым повторным получением или пересчётом данных. Более сложные алгоритмы, которые дают более высокие показатели попадания, обычно сами по себе недешёвы. Случайное вытеснение из кэша просто и быстро и может быть эффективным во многих случаях. Аналогично случайная вставка в кэш может ограничить ваш кэш только популярными элементами с минимальной логикой. Хотя они могут быть не такими эффективными, как более сложные алгоритмы, большое улучшение будет заключаться в добавлении кэша: выбор конкретного алгоритма кэширования даёт лишь незначительные улучшения.
Важно протестировать выбранный вами алгоритм вытеснения кэша с помощью реальных данных. Если в реальном мире повторяющиеся запросы достаточно редки, может оказаться дороже хранить кэшированные ответы, чем просто пересчитывать их при необходимости. У меня были сервисы, где тестирование с производственными данными показало, что даже оптимальный кэш не стоил того. У нас просто не было достаточного количества повторяющихся запросов, чтобы усложнение кэша имело смысл.
Ваш ожидаемый коэффициент попаданий в кэш важен. Вы захотите экспортировать соотношение в свой стек мониторинга. Изменение соотношений покажет сдвиг в трафике. Тогда пришло время пересмотреть размер кэша или политику истечения срока действия.
Большой кэш может увеличить нагрузку на GC. В крайнем случае (отсутствие или минимальное вытеснение, кэширование всех запросов к дорогостоящей функции) это может превратиться в мемоизацию.
Настройка программы:
Настройка программы — это искусство постепенного улучшения программы небольшими шагами. Эгон Элбре излагает свою процедуру:
Настройки могут принимать разные формы.
a < b/c => a * c < b;Многие народные советы по настройке производительности для оптимизации полагаются на плохо оптимизирующие компиляторы и побуждают программиста выполнять эти преобразования вручную. Компиляторы уже 15 лет используют сдвиги вместо умножения или деления на степень двойки — никто не должен делать это вручную. Аналогично, инвариантные вычисления, вынесение за пределы цикла, базовое разворачивание цикла, устранение общих подвыражений и многое другое автоматически выполняется gcc, clang и подобными. Компилятор Go делает многие из них и продолжает улучшаться. Как всегда, проведите тестирование перед переходом на новую версию.
Преобразования, которые компилятор не может выполнить, зависят от того, знаете ли вы что-то об алгоритме, о входных данных, об инвариантах в вашей системе и других предположениях, которые вы можете сделать, и от учёта этого неявного знания при удалении или изменении шагов в структуре данных.
Каждая оптимизация кодифицирует предположение о ваших данных. Эти должны быть задокументированы и, ещё лучше, протестированы. Эти предположения будут причиной сбоя вашей программы, замедления её работы или начала возврата неверных данных по мере развития системы.
Улучшения настройки программы накапливаются. 5x 3% улучшений — это 15% улучшения. При внесении оптимизаций стоит подумать об ожидаемом повышении производительности. Замена хеш-функции на более быструю — это улучшение постоянного коэффициента.
Понимание ваших требований и того, где их можно изменить, может привести к повышению производительности. Одна проблема, которая была представлена в канале Slack #performance Gophers, заключалась в том, сколько времени тратилось на создание уникального идентификатора для карты пар ключ/значение строк. Исходное решение состояло в извлечении ключей, сортировке их и передаче полученной строки в хеш-функцию. Улучшенное решение, которое мы придумали, заключалось в отдельном хешировании ключей/значений по мере их добавления на карту, а затем xor всех этих хешей вместе для создания идентификатора.
Вот пример специализации.
Допустим, мы обрабатываем огромный файл журнала за один день, и каждая строка начинается с временной метки.
Sun 4 Mar 2018 14:35:09 PST <...........................>
Для каждой строки мы будем вызывать time.Parse(), чтобы превратить её в эпоху. Если профилирование покажет нам, что time.Parse() является узким местом, у нас есть несколько вариантов, как ускорить процесс.
Самый простой — сохранить одноэлементный кэш ранее увиденной временной метки и связанной с ней эпохи. Пока в нашем файле журнала есть несколько строк за одну секунду, это будет выигрышем. Для случая файла журнала из 10 миллионов строк эта стратегия сокращает количество дорогостоящих вызовов time.Parse() с 10 000 000 до 86400 — по одному для каждой уникальной секунды.
TODO: пример кода для одноэлементного кэша
Можем ли мы сделать больше? Поскольку мы точно знаем, в каком формате находятся временные метки и что все они приходятся на один день, мы можем написать собственную логику синтаксического анализа времени, учитывающую это. Мы можем вычислить эпоху полуночи, затем извлечь час, минуту и секунду из строки временной метки — все они будут находиться в фиксированных смещениях в строке — и выполнить некоторые целочисленные вычисления.
TODO: код примера для версии со смещением строки Пайк
Техники, специфичные для архитектуры, на которой выполняется код.
Введение в кэши процессора.
Прогнозирование ветвлений.
Удалите ветки из внутренних циклов: if a { for { } } else { for { } }, вместо for { if a { } else { } }. Сравните с прогнозированием ветвления. Структура для избежания ветвления:
if i % 2 == 0 { evens++ } else { odds++ }
counts[i & 1] ++ «код без ветвей», сравните с ним; не всегда быстрее, но часто труднее для чтения. TODO: пример подсчёта ASCII классов с бенчмарками.
Сортировка данных может помочь повысить производительность за счёт как локальности кэша, так и прогнозирования ветвлений, даже учитывая время, необходимое для сортировки.
Накладные расходы на вызовы функций: инлайнер становится лучше.
Уменьшите количество копий данных (включая повторяющиеся большие списки параметров функций).
Комментарий о числах Джеффа Дина 2002 года (плюс обновления).
TODO: небольшой комментарий об оптимизации выравнивания кода (или деоптимизации).
Вам нужен мьютекс для защиты общего изменяемого состояния. Если у вас много конфликтов мьютексов, вам нужно либо уменьшить общее количество, либо сделать его неизменяемым. Два способа уменьшить общее: 1) разделить блокировки или 2) обрабатывать независимо и объединять впоследствии. Чтобы уменьшить изменяемость: сделайте вашу структуру данных доступной только для чтения. Вы также можете уменьшить время, в течение которого данные должны быть общими, уменьшив критическую секцию — удерживайте блокировку как можно меньше. Иногда RWMutex будет достаточно, хотя обратите внимание, что они медленнее, но позволяют нескольким читателям.
Если вы разделяете блокировки, будьте осторожны с общими кэш-строками. Вам нужно заполнить, чтобы избежать перескакивания кэш-строк между процессорами.
var stripe [8]struct{ sync.Mutex; _ [7]uint64 } // мьютекс 64-битный; заполнение заполняет остальную часть кэш-линии
Не делайте ничего дорогого в критической секции, если можете. Это включает такие вещи, как ввод-вывод (который дёшев, но медленен).
TODO: как разложить задачу для параллельного выполнения. TODO: причины, по которым параллельная реализация может работать медленнее (накладные расходы на связь, лучший алгоритм является последовательным и т. д.).
В большинстве случаев вам не придётся иметь дело с отдельной задачей, связанной с процессором. Это простой случай. Если у вас есть сервис, который нужно оптимизировать, вам нужно взглянуть на всю систему. Мониторинг. Метрики. Регистрируйте множество вещей в течение времени, чтобы вы могли видеть, как они ухудшаются, и чтобы вы могли увидеть влияние ваших изменений в рабочей среде.
Ссылки для проектирования системы: SRE Book, практическое проектирование распределённой системы.*
Дополнительное оснащение: больше регистрации + анализ.*
Два основных правила: либо ускоряйте медленные процессы, либо делайте их реже.*
Распределённая трассировка для отслеживания узких мест на более высоком уровне.*
Шаблоны запросов для запроса одного сервера вместо массового.*
Проблемы с производительностью могут быть не связаны с вашим кодом, но вам всё равно придётся их решать.*
https://docs.microsoft.com/en-us/azure/architecture/antipatterns/
Оснащение
Это краткая шпаргалка по использованию инструментария pprof. Существует множество других руководств по этому вопросу. Ознакомьтесь с https://github.com/davecheney/high-performance-go-workshop.
Советы по реализации работ: (вместо «алгоритм» читайте также «структура данных»)
«Современные» алгоритмы, как правило, имеют более низкую теоретическую сложность, но высокие постоянные коэффициенты и большую сложность реализации. Одним из классических примеров этого являются кучи Фибоначчи. Они известны своей сложностью и имеют огромный постоянный коэффициент. Было опубликовано несколько статей, сравнивающих различные реализации куч на разных рабочих нагрузках, и в целом 4- или 8-арные неявные кучи постоянно выходят на первое место. И даже в тех случаях, когда куча Фибоначчи должна быть быстрее (из-за O(1) «уменьшения ключа»), эксперименты с алгоритмом Дейкстры показывают, что она работает быстрее при использовании прямого удаления и добавления кучи.
Аналогично, treaps или skiplists против более сложных красно-чёрных или AVL деревьев. На современном оборудовании «более медленный» алгоритм может быть достаточно быстрым. Самый быстрый алгоритм часто можно заменить на другой, который почти так же быстр и гораздо проще для понимания.
— Дуглас У. Джонс, Университет Айовы
и
Правило 3. Необычные алгоритмы работают медленно при малых значениях n, а значение n обычно мало. Необычные алгоритмы имеют большие константы. Пока вы не убедитесь, что значение n часто будет большим, не усложняйте. Правило 4. Необычные алгоритмы содержат больше ошибок, чем простые, и их намного сложнее реализовать. Используйте простые алгоритмы, а также простые структуры данных. — «Заметки о программировании на C» (Роб Пайк, 1989)
Добавленная сложность должна быть достаточной, чтобы выигрыш действительно стоил того. Ещё один пример — алгоритмы вытеснения из кэша. Разные алгоритмы могут иметь гораздо более высокую сложность лишь для небольшого улучшения коэффициента попаданий. Конечно, вы можете не суметь протестировать это, пока у вас не будет работающей реализации и вы не интегрируете её в свою программу.
Иногда в статье будут графики, но, подобно тенденции публиковать только положительные результаты, они будут искажены в пользу демонстрации того, насколько хорош новый алгоритм.
Часто более ранние статьи легче для понимания и обязательно содержат более простые алгоритмы.
Не все статьи хороши.
Посмотрите на контекст, в котором была написана статья. Определите предположения об оборудовании: дисковое пространство, использование памяти и т. д. Некоторые старые статьи делают разные компромиссы, которые были разумными в 70-х или 80-х годах, но не обязательно применимы к вашему случаю использования. Например, то, что они считают «разумным» соотношением использования памяти и диска. Размеры памяти сейчас на порядки больше, а твердотельные накопители изменили штраф за задержку при использовании диска. Аналогично некоторые потоковые алгоритмы разработаны для оборудования маршрутизаторов, что может затруднить перевод в программное обеспечение.
Убедитесь, что предположения, которые делает алгоритм относительно ваших данных, верны.
Это потребует некоторого изучения. Вероятно, вы не захотите реализовывать первую найденную статью.
Убедитесь, что вы понимаете алгоритм. Это кажется очевидным, но иначе отладить его будет невозможно.
https://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/07/paper-reading.pdf
Хорошее понимание может позволить вам извлечь ключевую идею из статьи и, возможно, применить её непосредственно к вашей проблеме, что может быть проще, чем полная переделка.
Оригинальная статья о структуре данных или алгоритме не всегда лучшая. Более поздние статьи могут содержать лучшие объяснения.
Некоторые статьи публикуют справочный исходный код, с которым вы можете сравнить свой, но
Также обратите внимание на другие реализации на GitHub: они могут иметь те же (или другие!) ошибки, что и ваша.
Другие ресурсы по этой теме:
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )