Есть тысяча способов решить проблему.

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

Решение - не всегда хорошее решение

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

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

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

Хотя в приведенных ниже примерах мы будем использовать Java, эта статья действительна для любого языка программирования. Улучшая алгоритм, лежащий в основе решения, мы можем повысить производительность приложения. Однако это говорит само за себя, насколько мы должны быть в этом крайности? Давайте погрузимся в это!

Задача: подсчет дубликатов

В этом примере мы сосредоточимся на этой кате CodeWars: подсчете дубликатов. Вот инструкции для этого ката:

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

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

Abcde - ›0 # no characters repeats more than once
'aabbcde' -› 2 # 'a' and 'b'
'aabBcde' - ›2 # 'a' occurs twice and 'b' twice (`b` and `B`)
неделимость -› 1 # 'i' occurs six times
Неделимость - ›2 # 'i' occurs seven times and 's' occurs twice
'aA11' - ›2 # 'a' and '1'
'ABBA' -› 2 # 'A' and 'B' each occur twice
 Источник: CodeWars

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

Первое решение

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

Первое решение: код

Теперь у нас есть первое рабочее решение этой проблемы! Проблема решена, все в порядке, правда? Это? Давайте на секунду задумаемся над тем, чего мы достигли. Сколько памяти мы использовали? В чем сложность этого решения? Делали ли мы ненужные действия? Давайте взглянем.

Первая мета решения: космическая сложность

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

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

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

Первая мета решения: сложность времени

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

На первый взгляд, O(n²) не очень эффективный способ вычислений, если это действительно не нужно.

Первая мета решения: ненужные вычисления

Наше решение не содержит ненужных переменных или вычислений.

Мета первого решения: заключение и мета

Наша пространственная сложность довольно хороша с O(n), но наша временная сложность O(n²) действительно невелика.

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

Второе решение

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

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

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

Пойдем и реализуем это решение!

Второе решение: код

Теперь у нас есть второе рабочее решение. Давайте еще раз поразмышляем над тем, что мы сделали в трех областях.

  1. Сложность времени
  2. Космическая сложность
  3. Ненужный код

Вторая мета решения: космическая сложность

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

Мы можем заключить, что сложность нашего пространства составляет около O(n). Не забывайте, что это оценка, поэтому, если это на 4–5 целых числа больше, мы все равно оставим O(n), поскольку оно никогда не должно достигать O(2n) или O(n²), если n не является нереально низким.

Вторая мета решения: сложность времени

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

Мы можем заключить, что это временная сложность примерно O(2n).

Вторая мета решения: ненужные вычисления

И на этот раз у нас нет ненужных переменных или вычислений.

Вторая мета решения: заключение и мета

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

Резюме и выводы

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

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

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

Комплексные решения для увеличения производительности

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

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

Другие решения

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