Алгоритмическая эффективность

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

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

Например, пузырьковая сортировка и временная сортировка - это алгоритмы для сортировки списка элементов от наименьшего к наибольшему. Пузырьковая сортировка сортирует список по времени, пропорциональному количеству элементов в квадрате ( см. Нотацию Big O ), но требует лишь небольшого количества дополнительной памяти, которая является постоянной по отношению к длине списка ( ). Timsort сортирует список по времени линейнофмически (пропорционально количеству, умноженному на его логарифм) по длине списка ( ), но требует места, линейного по длине списка (${\ Displaystyle \ scriptstyle {{\ mathcal {O}} \ left (п ^ {2} \ right)}}$${\ textstyle \ scriptstyle {{\ mathcal {O}} \ left (1 \ right)}}$${\ textstyle \ scriptstyle {\ mathcal {O \ left (n \ log n \ right)}}}$${\ textstyle \ scriptstyle {\ mathcal {O \ left (n \ right)}}}$). Если для данного приложения требуется высокоскоростная сортировка больших списков, лучше выбрать timsort; однако, если минимизация объема памяти, используемого при сортировке, важнее, пузырьковая сортировка - лучший выбор.

Фон [ править ]

Важность эффективности по отношению ко времени была подчеркнута Адой Лавлейс в 1843 году применительно к механической аналитической машине Чарльза Бэббиджа :

"Практически в каждом вычислении возможно большое разнообразие схем для последовательности процессов, и различные соображения должны влиять на выбор среди них для целей вычислительной машины. Одна важная цель состоит в том, чтобы выбрать такую ​​схему, которая должна стремиться к минимум времени, необходимого для завершения расчета » ^[1]

Ранние электронные компьютеры были сильно ограничены как скоростью операций, так и объемом доступной памяти. В некоторых случаях было обнаружено, что существует компромисс между пространством и временем , при котором задача может быть обработана либо с помощью быстрого алгоритма, который использует довольно много рабочей памяти, либо с помощью более медленного алгоритма, который использует очень мало рабочей памяти. . Тогда инженерный компромисс заключался в использовании самого быстрого алгоритма, который уместился бы в доступной памяти.

Современные компьютеры значительно быстрее ранних компьютеров и имеют гораздо больший объем доступной памяти ( гигабайты вместо килобайт ). Тем не менее, Дональд Кнут подчеркнул, что эффективность по-прежнему остается важным фактором:

«В общепринятых инженерных дисциплинах легко достижимое улучшение на 12% никогда не считается маргинальным, и я считаю, что такая же точка зрения должна преобладать в разработке программного обеспечения» ^[2]

Обзор [ править ]

Алгоритм считается эффективным, если его потребление ресурсов, также известное как вычислительные затраты, находится на приемлемом уровне или ниже. Грубо говоря, «приемлемый» означает: он будет работать в течение разумного промежутка времени или пространства на доступном компьютере, обычно в зависимости от размера входных данных. С 1950-х годов в компьютерах произошел резкий рост как доступной вычислительной мощности, так и доступного объема памяти, поэтому нынешние приемлемые уровни были бы неприемлемыми даже 10 лет назад. Фактически, из-за примерного удвоения мощности компьютера каждые 2 года задачи, которые приемлемо эффективны на современных смартфонах и встроенных системах, могли оказаться неприемлемо неэффективными для промышленных предприятий.сервера 10 лет назад.

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

Есть много способов, которыми можно измерить ресурсы, используемые алгоритмом: два наиболее распространенных показателя - это скорость и использование памяти; другие меры могут включать скорость передачи, временное использование диска, долгосрочное использование диска, энергопотребление, общую стоимость владения , время отклика на внешние стимулы и т. д. Многие из этих мер зависят от размера входных данных алгоритма, т. е. количество данных для обработки. Они также могут зависеть от способа организации данных; например, некоторые алгоритмы сортировки плохо работают с данными, которые уже отсортированы или отсортированы в обратном порядке.

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

Теоретический анализ [ править ]

