Производительность решения (DP, hashtable) для равных подмножеств суммы разделов

Question

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

Вопрос в следующем: Учитывая непустой массив, содержащий только положительные целые числа, найдите, может ли массивразделить на два подмножества так, чтобы сумма элементов в обоих подмножествах была равна. https://leetcode.com/problems/partition-equal-subset-sum/

т.е. [1, 5, 11, 5] = True, [1, 5, 9] =Неверно

Решая эту проблему, я попробовал 3 подхода:

• Подход 1: Динамическое программирование.Сверху вниз рекурсия + запоминание (Результат: Превышен лимит времени ):

  def canPartition(nums):
      total, n = sum(nums), len(nums)
      if total & 1 == 1: return False
      half = total >> 1
      mem = [[0 for _ in range(half)] for _ in range(n)]
      def dp(n, half, mem):
          if half == 0: return True
          if n == -1: return False
          if mem[n - 1][half - 1]: return mem[n - 1][half - 1]
          mem[n - 1][half - 1] = dp(n - 1, half, mem) or dp(n - 1, half - nums[n - 1], mem)
          return mem[n - 1][half - 1]
      return dp(n - 1, half, mem)
  

• Подход 2: Динамическое программирование.Вверх дном.(Результат: 2208 мс Принято ):

  def canPartition(self, nums):
      total, n = sum(nums), len(nums)
      if total & 1 == 1: return False
      half = total >> 1
      matrix = [[0 for _ in range(half + 1)] for _ in range(n)]
      for i in range(n):
          for j in range(1, half + 1):
              if i == 0: 
                  if j >= nums[i]: matrix[i][j] = nums[i]
                  else: matrix[i][j] = 0
              else:
                  if j >= nums[i]:
                      matrix[i][j] = max(matrix[i - 1][j], nums[i] + matrix[i - 1][j - nums[i]])
                  else: matrix[i][j] = matrix[i - 1][j]
              if matrix[i][j] == half: return True
      return False
  

• Подход 3: HashTable (Dict).Результат ( 172 мс Принято ):

  def canPartition(self, nums):
      total = sum(nums)
      if total & 1 == 0:
          half = total >> 1
          cur = {0}
          for number in nums:
              cur |= { number + x for x in cur} # update the dictionary (hashtable) if key doesn't exist
              if half in cur: return True
      return False
  

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

• Я ожидал бы, что подход 1 и подход 2 должен иметь тот же результат .И то, и другое использует таблицу (матрицу) для записи вычисленного состояния, но почему подход «снизу вверх» быстрее?
• Я не знаю, почему подход 3 намного быстрее по сравнению с другими.Примечание: на первый взгляд подход 3 кажется подходом от 2 до N-й степени, но он использует словарь для отбрасывания дублирующегося значения, поэтому временная сложность должна составлять T (n * half) .

Answer 1

Вы правы, подход 1) и 3) имеют одинаковую сложность по времени, подход 2 - версия рюкзака DP (0/1), подход 1 - версия ветвления и ограничения.Вы можете улучшить первый подход, обрезав дерево с помощью любой эвристики ранца, но оптимизация должна быть строгой, например, если существующая сумма и сумма оставшихся элементов на уровне K меньше половины, пропустите ее.Этот способ подхода 1) может иметь лучшую вычислительную сложность, чем 3).

Почему у подхода 1) и 3) разное время выполнения,

[ В некоторой степени ]

Это больше связано с реализацией словарей в python.Словари изначально реализованы интерпретатором Python, любая операция над ними будет выполняться быстрее, чем все, что нужно интерпретировать в первую очередь и чаще.Кроме того, вызовы функций имеют больше накладных расходов в Python, они являются объектами.Таким образом, вызов one - это не просто увеличение стека и операция jmp / call.

[ В значительной степени ]

Еще одним аспектом, который стоит обдумать, является временная сложность третьего подхода.Для подхода 3 единственная сложность времени может быть экспоненциальной, если каждая итерация приводит к вставке столько слов, сколько имеется в словаре для текущей итерации.

  cur |= { number + x for x in cur}

Приведенная выше строка должна удвоиться |cur |.

Я думаю, что это возможно для таких серий, как,

s = {k, K ² , K ³ , ..., k ⁿ , (> K ^{n + 1} )}

(где K - простое число> 2), чтобы датьнаихудшее время порядка 2 ⁿ для подхода 3. Еще не уверен, какова средняя ожидаемая сложность времени.

Answer 2

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

Подход3 зависит исключительно от количества элементов ввода и количества сумм, которые могут быть сгенерированы.На каждой итерации он добавляет текущий номер на входе ко всем ранее достижимым числам, добавляя только новые в этот список.Например, учитывая список [50000, 50000, 50000], подход 3 будет повторять не более трех сумм: 50000, 100000 и 150000. Но поскольку это зависит от диапазона, подход 2 будет повторяться не менее 75000 * 3 раза!

Учитывая список [50000, 50000, 50000], подходы 1, 2 и 3 генерируют следующее число итераций: 15, 225000 и 6.