Как ускорить цикл питона

Question

Я посмотрел несколько рассуждений на нескольких сайтах, и ни один из них не дал мне решения. Этот фрагмент кода выполняется более 5 секунд:

for i in xrange(100000000):
  pass

Я работаю над задачей целочисленной оптимизации, и мне нужно использовать алгоритм O (n log n) edit: алгоритм O (n² / 4), где n обозначает все элементы матрицы, т. е. в следующем коде n * m = 10000. Таким образом, для матрицы 100 * 100 с 10000 элементов это приведет к почти 25000000 итерациям ... . Его код можно представить так:

m = 100
n = 100
for i in xrange(m):
  for j in xrange(n):
    for i2 in xrange(i + 1, m):
      for j2 in xrange(j + 1, n):
        if myarray[i][j] == myarray[i2][j2] and myarray[i2][j] == myarray[i][j2]:
          return [i, j], [i2, j2]

Должен ли я отказаться от Python и вернуться к Java или к C?

Я работаю с Python 2.7, а Psyco недоступен. PyPy не поддерживает Tkinter из коробки, и я использую Tkinter.

Так, они улучшат скорость зацикливания? Есть ли другие решения?

Answer 1

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

try:
    i,j,i2,j2 = ((i,j,i2,j2)
        for i in xrange(m)
          for j in xrange(n)
            for i2 in xrange(i + 1, m)
              for j2 in xrange(j + 1, n)
                if myarray[i][j] == myarray[i2][j2] and 
                    myarray[i2][j] == myarray[i][j2]).next()
    return [i,j],[i2,j2]
except StopIteration:
    return None

Обновлено для использования встроенных next и product и Py3 range вместо xrange:

from itertools import product
match = next(((i,j,i2,j2)
    for i, j in product(range(m), range(n))
        for i2, j2 in product(range(i+1, m), range(j+1, n))
            if myarray[i][j] == myarray[i2][j2] and 
                myarray[i2][j] == myarray[i][j2]), None)
if match is not None:
    i,j,i2,j2 = match
    return [i,j],[i2,j2]
else:
    return None

Answer 2

Вы все еще можете использовать нотацию Python и иметь скорость C, используя проект Cython . Первым шагом будет преобразование цикла в цикл C: это автоматически выполняется путем ввода всех переменных, используемых в цикле:

cdef int m = 100
cdef int n = 100
cdef int i, j, i2, j2
for i in xrange(m):
  for j in xrange(n):
    for i2 in xrange(i + 1, m):
      for j2 in xrange(j + 1, n):

Для следующей части было бы еще лучше, если бы этот массив был чистым массивом C, тогда не было бы никакого расширенного сравнения Python или доступа к массиву. С вашим массивом python вы можете удалить расширенное сравнение, выполнив собственное сравнение (если в вашем массиве есть double):

        cdef double a, b, c, d
        a = myarray[i][j]
        b = myarray[i2][j2]
        c = myarray[i2][j]
        d = myarray[i][j2]

        if a == b and c == d:
          return [i, j], [i2, j2]

Вы можете увидеть, как идет оптимизация, запустив cython -a yourfile.pyx, затем откройте генерацию yourfile.html. Вы увидите, как Cython оптимизировал ваш код и удалил накладные расходы Python.

Answer 3

Извините, что говорю вам, но это не вопрос оптимизации. Независимо от того, какой язык или реализацию вы выберете, этот алгоритм не является O(n*log n) в худшем и среднем случае. Возможно, вы захотите прочитать , как работает нотация Big-O , и разработать лучший алгоритм.

Answer 4

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

Ответ-часть: : Если вы ищете подходящий алгоритм, рассмотрите алгоритм линии сканирования. Я нашел пример здесь @ SO для "самого большого прямоугольного решения".

Мой вопрос к вам, что вы действительно ищете?

1. лучший способ решить дилемму цикла
2. лучший язык для вашего алгоритма
3. более быстрый алгоритм поиска прямоугольников

Я также должен указать, что решение Пола и ваше решение дают разные результаты, поскольку Полс предполагает, что углы помечены одинаковыми значениями, а вы предполагаете, что углы помечены двумя разными значениями!

Я нашел время и свободу, чтобы проиллюстрировать это уродливым скриптом c & p: Он сравнивает оба алгоритма путем создания 2D-поля и заполняет его string.lowercase символов и превращает углы в символы верхнего регистра.

from random import choice
from string import lowercase
from collections import defaultdict
from itertools import permutations
from copy import deepcopy

m,n = 20, 20
myarray = [[choice(lowercase) for x in xrange(m)] for y in xrange(n)]

def markcorners(i,j,i2,j2):
    myarray[i][j] = myarray[i][j].upper()
    myarray[i2][j] = myarray[i2][j].upper()
    myarray[i2][j2] = myarray[i2][j2].upper()
    myarray[i][j2] = myarray[i][j2].upper()

def printrect():
    for row in myarray:
        print ''.join(row)
    print '*'*m

def paul_algo():
    tally = defaultdict(list)
    for i,row in enumerate(myarray):
        for j,n in enumerate(row):
            tally[n].append((i,j))

    # look for rectangular quads in each list
    for k,v in tally.items():
        for quad in permutations(v,4):
            # sort quad so that we can get rectangle corners 
            quad = sorted(quad)
            (i1,j1),(i2,j2) = quad[0], quad[-1]

            # slice out opposite corners to see if we have a rectangle
            others = quad[1:3]

            if [(i1,j2),(i2,j1)] == others:
                markcorners(i1,j1,i2,j2)

def xavier_algo():   
    for i in xrange(m):
        for j in xrange(n):
            for i2 in xrange(i + 1, m):
                for j2 in xrange(j + 1, n):
                    if myarray[i][j] == myarray[i2][j2] and myarray[i2][j] == myarray[i][j2]:
                        markcorners(i,j,i2,j2)

savearray = deepcopy(myarray)
printrect()

xavier_algo()
printrect()

myarray = deepcopy(savearray)
paul_algo()
printrect()

Answer 5

Извините, генератор не работает. Вот другая схема, которая сначала подсчитывает все одинаковые значения, а затем ищет прямоугольные группы:

from collections import defaultdict
from itertools import permutations
def f3(myarray):
    tally = defaultdict(list)
    for i,row in enumerate(myarray):
        for j,n in enumerate(row):
            tally[n].append((i,j))

    # look for rectangular quads in each list
    for k,v in tally.items():
        for quad in permutations(v,4):
            # sort quad so that we can get rectangle corners 
            quad = sorted(quad)
            (i1,j1),(i2,j2) = quad[0], quad[-1]

            # slice out opposite corners to see if we have a rectangle
            others = quad[1:3]

            if [(i1,j2),(i2,j1)] == others:
                return [i1,j1],[i2,j2]