При теоретическом анализе алгоритмов обычной практикой является оценка их сложности в асимптотическом смысле. Наиболее часто используемые обозначения для описания потребления ресурсов или «сложности» является Дональд Кнут «s Big O обозначение , представляющее сложность алгоритма в зависимости от размера входного . Обозначение Big O - это асимптотическая мера сложности функции, где примерно означает, что время, необходимое для алгоритма, пропорционально , исключая члены более низкого порядка, которые вносят меньший вклад, чем в рост функции, когда она становится сколь угодно большой . Эта оценка может ввести в заблуждение, когда${\ textstyle \ scriptstyle n}$${\ textstyle \ scriptstyle {е \ влево (п \ вправо) \, = \, {\ mathcal {O}} \ влево (г \ влево (п \ вправо) \ вправо)}}$${\ Displaystyle \ scriptstyle {г \ влево (п \ вправо)}}$${\ Displaystyle \ scriptstyle {г \ влево (п \ вправо)}}$${\ displaystyle \ scriptstyle n}$ ${\ textstyle \ scriptstyle n}$мала, но обычно достаточно точна, когда она велика, поскольку обозначения асимптотические. Например, пузырьковая сортировка может быть быстрее сортировки слиянием, когда нужно отсортировать только несколько элементов; однако любая реализация, вероятно, будет соответствовать требованиям к производительности для небольшого списка. Обычно программистов интересуют алгоритмы, которые эффективно масштабируются до больших размеров входных данных, и сортировка слиянием предпочтительнее пузырьковой сортировки для списков длины, встречающихся в большинстве программ с большим объемом данных.${\ textstyle \ scriptstyle n}$

Некоторые примеры нотации Big O, применяемой к асимптотической временной сложности алгоритмов, включают:

Обозначение	Имя	Примеры
${\ Displaystyle {\ mathcal {O}} (1) \,}$	постоянный	Нахождение медианы из отсортированного списка измерений; Использование таблицы поиска постоянного размера ; Использование подходящей хеш-функции для поиска элемента.
${\ Displaystyle {\ mathcal {O}} (\ журнал {п}) \,}$	логарифмический	Поиск элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева поиска, а также все операции в биномиальной куче .
${\ Displaystyle {\ mathcal {O}} (п) \,}$	линейный	Нахождение элемента в несортированном списке или искаженном дереве (худший случай) или в несортированном массиве; Добавление двух n- битных целых чисел с помощью пульсации переноса .
${\ Displaystyle {\ mathcal {O}} (п \ журнал п) \,}$	linearithmic , loglinear или квазилинейный	Выполнение быстрого преобразования Фурье ; пирамидальная сортировка , быстрая сортировка ( лучший и средний случай ), или сортировка слияния
${\ Displaystyle {\ mathcal {O}} (п ^ {2}) \,}$	квадратичный	Умножение двух n- значных чисел простым алгоритмом ; пузырьковая сортировка (наихудший случай или простая реализация), сортировка Shell , быстрая сортировка ( наихудший случай ), сортировка выбора или сортировка вставкой
${\ displaystyle {\ mathcal {O}} (c ^ {n}), \; c> 1}$	экспоненциальный	Нахождение оптимального (не приближенного ) решения задачи коммивояжера с помощью динамического программирования ; определение эквивалентности двух логических операторов с помощью перебора

Бенчмаркинг: измерение производительности [ править ]

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

Некоторые тесты предоставляют возможности для проведения анализа, сравнивающего относительную скорость различных компилируемых и интерпретируемых языков, например ^{[3] [4]} и The Computer Language Benchmarks Game сравнивает производительность реализаций типичных проблем программирования на нескольких языках программирования.

Даже создание тестов « сделай сам » может продемонстрировать относительную производительность различных языков программирования с использованием множества критериев, заданных пользователем. Это довольно просто, как показывает пример Кристофера В. Коуэлл-Шаха «Обзор производительности девяти языков». ^[5]

Проблемы реализации [ править ]

