Фон

Прошедшая неделя была беспокойной, так как было Рождество, а это означало, что у нас было не так много времени на программирование. Хотя я физически не мог писать столько кода, сколько мне хотелось, я постоянно думал о следующих шагах для моего приложения Group Randomizer. Еще одна функция, которую я хочу добавить, - это функция фильтрации сохраненных групп при заполнении панели поиска. Например, если я наберу «Сэм» в строке поиска, появятся все сохраненные группы, в которые входит «Сэм».

Примечание. В этом блоге речь пойдет о моем мыслительном процессе, а не о реальном коде.

Мозговой штурм алгоритма фильтра

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

savedGroups = [
  {  name: "DnD Group", 
     options: ["Sam", "Bob", "Dylan", "Eva", "Dani"]
  }, 
  {  name: "Restaurants", 
     options: ["McDonalds", "Burger King", "Bareburger", "Shake Shack", "Chick-Fil-A"]
  },
  {  name: "Band",
     options: ["Sam", "Chris", "Billy", "Tabitha", "Vicky"]
  }
]

Когда я загружаю приложение, каждый элемент в savedGroups будет отображаться в свой собственный компонент и отформатирован соответствующим образом. Когда я набираю в строке поиска слово «Сэм», должны отображаться только сохраненные группы с options, которые включают «Сэм» (т.е. DnD Group и Band).

Первоначальная попытка алгоритма, назовем его алгоритмом фильтрации, скорее всего, будет использовать метод грубой силы. Это означает, что я буду перебирать каждый элемент в savedGroups и в каждом savedGroup элементе, я буду перебирать каждый элемент в массиве options. Ниже приведен псевдокод для этого метода грубой силы.

1. Initialize an empty array (call it filteredGroups)
2. Do a for loop to iterate through all elements in the savedGroups array
3. Do a second for loop, within the for loop from step #2, to iterate through all elements in the options array
4. Within the second for loop, write an if/else statement to check for the name typed in the search bar. If the name is included, push it to the filteredGroups array
5. Return the filteredGroups array

На шагах 2 и 3 создается вложенный цикл for. Поскольку первый цикл for выполняет итерацию по массиву, а второй цикл for также выполняет итерацию по массиву, временная сложность худшего случая составляет O (n²). С практической точки зрения, этого должно быть хорошо, потому что объем данных, который я изначально предполагал для запуска приложения, возможен для этой временной сложности (например, длина savedGroups и options выражается двузначными числами для наихудшего сценария).

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

Оптимизация алгоритма фильтрации

Временные сложности лучше, чем O (n²), для достаточно большого количества данных: O (1), O (log (n)), O (n) и O (n * log (n)).

Судя по моим исследованиям алгоритмов, оптимизация с O (n²) до O (n) включает преобразование одного из массивов в объект. Для алгоритма фильтрации имеет смысл преобразовать массив options в объект. Наш условный оператор основан на том, содержит ли options непосредственно имя, введенное в строке поиска. Элемент savedGroup косвенно содержит имя, но у нас нет прямого доступа к нему. Чтобы получить доступ к имени, нам в любом случае нужно будет пройти через options.

В идеале массив savedGroups теперь должен выглядеть следующим образом:

savedGroups = [
  {  name: "DnD Group", 
     options: {
       "Sam": true,
       "Bob": true,
       "Dylan": true,
       "Eva": true,
       "Dani": true 
     }
  }, 
  {  name: "Restaurants", 
     options: {
       "McDonalds": true, 
       "Burger King": true,
       "Bareburger": true,
       "Shake Shack": true, 
       "Chick-Fil-A": true
     }
  },
  {  name: "Band",
     options: {
       "Sam": true,
       "Chris": true,
       "Billy": true,
       "Tabitha": true,
       "Vicky": true
     } 
  }
]

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

С новой структурой savedGroups псевдокод должен быть похож на наш первый псевдокод.

