Алгоритм

Здравствуйте! С момента открытия миру, что под именем Николая Иронова в Студии Лебедева работала настоящая нейронная сеть, а также последовавших затем большого интервью с создателями Николая и открытия этого инструмента для всех желающих, прошло несколько месяцев. Другие публикации на эту тему мне не встречались, вероятно я стал одним из первых, кто поработал напрямую с Николаем, не будучи при этом как-либо связанным со студией. В этой статье я постарался описать свой опыт. Забегая вперёд, опыт свой оцениваю как весьма успешный. Думаю, Николай Иронов - это небольшая дверка в ту самую технологическую сингулярность, которая в будущем должна сделать искусственный интеллект эффективнее человека во всём или почти во всём.

Содержание:

1. Логика работы с нейросетью на момент написания статьи

2. Отмеченные особенности процесса

3. Логотипы, которые у меня получились

4. Пример набора данных в архиве

5. Отмеченные технические особенности

6. Общие впечатления. Резюме

Дисклеймер. Моё мнение может отличаться от мнения других пользователей, которые поработали с Николаем Ироновым. Аналогично, поскольку я не связан со Студией Лебедева, не могу гарантировать, что моя интерпретация происходящего совпадает с тем, как это работает на самом деле.

Логика работы

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

Этап 1 - диалог с Николаем, в котором пользователь инициирует запрос на новую порцию из 9 версий логотипов в проекте с возможностью добавить уточнения. Уточнений немного: можно выбрать некоторые образы из предложенного списка, которые автор ассоциирует со своим брендом, а также можно выбрать предпочтительные стили шрифтов, цветов и графики.

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

Этап 2 - настройка и корректировка выбранного логотипа перед этапом формирования графического набора.

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

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

Основные особенности

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

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

Таким образом, главная особенность, которую я для себя отметил - это непредсказуемость результата без активного участия пользователя.

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

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

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

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

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

Что у меня получилось

Всего на одном тарифе допускается создать до 5 проектов и скачать до 10 архивов. Изначально я затеял покупку доступа к системе для того, чтобы создать айдентику своего общественного проекта - фонда "Никто не один". В целом, учитывая ограничение на 999 версий логотипа в тарифе, я был готов к тому, что все попытки израсходую для поиска варианта, который мне подойдёт, но оказалось, что буквально с третьего сообщения от Николая с девятью очередными вариантами, там нашёлся вариант, который мне настолько понравился, что я даже не стал его никак редактировать и уже использую.

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

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

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

Пример архива

На примере одного из логотипов покажу также, что входит в набор айдентики, генерируемой системой для скачивания. В этом плане никаких отличий одного набора от другого, кроме собственно логотипа, не обнаружил. В набор входят:

1. Собственно логотип

2. Паттерн

3. Визитка

4. Бланк письма

5. Варианты графических шапок для социальных сетей

6. Набор цветов фирменного стиля

Отмечу, вся графика присутствует в наборе как в формате .png, так и в .svg, но до работы с векторными версиями у меня пока не доходили руки.

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

Технические особенности

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

Второе, что также стоит отметить - лично мне довелось столкнуться с несколькими накладками. Все они были успешно и достаточно быстро решены в общении с технической поддержкой, за что специалистам Студии огромное спасибо. Два раза у меня некорректно скачался архив, один раз меня запутал интерфейс личного кабинета и не совсем точно интерфейс настройки логотипа отображает варианты графики, которые будут добавлены в набор при скачивании. Последнее скорее фича, а не баг, но всё же стоит учитывать - в набор идут фоны, созданные Николаем при изначальной генерации, а не те, которые он показывает в качестве примера. Это должно легко правиться при работе с векторными файлами, но для тех, кто увидел в наборе интересное сочетание графики с фоном и хочет сразу после скачивания файл .PNG где-то применить, это может стать проблемой.

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

Кстати, на момент написания статьи на основной страничке Николая Иронова Студия добавила симпатичные видео о том, как можно в ручном режиме видоизменять графику и текст в варианте логотипа. Так вот, в примере логотипа Birb птичку не только масштабируют, но и вращают, однако у себя в интерфейсе я такой возможности не нашёл. Вероятно, эта опция доступна не для всех графических решений, но возможно, что у пользователей её пока в принципе нет. Я посмотрел на нескольких логотипах и нашёл только ползунки масштабирования элементов логотипа.

Резюме

Краткая версия: очень круто, причём как по результату, так и по впечатлению.

Чуть подробнее. По крайней мере на данный момент, при цене в 9900 рублей, которые я заплатил, это невероятно эффективное вложение средств. Никакие фрилансеры по соотношению впечатления * качество / цена не смогут встать рядом. Если вспомнить стоимость работы профессионалов, то та же Студия Лебедева Экспресс-дизайн предлагала за 100 000, причём результаты были как высоко оценённые заказчиками, так и не очень. Здесь же есть возможность напрямую влиять на результат, причём не только при составлении брифа.

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

P.S.: Оказалось, что называть машину именем, которое ей дали создатели, даже если это человеческое имя Николай, не составило для меня никакой моральной заминки. И в переписке с поддержкой, и при написании статьи это далось вполне естественно.

Как то в прошлом

Я написал статью о рекурсивном алгоритме Цекендорфа : пост

def le_fib(limit, fib)  theoretical = fib[fib.count - 1] + fib[fib.count - 2]  return fib.last if theoretical > limit  fib << theoretical  le_fib(limit, fib)enddef main(target,result)  temporary = le_fib(target, [1,1])  result << temporary  return result if target - temporary <= 0  main(target - temporary, result)endpp main(gets.to_i,[])

Хотя по правде говоря в комментах предложили более изящное решение :

n, F = 100, [1, 2]while F[-1] < n do  F << F[-2] + F[-1]endF.reverse.each do |f|  if f <= n    n -= f    print f    print '+' if n > 0  endend

На практике я буду применять именно второй алгоритм так как он мение перегружен лишними действиями.

Постановка задачи куда мы будем "впихивать этот алгоритм"

Есть некий набор продуктов, условно говоря :

[ Курица, томаты, лаваш, грибы ].

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

[ курица > томаты > грибы > лаваш ] .

Задача состоит в том что бы генерировать такой набор продуктов, который имел бы по крайней мере 1 "Low cost", и 1 "High cost" продукт.

Вот тут то я хочу приспособить этот алгоритм (Цекендорфа).

Главная идея в том что бы создать хэш (структура данных в Ruby) где ключ это число Фиббоначи, а значение собственно имя продукта.

Задача есть, теперь перейдем к решению.

Для начала анализируем сам алгоритм

Запустим его в цикле от x до y и посчитаем количество вхождений каждого числа.

1. [1,100][1,1000]

2. Как видим на малых Y вероятность того что число будет использовано в последовательности - равномерно распределенно так как верхняя граница чисел Фибоначчи постоянно растёт пропорционально к текущему числу в итерации.
   
   Что мы с этого получили - чем больше входное число, тем выше вероятность получения одного и того же граничнего числа последовательности Фибоначчи.
   
   Значит нам нужен отрезок с более равномерным распределением. Уменьшаем Y

   [1,143]

3. Видим пик на крайних числах 1 и 89. Что собственно отвечает постановки задачи, но при этом мы не теряем случайное равномерное выпадение "Middle cost" продуктов.
   
   Предлагаю остановится на 3 варианте где x = 1 и y = 143.

Реализация

Программы куда будем прописывать алгоритм Цекендорфа, выглядит так :

• Модуль-перечень продуктов (для возможной тематичности)

• Collector, который загружает перечень продуктов и составляет Hash (где ключ -> число Фибоначчи, значение -> название продукта)

Такую струтуру я использую для возможной тематичности продуктов, достаточно просто создать новый перечень продуктов и передать в autoloader название новой тематики, что бы времено ввести новые продукты в оборот.

К слову говоря, всё это я делаю для Telegram бота , который создан по гайду описаном в другом посте.

Итак, написав небольшой парсер, на выходе получаем такой результат

@fib = [1,2,3,5,8,13,21,34,55,89]    def collect_the_items      food_hash = Hash.new      (0..9).each do |iterator|        food_hash[@fib[iterator]] = FOOD.first[iterator]      end      puts food_hash.map{|key,value| "#{key} - #{value}"}    end

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

def get_sequence(limit)    result = []  n, fib = limit, [1, 2]    while fib[-1] < n do    fib << fib[-2] + fib[-1]  end  fib.reverse.each do |f|    if f <= n      n -= f      result << f    end  end  resultend

Я собираюсь использовать готовую последовательность и пройдя по ней - просто вывести все продукты по ключам.

def generate_food          food_array = Collector.collect_the_items          food = []          rarity = rand(1..143)          get_sequence(rarity).each do |key|            food << food_array[key]          end          foodend

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

примечание :
Low cost : ?
Mid cost : ?
High cost : ?

Результат

Применения алгоритма представления Цекендорфа меня полностью удовлетворяет. Тоесть - выполняет поставленную перед ним задачу.

Один из первых комментов под статьей на которой основано это практическое приминение, как раз таки и ставил перед мной вопрос : "а действительно, где это применить можно?". Как видим, вот для таких задач данный алгоритм вполне можно использовать.

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

Когда мои ученики, уже выучив основы синтаксиса языка Python, понимают, что проблема вовсе не в незнании синтаксиса, моё лицо расплывается в самодовольной, но всё же доброй улыбке. Мысль "ну я же говорил" больше не возникает. Повзрослел, видимо, дяденька.

Немного лирики

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

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

Задание

Сделаем перерыв в этой лирике и сразу перекинемся на разбор цикла. Положим, имеется список строчных объектов, по смыслу - имена селебрити:

А получить на выходе нужно список из тех же людей, но уже в формате инициалов:

Рассмотри эту задачу с точки зрения самого простого и, в то же время, самого популярного формата "ввод данных обработка данных вывод данных". Как вы уже догадались, присвоение переменной celebrities - это ввод данных.

Этапы

В размышлениях над задачами, где, скорее всего, понадобится цикл for, я выделяю 5 этапов (если не учитывать нулевой). Вот они:

• [этап 0] Понять, что задачу стоит решать именно циклом, и именно циклом for.

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

  В нашем случае на входе - список, что является последовательностью (наряду со строками, словарями, множествами, кортежами, numpy.array'ями, и т. д.), а на выходе - опять же список. Причём, длины их совпадают. Кажется, каждый элемент входного списка напрямую связан с соответственным элементом выходного - так и есть!

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

  Даже вид входных данных вызывает чувство, что нас ждёт рутина, а так как мозг ищёт легких путей, то и тут он наверняка придёт к мысли, что рутину можно упростить циклом.

• этап [1] Определиться, какой конкретно результат должен быть по исходу каждой итерации, и выполнить первые несколько итераций вручную, вообще без цикла.

  В нашем случае, мы делаем всё, чтобы имя одного селебрити превратилось в инициалы и улетело в список, предназаченный для выходных данных. Критерий успешности итерации - в выходном списке последним элементом лежит строка вида "{первая буква имени}.{первая буква фамилии}.".

  Приступим. "Tom Cruise" превращаем в "T.C." любым путём (ведь пока для нас на первом месте - критерий успешности итерации).

Результат получили? Получили! Если вы не совсем новичок, то уже чуете, что так всё конечно же, не останется.

Это была первая итерация грядущего цикла. Проделаем теперь ещё и вторую:

Всё круто. Первый этап пройден.

• этап [2] Привести итерации к однородному виду.

  Один и тот же результат всегда может быть получен разными путями. Сам результат обычно не несёт с собой информации о том, откуда он взялся. Самый простой пример будет понятен даже людям, далёким от мира программирования: положим, результат - число 11. С точки зрения математики, его могла породить сумма 5 + 6, разность 14 - 3, корень из 121 и куча других действий. Ведь так? И это была лишь арифметика. А если зайти на высшую математику? А если на территорию Python? Ведь команды в Python - это далеко не только вычисления!

  Ключевая команда из нашего алгоритма - это конвертация имени в инициалы:

Она состоит из константной (неизменной) части, и постоянно меняющейся. Чтобы иметь возможность такую "ручную" итерацию превратить в реальную итерацию цикла, все меняющиеся части нужно заменить на неизменные, чаще всего - просто на какие-либо команды. Индексы 4 и -5 - это то, что нам здесь не нравится.

Ну и вариант максимально независимый от конкретных имён из списка:

Теперь намного лучше! Результат - тот же, но теперь каждая итерация более похожа на другую. Мы привели их к однородному виду.

• этап [3] Выделить группу объектов, которые неизбежно меняются при переходе от одной итерации к другой.

  В нашем случае это вовсе не группа, а всего лишь одно целое число, которое играет роль индекса после переменной celebrity. Поэтому для полноценной иллюстрации этого этапа лучше обратиться к другому примеру:

Здесь требовалось получить список, состоящий из копий одного и того же слова чётной длины, в котором по очереди будут подняты в регистре пары букв. Кстати, попробуйте эту задачу прогнать между делом по всем 5 этапам нашего алгоритма размышлений.

Как видим, здесь в ключевой команде - набор уже из 4 объектов. Для первой итерации - 0,0,2,2, для второй - 2,2,4,4, и т. д. В рамках каждой группы необходимо уследить внутреннюю связь между объектами. Здесь она довольно проста: мы имеем два одинаковых числа, и ещё два одинаковых, которые всегда больше первых ровно на 2. Приглядитесь, и увидите эту связь. Зачем нам это нужно? Напомню, у нас цель - написать цикл. Пока что итерации отличаются друг от друга, хоть и несильно. Тем не менее, наша задача - превратить их в универсальный кусок кода, который можно будет разместить в теле грядущего цикла. Внутренняя связь между объектами в группе позволит избежать, например, использования множественных переменных. Каждая группа теперь - n, n, n+2, n+2. Самую первую замену из этих четырёх назовём главной переменной. Если бы бы не заморачивались об этой связи, то набор был бы более напряжным - a, b, c, d. Поверьте, вы сами себе скажете "спасибо", когда уменьшите количество переменных в коде и увеличите число логических взаимосвязей между его частями.

• этап [4] Уловить закономерность изменения главной переменной при переходе от предыдущей итерации к следующей.

  Для этого часто нужно понять смысл того объектам в алгоритме, который представлен этой главной переменной. В алгоритме со строкой "resident" имеем ряд 0,2,4,6. По смыслу - это индекс первой буквы, "поднятой по регистру". По внешнему виду - арифметическая прогрессия (сразу мысль о функции range()) с шагом 2, которая всегда начинается с 0 и кончается числом, на 2 меньшим, чем длина слова (длина слова "resident" равна 8).

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

Придётся перебрать все индексы списка. Какой командой это сделать - думаю, подсказки не нужно.

• этап [5] Завершение. Просто приписываем заголовок цикла по всем канонам к уже понятной универсальной итерации.

Заключение

Программирование очень похоже на работу классического крутого детектива из голливудских сериалов. Постоянно нужно улавливать связь между вещями, которые на первый взгляд абсолютно разрознены. Жду критики моих философствований от гуру программирования внизу в комментариях. Ну а если вы просто человек, который пока далёк от программирования, но жаждет научиться, общаясь по-человечески, а не заумными научными терминами, то дайте о себе знать.

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

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

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

Бесконечность не предел

Но перед этим немного вспомним математику. Из школьного курса математики мы знаем, что чисел существует бесконечно много какое бы большое число мы не взяли, всегда можно прибавить единицу и получить число еще большее. Обычно в школе этим и ограничиваются. В университете на курсе высшей математики нам расскажут, что бесконечности на самом деле бывают разные: множества, элементы которого можно пронумеровать натуральными числами считаются счётно-бесконечными. К таким множествам относят сами натуральные числа (числу 1 мы дадим номер один, числу 2 номер два и т.д.), целые числа - натуральные плюс ноль и отрицательные целые числа (первый номер отдаем нулю, второй - числу 1, третий - числу -1, то есть каждой положительное число k получает номер 2k, а каждое отрицательное число -m получает номер 2m + 1). К счетно-бесконечным множествам относят четные, нечетные и даже рациональные числа (числа представимые в виде несократимой дроби m/n, где m - целое, n - натуральное). Получается, что натуральных чисел ровно столько же, сколько четных, и, в то же время, ровно столько же, сколько целых. Количество (мощность) множества натуральных чисел обозначается символом ₀ (алеф-ноль).

Такой же трюк с нумерацией не пройдет для бесконечных непериодических дробей (иррациональных чисел). Допустим такое множество счетное, то есть элементы этого множества можно пронумеровать натуральными числами. Тогда рассмотрим бесконечную десятичную дробь с нулевой целой частью, у которой первая цифра после запятой не равняется цифре на той же позиции у дроби с номером 1, вторая цифра не равняется цифре на второй позиции у дроби с номером 2 и т.д. Тогда полученная дробь будет заведомо отличаться от всех дробей хотя бы одной цифрой. Получается для нее не нашлось номера в нашей бесконечной нумерации! Примененная схема доказательства называется канторовским диагональным методом в честь придумавшего ее математика Георга Кантора.

Говорят, что множество бесконечных десятичных дробей имеет мощность континуум, которая обозначается символом ₁ (алеф-один). В дальнейшем нам понадобится следующее множество. Рассмотрим некоторый алфавит (конечное множество символов). Теперь представим множество всех конечных цепочек символов алфавита A*. Коль скоро алфавит конечен, и каждая цепочка конечна, то множество таких цепочек счетно (их можно пронумеровать натуральными числами).

Конструктивно оперировать континуальными бесконечностями невозможно. Даже работая со счетными множествами, мы не рассматриваем сами множества, а только говорим, что какой бы не был элемент N, всегда найдется элемент N+1. Если мы ставим себе прикладную задачу, появление в наших рассуждениях континуальной бесконечности должно служить нам тревожной лампочкой: осторожно, выход за пределы конструктивного.

Алгоритмы и вычислимость

Суть работы компьютера заключается в проведении некоторого вычисления преобразования одной порции информации в другую порцию. Причем результатом работы не обязательно должно быть число, главное, чтобы информация была представлена в некоторой объективной форме. Обычно под такой формой имеют в виду конечные цепочки символов некоторого алфавита. Получается, компьютерное вычисление есть некоторая функция в сугубо математическом смысле, с областью определения и значений в рассмотренном выше множестве A*. Именно тут возникают определенные проблемы. Если мы можем вычислить функцию, то можем записать промежуточные вычисления в виде текста. Более того, в виде тексте можно описать вообще правила вычисления. Мы знаем, что множество всех текстов счетное. Однако выясняется, что множество всех функций над натуральными числами имеет мощность континуум. Если мы пронумеруем все тексты, то получается функций вида A* -> A* тоже континуум. Получается, что некоторые функции вычислимы, а некоторые нет.

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

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

Частично-рекурсивные функции и тезис Черча

Все началось с того, что математик Давид Гильберт в 1900 году предложил список нерешенных на тот момент математических проблем. Позже выяснилось, что десятая проблема (проблема решения произвольного диофантового уравнения) оказалось неразрешимой, но для доказательства этого факта пришлось составить целую новую математическую теорию. Вопросами того, какие задачи можно конструктивно решить, и что такое конструктивное решение, занялись математики Курт Гедель, Стивен Клини, Алонсо Черч и Алан Тьюринг.

Как выяснилось выше, континуальные бесконечности не всегда подходят под конструктивные рассуждения, поэтому Гедель и Клини предложили рассматривать только функции натурального аргумента (при необходимости любые функции над счетными множествами можно привести к натуральным функция путем замены элементов множеств их номерами). Изучая вычислимость таких функций, Гедель, Клини, Аккерман и другие математики пришли к так называемому классу частично-рекурсивных функций. В качестве определения этого класса рассматривается набор базовых, очень простых функций (константа, увеличение на единицу и проекция, которая сопоставляет функции многих аргументов один из ее аргументов) и операторов, позволяющих из функций строить новые функции (операторы композиции, примитивной рекурсии и минимизации). Слово частичные показывает, что эти функции определены лишь на некоторых числах. На остальных они не могут быть вычислены. Попытки расширить класс частично-рекурсивных функций ни к чему не привели, так как введение новых операций приводило к тому, что получалось множество функций, совпадающее с классом частично-рекурсивных. В дальнейшем Алонсо Черч отказался от попыток расширения этого класса, заявив, что, видимо:

Частично-рекурсивные функции соответствуют вычислимым функциям в любом разумном понимании вычислимости.

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

Тезис Тьюринга

Формальная теория алгоритмов во многом построена аналогично теории вычислимости. Считается, что алгоритм есть некое конструктивное преобразование входного слова (цепочки символов некоторого алфавита) в некоторое выходное слово. Опять же, здесь мы имеем с функциями вида A*->A*. Конечно, предложенное описание не подходит под определение алгоритма, так как неясно, что же такое конструктивное преобразование. Хоть понятия алгоритма и вычислимой функции близки, не стоит их смешивать. Для одного и того же алгоритма может быть предъявлено сколько угодно его записей на каком-нибудь формальном языке, но соответствующая вычислимая функция всегда одна. Один из основателей формальной теории алгоритмов, Алан Тьюринг, предложил формальную модель автомата, известного как машина Тьюринга. Тезис Тьюринга гласит:

Каково бы не было разумное понимание алгоритма, любой алгоритм, соответствующий такому пониманию, может быть реализован на машине Тьюринга.

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

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

Свойства алгоритмов

Мы выяснили, почему у алгоритма не может быть конкретного определения. Однако можно определить свойства, которыми должен обладать каждый алгоритм. К сожалению, в литературе часто смешивают обязательные и необязательный свойств. Разберемся подробнее.

Обязательные свойства

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

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

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

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

Необязательные свойства

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

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

Теперь перейдем к пресловутой последовательности шагов. Дело в том, что алгоритм может быть представлен в любой из имеющихся формальных систем (частично-рекурсивные функции, машина Тьюринга, лямбда-исчисление и т.д.). Воплощение алгоритма в виде компьютерной программы далеко не всегда будет описанием последовательности шагов. Здесь все зависит от парадигмы программирования. В императивной парадигме программисты действительно оперируют последовательностью действий. Однако существуют и другие парадигмы, такие как функциональная (привет Haskell программистам), где нету никаких действий, а лишь функции в сугубо математическом смысле, или чистая объектно-ориентированная, которая основана не на последовательности действий, а на обмене сообщениями между абстрактными объектами.

Заключение

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

Материал данной статьи во многом опирается на 1-ый том Программирование: введение в профессию А. В. Столярова. Тем, кто хочет подробнее изучить вопросы, связанные с алгоритмами и теорией вычислимости, кроме этой книги, советую Босс В От Диофанта до Тьюринга и трехтомник А. Шеня по математической логике и теории алгоритмов.

Дата-центр ITSOFT размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.

Введение

Мы в Miro работаем над процессом шардирования баз Postgres и используем разные подходы в зависимости от бизнес-требований. Недавно перед нами встала задача шардирования новых баз, в ходе неё мы выбрали новый для нас подход к шардированию, основанный на согласованном хешировании (consistent hashing).

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

Oб архитектурном подходе

Есть много продуктов (mongo, redis, и т.д.), использующих согласованное хеширование для шардинга, и наша реализация будет сильно похожа на них.

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

Плюсами данного подхода являются:

• равномерное распределение сущностей по шардам;

• определение соответствия сущностей и шардов без дополнительного хранилища с минимум ресурсо-затрат;

• возможность добавления новых шардов в кластер.

Из минусов:

• неэффективность некоторых операций поиска, в которых необходимо делать запросы на все шарды;

• достаточно сложный процесс решардинга.

Требования

Центральным местом решения является выбор java-реализации хэш-функции.

Функция принимает на вход ключ - объект строки, размером до 256 символов, и выдает хэш-код - беззнаковое целое число, размером до 4 байт. На самом деле мы будем сравнивать реализации которые генерируют хэш-коды размером 2 и 4 байта.

Критерии сравнения

Рассмотрим четыре распространенных критерия сравнения реализаций хэш-функций:

1. Скорость, функция должна работать быстро, на любых входных данных;

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

3. Устойчивость к коллизиям (первого и второго рода);

4. Соответствие лавинному эффекту. Отражает зависимость всех выходных битов от каждого входного бита, на любых входных данных.

Для нашей задачи нам будут важны только первые два критерия: первый - поскольку операция расчета хэша будет очень частой; и второй - поскольку крайне важно, чтобы данные распределялись по шардам равномерно.

Отсутствие возможности атаки на характеристики функции делает для нас неважным третий критерий.

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

Реализации

Мы будем рассматривать самые популярные java-реализации не-криптографических хэш-функций:

1. DJB2 (32-бита);

2. SDBM (32-бита);

3. LoseLose (32-бита);

4. FNV-1 / FNV-1a (32-бита);

5. CRC16 (16-бит) ;

6. Murmur2/Murmur3 (32-бита).

Тестирование

Входные данные

В качестве входных данных мы будем использовать следующие наборы данных

1. Набор реальных данных, составленный из 216,553 английских слов;

2. Набор синтетических данных, составленный из рандомно сгенерированных символов в кодировке UTF-8.

В обоих тестовых наборах мы будем иметь группы строк с определенными длинами (кол-во символов) - "2", "4", "8", "16", "32", "64", "128", "256".

Метрики

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

1. Для первого критерия, скорости - ops/ms (кол-во операций в миллисекунду работы);

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

Инструменты

Оценка скорости работы

Для оценки скорости работы мы воспользуемся нагрузочными тестами и библиотекой JMH. Общая схема тестовой итерации выглядит следующим образом:

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

Для бэнчмарков мы будем использовать следующие настройки

• Кол-во warmup-итераций - 50;

• Кол-во measurement-итераций - 100;

• Режим - throughput

• Добавим ограничение по памяти -Xms1G, -Xmx8G

• Для оценки расхода памяти добавим GCProfiler

Полный код тестов можно посмотреть здесь.

Оценка распределения результатов

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

Алгоритм для проверки гипотезы следующий:

1. Разобьем выборку на частичные интервалы, число которых найдем по формуле Стерджеса, а их длину найдем по правилу равноинтервальной группировки;

2. Для каждого интервала подсчитаем его характеристики - среднее значение, частоты, относительные частоты;

3. Подсчитаем выборочное среднее , среднеквадратическое отклонение и теоретические частоты

   ,

   где n число элементов в выборке, а вероятность попадания случайной величины в частичные интервалы, в нашем случае она равна -

   ,

   где - одинаковая длина интервалов, a параметры a и b - , ;

4. Можем приступить к расчёту критерия согласия, по формуле

   ,

   где - эмпирические частоты, полученные из выборки, - теоретические частоты, найденные по формулам выше;

5. Определяем по таблице критических точек распределения , по заданному уровню значимости и числу степеней свободы k ;

6. Если , то принимаем гипотезу, если же данное условие не выполняется отвергаем.

Код для расчёта критерия согласия и вероятностных характеристик выборок здесь.

Общая схема тестовой итерации похожа на схему в предыдущем разделе и выглядит следующим образом:

Слова из каждого тестового набора мы сгруппируем по длине, при максимальном значении символов в 256. Затем создадим входные тестовые выборки разных размеров в диапазоне 16384, 8192, 4096, 2048, 1024, в выборки поместим слова из каждой группы, с одинаковой вероятностью.

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

Полный код тестов можно посмотреть здесь.

Результаты

Оценка скорости работы

Рассмотрим скорость работы (количество операций в миллисекунду) для различных имплементаций в зависимости от длины входных строк.

В диапазоне от двух до восьми символов:

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

В диапазоне от 16 до 256 символов:

Функция murmur2 явный фаворит, ей немного уступает murmur; crc16 и sdbm остались в аутсайдерах и на этой выборке.

Оценка распределения результатов

Рассмотрим таблицу результатов соответствия критерию Пирсона

Видно, что имплементации crc16, murmur2, murmur3 удовлетворяют критерию Пирсона о равномерном распределении практически на всех выборках.

Рассмотрим гистограммы относительных частот, в разрезе разных выборок.

На гистограммах ниже, для loseLose, Djb2, Sdbm, не прошедших тест, видно, что распределение далеко от равномерного и больше похоже на геометрическое:

Для проваливших тест Fnv1 и Fnv1a ситуация похожа, распределения отдалённо напоминают нормальное:

.

Смотрим на тройку победителей:

За исключением некоторых всплесков, crc16, murmur2, murmur3 удовлетворяют критерию Пирсона, что согласуется с характеристиками их гистограмм относительных частот.

Выводы

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

Скорость работы. Функции murmur2/murmur3 имеют лучшее время работы для входных строк длиной больше 8 символов.

Удовлетворение гипотезы о равномерном распределении. Можем выделить три функции, для которых гипотеза принимается для большинства наборов данных: crc16, murmur2/murmur3. Графики распределения гистограмм относительных частот подтверждают вид равномерного распределения для функций crc16, murmur2/murmur3.

Таким образом, исходя из двух критериев, лучшим выбором являются реализации murmur2/murmur3.

Приветики-омлетики

Спасибо добрым участникам Хабра, за то, что пригласили писать посты и получать на них фидбек.

Сегодня я бы хотел освятить тему представления чисел с помощью ряда Фибоначи и разумеется написать простенькое REST API c использованием Mongo DB алгоритм с помощью языка Ruby, который бы по заданому числу N возвращал его представление.

Часть 1 : представление Цекендорфа

Как гласит статья из Википедии :

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

100 = 89 + 8 + 3.

Я думаю, понимая что такое числа Фибоначи, не составит труда понять в чём заключенна данная теорема.

Цели которые должны быть достигнуты :

• скорость работы

• максимальная простота кода

Как язык програмирования я буду использовать Ruby, почему? Потому что Ruby - это

Лучший друг программиста.

Сначала теоретически нужно найти закономерность по которой и будет написан алгоритм.

Выписав все числа Фибоначи которые меньше заданого, на листочек (школа), я обнаружил, что выгодней всего для такой суммы брать самое последнее число, но при условии что оно меньше чем наше искомое число.

Пример:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.

Берём число 34, соседнее с ним число (21) можно сразу пропустить, ибо их сумма будет заведомо больше нашего входного числа N, ибо числа Фибоначи мы ищем пока они не превысят входное, ведь зачем нам числа больше входного :-).

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

