Действительно ли необходимы структура данных и алгоритмы?

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

Предположим, что нам нужно написать код для подсчета множителей заданного числа. Звучит довольно просто, не так ли? Запишем код:

function countFactors(N) {
  let count = 0;
  for (let i = 1; i <= N; i++) {
    if (N % i === 0) {
      count = count + 1;
    }
  }
  return count;
}

Все, что нам нужно сделать, это выполнить итерацию от 1 до N и проверить с каждым значением i, что N/i дает остаток как 0, и подсчитать те явления. Этот код отлично работает с небольшими входными данными, но что произойдет, если размер входных данных будет большим? Давайте сделаем некоторые расчеты и посмотрим, как выполняется этот код.

Предположим, что 1 операция = 1/10⁸ с, и допустим, что цикл выполняет 1 операцию (предположение для простоты).

Возьмем N = 10⁹ N операций = 10⁹ * 1 / 10⁸ сек = 10 сек

Let us take N = 10⁹
operations = 10⁹ * 1 / 10⁸ sec 
           = 10 sec

Выглядит неплохо, правда? теперь давайте увеличим значение N

Let us take N = 10¹⁸ 

N operations = 10¹⁸ * 1/10⁸ sec 
             = 10¹⁰ sec 

Let's calculate in terms of years 

1 day = 86400 sec 
1 year = 365 days = 365 * 86400 sec 

Therefore, 
N operations = 10¹⁰ sec 
             = 10¹⁰ / (365 * 86400) years 
             = 317 years (approx.)

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

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

Let's get the factor for 12

1 x 12
2 x 6
3 x 4
4 x 3
6 x 2
12 x 1

I x J = N

Если мы внимательно посмотрим, мы можем сделать несколько выводов:

1. Факторы встречаются парами (пример: 2 x 6, где оба фактора являются факторами)
2. После заданной точки факторы повторяются
3. Факторы начинают повторяться, когда I больше, чем J.

Чтобы подтвердить наши выводы, давайте попробуем то же самое с другими входными данными:

I x J = N
J = N / I

For the factors to repeat I >= J

Therefore, 
   I >= J
   I >= N / I
   I x I >= N
   I >= sqrt(N)

Как видите, нам просто нужно найти множители между [1 — sqrt(N)]

Давайте напишем код с этой логикой и увидим разницу

function countFactors(N) {
  let count = 0;
  for (let i = 1; i <= Math.sqrt(N); i++) {
    if (N % i === 0) {
      if (i === Math.sqrt(N)) {
        count = count + 1;
      } else {
        count = count + 2;
      }
    }
  }
  return count;
}

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

Let us take N = 10¹⁸ 

N operations = sqrt(10¹⁸) * 1/10⁸ sec 
             = 10⁹ * 1/10⁸ sec 
             = 10 sec

Ух ты!!! Это значительное улучшение с 317 лет до 10 секунд. Теперь нам, возможно, не придется менять профессию. Это основная причина, по которой DS и Algo очень важны для эффективного написания, поскольку они могут сэкономить вам много ресурсов и времени, тем самым обеспечив вам хороший пользовательский интерфейс. Надеемся, что постановка задачи и решение были достаточно ясными, чтобы помочь вам понять использование таких методов, как DS и Algo.

Оставайтесь с нами, чтобы узнать больше о DS и Algo.

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