1. Initialize an empty array (call it filteredGroups)
2. Do a for loop to iterate through all elements in the savedGroups array
3. In the for loop from step #2, write an if/else statement to check the name typed in the search bar to see if it is in the options object. If it is, push the savedGroup into the filteredGroups array.
4. Return the filteredGroups array

Мы смогли убрать шаг в псевдокоде! Общая временная сложность этого теперь составляет O (n). Почему?

На шаге 2 мы выполняем итерацию по всей длине массива savedGroups, что составляет временную сложность O (n). На шаге 3 мы проверяем, есть ли имя в объекте options. Простой способ проверить это - получить доступ к имени в самом объекте options (т. Е. options[searchName]). Временная сложность доступа к объекту составляет O (1). Поскольку шаг 3 находится внутри шага 2 цикла for, общая временная сложность составляет O (n) умножить на O (1), что составляет O (n)!

Последствия оптимизации объекта

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

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

Что, если уже существуют другие функции, которые зависят от структуры данных options как массива вместо объекта?

Когда я впервые осознал последствия изменения структуры данных, у меня был один из двух вариантов:

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

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

Рекурсивная оптимизация

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

Я хочу сохранить структуру данных в виде массивов как для savedGroups, так и для options. Кажется, мне все равно нужно будет перебирать каждый элемент в массиве saveGroups, что означает, что часть оптимизации нужно будет учитывать при итерации по массиву options. Итерирование каждого элемента в массиве options приводит к временной сложности O (n²), что неэффективно, как объяснялось в предыдущем разделе этого блога, и изменение структуры данных options с массива на объект нецелесообразно, поскольку мы хотите сохранить структуру данных как есть.

Хм ... что, если мы посмотрим на options блоков массива за раз? Как бинарный поиск? Бинарный поиск изначально имеет временную сложность O (log (n)) и использует рекурсию как основу своей реализации. Следующий псевдокод будет выглядеть следующим образом:

1. Create a binary recursive search function. This binary recursive search function is outside the scope of the filter algorithm
2. Initialize an empty array (call it filteredGroups)
3. Do a for loop to iterate through all elements in the savedGroups array
4. In the for loop from step #2, invoke the binary recursive search function from step #1
5. Return the filteredGroups array

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

Давайте посмотрим на временную сложность. И снова мы перебираем весь массив массива savedGroups, поэтому временная сложность для этого составляет O (n). При итерации по каждому элементу savedGroup вызывается двоичная рекурсивная функция. Я не знаю точных деталей самой бинарной рекурсивной функции, но обычно предполагаю, что это O (log (n)). Мне нужно будет дважды проверить это предположение после создания этой функции. Шаг 4 находится в цикле for из шага 3, поэтому временная сложность составляет O (n) * O (log (n)), что составляет O (n * log (n)).

Это все еще лучше, чем наша предыдущая временная сложность O (n²)!

Последствия рекурсивной оптимизации.

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

  1. Временная сложность O (log (n)). Предполагается, что весь код в бинарной рекурсивной функции равен O (1).
  2. Массив options предварительно сортируется при вызове двоичной рекурсивной функции.

Первое, что я могу придумать для предварительной сортировки options, - это использовать .sort. Однако .sort в худшем случае имеет временную сложность O (n²). Использование метода с той же временной сложностью, что и мы пытаемся оптимизировать, не оправдывает цели оптимизации.

Итак, как мы можем отсортировать массив options без использования .sort? Хм… Для приложения массив options заполняется всякий раз, когда пользователь отправляет опцию.

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

Что, если бы существовал способ сортировки массива options после каждой отправки варианта пользователем? Если бы такой способ был, когда пользователь сохраняет этот список опций в массив savedGroups, список опций или options уже будет отсортирован перед вызовом алгоритма фильтрации. Это потребует создания нового алгоритма сортировки, в идеале с временной сложностью лучше, чем O (n²).

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

Ключевые выводы

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