Python 3.1 - Ошибка памяти во время выборки большого списка

Question

В списке ввода может быть более 1 миллиона номеров. Когда я запускаю следующий код с меньшими «повторами», его штраф;

def sample(x): 
    length = 1000000 
    new_array = random.sample((list(x)),length) 
    return (new_array) 

def repeat_sample(x):  
    i = 0 
    repeats = 100 
    list_of_samples = [] 
    for i in range(repeats): 
     list_of_samples.append(sample(x)) 
    return(list_of_samples) 

repeat_sample(large_array) 

Однако, использование высоких повторов, таких как выше 100, приводит к MemoryError. Traceback выглядит следующим образом.

Traceback (most recent call last): 
    File "C:\Python31\rnd.py", line 221, in <module> 
    STORED_REPEAT_SAMPLE = repeat_sample(STORED_ARRAY) 
    File "C:\Python31\rnd.py", line 129, in repeat_sample 
    list_of_samples.append(sample(x)) 
    File "C:\Python31\rnd.py", line 121, in sample 
    new_array = random.sample((list(x)),length) 
    File "C:\Python31\lib\random.py", line 309, in sample 
    result = [None] * k 
MemoryError 

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

Благодарим вас за внимание!

Answer 1

Расширение на мой комментарий:

Допустим обработка вы делаете для каждого образца вычислить его среднее значение.

def mean(samplelists): 
    means = [] 
    n = float(len(samplelists[0])) 
    for sample in samplelists: 
     mean = sum(sample)/n 
     means.append(mean) 
    return means 

calc_means(repeat_sample(large_array)) 

Это сделает вас потеть, удерживая все эти списки в памяти. Вы можете получить его гораздо легче, как это:

def mean(sample, n): 
    n = float(n) 
    mean = sum(sample)/n 
    return mean 

def sample(x): 
    length = 1000000 
    new_array = random.sample(x, length) 
    return new_array 

def repeat_means(x):  
    repeats = 100 
    list_of_means = [] 
    for i in range(repeats): 
     list_of_means.append(mean(sample(x))) 
    return list_of_means  

repeat_means(large_array) 

Но это все еще не достаточно хорошо ... Вы можете сделать все это с только когда-либо построения списка результатов:

import random 

def sampling_mean(population, k, times): 
    # Part of this is lifted straight from random.py 
    _int = int 
    _random = random.random 

    n = len(population) 
    kf = float(k) 
    result = [] 

    if not 0 <= k <= n: 
     raise ValueError, "sample larger than population" 

    for t in range(times): 
     selected = set() 
     sum_ = 0 
     selected_add = selected.add 

     for i in xrange(k): 
      j = _int(_random() * n) 
      while j in selected: 
       j = _int(_random() * n) 
      selected_add(j) 
      sum_ += population[j] 

     mean = sum_/kf 
     result.append(mean) 
    return result 

sampling_mean(x, 1000000, 100) 

Теперь, может ваш алгоритм должен быть упорядочен так?

Answer 2

Единственное улучшения вы можете сделать, это изменить свой код:

list_of_samples = [random.sample(x, length) for _ in range(repeats)] 

Это не меняет тот факт, однако, что вы не можете создать список произвольной длины в реальном мире.

Answer 3

Два ответа:

1. Если вы не используете старую машину, то маловероятно, что вы на самом деле запустить из памяти. Вы получаете MemoryError, потому что вы, вероятно, используете 32-битную сборку Python и не можете выделить более 2 ГБ памяти.

2. Ваш подход неверен. Вы должны использовать произвольный образец генератор вместо создания списка образцов.

Answer 4

Вы можете попытаться использовать объект массива http://docs.python.org/py3k/library/array.html. Это должно быть гораздо более эффективным для памяти, чем список, но, вероятно, немного сложнее в использовании.

Answer 5

версия генератора random.sample() также помогло бы:

from random import random 
from math import ceil as _ceil, log as _log 

def xsample(population, k): 
    """A generator version of random.sample""" 
    n = len(population) 
    if not 0 <= k <= n: 
     raise ValueError("sample larger than population") 
    _int = int 
    setsize = 21  # size of a small set minus size of an empty list 
    if k > 5: 
     setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets 
    if n <= setsize or hasattr(population, "keys"): 
     # An n-length list is smaller than a k-length set, or this is a 
     # mapping type so the other algorithm wouldn't work. 
     pool = list(population) 
     for i in range(k):   # invariant: non-selected at [0,n-i) 
      j = _int(random() * (n-i)) 
      yield pool[j] 
      pool[j] = pool[n-i-1] # move non-selected item into vacancy 
    else: 
     try: 
      selected = set() 
      selected_add = selected.add 
      for i in range(k): 
       j = _int(random() * n) 
       while j in selected: 
        j = _int(random() * n) 
       selected_add(j) 
       yield population[j] 
     except (TypeError, KeyError): # handle (at least) sets 
      if isinstance(population, list): 
       raise 
      for x in sample(tuple(population), k): 
       yield x