Оценка скорости кода. Сложность алгоритма

Публикация № 1131829

Разработка - Практика программирования

Компьютер-саенс сложность алгоритма вычислительная нотация большого О

Эта тема одной из первых всплывает на собеседовании программистов языков вроде Java и C, но она почти неизвестна в "мире 1С". Поговорим о вычислительной сложности алгоритмов.

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

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

Тут можно подумать: что за ерунда? Если надо обработать массив из 10 элементов - надо выподнить что-то 10 раз. Если из 100 элементов - 100 раз, как может быть иначе?

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

Для и1 = 0 По Массив.ВГраница() Цикл
	Для и2 = 0 ПО Массив.ВГраница() Цикл
		...

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

похоже на параболу.

Если массив имеет 4 элемента - цикл выполнится 16 раз. Если 5 - 25, 6 - 36 и т.д. Это называется квадратичной сложностью. На самом деле есть оптимизации позволяющие сократить это время более чем вдвое, чтобы формула сложности выгляделя так: n²/2 - n/2, но поскольку мы говорим не о каких-то точных значениях, а об оценке алгоритма и фрагмент n² тут доминирует над остальными операциями, всей остальной частью формулы обычно пренебегают и говорят, что сложность алгоритма пузырьковой сортировки - n². Записывают обычно в таком виде: O(n²), это называется "нотация большого О".

В разработке прикладных решений понимание того факта, какой сложносьтю обладает разработанный алгоритм не всегда нужно, поскольку высокая (квадратичная или даже выше) сложность обычно нивелируется небольшим количеством обрабатываемых данных и высокой производительостью серверов в энтерпрайзе. Ну какое количество строк может быть в накладной? 50? 100? 500? Алгоритм с квадратичной зависимостью на 10 строках будет иметь 100 итераций, а на 100 - 100 тысяч. Казалось бы колоссальный рост, но если выражать его в секундах - то на хорошем Xeon мы выросли с 0,0005 до 0,5 секунды - кому это будет интересно на фоне того сколько он будет проводиться? Ну документ большой, работает долго, подумаешь..

Но!

Во-первых, строк не всегда 500. Если вы имеете дело с каким-нибудь хитрым алгоритмом анализа остатков или распределения товаров, где, например, 25 тысяч товаров умножаются на 300 магазинов - строк уже не много не мало 7,5 миллионов. Каждая новая строка в таком случае будет добавлять 7,5 миллионов итераций, что уже, согласитесь существенно. Тут стоит всеми правдами и неправдами стараться перестроить алгоритм так, чтобы вместо одного вложенного цикла, дающего сложность O(n²), у нас было 2,3,4 обычных цикла, дающих сложность O(2n), O(3n), O(4n) соответственно. Как добиться такой замены - отдельный вопрос, это не всегда возможно (например пройти первый раз - построить индекс - пройти второй раз с поиском не перебором, а по индексу с логарифмической сложностью), но если возможно - делать стоит однозначно. На следующем графике приведен рост временивыполнения алгоритмов O(n), O(4n) и O(n2):

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

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

на этом графике всего лишь 5 элементов по той же причине.

На самом деле, хитрые компьютер-саенс специалисты для большинства типичных операций имеют алгоритмы лучше чем квадратичной сложности. Как правило, алгоритм обработки большого объема данных обходитя в log(n), а в некоторых случаях вообще обходится константной сложностью (это когда время выполнения вообще не зависит от объема данных). Все алгоритмы сортировки, поиска и т.п. так умеют. Достигается это иногда при помощи улучшения самого алгоритма, иногда построения хитрых индексных или хэш- таблиц, но достигается всегда. Почти ). Поэтому когда вы реализуете алгоритм, обладающий квадратичной или хуже сложностью - задумайтесь: не стоит ли его оптимизировать?

Специальные предложения

Комментарии
Избранное Подписка Сортировка: Древо
2. EVKash 3 07.10.19 16:27 Сейчас в теме
(0)
Эта тема одной из первых всплывает на собеседовании программистов языков вроде Java и C, но она почти неизвестна в "мире 1С".