Проблемы реализации также могут влиять на эффективность, такие как выбор языка программирования или способ, которым фактически кодируется алгоритм ^[6], или выбор компилятора для конкретного языка, или используемые параметры компиляции , или даже используемая операционная система . Во многих случаях язык, реализованный интерпретатором, может быть намного медленнее, чем язык, реализованный компилятором. ^[3] См. Статьи о языках своевременной компиляции и интерпретируемых языках .

Существуют и другие факторы, которые могут повлиять на проблемы с временем или пространством, но которые могут быть вне контроля программиста; они включают в себя выравнивание данных , детализацию данных , кэш локальность , когерентность кэша , вывоз мусора , параллелизм на уровень команд , многопоточность (на любом аппаратном или программном уровне), одновременно многозадачность и подпрограмму вызовы. ^[7]

Некоторые процессоры имеют возможности векторной обработки , что позволяет одной инструкции работать с несколькими операндами ; Программисту или компилятору может быть или непросто использовать эти возможности. Алгоритмы, предназначенные для последовательной обработки, могут нуждаться в полной переработке, чтобы использовать параллельную обработку , или их можно легко перенастроить. По мере роста важности параллельных и распределенных вычислений в конце 2010- х годов все больше инвестиций вкладывается в эффективные высокоуровневые API - интерфейсы для параллельных и распределенных вычислительных систем, таких как CUDA , TensorFlow , Hadoop., OpenMP и MPI .

Другая проблема, которая может возникнуть при программировании, заключается в том, что процессоры, совместимые с одним и тем же набором инструкций (например, x86-64 или ARM ), могут реализовывать инструкцию по-разному, поэтому инструкции, которые относительно быстрые на некоторых моделях, могут быть относительно медленными на других моделях. . Это часто создает проблемы для оптимизации компиляторов , которые должны обладать обширными знаниями о конкретном процессоре и другом оборудовании, доступном на цели компиляции, чтобы наилучшим образом оптимизировать программу по производительности. В крайнем случае компилятор может быть вынужден эмулировать инструкции, не поддерживаемые целевой платформой компиляции, заставляя его генерировать код илисвяжите вызов внешней библиотеки, чтобы получить результат, который в противном случае невозможно было бы вычислить на этой платформе, даже если он изначально поддерживается и более эффективен на оборудовании на других платформах. Это часто имеет место во встроенных системах в отношении арифметики с плавающей запятой , где небольшие и маломощные микроконтроллеры часто не имеют аппаратной поддержки для арифметики с плавающей запятой и, таким образом, требуют дорогостоящих в вычислительном отношении программных программ для выполнения вычислений с плавающей запятой.

Меры использования ресурсов [ править ]

Меры обычно выражаются как функция размера входных данных .${\ displaystyle \ scriptstyle {n}}$

Двумя наиболее распространенными мерами являются:

• Время : сколько времени занимает выполнение алгоритма?
• Пространство : сколько оперативной памяти (обычно ОЗУ) требуется алгоритму? Это имеет два аспекта: объем памяти, необходимый для кода (использование вспомогательного пространства), и объем памяти, необходимый для данных, с которыми работает код (внутреннее использование пространства).

Для компьютеров, питание которых осуществляется от аккумулятора (например, ноутбуков и смартфонов ), или для очень длинных / больших вычислений (например, суперкомпьютеры ), другие представляющие интерес меры:

• Прямое энергопотребление : мощность, необходимая непосредственно для работы компьютера.
• Косвенное энергопотребление : мощность, необходимая для охлаждения, освещения и т. Д.

По состоянию на 2018 год ^{[Обновить]}потребление энергии растет как важный показатель для вычислительных задач всех типов и во всех масштабах, начиная от встроенных устройств Интернета вещей и заканчивая устройствами системы на кристалле и фермами серверов . Эту тенденцию часто называют экологичными вычислениями .

В некоторых случаях могут быть уместны и менее распространенные меры вычислительной эффективности:

