Ускорение подсчета кортежей

Question

Ускорение подсчета кортежей

Для проекта, который я делаю, я заинтересован в создании списка всех кортежей (i,j,k,z,f), которые соответствуют следующим критериям:

все пять переменных могут варьироваться от 0 до 343
я == k или j==z или k == f

Что я придумала до сих пор, так это:

z1=set()
for i in xrange(344):
    for j in xrange(344):
        for k in xrange(344):
            for z in xrange(344):
                for f in xrange(344):
                    if f!=k:
                        continue
                    z1.add((i,j,k,z,f))
for i in xrange(344):
    for j in xrange(344):
        for k in xrange(344):
            for z in xrange(344):
                for f in xrange(344):
                    if z!=j:
                        continue
                    if (i,j,k,z,f) not in z1:
                        z1.add((i,j,k,z,f))
for i in xrange(344):
    for j in xrange(344):
        for k in xrange(344):
            for z in xrange(344):
                for f in xrange(344):
                    if k!=i:
                        continue
                    if (i,j,k,z,f) not in z1:
                        z1.add((i,j,k,z,f))

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

1

python performance for-loop counting

Источник

user3264199 10 апр '14 в 18:34

5 ответов

Другие вопросы по тегам python performance for-loop counting

user1071311 10 апр '14 в 18:45 2014-04-10 18:45 · Answer 1 · 2014-04-10 18:45

Вам нужно больше памяти. Много и много памяти. Давайте просто посмотрим на первое условие, i == k, Количество кортежей, удовлетворяющих этому условию, равно 343 ** 4 = 13841287201, 13 миллиардов! Если каждому кортежу нужны только 5*4 = 20 байтов памяти, это все еще 257 ГБ, которые необходимы для набора. И это даже не все элементы набора, который вы желаете.

Нет, нет легкого выхода. Если бы мне пришлось оптимизировать эту проблему до приемлемого размера, я бы сначала спросил mysqlf: действительно ли мне нужен такой большой список? Или я могу решить эту проблему без этого?

user763505 10 апр '14 в 18:45 2014-04-10 18:45 · Answer 2 · 2014-04-10 18:45

Можете ли вы меньше цикл и меньше сравнивать.

Попробуйте следующее, это может быть быстрее:

def doit ():
    theRange = range (343)
    for i in theRange:
        for j in theRange:
            for k in theRange:
                cond1 = i == k
                for z in theRange:
                    cond2 = j == z
                    for f in theRange:
                        if cond1 or cond2 or k == f:
                            yield i, j, k, z, f

for x in doit ():
    doSomethingWith (x)

user3280538 10 апр '14 в 18:59 2014-04-10 18:59 · Answer 3 · 2014-04-10 18:59

Вам не нужны условия для этого,

Используйте наборы, содержащие только одно значение.

a = set()
for index in xrange(344):
    for i in xrange(344):
        for j in xrange(344):
            for k in xrange(344):
                #i==k
                a.add((index,i,index,j,k))
                #j==z
                a.add((i,index,j,index,k))
                #k==f
                a.add((i,j,index,k,index))

РЕДАКТИРОВАТЬ изменил тип значения на значение ~ Мне нужно больше кофе

user13005 10 апр '14 в 18:56 2014-04-10 18:56 · Answer 4 · 2014-04-10 18:56

Так как у вас не хватит памяти, пытаясь создать набор, используйте генератор для итерации по ним, не сохраняя их все:

itertools.ifilter(
    lambda x: x[0] == x[2] or x[1] == x[3] or x[2] == x[4],
    itertools.product(xrange(344), repeat=5)
)

Конечно, для итерации все равно потребуется много времени, поскольку предстоит еще многое сделать (около 5 триллионов значений). Подробнее об этом позже.

Если вам действительно нужен этот набор по какой-то особой причине, вы можете использовать эту идею для определения "ленивого" неизменяемого набора. В Python 2:

class MyCollection(collections.Set):
    def __contains__(self, x):
        if not isinstance(x, tuple): return False
        if not len(x) == 5: return False
        if not all(isinstance(y, int) for y in x): return False
        if not all(0 <= y <= 343 for y in x): return False
        return self.match(x)
    @classmethod
    def match(cls, x):
        return (x[0] == x[2] or x[1] == x[3] or x[2] == x[4])
    def __iter__(self):
        return itertools.ifilter(
            self.match,
            itertools.product(xrange(344), repeat=5)
        )
    def __len__(self):
        # um. Left as an exercise for the reader. About 39 billion or so.

z1 = MyCollection()

Вы также можете сделать итерацию несколько более эффективной, если придумаете способы избежать посещения каждой комбинации. Самое простое, о чем я могу думать, это то, что если i!=k а также j!=zтогда единственно возможное значение f является k, Так что в этом случае не повторяйте все возможное f, просто выведите тот, который будет работать.

Однако наиболее эффективным, вероятно, является:

перебрать все комбинации из 4 значений
у вас есть еще одно значение, чтобы добавить. Это будет либо помечено на конце как f (в этом случае это равно k) или вставлен в середину как z или же k (и равно i или же j).

Их 42 миллиарда, но в них есть некоторые дубликаты. Я не думаю, что их так просто исключить, но я бы выбрал правильные 4-кортежи в порядке от (0,0,0,0) в (344,344,344,344), Перед выводом одного из трех 5-кортежей, сгенерированных из каждого 4-кортежа, решите, мог ли его сгенерировать какой-либо более ранний 4-кортеж. Если так, то пропустите это.

user33258 10 апр '14 в 18:57 2014-04-10 18:57 · Answer 5 · 2014-04-10 18:57

Небольшая настройка кода @Hyboreus:

def legal_tuples():
    r = range(344)
    for i in r:
        for j in r:
            for k in r:
                i_eq_k = i == k
                for z in r:
                    if i_eq_k or j == z:
                        for f in r:
                            yield i,j,k,z,f
                    else:
                        yield i,j,k,z,k

1

Источник

user33258 10 апр '14 в 18:57