Блог

Главная - Вопросы по программированию - Ошибка памяти python, вычисляющая перестановки списка

Ошибка памяти python, вычисляющая перестановки списка

#python #python-2.7 #permutation #combinatorics

#python #python-2.7 #перестановка #комбинаторика

Вопрос:

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

 combinations = map(list, itertools.product([0, 1], repeat=n))

Это отлично работает с низкими n, но я хочу вычислить это для больших n (т. Е. Значений между 25-35). Есть ли лучший и более эффективный способ создания этого списка?

Комментарии:

1. Мне нужен список списков, и в любом случае это не работает на моем компьютере, ошибка памяти для большого n.

2. Какова конечная цель? Если вам не нужны все значения сразу, почему бы просто не сохранить итератор, а не map списки?

3. В чем собственно проблема? Ошибка памяти? Пожалуйста, предоставьте вывод ошибки

4. Эта проблема принципиально экспоненциальна во времени и пространстве (если вы хотите фактически хранить все списки в памяти). Извините, вы мало что можете сделать.

Ответ №1:

Просто создайте список «лениво», чтобы не сохранять все сразу в памяти:

 n = some-largish-value

for i in itertools.product([0, 1], repeat=n):
   result = do_something_with(list(i))

Ответ №2:

Вы пытаетесь найти все комбинации 0 и 1 для n членов. Общее количество таких комбинаций будет 2**n . Для n=30 , всего таких комбинаций 1073741824 . Огромный, не так ли?

Чтобы избавиться от ошибки памяти, вы должны использовать генератор, который yield динамически комбинирует вместо того, чтобы сохранять их в виде списка. Кроме того, поскольку это комбинация только 0 и 1. Почему бы не печатать двоичные числа от 0 до '1'*n ?

Ниже приведен итератор для достижения этой цели как:

 def binary_combinations(num):
    my_binary_string = '1'*num
    my_int_num = int(my_binary_string, 2)
    format_string = '{' ':0{}b'.format(num) '}'
    for i in xrange(my_int_num):
        yield format_string.format(i)
    else:
        raise StopIteration('End of Memory Issue!')

Чтобы выполнить это, выполните:

 >>> for i in binary_combinations(3):
...     print i
...
000
001
010
011
100
101
110

Здесь n = 3 . Теперь вы можете использовать его с n = 30, 40, .. ИЛИ как угодно;)

Ответ №3:

Нет, если вам действительно нужен список списков, тогда ваш код почти настолько эффективен, насколько это возможно. Ваша проблема заключается в размере списка, а не в том, как вы его вычисляете.

Вы понимаете, что для n = 35 у вас будет 1 202 590 842 880 элементов? Большинство (если не все) настольных компьютеров не могут хранить так много целых чисел python в памяти.