Избегайте дублирования вычислений, чтобы оптимизировать временную сложность вложенного цикла for - PullRequest
Новая
       9

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

0 голосов
/ 27 ноября 2018

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

Позвольте мне наглядно показать вам, что происходит. К тому времени, как я закончу, мой пример кода будет очень далеко внизу!

Код берет первое число в массиве чисел и добавляет его ккаждое последующее число и проверяет, делится ли оно на k = 3.

В массиве из 6 чисел, что равняется 15 циклам, что будет O(n²), что означает, что мои циклы будут расти в геометрической прогрессии до величинывход.7 чисел будет 21 петлей.

PS, вы можете подумать, что 6 должно быть 21 петлей, а 7 должно быть 28, но имейте в виду, что я всегда беру текущий номер и добавляю его кдалее, за исключением последнего номера.

Визуальная разбивка

input: [1, 3, 2, 6, 1, 2]

  • 1 + 3, 1 + 2 ,1 + 6, 1 + 1, 1 + 2
  • 3 + 2, 3 + 6 , 3 + 1 , 3 + 2
  • 2 + 6, 2 + 1 , 2 + 2
  • 6 + 1 , 6 + 2
  • 1 + 2

Объяснение

Если вы посмотрите на числа, которые я ввел жирным шрифтом , вы увидите, что они являются дублирующими вычислениями.Числа курсив - это числа, кратные k = 3.Теперь мы подходим к моему мясу моего вопроса.Как я могу устранить эту повторяющуюся математику, которая снизит количество циклов с 15 до 8 в этом конкретном примере.Алгоритм все равно имел бы худший сценарий O(n²), если бы все числа были разными, но, тем не менее, это была бы оптимизация.

Демонстрация кода 

function divisibleSumPairs(k, a) {
  let pairs = 0;
  for (let i = 0; i < a.length - 1; i++) {
    for (let j = i + 1; j < a.length; j++) {
      if ((a[i] + a[j])/k % 1 === 0) pairs++;
    }
  }
  console.log(pairs);
}

divisibleSumPairs(3, [ 1, 3, 2, 6, 1, 2 ])

Ответы [ 2 ]

0 голосов
/ 27 ноября 2018

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

Тогда я подумал: «Что, если вместо этого я предварительно обработаю делитель»?

Недостатком этого подхода является то, что он создает и массив равного размера с делителем, но делает это в O(n) сложности времени (сложность винтового пространства, смеется)

Для этого конкретного примера у нас есть 3 цикла для делителя и 6 циклов для вычисления, всего 9 циклов, что экономит 6 циклов по сравнению с исходным решением,и исключение O(n²).

Это приводит к тому, что моя функция имеет общую временную сложность O(n)

function divisibleSumPairs(k, a) {
  const mod = new Array(k).fill(0);
  let pairs = 0;
  
  for (let i = 0; i < a.length; i++) {
      const position = a[i] % k;
      
      pairs += mod[(k - position) % k];
      mod[position]++;
  }
  
  console.log(pairs);
}

divisibleSumPairs(3, [ 1, 3, 2, 6, 1, 2 ])

Тестирование производительности

Я провел несколько итераций своего кода через тест производительности, я был удивлен, увидев, насколько лучше простой цикл for по сравнениюforEach и reduce.

  1. for^2: исходный код
  2. for: код в этом сообщении
  3. forEach:этот пост, используя forEach вместо
  4. reduce: этот пост, используя reduce вместо

https://jsperf.com/for-2-vs-for-vs-foreach-vs-reduce/1

0 голосов
/ 27 ноября 2018

Чтобы решить эту динамическую проблему

Попробуйте сохранить результат в Object скажем, sum_map, если найден, это означает, что мы уже вычислили эту сумму, если не рассчитать сумму, и сохраняем результат в карте дляссылка на будущее.

образец фрагмента: 

let d = [1, 3, 2, 6, 1, 2]

const len = d.length

const sum_map = {}

let pairs = 0

for (let i = 0; i < d.length - 1; i++) {
  for (let j = i + 1; j < d.length; j++) {
    const key1 = `${d[i]}_${d[j]}`
    const key2 = `${d[j]}_${d[i]}`
    let result = 0
    if (sum_map[key1]) {
      result = sum_map[key1]
    } else if (sum_map[key2]) {
      result = sum_map[key2]
    } else {
      result = d[j] + d[i]
      sum_map[`${d[i]}_${d[j]}`] = result
    }
    if (result % 3 === 0) {
      pairs += 1
    }
  }
}
console.log(pairs)

Чтобы избежать O (n ^ 2), нужно просто уловить, что

Пример

допустим, число, с которым вы проверяете, равно 5 и arr = [1,3,2,6,1,2,5]

  1. вы найдете суммы, кратные числу, только если его числа дополняют остаток

, как, например, пара чисел, делимая на 5, это только те, которые дают остаток комплимента, т.е. 3 % 5 = 2 и 2 % 5 = 3, поэтому сумма будет делиться на 5

так что для решения этой проблемы просто найдите остатки комплимента и выберите из них

, например, скажем, что вы 3 числа, дающие остаток 2, и 4 числа, дающие остаток 3

, поэтому пары выберут 1 из этих 3 чисел *выберите 1 из этих 4 чисел

если число делится на 5, но если его только 1, то его сумма никогда не будет делиться.

фрагмент кода: 

let d = [1, 3, 2, 6, 1, 2, 5]

const check_div_num = 5

remainder_map = {}

mod_arr = d.map((i) =>{
  const rem = i % 5
  if(remainder_map[rem]) {
    remainder_map[rem] += 1
  } else {
    remainder_map[rem] = 1
  }
  return rem
})

const till = Math.floor(check_div_num / 2)

keys = Object.keys(remainder_map)


let pairs = 0

for (let j = 0; j < keys.length; j++) {
  const key = keys[j]
  if(key === '0' && remainder_map["0"] > 1) {
    pairs += remainder_map[key] / 2
    continue
  }
  if(Number(key) <= till) {
    let compliment = remainder_map[check_div_num - Number(key)]
    const compliemnt_key = check_div_num - Number(key)
    if(compliment) {
      pairs += remainder_map[key]*remainder_map[compliemnt_key.toString()]
    } else {
      continue
    }
  } else {
    break
  }
}
console.log(pairs)

учти, я повторяюсь только до половиныиз 5 т.е. Math.floor (5/2), так как мы уже проверяем их комплимент

...