Jak utworzyć listę, która przekracza maksymalny rozmiar w Pythonie

Question

Według this, maksymalny rozmiar listy Pythona na systemie 32 bitowym jest 536,870,912 elementy.

Czy istnieje sposób na zainicjowanie listy o większym rozmiarze?

Powiedzmy:

list1 = [None]*1000000000 

Answer 1

Listy że duża zajęłoby ogromną ilość miejsca, a każdy element na liście zajmie co najmniej 4 bajty, więc tylko jedną listę z maksymalnych dopuszczalnych elementów zajęłoby minimum 2 GB pamięci RAM: . I to bez uwzględniania systemów 64-bitowych .

1. 4 * 5.4e+8 = 2.1e+9, 2,1 GB
2. 8 * 1.2e+18 = 9.2+18, 9,2 EB (tak, eksabajty)

Jednak przez wzgląd na pytanie, załóżmy, że masz dużo pamięci RAM.

---

Jedną z najprostszych opcji byłoby stworzenie własnego obiektu do przechowywania i obsługi ogromnej listy. Zasadniczo podzieliłby ogromną listę na mniejsze listy, a następnie uzyskałby do nich odpowiedni dostęp w razie potrzeby. Ponieważ istnieje no real benefits of subclassing list, ponieważ i tak musiałbyś przerobić wszystkie metody, lepiej byłoby po prostu podklasować object, a następnie przejść z tego miejsca. Jedyną rzeczą, która jest tutaj niezbędna, jest to, aby nigdy nie łączyć ani nie kopiować podkatalogów (ponieważ są one ogromne), więc użyj itertools.chain, aby zapętlić listy, gdy jest to konieczne.

Oto przykład z najprostszych lista-metodami append, extend, get/setitem robocze:

import sys 
from itertools import chain 

class largeList(object): 
    def __init__(self, mylist=[]): 
     self.maxSize = sys.maxsize/4 
     self.src = [[]] 
     self.extend(mylist) 

    def __iter__(self): 
     return chain(*self.src) 

    def __getitem__(self, idx): 
     return self.src[int(idx/self.maxSize)][idx%self.maxSize] 

    def __setitem__(self, idx, item): 
     self.src[int(idx/self.maxSize)][idx%self.maxSize] = item 
     # expand set/getitem to support negative indexing. 

    def append(self, item): 
     if len(self.src[-1]) < self.maxSize: 
      self.src[-1].append(item) 
     else: 
      self.src.append([item]) 

    def extend(self, items): 
     remainder = self.maxSize - len(self.src[-1]) 
     self.src[-1].extend(items[:remainder]) 
     for i in xrange(0, len(items[remainder:]), self.maxSize): 
      self.src.append(items[remainder:][i:i+self.maxSize]) 

    def __len__(self): 
     return sum(len(l) for l in self.src) 

    def __str__(self): 
     size = self.__len__() 
     if size >= 8: 
      first, last = [], [] 
      for i, ele in enumerate(self.__iter__()): 
       if i < 3: 
        first.append(ele) 
       if i >= size - 3: 
        last.append(ele) 
      return str(first)[:-1] + ', ..., ' + str(last)[1:] 
     return str(list(self.__iter__())) 

Przykład użycia (jeśli masz mniej niż 4 GB wolnej pamięci RAM lub jesteś na systemie 64-bitowym zmień sys.maxsize przed próbą tego):

#sys.maxsize = 1000 

list1 = largeList(xrange(sys.maxsize/4 + 2)) 
print len(list1) 
# 53687093 
print list1 
#[0, 1, 2, ..., 536870910, 536870911, 536870912] 
print list1.src 
#[[0, 1, 2 ..., 536870910], [536870911, 536870912]] 
list1.extend([42, 43]) 
print list1 
#[0, 1, 2, ..., 536870912, 42, 43] 

rezultat: wewnętrznie wykazy są podzielone na wiele list, a oni wydają się być ju st jeden podczas pracy z nimi. Więcej funkcji można łatwo dodać, dodając więcej metod. Na przykład. pop, remove, insert i index:

(...) 

    def pop(self, idx): 
     listidx = int(idx/self.maxSize) 
     itempopped = self.src[listidx].pop(idx%self.maxSize) 
     for i in xrange(listidx, len(self.src)-1): 
      self.src[i].append(self.src[i+1].pop(0)) 
     if not self.src[-1]: 
      del self.src[-1] 
     return itempopped 

    def remove(self, item): 
     for i, ele in enumerate(self.__iter__()): 
      if ele == item: 
       self.pop(i) 
       break 

    def insert(self, idx, item): 
     listidx = int(idx/self.maxSize) 
     itemtoshift = self.src[listidx].pop(-1) 
     self.src[listidx].insert(idx%self.maxSize, item) 
     for i in xrange(listidx+1, len(self.src)-1): 
      itemremoved = self.src[i].pop(-1) 
      self.src[i].insert(0, itemtoshift) 
      itemtoshift = itemremoved 
     if len(self.src[-1]) < self.maxSize: 
      self.src[-1].insert(0, itemtoshift) 
     else: 
      self.src.append([self.src[-1].pop(-1)]) 
      self.src[-2].insert(0, itemtoshift) 

    def index(self, item): 
     for i, ele in enumerate(self.__iter__()): 
      if ele == item: 
       return i 
     return -1 

Przykład wykorzystania, kontynuował:

#sys.maxsize = 1000 

list1 = largeList(xrange(sys.maxsize/4 + 2)) 
list1.insert(0, 'a') 
print list1 
#['a', 0, 1, ..., 536870910, 536870911, 536870912] 
list1.pop(2) 
#1 
list1.remove(536870910) 
print list1.index('a') 
#0 
print len(list1) 
#536870911 
print list1 
#['a', 0, 2, ..., 536870909, 536870911, 536870912] 
print list.src 
#[['a', 0, 2, ..., 536870909, 536870911], [536870912]]