• Размер передачи : ограничивающим фактором может быть полоса пропускания. Сжатие данных может использоваться для уменьшения объема передаваемых данных. Отображение картинки или изображения (например, логотипа Google ) может привести к передаче десятков тысяч байтов (в данном случае 48 КБ) по сравнению с передачей шести байтов для текста «Google». Это важно для вычислительных задач, связанных с вводом-выводом .
• Внешнее пространство : пространство, необходимое на диске или другом внешнем запоминающем устройстве; это может быть временное хранение на время выполнения алгоритма, или это может быть долгосрочное хранение, которое необходимо перенести для дальнейшего использования.
• Время отклика ( задержка ): это особенно актуально в приложении реального времени, когда компьютерная система должна быстро реагировать на какое-то внешнее событие .
• Общая стоимость владения : особенно если компьютер предназначен для работы с одним конкретным алгоритмом.

Время [ править ]

Теория [ править ]

Проанализируйте алгоритм, обычно используя анализ временной сложности, чтобы получить оценку времени выполнения в зависимости от размера входных данных. Результат , как правило , выражается с помощью Big O обозначения . Это полезно для сравнения алгоритмов, особенно когда нужно обработать большой объем данных. Для сравнения производительности алгоритмов при небольшом объеме данных необходимы более подробные оценки, хотя это, вероятно, будет иметь меньшее значение. Алгоритмы, включающие параллельную обработку, могут быть более трудными для анализа .

Практика [ править ]

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

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

Этот вид теста также сильно зависит от выбора конкретного языка программирования, компилятора и параметров компилятора, поэтому сравниваемые алгоритмы должны быть реализованы в одних и тех же условиях.

Пробел [ править ]

Этот раздел касается использования ресурсов памяти ( регистры , кеш , RAM , виртуальная память , вторичная память ) во время выполнения алгоритма. Что касается временного анализа, описанного выше, проанализируйте алгоритм, обычно используя анализ пространственной сложности, чтобы получить оценку необходимой оперативной памяти в зависимости от размера входных данных. Результат , как правило , выражается с помощью Big O обозначения .

Следует учитывать до четырех аспектов использования памяти:

• Объем памяти, необходимый для хранения кода алгоритма.
• Объем памяти, необходимый для входных данных .
• Объем памяти, необходимый для любых выходных данных .
  • Некоторые алгоритмы, такие как сортировка, часто меняют порядок входных данных и не требуют дополнительного места для выходных данных. Это свойство называется операцией « на месте ».
• Объем памяти, необходимый в качестве рабочего пространства во время расчета.
  • Сюда входят локальные переменные и любое пространство стека, необходимое для подпрограмм, вызываемых во время вычислений; это пространство стека может быть значительным для алгоритмов, использующих рекурсивные методы.

Ранние электронные компьютеры и ранние домашние компьютеры имели относительно небольшой объем рабочей памяти. Например, автоматический калькулятор с электронным запоминающим устройством (EDSAC) 1949 года имел максимальную рабочую память 1024 17-битных слов, тогда как Sinclair ZX80 1980 года изначально имел 1024 8-битных байта рабочей памяти. В конце 2010- х годов для персональных компьютеров типично иметь от 4 до 32 ГБ оперативной памяти, что более чем в 300 миллионов раз превышает объем памяти.

Кеширование и иерархия памяти [ править ]

Современные компьютеры могут иметь относительно большие объемы памяти (возможно, гигабайты), поэтому необходимость втиснуть алгоритм в ограниченный объем памяти - гораздо меньшая проблема, чем раньше. Но наличие четырех разных категорий памяти может иметь значение:

