Очередная попытка выбора "алгоритма алгоритмов". Теперь обоснованная

11 июнь, 2014 - 18:14Андрей Зубинский

Множество раз мне попадались каждый раз новые статьи примерно такого названия – «10 самых-самых алгоритмов». И все они оказывались чем-то вроде «10 алгоритмов, которые нравятся лично автору статьи». Чтобы не повторять такой ошибки, решил не замахиваться на целых десять алгоритмов, и ограничиться всего одним. Благо, есть набор чётких критериев, позволяющий утверждать, что речь идёт действительно о «самом-самом» - распространённость плюс востребованность плюс принципиальная необходимость, с очевидным ростом всего этого и с пока не наблюдаемой возможной заменой.

К сожалению, у меня нет сравнительно «свежих» точных данных (уж больно они дорогие), но если считать, что краткосрочные оценки рынка, сделанные в начале 2013 года, не сильно ошибочны, можно утверждать – только в одном сегменте рынка «алгоритм всех времён и народов» был в прошлом году растиражирован примерно 17ю миллиардами копий. А до этого, в 2011 году, например, 11ю миллиардами, в 2012-м – 15ю миллиардами. То есть, за три года суммарное число «инсталляций» реализаций алгоритма составило порядка 43х миллиардов. И это ещё не всё, есть ещё один сегмент рынка, в котором доступны, к сожалению, только финансовые оценки, зато его ёмкость весьма стабильна (порядка $3 миллиарда в год), и примерно половина его – это тоже «алгоритм всех алгоритмов». Причём специфика этих «тиражей» и сегментов рынка такова, что «самый-самый алгоритм» категорически необходим, без него просто бесполезны содержащие (и реализующие) его устройства.

Ещё есть непригодные для оценок «сугубо программные» рынки, но они уже не особо интересны, потому как пока никто не может похвастаться подобными порядками «инсталляционной базы». Их пришлось упоминать отдельно, потому что в самом массовом использовании «алгоритм алгоритмов» реализован аппаратно (что само по себе – событие).

В общем, пора открыть карты – алгоритм всех времён и народов, классический дихотомический поиск «разделяй и властвуй», или, языком практиков – бинарный поиск. Он настолько «общеизвестный», что не получается даже отыскать его автора (или авторов), если такой вообще был (Д.Кнут в «Искусстве программирования» упоминает, что первый вариант алгоритма был опубликован в 1946 г., но первая безошибочно работающая реализация его – в 1962).

При этом он настолько хорош нюансами, что во времена, когда профессиональные программисты ещё вынуждены были «писать руками» свои реализации бинарного поиска, Джон Бентли (автор знаменитой книги «Programming Pearls» и преподаватель, подготовивший не одного гуру программирования), проверяя «боевых» программистов Bell Labs и IBM, сделал открытие – только 10% профессиональных программистов способны написать безошибочно с первого раза работающую процедуру бинарного поиска.

Без «лишних» деталей (которые обычно кроются во внимательном отношении к граничным условиям) и в сугубо «программистской» формулировке, алгоритм бинарного поиска даёт метод быстрого поиска нужного значения в предварительно упорядоченном массиве. «Быстро» здесь означает, что результат может быть найден существенно быстрее, чем при очевидном «линейном поиске» последовательным просмотром-сравнением всех элементов массива (если количество элементов N, то в N/log2N раз). «Программистская» формулировка же – понятие куда более интересное, чем показатели «быстродействия». В общем случае для бинарного поиска никакого массива не требуется, его можно заменить любой монотонной функцией, и алгоритм будет всё равно «работать», и всё равно в среднем быстро. Благодаря именно этому свойству, бинарный поиск и стал «алгоритмом алгоритмов».

Предположим, мы хотим измерить в какой-то момент времени некоторое значение сравнением с сеткой эталонных значений. Нам известен диапазон возможных изменений измеряемого. Раз он известен, то мы можем говорить, что вне зависимости от изменения измеряемого во времени, в каждый конкретный момент измеряемая величина фактически описывается монотонной функцией – она может быть точкой на линейной шкале в заданных известных пределах измерения. Эта отправная идея – собственно, и почти всё нужное, чтобы применить алгоритм бинарного поиска: мы «предъявляем» для сравнения точку в середине шкалы, сравниваем значение с измеряемым, выбираем в какой половине шкалы находится измеряемое значение, предъявляем для сравнения середину этой половины шкалы, и т.д., до совпадения. Механика в реализации несколько сложнее, чем последовательный линейный поиск, но скорость…

