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

Question

Я хотел бы попробовать 26-мерное пространство, скажем, с 10 точками в каждом направлении. Это означает, что в общей сложности 10 ** 26 образцов, но я отброшу более 99,9999 ...%. Использование python немедленно приводит к ошибкам памяти.

Первый наивный подход заключается в использовании вложенных циклов:

p = list(range(10))
for p1 in p:
    for p2 in p:
        ...

Однако Python имеет встроенный максимум на количество вложенных циклов: 20.

Лучше всего было бы использовать команду numpy .indices:

import numpy as np
dimensions = (10,)*26
indices = np.indices(*dimensions)

Это происходит с сообщением «слишком большой массив», поскольку Numpy не может вместить все 10 ** 26 индексов в памяти. Понятно.

Мой последний подход состоял в том, чтобы использовать итератор, надеясь, что ему не нужно больше памяти:

import numpy as np
dimensions = (10,)*26
for index in np.ndindex(*dimensions):
    # do something with index

Однако, это ТАКЖЕ завершается ошибкой с сообщением "слишком большой массив", так как под капотом Numpy все еще пытается создать плотный массив.

У кого-нибудь еще есть лучший подход?

Спасибо! Том

РЕДАКТИРОВАТЬ: Сообщение "массив слишком большой", вероятно, потому что 10 ** 26 больше, чем максимальное значение, которое может хранить Int64. Если бы вы могли указать Numpy хранить размер как Int128, это могло бы обойти ValueError по крайней мере. Тем не менее, для хранения всех индексов как Int64 все равно потребуется почти 20 ГБ ...

Answer 1

Пока что это решение, которое я нашел:

class IndicesGenerator:
    def __init__(self, nbDimensions, nbSamplesPerDimension):
        self.nbDimensions = nbDimensions
        self.nbSamplesPerDimension = nbSamplesPerDimension
    def getNbDimensions(self):
        return self.nbDimensions
    def getNbSamplesPerDimension(self):
        return self.nbSamplesPerDimension
    def getIndices(self):
        d = self.getNbDimensions()
        N = self.getNbSamplesPerDimension()
        # create indices
        indices = []
        prevIndex = None
        for i in range(d):
            newIndex = Index(maxValue=N-1, prev=prevIndex)
            indices.append(newIndex)
            prevIndex = newIndex
        lastIndex = indices[-1]
        while True:
            try:
                yield list(map(lambda index: index.getValue(), indices))
                lastIndex.increment()
            except RuntimeError:
                break

class Index:
    def __init__(self, maxValue, prev=None):
        assert prev is None or isinstance(prev, Index)
        assert isinstance(maxValue, int)
        self.prev = prev
        self.value = 0
        self.maxValue = maxValue
    def getPrevious(self):
        return self.prev
    def getValue(self):
        return self.value
    def setValue(self, value):
        assert isinstance(value, int)
        self.value = value
    def getMaximumValue(self):
        return self.maxValue
    def increment(self):
        if self.getValue() == self.getMaximumValue():
            # increment previous and set the current one to zero
            if self.getPrevious() is None:
                # the end is reached, so raise an error
                raise RuntimeError
            else:
                self.setValue(0)
                self.getPrevious().increment()
        else:
            self.setValue(self.getValue()+1)
if __name__ == '__main__':
    import time
    nbIndices = 0
    d = 3
    N = 5
    start = time.time()
    for indices in IndicesGenerator(nbDimensions=d, nbSamplesPerDimension=N).getIndices():
        # print(indices)
        nbIndices += 1
    assert nbIndices == N**d
    end = time.time()
    print("Nb indices generated: ", nbIndices)
    print("Computation time: ", round(end-start,2), "s.")

Это не быстро для больших размеров, но, по крайней мере, оно работает без ошибок памяти.