• Регистры процессора , самая быстрая из технологий компьютерной памяти с наименьшим объемом памяти. Большинство прямых вычислений на современных компьютерах происходит с операндами источника и назначения в регистрах перед обновлением в кеш-памяти, основной памяти и виртуальной памяти, если это необходимо. В ядре процессора обычно имеется порядка сотен байтов или меньше доступных регистров, хотя регистровый файл может содержать больше физических регистров, чем архитектурные регистры, определенные в архитектуре набора команд.
• Кэш-память является второй по быстродействию и второй по размеру доступной памятью в иерархии памяти. Кеши присутствуют в процессорах, графических процессорах, жестких дисках и внешних периферийных устройствах и обычно реализуются в статической оперативной памяти . Кеши памяти многоуровневые ; более низкие уровни крупнее, медленнее и , как правило , совместно между ядрами процессора в многоядерных процессорах . Для обработки операндов в кэш-памяти блок обработки должен извлечь данные из кеша, выполнить операцию в регистрах и записать данные обратно в кэш. Это работает на скоростях, сопоставимых (примерно в 2-10 раз медленнее) с арифметико-логическим блоком CPU или GPU илиблок с плавающей запятой, если он находится в кэше L1 . ^[8] Это примерно в 10 раз медленнее, если есть промах кэша L1, и он должен быть получен и записан в кеш L2 , и еще в 10 раз медленнее, если есть промах кэша L2, и он должен быть получен из L3 кеш , если есть.
• Основная физическая память чаще всего реализуется в динамической RAM (DRAM). Основная память намного больше (обычно гигабайт по сравнению с ≈8 мегабайт ), чем кэш ЦП L3, а задержки чтения и записи обычно в 10–100 раз меньше. ^[8] По состоянию на 2018 год ^{[Обновить]}ОЗУ все чаще внедряется на кристалле процессоров в виде памяти ЦП или ГП .
• Виртуальная память чаще всего реализуется с точки зрения вторичного хранилища, такого как жесткий диск , и является расширением иерархии памяти, которая имеет гораздо больший объем хранилища, но гораздо большую задержку, обычно примерно в 1000 раз медленнее, чем промах кеша для значения в ОЗУ. . ^[8] Виртуальная память изначально была мотивирована для создания впечатления наличия большего количества доступной памяти, чем было действительно доступно, однако в современном использовании виртуальная память более важна из-за компромисса между пространством и временем и возможности использования виртуальных машин . ^[8] Промахи кэша из основной памяти называются ошибками страниц., и влечет за собой огромные потери производительности программ.

Алгоритм, потребности в памяти которого умещаются в кэш-памяти, будет намного быстрее, чем алгоритм, который умещается в основной памяти, который, в свою очередь, будет намного быстрее, чем алгоритм, который должен прибегать к виртуальной памяти. Из-за этого политики замены кеша чрезвычайно важны для высокопроизводительных вычислений, как и программирование с учетом кеширования и выравнивание данных . Чтобы еще больше усложнить проблему, некоторые системы имеют до трех уровней кэш-памяти с различными эффективными скоростями. Разные системы будут иметь разное количество этих различных типов памяти, поэтому влияние потребностей алгоритмов в памяти может сильно различаться от одной системы к другой.

На заре электронных вычислений, если алгоритм и его данные не помещались в основную память, алгоритм нельзя было использовать. В настоящее время использование виртуальной памяти, по-видимому, обеспечивает большой объем памяти, но за счет производительности. Если алгоритм и его данные умещаются в кэш-памяти, то можно получить очень высокую скорость; в этом случае минимизация пространства также поможет минимизировать время. Это называется принципом локальности , и его можно подразделить на эталонную локальность , пространственную локальность и временную локальность . Алгоритм, который не помещается полностью в кэш-память, но демонстрирует локальность ссылки, может работать достаточно хорошо.

Критика текущего состояния программирования [ править ]

• Дэвид мая FRS в британский ученый и в настоящее время профессор в области компьютерных наук в Университете Бристоля и основатель и технический директор по XMOS Semiconductor , считает один из проблем состоит в том, что существует зависимость от закона Мура решить неэффективностью. Он выдвинул «альтернативу» закону Мура (закон Мэя ), которая гласит: ^[9]

Эффективность программного обеспечения снижается вдвое каждые 18 месяцев, что компенсирует закон Мура.

Мэй продолжает:

