Przekroczenie limitu pamięci — Python

Question 1

Uruchamiam poniższy kod do pobierania indeksów dwóch liczb z listy wejściowej, których suma jest równa wartości docelowej.

import itertools

class Solution:
   def twoSum(self, nums, target):
        combs = set(itertools.combinations(enumerate(nums), 2))
        while combs:
           elem = combs.pop()
           if int(elem[0][1]) + int(elem[1][1]) == target:
               return [elem[0][0], elem[1][0]]

cls = Solution()
nums = [3,3]
lst = cls.twoSum(nums,6)
print(lst)

Działa dobrze, dopóki tablica wejściowa nie jest mała, ale kiedy rośnie do tysięcy, otrzymuję przekroczenie limitu pamięci. Uważam, że powinien istnieć inny zoptymalizowany sposób na zrobienie tego.

loops python-3.6

1

Neeraj Sharma 19 listopad 2018, 14:47

Answer

Cóż, ponieważ nie możemy mieć tablicy/kolejnych bloków pamięci więcej niż 10^6 lub 10^7

Jeśli mamy wielowymiarowy rozmiar tablicy zmniejszy się do Matrix[1000][1000], aby uzyskać łącznie ~10^7 bloków

Itertools generują wszystkie możliwe pary, które mogą być wykładnicze, a przechowywanie ich w zestawie z pewnością przepełni się zarówno w czasie, jak i przestrzeni.

Rozwiązaniem byłoby więc ulepszenie algorytmu zarówno pod względem złożoności czasowej, jak i pamięciowej.

Jednym ze sposobów rozwiązania tego problemu jest haszowanie,

Podstawowa idea to A + B = target, gdzie A,B to elementy tablicy

Więc utrzymujemy tablicę haszującą z kluczem = element i wartością = indeks

I iterujemy, aby znaleźć, czy B = cel - A, jest obecny w tablicy, jeśli zostanie znaleziony, wypisujemy indeks (A,B)

class Solution:
    def twoSum(self, nums, target):
        hashtable = dict() # key = number , value = index
        n = len(nums)
        lst = []
       for i in range(n):

           if(hashtable.get(target-nums[i],None) is None):
           # not found so update the hashtable
               hashtable[nums[i]] = i
           else:
           # pair found
               lst.append((hashtable[target-nums[i]],i))

        return lst

cls = Solution()

nums = [3,3]
lst = cls.twoSum(nums,6)

print(lst)

0

itsjwala 19 listopad 2018, 15:27

Question 2