Может быть потому, что основным методом получения информации в 1С является язык запросов? Оптимизировать нужно запросы. И не делать запросы в цикле. Но это как бы всем известно.
3. nomad_irk 47 07.10.19 18:04 Сейчас в теме
(2)далеко не всем и не всегда. Любое разыменование - запрос в ИБ, но кто ж об этом задумывается кода обрабатывает какие-нить документы/справочники пакетно?

По поводу статьи: имхо, в 1с со сложностью кода все сложно и просто одновременно. Если требуется сортировка какого-то большого массива данных, будет быстрее загнать этот массив данных в запрос/набор, умеющий выполнять сортировку по значению и выполнить сортировку с помощью SQL/набора, чем пытаться самому, честно, используя объектный подход, с помощью цикла(-ов) выполнять сортировку.
5. kote 506 08.10.19 08:31 Сейчас в теме
(2)
в корне неверное представление..
В языке запросов описанное тоже имеет место.. Ну например, при объединении таблиц, когда нужно получить перемножение таблиц - это полный аналог 2х циклов вложенных друг в друга..
6. nomad_irk 47 08.10.19 08:41 Сейчас в теме
(5)Может все же при соединение таблиц, а не объединении?
10. kote 506 16.10.19 10:46 Сейчас в теме
(6) Да, так будет точнее - пример приведен для соединения таблиц
4. stepan_s 08.10.19 06:18 Сейчас в теме
На сколько я понимаю - статья для того, чтоб обратить внимание на проблему обработки больших массивов данных простыми циклами?
Не уловил мысли что предлагается конкретно :( Тема верная, но какие подходы нужно выбирать?
И самое важное....
Как много ситуаций, когда на клиента приходят данные огромного объема? И эти ситуации действительно адекватны?
7. capitan 1465 09.10.19 17:37 Сейчас в теме
Поэтому когда вы реализуете алгоритм, обладающий квадратичной или хуже сложностью - задумайтесь: не стоит ли его оптимизировать?

даже люди профессионально преподающие алгоритмы спокойно к этому относятся.
Все дело в величине выборки
Т.е. в данном случае оценивается величина выборки/сложность алгоритма
Выборок действительно большого объема в 1С не так уж и много, тем более требующих самостоятельной реализации сортировки
Это хорошо для модной темы биг дата.
А в 1С обычно решение нужно вчера, поэтому если вы его сделаете на простейшем алгоритме сегодня, а не на супер навороченном через месяц - все вас от этого прославят в веках
И как правило не бывает ничего бесплатного - более быстрый алгоритм требует больших ресурсов и наоборот
Артано; +1 Ответить
9. Артано 666 11.10.19 17:43 Сейчас в теме
(7) Практически снято с языка. Добавлю только, что алгоритмы для обработки больших массивов данных это зачастую штучная работа, и в любом случае должно быть деление для условных алгоритмов сортировки на две категории:

1. Сортировать();
2. СортироватьМногоДанных();
8. kuzyara 924 11.10.19 10:52 Сейчас в теме
Полезней было бы привести примеры расчета O для запросов.
11. Pixar0000 18.10.19 15:00 Сейчас в теме
аффтору просто стоит "вспомнить" первый курс института, курс прикладная математика, если филолог то, соррян
Оставьте свое сообщение

См. также

Программная работа с настройками СКД

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

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

27.01.2020    5259    ids79    25       

Базовый курс по обмену данными в системе 1С:Предприятие. Онлайн-интенсив с 12 по 28 мая 2020 г. Промо

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

5500 рублей

[СКД] Программное создание схемы компоновки данных

Статья Программист Стажер Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

Сделаем отчет на СКД полностью программно, без использования макета "схема компоновки данных".

15.01.2020    7238    John_d    21       

30 задач. Странных и не очень

Статья Программист Стажер Нет файла v8 Бесплатно (free) Практика программирования

30 задач на знание языка программирования 1С и некоторого поведения платформы. Маленьких. Странных и не очень.

02.12.2019    9223    YPermitin    72       

1C:Предприятие для программистов: Расчетные задачи (зарплата). Онлайн-интенсив с 01 по 17 июня 2020 г. Промо

Данный онлайн-курс предусматривает изучение механизмов платформы “1С:Предприятие”, которые предназначены для автоматизации периодических расчетов, а именно - для расчета зарплаты. Курс предназначен для тех, кто уже имеет определенные навыки конфигурирования и программирования в системе “1С:Предприятие”, а также для опытных пользователей прикладного решения “1С:Зарплата и управление персоналом” и прочих прикладных решений, в которых реализован функционал расчета зарплаты.

4900 рублей

Программы для исполнения 488-ФЗ: Маркировка товаров Промо

1 января 2019 года вступил в силу ФЗ от 25.12.2018 № 488-ФЗ о единой информационной системе маркировки товаров с использованием контрольных (идентификационных) знаков, который позволяет проследить движение товара от производителя до конечного потребителя. Инфостарт предлагает подборку программ, связанных с применением 488-ФЗ и маркировкой товаров.

Агрегатные функции СКД, о которых мало кто знает

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

Пользуетесь ли Вы всеми возможными агрегатными функциями, которые предоставляет система компоновки данных? Если Вы используете только: СУММА, КОЛИЧЕСТВО, МИНИМУМ, МАКСИМУМ, СРЕДНЕЕ, то эта статья для Вас.

05.09.2019    23875    ids79    45       

Онлайн-курс "Подготовка к экзамену 1С:Эксперт и 1С:Профессионал по технологическим вопросам" с 7 по 24 апреля 2020 г. Промо

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

16450 рублей

Три костыля. Сказ про фокусы в коде

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования

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

03.09.2019    15436    YPermitin    75       

Отслеживание выполнения фонового задания

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования Универсальные функции Разработка

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

17.08.2019    18161    ids79    16       

Базовый курс по управлению ИТ-проектами. Курс проходит с 26 февраля по 22 апреля 2020 года. Промо

Отличительная черта курса - органичное сочетание трех вещей: 1.Теория проектного управления (PMI®+Agile Alliance+Российские ГОСТ+Методологии от 1С); 2. Опыт внедрения продуктов 1С (опыт франчайзи и успешных компаний + тренды Infostart Event и Agile Days); 3. Разбор реальных проблем и рекомендации экспертов по проектам слушателей. Мы будем фиксироваться на тех инструментах, которые реально оказываются полезными в практике руководителей проектов внедрения. Ведущая курса - Мария Темчина.

от 11000 рублей

Функции СКД: ВычислитьВыражение, ВычислитьВыражениеСГруппировкойМассив

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

Подробное описание и использование внутренних функций системы компоновки данных: Вычислить, ВычислитьВыражение, ВычислитьВыражениеСГруппировкойМассив, ВычислитьВыражениеСГруппировкойТаблицаЗначений.

08.08.2019    32895    ids79    36       

Фоновое выполнение кода в 1С - это просто

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования

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

02.08.2019    18239    avalakh    21       

INFOSTART MEETUP Kazan. 13 марта 2020 г. Промо

Инфостарт продолжает путешествие по России. Следующая остановка - Казань. Тема мероприятия - управление и технологии автоматизации учета на платформе "1С: Предприятие". Ждем всех: докладчиков и участников! Стоимость участия - 5 500 рублей. Цена действительна до 30.01.2020

5 500

СКД - наборы данных и связи между ними, создание собственной иерархии, вложенные отчеты

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

Набор данных объект. Использование в схеме компоновки нескольких наборов данных. Различные варианты связи наборов: объединение, соединение. Использование иерархии в отчетах на СКД. Создание собственной иерархии, иерархия детальных записей. Использование вложенных схем в отчетах на СКД.

26.07.2019    26895    ids79    9       

Сдача регламентированной отчетности из программ 1С Промо

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

от 1500 руб.

Управление качеством кода

Статья Программист Руководитель проекта Нет файла v8 Бесплатно (free) Математика и алгоритмы Рефакторинг и качество кода

О SonarQube, АПК, EDT. Какие преимущества дает их использование. Для каких команд подходит.

22.07.2019    11553    Stepa86    33       

СКД - использование расширений языка запросов, секция ХАРАКТЕРИСТИКИ

Статья Программист Нет файла v8 v8::СКД Бесплатно (free) Инструментарий разработчика Практика программирования

Автоматическое и не автоматическое заполнение полей компоновки данных. Использование расширений языка запросов для СКД «{…}», секция ВЫБРАТЬ, секция ГДЕ, параметры виртуальных таблиц. Автоматизированное использование дополнительных данных в запросе: секция ХАРАКТЕРИСТИКИ.

17.07.2019    19473    ids79    27       

Программы для исполнения 54-ФЗ Промо

С 01.02.2017 контрольно-кассовая техника должна отправлять электронные версии чеков оператору фискальных данных - правила установлены в 54-ФЗ ст.2 п.2. Инфостарт предлагает подборку программ, связанных с применением 54-ФЗ, ККТ и электронных чеков.

Регистры сведений. За кулисами

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования Разработка

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

09.07.2019    14742    YPermitin    12       

"Меньше копипаста!", или как Вася универсальную процедуру писал

Статья Программист Стажер Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования Разработка

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

04.07.2019    12030    SeiOkami    49       

Голосование за доклады на INFOSTART MEETUP Kazan - до 25 февраля. Промо

Выбирайте и голосуйте за самые интересные доклады! Лучшие из лучших попадут в окончательную программу казанского митапа. Оставить свой голос можно до 25 февраля 2020 года.

Создание отчетов с помощью СКД - основные понятия и элементы

Статья Программист Нет файла v8 v8::СКД Бесплатно (free) Практика программирования Математика и алгоритмы

Основные принципы работы СКД. Понятия схемы компоновки и макета компоновки. Описание основных элементов схемы компоновки: наборы данных, поля, вычисляемые поля, ресурсы, параметры.

25.06.2019    31554    ids79    17       

Многопоточное ускорение однопользовательских нагрузок в 1С + Microsoft SQL Server 2017

Статья Программист Нет файла v8 v8::Запросы Бесплатно (free) Практика программирования Разработка

Взаимодействие с Microsoft SQL Server нередко вызывает трудности у 1С-ников, а потому интересны любые моменты, связанные с его использованием. О своем опыте работы с новым SQL Server 2017 участникам конференции Infostart-2018 рассказал директор ООО «Аналитика софт» Дмитрий Дудин.

11.06.2019    16848    dmurk    144       

Подборка программ для взаимодействия с ЕГАИС Промо

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

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

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования Разработка

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

16.05.2019    27089    YPermitin    27       

Выполнение внешней обработки в фоновом задании

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования Разработка

Подробное описание подхода к созданию длительной операции на основе внешней обработки. Реализация протестирована на 1С 8.3.12.1714 (x64).

11.05.2019    17188    Eret1k    23       

Управление ИТ-проектами. Модуль 2: продвинутый онлайн-курс по классическим методам управления проектами. Вебинары проходят с 12 марта по 11 июня 2020 года. Промо

Продвинутый онлайн-курс по классическому управлению ИТ-проектами позволит слушателям освоить инструменты из PMBoK® и 1С:Технологии корпоративного внедрения и научиться их применять для проектов любого масштаба. Курс включает в себя 12 вебинаров и 12 видеолекции, разбор кейсов и рекомендации экспертов по проектам слушателей. Ведущая курса - Мария Темчина.

от 13000 рублей

Выгрузка документа по условию

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Разработка

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

25.04.2019    9259    m-rv    2       

Как прикрутить ГУИД к регистру сведений

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Перенос данных из 1C8 в 1C8 Разработка

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

16.04.2019    12376    m-rv    16       

​​​​​​​CorelDRAW Graphics Suite 2019 Промо

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

О расширениях замолвите слово...

Статья Программист Стажер Нет файла v8 Бесплатно (free) Практика программирования Разработка

О чём стоит задуматься при принятии решения о создании расширения конфигурации…

07.04.2019    23293    ellavs    125       

Git-репозитории для 1С-кода (опыт использования при небольших проектах)

Статья Программист Стажер Нет файла v8 Windows Бесплатно (free) Практика программирования Разработка

Инструкции по взаимодействию с Git-репозиторием, которые писались для тех наших программистов, которые вообще никогда не работали с Git (руководства в духе "Как получить код из git-репозитория?", "Как отправить код в git-репозиторий")...

28.03.2019    18480    ellavs    83