В повсеместных системах уменьшение вдвое выполняемых инструкций может удвоить срок службы батареи, а большие наборы данных открывают большие возможности для улучшения программного обеспечения и алгоритмов: сокращение количества операций с N x N до N x log (N) имеет драматический эффект, когда N велико. ... для N = 30 миллиардов это изменение равно пятидесятилетнему совершенствованию технологий.

• Автор программного обеспечения Адам Н. Розенбург в своем блоге « Провал цифрового компьютера » описал текущее состояние программирования как близкое к «горизонту программных событий» (имея в виду вымышленный « горизонт событий обуви », описанный Дугласом Адамсом в его Автостопом по книге Галактики ^[10] ). По его оценкам, с 1980-х годов произошло снижение производительности на 70 дБ или «99,99999 процентов его способности доставлять товары»: «Когда Артур Кларк сравнил реальность вычислений в 2001 году с компьютером HAL 9000 в своей работе. книга 2001: Космическая одиссея, он указал, насколько удивительно маленькие и мощные компьютеры, но каким разочаровывающим стало компьютерное программирование ».

Конкурсы на лучшие алгоритмы [ править ]

Следующие конкурсы приглашают участников на лучшие алгоритмы, основанные на некоторых произвольных критериях, установленных судьями:

• Журнал Wired ^[11]

См. Также [ править ]

• Анализ алгоритмов - как определить ресурсы, необходимые алгоритму
• Арифметическое кодирование - форма энтропийного кодирования переменной длины для эффективного сжатия данных.
• Ассоциативный массив - структура данных, которую можно сделать более эффективной с помощью деревьев Патрисии или массивов Джуди.
• Контрольный показатель - метод измерения сравнительного времени выполнения в определенных случаях.
• Наилучший, наихудший и средний случай - соображения по оценке времени выполнения в трех сценариях
• Алгоритм двоичного поиска - простой и эффективный метод поиска в отсортированных массивах.
• Таблица переходов - метод уменьшения длины пути инструкций, размера машинного кода (и часто также памяти)
• Сравнение парадигм программирования - особенности производительности парадигм
• Оптимизация компилятора - оптимизация на основе компилятора
• Вычислительная сложность математических операций
• Теория вычислительной сложности
• Производительность компьютера - показатели аппаратного обеспечения компьютера
• Сжатие данных - уменьшение пропускной способности передачи и дискового хранилища
• Индекс базы данных - структура данных, которая повышает скорость операций извлечения данных в таблице базы данных.
• Энтропийное кодирование - эффективное кодирование данных с использованием частоты появления строк в качестве критерия для замены.
• Сборка мусора - автоматическое освобождение памяти после использования
• Экологичные вычисления - шаг к внедрению «зеленых» технологий с меньшим потреблением ресурсов
• Алгоритм Хаффмана - алгоритм эффективного кодирования данных.
• Повышение производительности управляемого кода - библиотека Microsoft MSDN
• Локальность ссылки - во избежание задержек кэширования, вызванных нелокальным доступом к памяти.
• Оптимизация цикла
• Управление памятью
• Оптимизация (информатика)
• Анализ производительности - методы измерения фактической производительности алгоритма во время выполнения.
• Вычисления в реальном времени - другие примеры критичных ко времени приложений
• Анализ времени выполнения - оценка ожидаемого времени выполнения и масштабируемости алгоритма
• Одновременная многопоточность
• Алгоритм сортировки § Сравнение алгоритмов
• Спекулятивное исполнение или нетерпеливое исполнение
• Прогноз ветвления
• Суперпоточность
  • Hyper Threading
• Потоковый код - похож на таблицу виртуальных методов или таблицу ветвлений.
• Таблица виртуальных методов - таблица ветвей с динамически назначаемыми указателями для диспетчеризации.

Ссылки [ править ]

Внешние ссылки [ править ]

В Викиучебнике есть книга на тему: Оптимизация кода для повышения скорости.

• Анимация алгоритма Бойера-Мура ( Java-апплет )
• «Как алгоритмы формируют наш мир». TED (конференции) Обсуждение Кевин Славин.
• Заблуждения об алгоритмической эффективности в средней школе