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

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

Порядок функций и обозначение Big-O

Обещаю, что лекции в университете будут краткими. Когда мы говорим о том, как работает алгоритм, мы часто говорим о «порядке» функции, который мы выражаем в нотации «большой О». Big-O не так сложен, как может показаться. Он просто описывает, как конкретное измерение производительности, такое как время выполнения или потребление памяти, изменяется по мере увеличения размера набора данных. Это легче понять на примере.

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

..или, если вы предпочитаете функциональный подход:

В любом случае эти подпрограммы выполняют console.log () один раз для каждого элемента в массиве, всего 1000 раз. Если мы добавим к набору данных еще 9 000 строк, он выполнит console.log () 10 000 раз. Время, необходимое для выполнения этого алгоритма, линейно растет по мере роста набора данных. В нотации Big-O мы описываем эту функцию как O (n).

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

Когда этот алгоритм работает с нашим набором данных из 1000 элементов, он выполняет внутренний цикл 1000 раз для каждого элемента в массиве, или 1000 * 1000 раз, или 1000², всего 1000000 раз. Если наш набор данных вырастет до 10 000 строк, он будет выполнен 10 000² или 100 000 000 раз. В этом случае время выполнения растет пропорционально квадрату размера набора данных, или O (n²).

Приведенный выше алгоритм написан плохо, чтобы дать простой пример для иллюстрации алгоритма O (n²). Если мы пытаемся определить, есть ли дубликаты в наборе данных, нам не обязательно проходить через весь набор данных. Мы можем замкнуть внутренний цикл, как только найдем первое совпадение. Однако для целей анализа производительности мы хотим оценить наихудший сценарий, например искомый элемент находится в конце набора данных. Так что даже если мы переписали алгоритм следующим образом:

… Мы по-прежнему рассматриваем этот алгоритм как O (n²).

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

… Второй алгоритм печатает каждый элемент дважды. Учитывая, что печать элемента занимает некоторое время, вы можете сравнить эти два алгоритма как O (n) для первого и O (2n) для второго - выполнение второго алгоритма занимает в два раза больше времени, чем первого. Хотя верно, что второй алгоритм будет медленнее, чем первый алгоритм, по сравнению с алгоритмом O (n²) этот объем работы становится незначительным, поэтому второй алгоритм все равно будет считаться алгоритмом O (n).

Теперь у нас достаточно инфраструктуры, чтобы провести базовый анализ и сравнение. Алгоритм O (n) (простой цикл) будет более эффективен при выполнении своей задачи, чем алгоритм O (n²) (вложенный цикл), который будет более эффективным, чем алгоритм O (n³) и т. Д.

А теперь по делу ...

Я уверен, что вы думаете: «Эй, это должно было быть о чем-то, что называется Шаблон словаря». Это. В частности, речь идет о том, как идентифицировать алгоритмы O (n²) в вашем коде и как вы можете применить этот шаблон для их оптимизации.

Раньше, до HTML5, я был разработчиком Adobe Flex. У Flex была структура данных, называемая словарем - в основном это было хранилище ключей / значений. Ключи существуют только один раз, и каждый ключ имеет произвольное значение, которое можно получить, используя его ключ. Ключевая особенность, которую следует понять в контексте этой статьи, заключается в том, что получение значения по его ключу является операцией O (1) - независимо от того, сколько ключей и значений находится в словаре, получение значения по ключу занимает одинаковое количество времени. .

Я также кодирую на Java, который имеет гораздо более богатый набор структур данных, чем Javascript. Два из них, в частности, похожи на тип словаря Flex. HashMap фактически является однозначным эквивалентом. В нем хранится ключ и связанное с ним значение. Set больше похож на массив, в котором элемент может существовать только один раз. Его отношение к словарю Flex или Java HashMap заключается в том, что его можно рассматривать как структуру ключ / значение, которая содержит только ключи или где ключ и значение являются одним и тем же объектом.

В Javascript у нас нет этих структур данных, но у нас есть анонимные объекты, к которым мы можем прикреплять произвольные свойства. Мы можем использовать анонимные объекты для имитации HashMap или Set, а затем мы можем использовать эти структуры данных для оптимизации алгоритмов O (n²).

Вспомните пример, в котором мы искали дубликаты в нашем наборе данных:

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

Эта процедура просматривает наш набор данных, создает ключ / значение для элемента, если он не существует на карте, а затем увеличивает значение. Когда он завершит выполнение, карта будет содержать ключ для каждой строки в наборе данных, значение которой - это количество раз, которое она встречается в наборе. Важно понимать, что мы взяли алгоритм O (n²) и преобразовали его в алгоритм O (n). По мере роста набора данных время, необходимое для обработки, увеличивается линейно, а не пропорционально квадрату размера набора данных, потому что мы можем получить доступ к счетчику для каждого элемента, используя поиск O (1) вместо того, чтобы повторять цикл по набору данных повторно и подсчет вхождений определенного значения.

Возможно, вместо количества нам просто нужен отдельный список, в котором мы извлекаем только уникальные значения в наборе данных. Мы можем подойти к этому с точки зрения Java’s Set, используя аналогичную технику:

В результате мы перебираем набор данных один раз в цикле forEach, а затем перебираем ключи набора с помощью Object.keys (). В худшем случае набор данных не содержит дубликатов, и в этом случае это алгоритм O (2n).

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

Если вы написали что-то вроде этого, чтобы искать имена клиентов для каждого счета:

это алгоритм O (n²). Он может отлично работать при разработке, когда ваш набор данных содержит только небольшое количество клиентов и счетов-фактур. Как только ваши наборы данных расширятся до тысяч клиентов и десятков тысяч счетов-фактур, производительность начнет падать.

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

Это алгоритм O (2n), который будет работать значительно лучше при увеличении размеров набора данных.

В итоге

Ищите вложенные циклы как контрольные признаки плохо масштабируемых алгоритмов. Поймите, что вложенные циклы могут скрываться в ваших конструкциях функционального программирования, таких как вызовы Array.find () внутри цикла Array.forEach ().

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