Собственно, мы только что построили примитивную модель одного из вариантов устройства, без которого невозможно взаимодействие машины с физическим миром – SAR ADC или, весьма коряво, «аналогово-цифрового преобразователя последовательного приближения». По сути, это устройство – аппаратное овеществление алгоритма бинарного поиска:

Очередная попытка выбора "алгоритма алгоритмов". Теперь обоснованная

 
Регистр последовательного приближения (некогда они выпускались в виде отдельных микросхем) реализует основную часть алгоритма бинарного поиска (что с помощью двоичной логики на удивление просто) – формирует коды «середин» в «половинах», цифро-аналоговый формирователь преобразует эти коды в аналоговые значения, К – устройство сравнения (в инженерных терминах – компаратор). Когда К выдаёт сигнал «совпадение найдено», код на выходе регистра последовательно приближения (и входе цифро-аналогового преобразователя) будет цифровым описанием измеренного значения. Собственно, это всё фундаментальное, что достаточно знать и понимать.

SAR ADC – де-факто обязательный узел любого микроконтроллера (по сути, один из ключевых узлов, наличие которых отличает микроконтроллер от универсального микропроцессора). А микроконтроллеров производится примерно столько, сколько было сказано в самом начале – около 43 миллиардов за 3 года.

Очередная попытка выбора "алгоритма алгоритмов". Теперь обоснованная

И ещё есть SAR DAC, выполненные в виде отдельных микросхем, и это тоже очень большой рынок (примерно половина всего 3-миллиардного годового рынка АЦП).

Что получается в итоге? Фактически копеечным и всегда «в нагрузку» к любому микроконтроллеру стал встроенный 10-битовый SAR ADC. То есть, преобразующий измеряемое напряжение в 10-битовый код. Сейчас ему на смену приходят де-факто стандартные 12 битов (при той же скорости работы механизмов бинарного поиска). Массово доступная скорость одного бинарного поиска обеспечивает до 100 тысяч измерений в секунду.

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

Очередная попытка выбора "алгоритма алгоритмов". Теперь обоснованная

( LTC2378-20 - пока вроде рекордсмен в мире SAR ADC, до миллиона 20-битовых бинарных поисков в секунду, к "эскстремалам" можно отнести и Maxim MAX11156 - 500 тысяч 18-битовых бинарных поисков в сек., это всё крайне "небытовые" микросхемы с ценой порядка $50 за штуку)

Впрочем, экстремальные SAR ADC конкурируют с аналогичными других архитектур, да и экстремальность всегда далеко не самая востребованная.

А вот в области «обыденных», то есть, реально нужных для решения реальных задач, параметров, дешёвые «измерительные машины бинарного поиска», по сути – реализации великого алгоритма, – вне конкуренции. И их будет ещё больше, даже не берусь представить сколько – достаточно упомянуть одну новость: правительство Китая «запускает» программу государственной поддержки развития IoT (Internet of Things) с объёмом финансирования… $600 миллиардов до 2020 года (и ещё одно далёкое отступление в новости - чем оборачивается китайская поддержка сугубо своих IT-производителей, позволяет оценить ещё один факт – буквально на днях очень китайское мобильное приложение Kingsoft Office было переименовано в WPS Office в честь преодоления 210-миллионого барьера числа пользователей во всём мире, по-моему, это впечатляющий результат для разработчика, пользующегося господдержкой и буквально пару лет назад никому за пределами Поднебесной не известного).

В общем, я не нашёл замены этому претенденту на звание «алгоритма алгоритмов». Про остальные девять (раз уж принято писать почему-то про 10 именно) ничего сказать пока не могу, но бинарный поиск – бесспорный №1. Что в бритвенном станке с моторчиком, что в зарядном устройстве для аккумуляторов, что в приводе стёкол автомобиля, в общем, почти везде – каждое любое измерение (которых обычно делается тьма в секунду) – это бинарный поиск.

Откланиваюсь