И тогда появилась идея: а что если отнимать от N последнее число в ряду Фибоначи, и искать новый ряд где эта разница будет лимитом, и рекурсивно продолжать это действия пока разница не станет <= 0.

Пример:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
ans = [34]

N = 51 - 34 = 17
F = 1 , 1 , 2 , 3 , 5 , 8 , 13.
ans = [34 , 13]

N = 17 - 13 = 4
F = 1 , 1 , 2 , 3.
ans = [34 , 13 , 3]

N = 4 - 3 = 1
F = 1
ans = [34 , 13 , 3, 1]

Сразу попробую записать в код :

def le_fib(limit, fib)  theoretical = fib[fib.count - 1] + fib[fib.count - 2]  return fib.last if theoretical > limit  fib << theoretical  le_fib(limit, fib)enddef main(target,result)  temporary = le_fib(target, [1,1])  result << temporary  return result if target - temporary <= 0  main(target - temporary, result)endpp main(gets.to_i,[])

Функция le_fib - рекурсивно ищет ряд Фибоначи с пределом, на то, что бы следующее число не было больше чем входное число target. Здесь важно, что нас не интересует ряд Фибоначи целиком, нам важно лишь его окончание.

Функция main - рекурсивно ищет масcив, числа которого есть числами Фибоначе, и которые бы в сумме давали нам входное число.

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

Пример работы для 20 случайных чисел до 1000

Оценка времени работы в зависимости от величины ряда (входного числа)

Как видим время работы даже на числах до 10^9 очень позитивное.

А общий обьем кода в 17 строк говорит о том что обе задачи выполнены успешно.

Статья про интерес, всегда в рукаве нужно иметь пару задач с числами Фибоначе, иначе какой из тебя программист :-)

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

Одно время мы выпускали несложный контроллер облачной СКУД на 100 пользователей. В его основе лежал микроконтроллер PIC18F46K22. В качестве памяти для хранения кодов ключей пользователей использовалась FLASH-память с интерфейсом I^₂C ёмкостью 64 кБ. Сама флешка довольно быстрая, но на шине I²C находилась ещё микросхема часов DS1307, которая работает на скорости не выше 100 кбит/сек. Высокой скорости работы нам не требовалось, поэтому в итоге вся шина была запущена на частоте 100 кГц.

Однако со временем мы начали разрабатывать новую версию контроллера, поддерживающего уже 3000 пользователей. Не хотелось сильно менять архитектуру, поэтому основные узлы были сохранены, но при этом был увеличен объём FLASH-памяти до 256 кБ.

И вот тут возник один интересный момент. В первой версии поиск ключа в памяти осуществлялся простым перебором всех 100 ключей. Этот процесс занимал долю секунды и поэтому каких-либо оптимизаций кода не производилось. Но при количестве в 3000 записей это время увеличилось в 30 раз, что оказалось недопустимым, так как у пользователя появлялась неприятная задержка между считыванием карты и открытием замка.

Решить данную проблему можно двумя способами. Первый аппаратный вариант, предполагающий использование более быстрого интерфейса с флешкой, например, SPI. Скорости чтения здесь на два порядка выше, чем при использовании I²C. Это, так сказать, решение в лоб. Неудобство лишь состоит в том, что приходится закладывать в устройство новый компонент, переделывать код и печатную плату. Плюс потребуются дополнительные линии микроконтроллера для подключения такой микросхемы памяти.

Но есть и другой способ программный. Заключается он в переделке самой процедуры поиска. Изначально она выглядела так:

typedef struct{    uint32_t COD;    uint8_t nSchedule;} TSKUD_User;bool skudFindUserByCode(uint32_t pCOD){  TSKUD_User user;  for (uint8_t i = 0; i < SKUD_USERS_COUNT; i++)  {    skudReadUser(i, &user);    if (user.COD == pCOD)      return 1;  }  return 0;}

Функция skudReadUser считывала блок данных из I²C памяти, далее осуществлялась проверка на совпадение кода.

При ста пользователях в худшей случае (когда код находился в самом конце массива данных) время поиска занимало порядка 0,1 сек. При переходе же к 3000 пользователей время выросло 3 сек!

Поэтому для ускорения функция была переписана следующим образом:

bool skudFindUserByCode(uint32_t pCOD){  TSKUD_User user;  int16_t m, beg, end;  beg = 0;  end = SKUD_USERS_COUNT - 1;  while (beg <= end)  {    m = (beg + end) / 2;    skudReadUser(m, &user);    if (pCOD == user.COD)      return true;    if ((pCOD < user.COD) || (user.COD == 0))      end = m - 1;    else      beg = m + 1;  }  return false;}

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

О различных частных случаях при реализации бинарного поиска можно почитать в статье:Я не могу написать бинарный поиск (http://personeltest.ru/aways/habr.com/ru/post/146228).

Итак, рассмотрим работу алгоритма. Переменные beg и end задают начальный и конечный индекс массива данных. На каждой итерации мы вычисляем индекс m, который находится посередине между beg и end, и сравниваем требуемое значения ключа с тем, что находится по этому индексу. В этом случае возможны три варианта:

1. Если значения совпадают, то мы нашли нужный ключ и можно открывать замок.

2. Если номер искомой карты меньше, то следует его искать в левой части массива. Тут мы отбрасываем сразу половину заведомо не подходящих вариантов. Индекс end теперь будет равен m 1.

3. Если номер искомой карты меньше, то следует его искать в правой части массива. Так же отбрасываем сразу половину заведомо не подходящих вариантов, но меняем индекс beg (он будет равен m + 1).

Если в массиве данных вообще нет искомого значения ключа, то нам нужно выйти из цикла. Условием выхода является beg > end.

Очень важным является дополнительное условие user.COD == 0 в строке:

    if ((pCOD < user.COD) || (user.COD == 0))

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

Можно было бы записывать туда значения 0xFFFFFFFF, но его мы используем в качестве сервисного для служебных нужд системы. Поэтому дополнительное условие user.COD== 0 всегда заставляет алгоритм искать код в левой половине массива данных.

Кто-то может справедливо заметить, что нет смысла тогда вообще обрабатывать эти нулевые значения. Но дело в том, что мы не передаём в контроллер реальное количество карт доступа. Изначально для 100 карт это не имело смысла (поиск и так работал очень быстро), а потом мы просто не стали менять структуру данных. Но, по большому счёту, это и не нужно, так как бинарный поиск очень сильно ускоряет работу.

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

А вот при бинарном поиске количество сравнений будет составлять log₂3000 11 шт!

Интересно, что если записей будет аж 4 миллиарда, то количество сравнений при использовании бинарного поиска увеличится всего лишь до 32!

Попробуем пошагово проверить алгоритм бинарного поиска на вышеприведённой табличке. Допустим, нам требуется найти значение ключа 2174082.

В итоге мы за 11 итераций нашли искомое значение. Важно понимать, что 11 итераций это максимальное время поиска. В вышеприведённом примере в случае, если бы мы искали значение 2290467, то количество итераций было бы равно 9.

Так в чём преимущество такого решения? В начале статьи я указывал, что алгоритм реализовывался на микроконтроллере. Использование крайне дешёвой памяти с интерфейсом I^₂C снижает общую себестоимость изделия, а новый алгоритм поиска сильно уменьшает время реакции контроллера.

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

Вот работа линейного поиска:

А вот бинарного:

Результат, как говориться, на лицо!

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

Естественным перед началом анализа будет указание ограничений на ширину и глубину исследований. Принимаем, что многозадачность в рассматриваемых параллельных системах осуществляется простейшим путём - перегрузкой всего блока (связки) выполняющихся операторов (одновременное выполнение операторов разных программ не предполагается) или же система работает в однозадачном режиме; в противном случае высказанное в предыдущей фразе утверждение может быть неверным. Минимизация объёма устройств временного хранения данных (описано здесь http://personeltest.ru/aways/habr.com/ru/post/534722/) проводиться не будет. На этом этапе исследований также не учитываются задержки времени на обработку операторов и пересылку данных между ними (для системы SPF@home формально эти параметры могут быть заданы в файлах с расширениями med и mvr).

В предыдущей публикации http://personeltest.ru/aways/habr.com/ru/post/540122/ была описана технология получения ПВПП на основе модели потокового (Data-Flow) вычислителя. Обычно считают, что правила выбора операторов для выполнения в такой машине подчиняются логике действия некоторых сущностей, совместно выполняющих определённые действия актёров (actors); при этом естественным образом моделируются связанные с характеристиками времени параметры обработки операторов. В общем случае при этом отдельные операторы выполняются асинхронно. В публикации показано, что описанный принцип получения ПВПП приемлем (при выполнении несложных условий) и для машин архитектуры VLIW (Very Long Instruction Word, сверхдлинное машинное слово), отличающихся требованием одновременности начала выполнения всех операторов в связке. В расчётах использовали модель ILP (Instruction-LevelParallelism, параллелизм уровня машинных команд).

В рассматриваемый программный комплекс http://personeltest.ru/aways/habr.com/ru/post/530078/ включен модуль SPF@home, позволяющей работать с гранулами параллелизма любого размера (оператор любой сложности). Основным инструментом этого модуля является метод получения ярусно-параллельной формы (ЯПФ) графа алгоритма (здесь используется информационный граф, в котором вершинами являются узлы преобразования информации, а дугами её передачи).

Реформирование ЯПФ может дать результат, идентичный полученному моделированием выполнения программы на Data-Flow -машине, но в некоторых случаях результаты расходятся. В самом деле, это во многом различные подходы. Не столь сложно представить себе рой самостоятельных, взаимодействующих программ-актёров, выполняющих действия по поиску готовых к выполнению операторов, свободных в данный момент отдельных вычислителей и назначающих обработку выбранных операторов конкретному вычислителю etc etc, но действия эти логично производятся в RunTime и именно на границе (линии фронта) между уже выполненными и ещё не выполненными операторами (метафора поиска в ширину, а не в глубину в теории графов). При этом естественным образом создаётся очень подробный план выполнения параллельной программы с точными временными метками начала и конца выполнения операторов с привязкой их к конкретным вычислителям. Такой план хорош (с точностью до математической модели, которая в конечном счёте всегда в чём-то ограничена), однако автор сомневается в степени достаточной безумности практического использования полученного т.о. ПВПП

Метод обработки ЯПФ в целом более теоретичен и от многих особенностей абстрагирован, однако он может ещё до выполнения программы (DesignTime) показать ПВПП сверху (учитывая не только параллельный фронт выполнения операторов, но и всю карту боевых действий). Следствием большего абстрагирования ЯПФ-метода является субъективность интерпретации связи моментов обработки операторов с собственно ярусом ЯПФ. В самом деле, можно рассмотреть несколько укрупнённых подходов к таким интерпретациям; см. рис. ниже слева варианты a) и б) соответственно. На этом рисунке операторы показаны красными прямоугольниками, а яруса (в целях большей выразительности сказанного) - горизонтальными линиями:

• выполнение всех принадлежащих конкретному ярусу операторов начинается одновременно (тогда это фактически VLIW-идеологема и ПВПП изначально обладает ограниченностью, связанной с потерями времени на ожидание выполнения наиболее длительного оператора на ярусе; точное решение получается лишь при одинаковости времён выполнения всех операторов на ярусе);

• промежуток времени выполнения операторов может плавать относительно связанного с ярусом момента времени (возможна даже ограниченная асинхронность выполнения операторов).

При использовании ЯПФ в своих изысканиях Исследователь должен сам выбрать определённую модель и далее ей следовать. В рамках системы SPF@home, например, имеется возможность целевой реорганизации ЯПФ с конечной целью собрать на ярусах операторы с наиболее близкими длительностями обработки. Именно использование ЯПФ как нельзя лучше отвечает идеологеме EPIC (Explicitly Parallel Instruction Computing, явный параллелизм выполнения команд), позволяющей параллельной вычислительной системе выполнять инструкции согласно плану, заранее сформированному компилятором. Не следует игнорировать и субъективный фактор - бесспорным преимуществом ЯПФ является возможность простой и недвусмысленной визуализации собственно ПВПП.

Исходными данными для модуля SPF@home служат описания информационных графов алгоритма (программы) в стандартной DOT-форме (расширения файлов gv, могущие быть полученными импортом из модуля Data-Flow или иными путями). Допустимые (не нарушающие информационные связи в алгоритме) преобразования ЯПФ управляются программой на языке Lua, реализующей разработанные методы реструктуризации ЯПФ (дополнительная информация приведена в публикации http://personeltest.ru/aways/habr.com/ru/post/530078/). Эти методы неизбежно будут являться эвристическими вследствие невозможности прямого решения поставленных (относящихся к классу NP-полных) задач.

Т.о. вся ценность исследования сосредотачивается в разработке эвристических методов (эвристик) создания ПВПП при заданных целях и определённых ограничениях (напр., c учётом заданного поля параллельных вычислителей, максимума скорости выполнения, минимизации или ограничения размеров временного хранения данных и др.). Конечная цель работы встраивание этих алгоритмов в состав распараллеливающих компиляторов новых поколений.

В действительности эвристический подход предполагает метод итераций по постепенному приближению к наилучшему решению сформулированной задачи (ибо точное оной решение априори неизвестно). Поэтому тут же встаёт вопрос определения качества работы этих эвристик и их вычислительной сложности с многокритериальной оптимизацией по этим (определённым количественно, конечно же!) параметрам. Учитывая сложность обсуждаемых эвристических алгоритмов данную область знания можно обоснованно отнести к наиболее сложным случаям Науки о данных (Data Science).

В качестве пациентов использовались имеющиеся в наличии информационные графы алгоритмов, в основном класса линейной алгебры (как одни из наиболее часто встречающиеся в современных задачах обработки данных). По понятным причинам исследования проводились на данных небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера. Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач. При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow (http://personeltest.ru/aways/habr.com/ru/post/535926/) с последующим импортом в форме информационного графа в модуль SPF@home.

Как было сказано, основной целью исследования выбрано получение плана выполнения параллельной программы с максимальной плотностью кода. В данном случае плотность кода определяем через степень использования ресурсов вычислительной системы чем больше из имеющихся параллельных вычислителей занято процессом обработки данных на каждом этапе выполнения программы, тем плотность кода выше. Т.к. имеем дело с ярусно-параллельной формой графа алгоритма, логично в качестве количественной характеристики целевой функции использовать величину неравномерности распределения ширин ярусов ЯПФ (формально идеалом является равенство числа операторов по всем ярусам).

Ниже приведены результаты моделирования трёх наиболее часто встречающихся типов задач (в реальном случае обычно требуется выполнение нескольких из них одновременно):

1.Расписание выполнения программ на минимальном числе параллельных вычислителей при сохранении высоты ЯПФ

Фактически задача заключается в балансировке числа операторов по всем
ярусам ЯПФ (здесь балансировка стремление к достижению одинакового числа), причём идеалом является число операторов по уровням, равное средне-арифметическому (с округлением до целого вверх). Такая организация ЯПФ фактически позволяет увеличить плотность кода, недостатком которой часто страдают вычислители VLIW-архитектуры. Надо понимать, что данная постановка задачи имеет в большей степени методологическую ценность, ибо число физических параллельных вычислителей обычно много меньше ширины ЯПФ реальных задач.

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

Эмпирический метод 1-01_bulldozer имеет целью получение наиболее равномерного распределения операторов по ярусам ЯПФ без возрастания её высоты (сохранение времени выполнения программы); операторы переносятся только вниз (первоначально ЯПФ строится в верхнем варианте). Для этого метод старается перенести операторы с ярусов шириной выше среднего на яруса с наименьшей шириной. На каждом ярусе операторы перебираются в порядке очередности слева направо.

Метод 1-02_bulldozer является модификацией предыдущего с адаптацией. Для оператора с максимумом вариативности (назовём так диапазон возможного размещения операторов по ярусам ЯПФ без изменения информационных связей в графе алгоритма) в пределах яруса вычисляются верхний и нижний пределы его возможного расположения по ярусам.

В результирующей табл.1 рассматриваются: mnk_N программа аппроксимации методом наименьших квадратов N точек прямой, mnk_2_N то же, но квадратичной функцией, korr_N вычисление коэффициента парной корреляции по N точкам, slau_N решение системы линейных алгебраических уравнений порядка N прямым (не итерационным) методом Гаусса, m_matr_N - программа умножения квадратных матриц порядка N традиционным способом, m_matr_vec_N умножение квадратной матрицы на вектор, squa_equ_2 решение полного квадратного уравнения в вещественных числах, squa_equ_2.pred то же, но с возможностью получения вещественных и мнимых корней при использовании метода предикатов для реализации условного выполнения операторов, e17_o11_t6, e313_o206_t32, e2367_o1397_t137, e451_o271_t30, e916_o624_t89, e17039_o9853_t199 сгенерированные специальной программой по заданным параметрам информационного графа. Вычислительную трудность преобразования будем характеризовать числом перемещений операторов с яруса на ярус. Неравномерность распределения числа операторов по ярусам ЯПФ характеризуется коэффициентом неравномерности (отношение числа операторов на наиболее и наименее нагруженных ярусов соответственно).

Для удобства анализа в таблице цветом выделены ячейки, соответствующие случаю достижению снижения ширины без возрастания высоты ЯПФ, а жирным начертанием цифр величины для сравнения.

Как видно из табл.1, во многих случаях удается значительно (до 1,5-2 раз) снизить ширину ЯПФ, но почти никогда до минимальной величины (средне-арифметическое значение ширин ярусов). В целом эвристика 1-02_bulldozer несколько более эффективна, но проигрывает по вычислительной сложности. В большинстве случаев увеличение размера обрабатываемых данных повышает эффективность балансировки (очевидно, это связано с повышением числа степеней свободы ЯПФ).

Интересно, что для некоторых алгоритмов (напр., slau_N) ни один из предложенных методов не дал результата. Сложность балансировки ЯПФ связана с естественным стремлением разработчиков алгоритмов создавать максимально плотные записи последовательности действий.

2.Расписания выполнения программ на фиксированном числе параллельных вычислителей при возможности увеличения высоты ЯПФ

Практический интерес представляют методы с увеличением высоты ЯПФ (см. табл.2, в которой дано сравнение двух методов с метафорическими названиями Dichotomy и WidthByWidth); при этом приходится смириться с увеличение времени выполнения программы. В ходе вычислительных экспериментов задавалась конечная ширина преобразованной ЯПФ (отдельные столбцы в правой части табл.2). Количественные параметры преобразований выдавались в форме частного, где числитель и знаменатель показывают число перемещений (первая строка), высоту ЯПФ (вторая) и коэффициент ковариации CV (третья строка) для каждого исследованного графа. Характеризующий неравномерность распределения ширин ярусов коэффициент ковариации рассчитывался как CV=/W, где - среднеквадратичное отклонение числа операторов по всем ярусам ЯПФ, W - среднеарифметическое числа операторов по ярусам.

Эвристика Dichotomy предполагает для разгрузки излишне широких ярусов перенос половины операторов на вновь созданный ярус под текущим, эвристика WidthByWidth реализует постепенный перенос операторов на вновь создаваемые яруса ЯПФ. Из табл.2 видно, что метод WidthByWidth в большинстве случаев приводит к лучшим результатам, нежели Dichotomy (например, высота преобразованной ЯПФ существенно меньше что соответствует снижению времени выполнения параллельной программы притом за меньшее число перемещений операторов).

3.Расписание выполнения программ на фиксированном числе гетерогенных параллельных вычислителей

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

Модуль SPF@home поддерживает эту возможность путём сопоставления информации из двух файлов для операторов и вычислителей (*.ops и *.cls соответственно). Имеется возможность задавать совпадение по множеству свободно назначаемых признаков для любого диапазона операторов/вычислителей. Условием выполнимости данного оператора на заданном вычислителе является minVal_1Val_1maxVal_1 для одинакового параметра (Val_1, minVal_1, maxVal_1 числовые значения данного параметра для оператора и вычислителя соответственно).

Разработка расписания для выполнения программы на гетерогенном поле параллельных вычислителей является более сложной процедурой относительно вышеописанных и здесь упор делается на программирование на Lua (API-функции системы SPF@home обеспечивают минимально необходимую поддержку). Т.к. на одном ярусе ЯПФ могут находиться операторы, требующие для выполнения различных вычислителей, полезным может служить концепция расцепления ярусов ЯПФ на семейства подъярусов, каждое из которых соответствует блоку вычислителей c определёнными возможностями (т.к. все данного операторы яруса обладают ГКВ-свойством, последовательность выполнения их в пределах яруса/подъяруса в первом приближении произвольна). На схеме ниже слева показано расщепление операторов на одном из ярусов ЯПФ в случае наличия 6 параллельных вычислителей 3-х типов.

Пример плана выполнения программы на поле из 3-х типов параллельно работающих вычислителей (c количествоv 5,3,4 штук соответственно и номерами 1-5, 6-8, 9-12 по типам, всего 12 штук) приведён в табл.3. При расчёте в качестве исходной использовался конкретный алгоритм, характеризующийся ЯПФ с числом операторов 206 и дуг 323, ярусов 32 (после расчета подъярусов получилось 48). Первый столбец таблицы показывает (разделитель символ прямого слеша) номер яруса/подъяруса; в ячейках таблицы приведены номера операторов, сумма их числа по подъярусам равно числу операторов на соответствующем ярусе ЯПФ.

Моделирование, результат которого приведён в табл.3, может быть использовано в форме решения обратной задачи при определении оптимального числа параллельных вычислителей различного типа для выполнения заданных алгоритмов (групп алгоритмов).

В самом деле, в рассматриваемом случае общее время T решения задачи определяется суммой по всем ярусам максимальных значений времён выполнения операторов на подъярусах данного яруса, т.к. группы операторов на подъярусах выполняются последовательно (первая сумма берётся по j, вторая по i, максимум по k_j):

T=(maxt_ik),

где j - число ярусов ЯПФ, i - число подъярусов на данном ярусе, k_{j -} типы вычислителей на j-том ярусе, t_{ik -} время выполнения оператора типа i на вычислителе типа k. Если ставится задача достижения максимальной производительности, вполне возможно определить число вычислителей конкретного типа, минимизирующее T (напр., для показанного табл.3 случая количество вычислителей типа II полезно увеличить в пику вычислителяv типа I).

Задача минимизации общего времени решения T усложняется в случае возможности выполнения каждого оператора на нескольких вычислителях вследствие неоднозначности t_ik в вышеприведённом выражении; здесь необходима дополнительная балансировка по подъярусам.

Описание параметров операторов располагается в файлах с расширением ops, параметров вычислителей cls; соответствующая API-функция (обёрнутая Lua-вызовом) возвращает значение, разрешающее или запрещающее выполнение данного оператора на заданном вычислителе. Описанные файлы являются текстовыми (формат данных определён в документации), что даёт возможность разработки внешних программ для генерации требуемого плана эксперимента с использованием модуля SPF@home в режиме командной строки.

В порядке обсуждения небезынтересно будет рассмотреть вариант ЯПФ в нижней форме (при этом все операторы перемещены максимально в сторону окончания выполнения программы). Такая ЯПФ может быть получена из верхней перемещениями операторов по ярусам как можно ниже или проще построением ЯПФ в направлении от конца программы к её началу. Ниже проиллюстрировано сравнение распределения ширин ЯПФ в верхней и нижней формах (изображения в строке слева и справа соответственно в 4-х рядах) для алгоритма умножения матриц традиционным способом при порядках матриц N=3,5,7,10. Здесь H, W и W высота, ширина и среднеарифметическая ширина ЯПФ (последняя показана на рисунках пунктиром; символ прямого слеша разделяет параметры для верхней и нижней ЯПФ (фиолетовый цвет ярус максимальной ширины, красный минимальной).

Соответствующие иллюстрации для процедуры решения систем линейных алгебраических уравнения порядков N=3,5,7,10 безытерационным методом Гаусса представлены ниже.

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

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

Общей тенденцией формы начальной верхней (до целенаправленной реорганизации) ЯПФ является интенсивный рост в начале выполнения программы с относительно плавным снижением к концу выполнения. Логично предположить, что повышение степени этой неравномерности является одной из важных причин возрастания вычислительная сложность преобразования ЯПФ. В связи с этим целесообразно иметь методику численной оценки такой неравномерности (полезно для классификации ЯПФ алгоритмов по этому признаку).

Выше использованные количественные характеристики неравномерности не дают информации о форме кривой, обладающей этой неравномерностью. В качестве дополнительной оценки неравномерности распределения операторов по ярусам ЯПФ может быть признан известный графо-аналитического метод определения дифференциации доходов населения, заключающегося в расчёте численных параметров расслоения (кривая Лоренца и коэффициент Джини), несмотря на зеркально-противоположную форму анализируемых кривых. Удобство сравнения ЯПФ различных алгоритмов достигается нормированием обоих осей графиков на общую величину (единицу или 100%).

На рисунке слева внизу приведены частичные результаты начала подобного анализа (на примере ЯПФ алгоритма решения полного квадратного уравнения в вещественных числах), равномерность распределения операторов по ярусам ЯПФ характеризуется близостью кривых к прямой равномерного распределения (диагональный штрих-пунктир).

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

Итак, программная система SPF@home выполняет практическую задачу по составлению расписаний выполнения заданных алгоритмов (программ) на заданном поле параллельных вычислителей и дает возможность проводить различного типа исследования свойств алгоритмов (в данном случае оценивать вычислительную сложность методов составления расписаний). Система нацелена в основном на анализ программ, созданных с использованием языков программирования высокого уровня без явного указания распараллеливания и в системах c концепцией ILP (Instruction-LevelParallelism, параллелизм на уровне команд), хотя возможности модуля SPF@home позволяют использовать в качестве неделимых блоков последовательности команд любого размера.

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

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

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

• Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом (http://personeltest.ru/aways/habr.com/ru/post/530078/, 26.11.2021)

• Такие важные короткоживущие данные (http://personeltest.ru/aways/habr.com/ru/post/534722/, 24.12.2021)

• Это непростое условное выполнение (http://personeltest.ru/aways/habr.com/ru/post/535926/, 03.01.2021)

• Динамика потокового вычислителя (http://personeltest.ru/aways/habr.com/ru/post/540122/, 01.02.2021).

Основные данные вычислительных экспериментов по реорганизации ярусно-параллельной формы (ЯПФ) информационных графов алгоритмов (ТГА) приведены в предыдущей публикации (http://personeltest.ru/aways/habr.com/ru/post/545498/). Цель текущей публикации показать окончательные результаты исследований разработки расписаний выполнения параллельных программ в показателях вычислительной трудоёмкости собственно преобразования и качества полученных расписаний. Данная работа является итогом вполне определённого цикла исследований в рассматриваемой области.

Как и было сказано ранее, вычислительную трудоёмкости (ВТ) в данном случае будем вычислять в единицах перемещения операторов с яруса на ярус в процессе реорганизации ЯПФ. Этот подход близок классической методике определения ВТ операций упорядочивания (сортировки) числовых массивов, недостатком является неучёт трудоёмкости процедур определения элементов для перестановки.

Т.к. в принятой модели ЯПФ фактически определяет порядок выполнения операторов параллельной программы (операторы выполняются группами по ярусам поочерёдно), в целях сокращения будем иногда использовать саму аббревиатуру ЯПФ в качестве синонима понятия плана (расписания) выполнения параллельной программы. По понятным причинам исследования проводились на данных относительно небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера. Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач. При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow (http://personeltest.ru/aways/habr.com/ru/post/535926/) с последующим импортом в формате информационного графа в модуль SPF@home для дальнейшей обработки.

Основной целью преобразований ЯПФ продолжаем считать получение максимальной плотности кода (фактически максимальная загрузка имеющихся в наличии отдельных вычислителей параллельной вычислительной системы). Кстати, именно с этими понятиями связано известное зло-ироничное высказывание об излишнем количестве NOP-инструкций в связках сверхдлинного машинного слова в вычислителях VLIW-архитектуры (даже при наличии участков полностью последовательного кода лакуны в сверхдлинном слове формально должны быть заполнены некоей операцией-пустышкой)

Как и ранее, будем ссылаться на разработанные эвристические методы (иногда сокращённо именуемые просто эвристиками), реализованные на языке Lua и управляющие преобразованиями ЯПФ. Также не учитываем возможности одновременного выполнения команд нескольких процессов на параллельном поле вычислителей (хотя теоретически это может привести к повышению плотности кода).

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

Полученные результаты предназначаются для улучшения качества разработки расписаний выполнения параллельных программ в распараллеливающих компиляторах будущих поколений. При этом внутренняя реализация данных конечно, совсем не обязана предусматривать явного построения ЯПФ в виде двумерного массива, как для большей выпуклости показано на рис.2 в публикации http://personeltest.ru/aways/habr.com/ru/post/530078/ и выдаётся программным модулем SPF@home (http://vbakanov.ru/spf@home/content/install_spf.exe). Она может быть любой удобной для компьютерной реализации например, в наивном случае устанавливающей однозначное соответствие между формой ИГА в виде множества направленных дуг {k,l} (матрица смежности) и двоек номеров вершин i_k,j_k и i_l,j_l, где i,j номера строк и столбцов в ЯПФ (процедуру преобразования ИГА в начальную ЯПФ провести всё равно придётся, ибо в данном случае именно она выявляет параллелизм в заданном ИГА алгоритме; только после этого можно начинать любые преобразования ЯПФ).

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

Для каждой из группы рассматриваемых задач (преобразования с сохранением высоты исходной ЯПФ или при возможности увеличения высоты оной) рассмотрим по две методики (эвристики, ибо так согласились именовать разработки) для перового случая это 1-01_bulldozer vs 1-02_bulldozer, для второго - WidthByWidtn vs Dichotomy. Мне стыдно повторять это, но высота ЯПФ определяет время выполнения программы

1. Получение расписания параллельного выполнения программ при сохранении высоты ЯПФ

Сохранение высоты исходной ЯПФ равносильно выполнению алгоритма (программы) за минимально возможное время. Наиболее равномерная нагрузка на все вычислители параллельной системы будет при одинаковой ширине всех ярусов ЯПФ (среднеарифметическое значение). В ЯПФ реальных алгоритмов и размерности обрабатываемых данных среднеарифметическое значение является довольно большим (практически всегда много большим числа отдельных вычислителей в параллельной системе). Т.о. рассматриваемый случай не часто встречается в практике, но всё же должен быть разобран.

Для сравнения выберем часто анализируемые ранее алгоритмы и два эвристических метода целенаправленного преобразования их ЯПФ эвристики 1-01_bulldozer и 1-02_bulldozer.

Результаты применения этих эвристик приведены на рис. 1-3; обозначения на этих рисунках (по осям абсцисс отложены показатели размерности обрабатываемых данных):

• графики a), b) и с) ширина ЯПФ, коэффициент вариации (CV ширин ярусов ЯПФ), число перемещений (характеристика вычислительной трудоёмкости) операторов соответственно;

• сплошные (красная), пунктирные (синяя) и штрих-пунктирные (зелёная) линии исходные данные, результат применения эвристик 1-01_bulldozer и 1-02_bulldozer cответственно.

Данные рис. 1-3 показывают, что во многих случаях удаётся приблизиться к указанной цели. Напр., рис. 1a) иллюстрирует снижение ширины ЯПФ до 1,7 раз (метод 1-01_bulldozer) и до 3 раз (метод 1-02_bulldozer) при умножении матриц 10-го порядка.

Коэффициент вариации ширин ярусов ЯПФ (рис. 1b) приближается к 0,3 (граница однородности набора данных) при использовании эмпирики 1-02_bulldozer и, что немаловажно, достаточно стабилен на всём диапазоне размерности данных.

Трудоёмкость достижения результата (рис. 1c) при использовании метода 1-02_bulldozer значительно ниже (до 3,7 раз при порядке матриц 10) метода 1-01_bulldozer.

Важно, что эффективность метода возрастает с ростом размерности обрабатываемых данных.

Не менее эффективным показал себя метод 1-02_bulldozer на алгоритме вычисления коэффициента парной корреляции (рис. 2).

Попытка реорганизации ЯПФ алгоритма решения системы линейных алгебраических уравнений (СЛАУ) порядка до 10 обоими методами (рис. 3) оказалась малополезной. Ширину ЯПФ снизить не удалось вообще (рис. 3a), снижение CV очень мало (рис. 3b), однако метод 1-02_bulldozer немного выигрывает в трудоёмкости (рис. 3c).

Для большей полноты выводов объём исследований должен быть расширен, однако уже сейчас ясно, далеко не каждый метод реорганизации ЯПФ одинаково эффективен для преобразования (в смысле построения рационального расписания параллельного выполнения) различных алгоритмов. Т.к. принятый в данной работе общий подход предполагает итеративное приближение к наилучшему решению поставленной задачи, надлежит продолжить разработку новых эвристик (с учётом достигнутого).

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

Эта постановка задачи максимально близка к реальному случаю составления расписания для VLIW-машины с заданным числом процессорных команд в машинном слове (размер связки, бандла сверхдлинного машинного слова). При этом достигается и повышение плотности кода.

Ниже рассматривается распространенный случай выполнения программы на заданном гомогенном поле из W параллельных вычислителей (от W=W₀ до W=1, где W₀ ширина ЯПФ, а нижняя граница соответствует полностью последовательному выполнению). Сравниваем два метода реорганизации ЯПФ Dichotomy и WidthByWidtn:

• Dichotomy. Цель получить вариант ЯПФ с c шириной не более заданного W c увеличением высоты методом перенесения операторов с яруса на вновь создаваемый ярус ниже данного. Если ширина яруса выше W, ровно половина операторов с него переносится на вновь создаваемый снизу ярус и так далее, пока ширина станет не выше заданной W. Метод работает очень быстро, но грубо (высота ЯПФ получается явно излишней и неравномерность ширин ярусов высока).

• WidthByWidtn. Подлежат переносу только операторы яруса с числом операторов выше заданного N>W путём создания под таким ярусом число ярусов М, равное:

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

На рис. 4,5 показаны результаты выполнения указанных эвристик в применении к двум распространенным алгоритмам линейной алгебры - умножение квадратных матриц классическим методом и решение системы линейных алгебраических уравнений прямым (неитерационным) методом Гаусса; красные и синие линии на этих и последующих рисунках соответствуют эвристикам WidthByWidtn и Dichotomy соответственно. Не забываем, что ширина реформированной ЯПФ здесь соответствует числу команд в связке сверхдлинного машинного слова.

Как видно из рис. 4 и 5, оба метода на указанных алгоритмах приводят к близким результатам (из соображений представления ЯПФ плоской таблицей и инвариантности общего числа операторов в алгоритме это, конечно, гипербола!). При большей высоте ЯПФ увеличивается время жизни данных, но само их количество в каждый момент времени снижается.

Однако при всех равно-входящих соответствующие методу WidthByWidtn кривые расположены ниже, нежели по методу Dichotomy; это соответствует несколько большему быстродействию. Полученные методом WidthByWidtn результаты практически совпадают с идеалом высоты ЯПФ, равным N_сумм./W_средн. , где N_сумм. общее число операторов, W_средн. среднеарифметическое числа операторов по ярусам ЯПФ при заданной ширине ея.

Анализ результатов, приведённый на рис. 6 и 7, более интересен (хотя бы потому, что имеет чисто практический интерес вычислительную трудоёмкость преобразования ЯПФ). Как видно из рис. 6 и 7, для рассмотренных случаев метод WidthByWidtn имеет меньшую (приблизительно в 3-4 раза) вычислительную трудоёмкость (в единицах числа перестановок операторов с яруса на ярус) относительно метода Dichotomy (хотя на первый взгляд ожидается обратное). Правда, при этом метод (эвристика) WidthByWidtn обладает более сложной внутренней логикой по сравнению с Dichotomy (в последнем случае она примитивна).

Т.о. проведено сравнение методов реорганизации (преобразования) ЯПФ конкретных алгоритмов с целью их параллельного выполнения на заданном числе вычислителей. Сравнение проведено по критериям вычислительной трудоёмкости преобразований и неравномерности загрузки параллельной вычислительной системы.

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

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

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

• Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом (http://personeltest.ru/aways/habr.com/ru/post/530078/, 26.11.2021)

• Такие важные короткоживущие данные (http://personeltest.ru/aways/habr.com/ru/post/534722/, 24.12.2021)

• Это непростое условное выполнение (http://personeltest.ru/aways/habr.com/ru/post/535926/, 03.01.2021)

• Динамика потокового вычислителя (http://personeltest.ru/aways/habr.com/ru/post/540122/, 01.02.2021)

• Параллелизм и плотность кода (http://personeltest.ru/aways/habr.com/ru/post/545498/, 05.03.2021)

• Сколько стоит расписание (http://personeltest.ru/aways/habr.com/ru/post/551688/, 10.04.2021) - текущая

Вместо вступления

Прежде всего хочется выразить признательность всем, кто откликнулся на первую статью об оптимизации кода на языке C/C++ на примере функции для вычисления квадратного корня из целого с округлением до ближайшего целого. Благодаря экспертному вниманию была исправлена опечатка в тексте; копилка эффективных алгоритмов пополнилась.

Интересен алгоритм sqrxi32 от @Sdima1357 Пример 1, далее для краткости именуемый как _i32. Алгоритм _i32 безусловно выполняет главное условие задачи округление до ближайшего целого на всём множестве значений аргумента [ 0 .. 0xFFFFFFFF ], при этом показывает высокую производительность.

Пример 1: Вычисление квадратного корня из целого с округлением до ближайшего целого.

uint16_t sqrxi32( uint32_t y ){if ( y == 1 )return 1;uint32_t xh = y > 0x10000ul ? 0x10000ul : y;uint32_t xl = 0;uint32_t xc;for ( int k = 0; k < 16; k++ ){xc = ( xh + xl ) >> 1ul;if ( xc * xc - xc >= y ){xh = xc;}else{xl = xc;}}return ( xh + xl ) >> 1ul;}

Другое хорошее качество алгоритма _i32 предсказуемость по времени. Время работы _i32 постоянно в отличие от алгоритма _evn, потребляющего машинное время пропорционально модулю аргумента.

О чём этот текст

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

Исходный код содержит содержит решение одной задачи разными алгоритмами.

Анализ результатов наблюдений за рамками настоящей публикации.

Условия и допуски

Для сокращение текста принимаем:

• аппаратных платформ для тестов 3 платформы;

• вариантов оптимизации сборки 3 значения

Для сборки двоичного кода применяем:

• Одну единицу компиляции теста (файл main.c)

• Компиляцию в моно-поточный исполняемый файл

• Единую сборочную среду: CubeIDE (она же Eclipce CDT)

• Стандартные настройки профиля сборки RELEASE в среде CubeIDE

• Единый диалект компилятора: ISO C11 + gnu extensions (-std=gnu11)

• Применительно к микроконтроллерам:

  • CubeMX default settings, +48MHz, +USART1, +HAL;

  • Runtime lib: Reduced C ( --spec=nano.specs );

  • Use float with printf from new lib nano ( -u _printf_float );

Таблица 1: Варианты сборки исполняемого кода

Таблица 2: Общие характеристики аппаратных платформ

Таблица 3: Технические характеристики аппаратных платформ

Тестовый набор содержит некоторые алгоритмы из предыдущей статьи и комментариев к ней.

Для оценки FPU платформы M4 в тестовый набор добавлена функция sqrt_fps, решающая вычислительную задачу с применением коротких действительных (float), именуемая далее _fps (Float Point Short) Пример 2.

Пример 2: Квадратный корень из целого с точностью float

uint16_t sqrt_fps( uint32_t number ){if ( number < 2 )return (uint16_t) number;float f_rslt = sqrtf( number );uint32_t rslt = (uint32_t) f_rslt;if ( !( f_rslt - (float) rslt < .5 ) )rslt++;return (uint16_t) rslt;}

Функция _fps работает без ошибок с аргументом менее 22-х бит, что соответствует десятичному порядку 1+E5 Иллюстрация 1.

Иллюстрация 1: Ошибки функции "_fps" на порядках 1+E6+

Для всех наблюдаемых алгоритмов ограничиваем диапазон аргумента множеством значений
[0 .. 1+E5].

Таблица 4: Список наблюдаемых алгоритмов

Основная единица измерения производительность, среднее число циклических вызовов функции за одну миллисекунду.

Относительная производительность платформ

Ожидаемо, производительность платформы x86 выше производительности платформы ARM Cortex безотносительно характера оптимизации сборки. Последнее демонстрирует левая часть графика Иллюстрация 2.

Иллюстрация 2: Относительная производительность аппаратных платформ

На левой части графика по оси Y отображается среднее время последовательного выполнения всех тестов (Таблица 4), измеренное в секундах. На оси X аппаратные платформы.

Чем ниже высота столбика на левой части графика (Иллюстрация 2), тем выше скорость работы, тем лучше производительность соответствующей аппаратной платформы.

График каждой платформы, в свою очередь, представлен тремя столбцами, демонстрирующими зависимость производительности от варианта оптимизации сборки: -O0, -Os, -O3.

Правая часть графика (Иллюстрация 2) показывает относительный прирост производительности у каждой аппаратной платформы в зависимости от варианта оптимизации сборки: -O0, -Os, -O3.

Производительность 100% демонстрирует двоичный код, собранный без оптимизации ( -O0 ). Это базовая производительность платформы.

Чем выше высота столбика относительно базовой производительности (O0) в правой части графика, тем лучше оптимизационные возможности программно-аппаратной платформы.

Наблюдаем наибольший прирост производительности от оптимизации на этапе сборки наплатформе M4.

Платформа x86

На графике (Иллюстрация 3) по оси Y отображается число цикличных вызовов наблюдаемых функций за одну миллисекунду. На оси X наблюдаемые функции (Таблица 4).

Чем выше на графике столбики, тем лучше производительность.

Цветом на оси X обозначен способ оптимизации на этапе сборки. Соответствие цвета и характера оптимизации отражает легенда.

Иллюстрация 3: Производительность алгоритмов на платформе x86

Платформа x86 максимально раскрывает преимущества алгоритмов с плавающей точкой перед целочисленными.

Заслуживает отдельного внимания часть графика в оранжевом контуре.

Производительность кода без оптимизации (O0) лучше на 39% для алгоритма _fpu (Os) и на 16% для алгоритма _fps (O3). Другими словами, любая оптимизация на этапе сборки снижает производительность платформы x86 на действительных числах.

В то же время, целочисленные алгоритмы показывают ожидаемый прирост производительности при сборке с параметрами -O3 и -Os.

Платформа M4

Платформа M4 демонстрирует предсказуемый результат (Иллюстрация 4).

Иллюстрация 4: Производительность алгоритмов на платформе M4

Модуль с плавающей точкой M4 даёт ожидаемый прирост производительности для алгоритма _fps, основанного на коротком действительном float.

Последнее подтверждается результатом сравнения производительности алгоритмов при отключенном модуле FPU на платформе M4 Иллюстрация 5.

Наблюдая графики помним, что точность вычислений алгоритма _fps гарантируется в диапазоном 1+E5 (см. Иллюстрация 1) без относительно того, включен ли модуль FPU на M4 или нет.

Иллюстрация 5: Производительность алгоритмов на платформе M4 без FPU

Платформа M0

Результаты платформы M0 похожи на результаты платформы M4безFPU (Иллюстрация 5), только медленнее Иллюстрация 6.

Заметим, тактовая частота при тестировании устанавливалась одинаковой и для M4, и для M0 48 MHz. Однако, производительность M0 хуже в два с лишним раза, чем M4, в условиях равенства прочих характеристик.

Иллюстрация 6: Производительность алгоритмов на платформе M0

Алгоритм _fps на платформе M0 ожидаемо опережает в два раза алгоритм _fpu.

Целочисленные алгоритмы опережают алгоритмы с плавающей точкой.

По странному стечению обстоятельств в заключительном графике (Иллюстрация 6) снова есть место для оранжевого контура.

При сборке без оптимизации (O0) алгоритм _evn быстрее алгоритма _i32. И алгоритм _evn медленнее, чем _i32, если сборка проводится с оптимизацией.

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

Вместо заключения

Производительность программы зависит от многих причин.

Оптимизация на этапе сборки способна ухудшать производительность, замедлять программу, что демонстрируют экспериментальные данные в оранжевых контурах выше (Иллюстрация 3 и Иллюстрация 6).

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

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

Приложение 1. Порядок тестирования платформы x86

1. Создать в среде CubeIDE (Eclipse CDT) проект C штатным способом

2. Написать текст программы Пример 3

3. Добавить в проект файл sqrt_cmp.h Пример 6

4. Осуществить сборку и запуск программы:

   1. штатными средствами IDE;

   2. или из командной строки Пример 4

5. Меняя вид оптимизации ( -O0, -O3, -Os ) наблюдать результат.

Пример 3: Исходный текст программы x86 main.c

#include sqrt_cmp.hint main( void ){main_Of_SqrtComp();return 0;}

Пример 4 Запуск теста на платформе x86 из терминала

gcc main.c -o main -I. -Wall -lm -std=gnu11 -O3 && ./main

Запуск теста из терминала платформы x86 предполагает, что файлы main.c и sqrt_cmp.h располагаются в одном каталоге, и этот каталог выбран рабочим (pwd).

Иллюстрация 7: Запуск теста из терминала x86

Приложение 2. Порядок тестирования платформы STM32

1. Создать в среде CubeIDE проект STM32 штатным способом (CubeMX)

2. Добавить файл sqrt_cmp.h в проект STM32 Пример 6

3. Включить sqrt_cmp.h в файл main.c Пример 5

4. Осуществить сборку и запуск программы штатными средствами IDE

5. Меняя вид оптимизации ( -O0, -O3, -Os ) наблюдать результат

Пример 5: Исходный текст для STM32 (с пропусками < ... >) main.c

<  >/* Private includes ----------------------------------------------------------*//* USER CODE BEGIN Includes */#include "sqrt_cmp.h"/* USER CODE END Includes */<  >/**  * @brief  The application entry point.  * @retval int  */int main(void){<  >  /* Infinite loop */  /* USER CODE BEGIN WHILE */  main_Of_SqrtComp();  while (1)  {    /* USER CODE END WHILE */    /* USER CODE BEGIN 3 */  }  /* USER CODE END 3 */

Приложение 3. Порядок тестирования других алгоритмов и платформ

Сборка теста для других платформ проводится по аналогии.

Для отличных от упомянутых выше аппаратных платформ (Таблица 3), вероятно, потребуется косметическая модификация файла sqrt_cmp.h.

Пример 6: Содержание файла sqrt_cmp.h

/****************************************************************************** * File: sqrt_cmp.h Created on 5 авг. 2020 г. * CC0 1.0 Universal (CC0 1.0) * Creative Commons Public Domain Dedication * No Copyright * * TAB Size .EQ 4 ********************************************************************************/#ifndef __SQRT_CMP_H#define __SQRT_CMP_H#include<math.h>#include<stdio.h>#include<stdint.h>#ifdef __cplusplusextern "C" {#endif/****************************************************************************** * Interface of the entry point for all sqrt tests ******************************************************************************/void main_Of_SqrtComp();/****************************************************************************** * test case selection: TEST_SET * select one of the test suite via a comment. ******************************************************************************/#define TEST_SETTEST_ALL//#define TEST_SETTEST_ROUNDING//#define TEST_SETTEST_PERFORMANCE/****************************************************************************** * Interfaces of test functions. * See implementation of them at the end of this file. ******************************************************************************/typedef uint16_t (*sqrt_func)( uint32_t number );uint16_t sqrt_fpu( uint32_t number );// floating point function from articleuint16_t sqrt_evn( uint32_t number );// integer function from articleuint16_t sqrxi32( uint32_t y );// integer function from comment byuint16_t sqrt_fps( uint32_t number );// optimized floating point function for Cortex M4// <-- insert interface of your function here/****************************************************************************** * Set to variable named as 'round_test_func' below * to the alias of one of the functions above. * The NULL will select last function in comp_list[] ******************************************************************************/sqrt_func round_test_func = sqrt_fps;// specific instance for the rounding test//sqrt_func round_test_func = sqrxi32;// specific instance for the rounding test//sqrt_func round_test_func = sqrt_evn;// specific instance for the rounding test//sqrt_func round_test_func = NULL;// last function in comp_list[]/****************************************************************************** * The array of test functions for competing routines is called comp_list[]. * Adding a new function to the test: - copy the implementation of the new function to the end of this file; - declare the function interface at the beginning of this file; - add the alias and declaration of the new function to end of array named comp_list[]. ******************************************************************************/// @formatter:offtypedef struct{sqrt_funcfsqrt;char *alias;} SCompFunc;SCompFunc comp_list[] =// competition list{{ sqrt_fpu, "_fpu" },{ sqrt_fps, "_fps" },{ sqrt_evn, "_evn" },{ sqrxi32,  "_i32" }// <-- insert your function name & alias here};/* @formatter:on *//****************************************************************************** * Platform-independent definitions ******************************************************************************/#define PUT_FORMAT_MSG(f_, ...) { \sprintf( (char *)s_buf, (char *)f_, ##__VA_ARGS__ ); \PUT_MSG( (char *)s_buf ); }#define MS_PER_SEC1000#define US_PER_SEC( MS_PER_SEC * MS_PER_SEC )#define ARRAY_SIZE(a) (sizeof a / sizeof *a)// size of static array at runtime#define SIRV(f) if ( f ) ;// suppress Ignore Return Value warning/****************************************************************************** * Platform-specific defines ******************************************************************************/#if defined( USE_HAL_DRIVER )// STM32 ARM Cortex platform#include<string.h>#include "main.h"//*****************************************************************************// Platform-specific defines for the helper functions#define SCALE_RATE1// must be .GE than 1#define X_CLOCKHAL_GetTick()#define X_DELAY( ms )HAL_Delay( ms )//*****************************************************************************// Platform-specific defines for the terminal output#define USART_HANDLEhuart1// set valid USART handler alias here defined by the config of MCU#define USART_TIMEOUT150// max timeout for HAL_UART_Transmitextern UART_HandleTypeDef USART_HANDLE;extern HAL_StatusTypeDef HAL_UART_Transmit ( UART_HandleTypeDef *huart, uint8_t *pData, uint16_t Size, uint32_t Timeout );#define PUT_MSG( msg ) \HAL_UART_Transmit( &USART_HANDLE, (uint8_t *)msg, strlen( (char *)msg ), USART_TIMEOUT )#define CPU_CLOCK_MHz( SystemCoreClock / US_PER_SEC )// CPU CLK in MHz#if defined( STM32F0 )#defineCPU_ID ( "STM32 ARM Cortex M0" )#elif defined ( STM32F3 )#defineCPU_ID ( "STM32 ARM Cortex M4" )#else#defineCPU_ID ( "Maybe STM32 ARM Cortex" )#endif#define PUT_SYS_INFOPUT_FORMAT_MSG( " %s @ "fdU()" MHz\n", CPU_ID, CPU_CLOCK_MHz )#else// #if defined( USE_HAL_DRIVER)#include <time.h>#include <stdlib.h>//*****************************************************************************// Platform-specific defines for the helper functions#define SCALE_RATE100// must be .GE than 1#define X_CLOCK(uint32_t) x_clock()#define X_DELAY( ms )x_delay( ms )uint32_t x_clock(){uint64_t result = (uint64_t) clock();result *= MS_PER_SEC;result /= CLOCKS_PER_SEC;return (uint32_t) result;}void x_delay( uint32_t ms ){uint64_t tm = x_clock();while ( ( x_clock() - tm ) < ms );}//*****************************************************************************// Platform-specific defines for the terminal output#define PUT_MSG( msg ) \printf( "%s", (char *)msg ), fflush ( stdout );#if defined( __unix__ )// anybody other platform for gcc#define PUT_SYS_INFOSIRV( system( "cat /proc/cpuinfo | grep 'model name' | head -1 | sed s/'model name\t:'/''/" ) )#else#define PUT_SYS_INFOPUT_MSG( "Undefined System & CPU" )#endif// #if defined( __unix__ )  // anybody other platform for gcc#endif// #if defined( USE_HAL_DRIVER)#if  ( __WORDSIZE == 64 )#define fdI(s)"%" #s "d"#define fdU(s)"%" #s "u"#define fdX(s)"%" #s "x"#else// let's say __WORDSIZE == 32#define fdI(s)"%" #s "ld"#define fdU(s)"%" #s "lu"#define fdX(s)"%" #s "lx"#endif// #if ( __WORDSIZE == 64 )#if defined ( DEBUG ) || defined ( _DEBUG ) // chk build mode of CubeIDE#defineBUILD_MODE"DEBUG"#else // Maybe Release#defineBUILD_MODE"RELEASE"#endif// #if defined ( DEBUG ) || defined ( _DEBUG )/****************************************************************************** * the helper data with testing ranges ******************************************************************************/// @formatter:offtypedef struct{uint32_tstart;uint32_tstop;uint32_trepeat;} STestRange;STestRangetest_rngs[] ={{ 0, 1000, 100 * SCALE_RATE },{ 0, 10000, 10 * SCALE_RATE },{ 0, 100000, 1 * SCALE_RATE }};uint32_t test_results[ARRAY_SIZE( test_rngs )][ARRAY_SIZE( comp_list ) + 1];#define MSG_BUFF_SIZE512uint8_t s_buf[MSG_BUFF_SIZE];// buffer for a terminal output/* @formatter:on *//****************************************************************************** * Test sets definitions. Do not change it. ******************************************************************************/#define TEST_ROUNDING1#define TEST_PERFORMANCE2#define TEST_ALL( TEST_ROUNDING | TEST_PERFORMANCE )#ifndef TEST_SET#defineTEST_SETTEST_ALL#endif#define HI_ROUND_TEST_RANGE_END0x007FFFFFUL#define HI_ROUND_TEST_RANGE_START( HI_ROUND_TEST_RANGE_END >> 4 )/****************************************************************************** * Interface of helper functions ******************************************************************************/void main_Header();void testRounding();void testPerformance();/****************************************************************************** * Implementation of the entry point for all sqrt tests ******************************************************************************/void main_Of_SqrtComp(){X_DELAY( MS_PER_SEC / 2 );// suppress the output of a previous instance// while the new instance is loading into the MCUuint32_t start_time = X_CLOCK;main_Header();// checking normal and extended ranges for roundingif ( TEST_SET & TEST_ROUNDING )testRounding();// checking normal ranges on execution timeif ( TEST_SET & TEST_PERFORMANCE )testPerformance();uint32_t test_time = X_CLOCK - start_time;uint32_t test_m = ( test_time / MS_PER_SEC ) / 60;uint32_t test_s = ( test_time / MS_PER_SEC ) % 60;uint32_t test_ms = test_time % MS_PER_SEC;PUT_FORMAT_MSG( "\ndone, spent time: "fdU()" m, "fdU()"."fdU()" s\n", test_m, test_s, test_ms );}/****************************************************************************** * Implementation of the helper functions ******************************************************************************/void main_Header(){PUT_MSG( "\n\n**********************************************************\n" );PUT_SYS_INFO;PUT_FORMAT_MSG( "*********** %s, built at %s\n", BUILD_MODE, __TIME__ );}void testPerformance(){uint32_t i_func, i_rpt, i_rng;uint32_t number, first, second, diff;uint64_t temp;PUT_MSG( "----------+ Performance test" );for ( i_rng = 0; i_rng < ARRAY_SIZE( test_rngs ); i_rng++ ){PUT_MSG( "\n" );PUT_FORMAT_MSG( "test range:["fdU()".."fdU()"], repeat="fdU()"\n", test_rngs[i_rng].start, test_rngs[i_rng].stop,test_rngs[i_rng].repeat );test_results[i_rng][0] = test_rngs[i_rng].stop;for ( i_func = 0; i_func < ARRAY_SIZE( comp_list ); i_func++ ){PUT_FORMAT_MSG( "%s ... ", comp_list[i_func].alias );first = X_CLOCK;for ( i_rpt = 0; i_rpt < test_rngs[i_rng].repeat; i_rpt++ )for ( number = test_rngs[i_rng].start; number < test_rngs[i_rng].stop; number++ )comp_list[i_func].fsqrt( number );second = X_CLOCK;diff = second - first;temp = ( test_rngs[i_rng].stop - test_rngs[i_rng].start ) * test_rngs[i_rng].repeat;test_results[i_rng][i_func + 1] = (uint32_t) ( temp / diff );if ( i_func < ARRAY_SIZE( comp_list ) - 1 )PUT_MSG( ", " );}}// small reportPUT_FORMAT_MSG( "\n----------+ Report: sqrt`s calls per ms\n%10s", "range" );for ( i_func = 0; i_func < ARRAY_SIZE( comp_list ); i_func++ )PUT_FORMAT_MSG( "%10s", comp_list[i_func].alias );for ( i_rng = 0; i_rng < ARRAY_SIZE( test_rngs ); i_rng++ ){PUT_MSG( "\n" );for ( i_func = 0; i_func < ARRAY_SIZE( comp_list ) + 1; i_func++ )PUT_FORMAT_MSG( fdU( 10 ), test_results[i_rng][i_func] );}PUT_FORMAT_MSG( "\n----------+\n%10s", "average" );for ( i_func = 0; i_func < ARRAY_SIZE( comp_list ); i_func++ ){temp = 0;for ( i_rng = 0; i_rng < ARRAY_SIZE( test_rngs ); i_rng++ )temp += test_results[i_rng][i_func + 1];temp /= ARRAY_SIZE( test_rngs );PUT_FORMAT_MSG( fdU( 10 ), (uint32_t)temp );}}void testRoundingFunction( uint32_t start, uint32_t finish, sqrt_func psqrt, char *fname );void testRounding(){uint16_t i_rng;uint16_t f_rng;PUT_MSG( "----------+ Rounding test\n" );// checking the existence for the test functionfor ( f_rng = 0; f_rng < ARRAY_SIZE( comp_list ); f_rng++ )if ( comp_list[f_rng].fsqrt == round_test_func )break;if ( !( f_rng < ARRAY_SIZE( comp_list ) ) ){f_rng = ARRAY_SIZE( comp_list ) - 1;PUT_FORMAT_MSG( "Value of 'round_test_func' not found.\n" );}PUT_FORMAT_MSG( "Function '%s' is tested for rounding.\n", comp_list[f_rng].alias );// checking standard rangesfor ( i_rng = 0; i_rng < ARRAY_SIZE( test_rngs ); i_rng++ )testRoundingFunction( test_rngs[i_rng].start, test_rngs[i_rng].stop, comp_list[f_rng].fsqrt, comp_list[f_rng].alias );// checking extended rangetestRoundingFunction( HI_ROUND_TEST_RANGE_START, HI_ROUND_TEST_RANGE_END, comp_list[f_rng].fsqrt, comp_list[f_rng].alias );}void turn_the_fan( uint32_t ms );void testRoundingFunction( uint32_t start, uint32_t finish, sqrt_func psqrt, char *fname ){uint32_t rf, ri;uint32_t n, c = 0;PUT_FORMAT_MSG( "test range:["fdU( 10 )".."fdU( 10 )"] ... ", start, finish );for ( n = start; n < finish; n++ ){rf = sqrt_fpu( n );ri = ( *psqrt )( n );if ( rf != ri ){if ( c++ > 3 ){PUT_FORMAT_MSG( "\b\n(!)too many mistakes in '%s', ", fname );break;}else{double d = sqrt( (double) n );PUT_FORMAT_MSG( "\b\n%s("fdU( 10 )")="fdU()" != "fdU(), fname, n, ri, rf );PUT_FORMAT_MSG( " (real value is %.6lf)", d );}}turn_the_fan( MS_PER_SEC );}if ( !c ){PUT_FORMAT_MSG( "\b done.\n" );}else{PUT_FORMAT_MSG( "test failed.\n" );}}void turn_the_fan( uint32_t ms ){static char ca[] = "|/-\\";static uint32_t cs = ARRAY_SIZE(ca) - 1;static uint32_t cn = 0;static uint32_t at = 0;uint32_t ct = X_CLOCK;if ( ct - at > ms ){at = ct;PUT_FORMAT_MSG( "\b%c", ca[cn++ % cs] );}}/****************************************************************************** * Implementation of the sqrt functions ******************************************************************************/// floating point arg & result with doubleuint16_t sqrt_fpu( uint32_t number ){if ( number < 2 )return (uint16_t) number;double f_rslt = sqrt( number );uint32_t rslt = (uint32_t) f_rslt;if ( !( f_rslt - (double) rslt < .5 ) )rslt++;return (uint16_t) rslt;}// floating point arg & result with floatuint16_t sqrt_fps( uint32_t number ){if ( number < 2 )return (uint16_t) number;float f_rslt = sqrtf( number );uint32_t rslt = (uint32_t) f_rslt;if ( !( f_rslt - (float) rslt < .5 ) )rslt++;return (uint16_t) rslt;}// unsigned integer arg & result// @formatter:offuint16_t sqrt_evn ( uint32_t number ){if ( number < 2 )return ( uint16_t ) number;uint32_t temp;uint32_t div;uint32_t rslt;if ( number & 0xFFFF0000L )if ( number & 0xFF000000L )if ( number & 0xF0000000L )if ( number & 0xE0000000L )div = 43771;elsediv = 22250;elseif ( number & 0x0C000000L )div = 11310;elsediv = 5749;elseif ( number & 0x00F00000L )if ( number & 0x00C00000L )div = 2923;elsediv = 1486;elseif ( number & 0x000C0000L )div = 755;elsediv = 384;elseif ( number & 0xFF00L )if ( number & 0xF000L )if ( number & 0xC000L )div = 195;elsediv = 99;elseif ( number & 0x0C00L )div = 50;elsediv = 25;elseif ( number & 0xF0L )if ( number & 0x80L )div = 13;elsediv = 7;elsediv = 3;rslt = number;while ( 1 ){temp = number / div;temp += div;div = temp >> 1;div += temp & 1;if ( rslt > div )rslt = div;else{if ( number / rslt == rslt - 1 && number % rslt == 0 )rslt--;return ( uint16_t ) rslt;}}}/* @formatter:on */// unsigned integer arg & resultuint16_t sqrxi32( uint32_t y ){if ( y == 1 )return 1;uint32_t xh = y > 0x10000ul ? 0x10000ul : y;uint32_t xl = 0;uint32_t xc;for ( int k = 0; k < 16; k++ ){xc = ( xh + xl ) >> 1ul;if ( xc * xc - xc >= y ){xh = xc;}else{xl = xc;}}return ( xh + xl ) >> 1ul;}// <-- insert implementation of your function sqrt here#ifdef __cplusplus}#endif#endif // __SQRT_CMP_H

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

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

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

Рассказываем, как мы внедрили алгоритм автоматического отключения таких призраков и уменьшили долю ненайденных товаров на 25%.

Как работает СберМаркет

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

К СберМаркету подключены сотни магазинов по всей России. В каждом уникальный ассортимент из десятков тысяч товаров. В общем каталоге сервиса больше 16 млн позиций. На таких объемах контролировать актуальность и наличие тяжело.

Чтобы улучшить сервис, нам предстояло не только сделать эффективный алгоритм, но и внедрить его в кратчайшие сроки. За время пандемии количество заказов выросло в 15 раз нужно соответствовать.

Идея алгоритма

В каждом из магазинов, подключенных к СберМаркету, есть постоянная команда сборщиков. Лидеры команды регулярно присылают в отдел контента список артикулов тех товаров, которые нужно отключить в каталоге: например, когда случилась задержка поставки или истек срок годности.

Исторически 70% таких артикулов имеют очень высокий показатель ненайденных товаров за последние дни продаж более 50%. Значит, нужно срочно заблокировать позицию в каталоге, чтобы клиенты не смогли купить то, что мы не можем привезти.

Выше представлена динамика неуспешных сборок по товару из категории фрукты в одном магазине. С 21 июня по 1 июля показатель ненайденных товаров был 100%. Хотя ретейлер передавал нам другие данные.

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

Было бы логичным отключить позицию еще в самом начале пика. Так мы спасли бы сборщиков от лишней работы, а клиентов от грусти и звонков. Как мы сформулировали задачу по итогам кейса: нужно построить такой алгоритм, который будет каждый час мониторить ненайденные сборщиками товары, отбирать из них самые проблемные и моментально отключать их в каталоге магазина.

И начали писать его на Python.

Как работает алгоритм

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

2. Из базы данных наших заказов вытаскиваем историю последних сборок. Для каждого ненайденного товара берём историю THRESHOLD_ORDERS.

3. Если в последних THRESHOLD_ORDERS заказах процент ненайденных товаров более THRESHOLD_CANCELLATION процентов, то эту позицию нужно заблокировать.

4. Если товар ещё ни разу не блокировался или с момента последней блокировки уже прошло DAYS_NO_CANC дней, то товар блокируется на HIDE_1 дней.

5. Если с момента последней блокировки товара прошло менее DAYSNOCANC дней, то:
   
   ~ товар блокируется на HIDE_2 дней, если текущая блокировка ставится второй раз подряд;
   ~ товар блокируется на HIDE_3 дней, если уже блокировался более двух раз подряд.

Пример параметров алгоритма для магазина:

'params': {  'DAYS_NO_CANC': 4,  'HIDE_1': 2,  'HIDE_2': 11,  'HIDE_3': 9,  'THRESHOLD_CANCELLATION': 0.4,  'THRESHOLD_ORDERS': 3  }

Параметры алгоритма подбирались отдельно для каждого магазина на исторических данных с использованием библиотеки hyperopt на Python. В процессе оптимизации максимизировалась метрика F-мера с beta 0.7.

Зачем так усложнять

Почему нельзя просто всегда блокировать товары на N дней? Зачем нам параметры DAYS_NO_CANC, HIDE_1, HIDE_2 и HIDE_3?

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

Кейс 1: товары нужно блокировать на маленький срок

У ретейлера A в магазине закончились бананы. Новую поставку смогут выложить в торговый зал через 1-2 дня. Бананы необходимо заблокировать на максимально маленький срок после этого они точно будут доступны для клиентов и сборщиков.

Кейс 2: товары нужно блокировать на большой срок

У ретейлера B случился сбой в поставке яблочного сока. Возможно, новая партия доедет до магазина через 2-3 недели. Нет смысла блокировать товар на маленький срок, так как после такой блокировки клиенты все равно смогут заказать товар, но сборщик не сможет его собрать.

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

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

Параметр HIDE_3 нужен для того, чтобы сохранять длительные блокировки. Возможно, сок из второго кейса появится не через 2-3 недели, а через месяц. В этом случае после блокировки на HIDE_2 дней сок заблокируется на HIDE_3 дней.

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

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

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

Чего вам не хватает в сервисах доставки продуктов или у нас? Делитесь в комментариях подумаем над решением.

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

Ниже, просто интимная история про чувства, этапы, страхи, немного фантастики и муки выбора.

Давайте представим.

Вы придумали какой-то свой алгоритм для очередной сложной задачи.

Не важно в какой сфере, не важно на каких языках и технологиях.

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

Представили?

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

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

Было? Знакомо? Давно?

Вы как человек не ленивый или просто очень увлекающийся - создаете модель, некрасивую и непродуманную, на коленках, пренебрегая всем чему вас учила жизнь и опыт, только ради проверки идеи - делаете простенький прототип. И О чудо! - он работает.

Энтузиазм увеличивается и без сна и отдыха воруя время у самого себя и любимых Творите! Творите и творите! Меняете инструменты и средства, выбираете наиболее подходящие технологии, пополняете поисковые запросы по словам неизвестных вам ранее решений. Оборачиваете красивыми классами и методами. Тестируете, опять на написанных "всё там же" исходных данных и снова тесты, проверки, тесты... Не получается Психуете удаляя в очередной раз все коммиты и бренчи. И начинаете заново И снова, и снова, и снова

Опять переписываете

Но эмоции от самоудовлетворения самим процессом и только вами видимого результата - зашкаливают.

И в один прекрасный момент, ваш алгоритм оживает и рождается - Он. Маленький звереныш. С огромным количеством лапок, несколькими головами, разноцветной шкуркой.

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

И начинаются судорожные скитания в поисках пропитания для Вашего звереныша.

Вы берете первые, какие-то уже настоящие, которые кажутся вам сначала большими данные. И с опаской предлагаете вашей, уже любимой, ИТ-зверюшке.

А она.. хрум, хрум - и съела.

Наступает полное торжество и обманчивое чувство осознания значимости созданной зверюшки! Вот она - Победа!Но, внутренний голос подсказывает, что зверюшка может, и самое главное ХОЧЕТ больше!

Начинаете искать еще больше пищи, больше данных. Находите. Готовите. Угощаете. И тут зверюшка, один раз Хрум и всё. Секунда, десять, минута а экран замер. Вы судорожно набираете htop и картина пугает. Всё улетело за 100%. И еще через несколько минут уже сами набираете kill, а потом еще и добиваете killall зверюшка, killall база, killall, killall, killall

И снова исправления, изменения, замены, удаления, все сначала, О! А можно вообще по другому и снова роль Творца и тесты, эксперименты, проверки

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

ПОЛУЧИЛОСЬ!

Корм съеден. Зверюшка, как ни в чем не бывало, радостно ждет следующую порцию.

Вы даете больше и больше. 100k, 1М, 10М, 40М порций. В один поток, два, десять, сто...

Хрум. Хрум. Хрум. Profit!

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

Наступает пора его подготавливать к реальной жизни.

Вы клонируете мир ваших текущих забот и работ. Помещаете туда питомца.

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

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

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

В эту секунду к Вам приходит безумнейшая мысль.

А что если Я создам и подарю ему целый мир, котором он будет жить.

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

Но все вокруг Вам говорят, Куда? Кто? Ты? Как? Такой мир построить - нужны десятки людей - творцов. И самое главное - очень богатых богов. Ты понимаешь, что они правы и страх, отсутствие веры, нехватка времени и знаний - и ты все откладываешь и переносишь на потом... ещё потом ещё потом

Но однажды, наступает тот момент, когда приходит осознание, что ПОТОМ - начинает превращаться в НИКОГДА. И ты понимаешь, что НИКОГДА - еще страшнее, чем все другие страхи.

И после этой, открытой именно тебе, истины, ты делаешь шаг. Бросаешь всё и начинаешь Создавать.

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

Рано или поздно, муки выбора проходят и наконец вот она ТВОЯ СИСТЕМА, в которой будут созданы миры. Только твои!

Создаешь, соединяешь, закрываешь, разрешаешь, пробрасываешь, перекидываешь. Творишь...

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

Проходит время - и видишь красивейший кластер. Твой мир.

При заселении, ты уже знаешь, что один твой питомец не проживет. Ты

придумываешь новых и приглашаешь других из чужих безопасных миров.

Создаешь ландшафты и садишь деревьями, рисуешь облака и наполняешь морями и океанами.

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

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

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

Заглядываешь в космопорт - а там от твоих красивых архитектурных решений только руины. Хранилище, базы, зоопарки - уцелели, но без связи.

Ты закрываешь весь мир огромной сферой и находясь опять в полном одиночестве с замершими планетами и всеми обитателями заново начинаешь искать. Где?, Ну где же, ты ошибся?

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

Всё!

Пришло время открыться!

Проверка каждого уголка. И ты принимаешь решение пустить в него первых посетителей - других обитателей вселенной.

Запуск!

Внутреннее эго раздуто, радость переполняет, ощущения восторга вперемешку с полным экстазом прячутся под гордой маской невозмутимости.

Всё отлично работает. Кто возмущается. Кому-то нравится. Кто-то подсказывает, где, что не так.

А кто-то тихо потешается над твоим водопадом, в котором вода течет не DESC, а ASC, рассказывая о этой находке всем кроме тебя.

И в целом - все хорошо. Ты расслабляешься продумывая дальнейшую жизнь.

Время идет. Мир существует. Твой питомец становится все сильнее и сильнее. Он обретает друзей среди других, созданных тобой и не только, питомцев.

Все планеты существуют в гармонии и мире. Созданы планеты позволяющие менять убранство других и пополнять хранилище.

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

Но мир создавал ты один. Один уже сделал то, про что остальные говорили - невозможно.

Значит пора делать очередной LevelUp. И снова начинать качать новые скилы.

И опять поиск. Опять прогулки в поиске даже не ответов, а только правильных вопросов. Куда? Кому? Как? Скольким или может быть одному? За сколько? И главное, снова - Зачем это все?

Опять муки выбора вариантов.

Начинать развивать мир с кем-то? Учить законы вселенных, учиться управлять, учиться рисковать, а также и всё-таки, учиться искать богатых покровителей, искать других творцов и всех тех, кто будет помогать, от управления до уборки мусора и еще познавать многое другое.

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

Найти уже давно существующий мир с сильным и богатым хозяином ради объединения? Но переживут ли такое слияние твои любимые питомцы, не запустится процесс бесконечной мутации, такой, что даже первое имя зверюшки будешь помнить только ты? И не превратишься ли ты в ту самую единичку которая занимается только подкормкой его?

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

Перенестись только вместе с питомцем в чужой мир? А этот оставить для красоты и самолюбования. Тогда, столько, самого ценного, что есть у человека- времени, будет потрачено зря.

Ничего не делать, опустить руки и уйти самому жить в другие миры?

И еще много очень много других мучительных вариантов.

Выбор.

Кто-то проходит через муки выбора, кто-то через радость что выбор есть, кто-то не видит выбора как такового и хватается за первое решение, а кто-то постоянно только ищет разные варианты не принимая никакого. Но выбор есть всегда!

Из одной маленькой идеи каждый может создать новый мир.

С Уважением, Дмитрий.