Матричная функция 3x3 - ускорение

Question

Я пишу большую программу, и очень важно, чтобы как можно быстрее определялись детерминанты матриц 3х3, чтобы она работала хорошо. Я читал, что могу использовать для этого numPy, но подумал, что, возможно, написание собственного кода будет более познавательным, поскольку я учусь на третьем семестре CompSci.

Итак, я написал две функции и использую time.clock () (я на машине с win7) для определения времени, которое требуется каждой функции для возврата значения.

Это первая функция:

def dete(a):
   x = (a[0][0] * a[1][1] * a[2][2]) + (a[1][0] * a[2][1] * a[3][2]) + (a[2][0] * a[3][1] * a[4][2])
   y = (a[0][2] * a[1][1] * a[2][0]) + (a[1][2] * a[2][1] * a[3][0]) + (a[2][2] * a[3][1] * a[4][0])
   return x - y

А это вторая функция:

def det(a):
    a.append(a[0]); a.append(a[1]);
    x = 0
    for i in range(0, len(a)-2):
        y=1;        
        for j in range(0, len(a)-2):    
            y *= a[i+j][j]      
        x += y

    p = 0
    for i in range(0, len(a)-2):
        y=1;
        z = 0;
        for j in range(2, -1, -1):  
            y *= a[i+z][j]  
            z+=1        
        z += 1
        p += y  
    return x - p

Они оба дают правильные ответы, однако первый, кажется, немного быстрее, что заставляет меня думать, что поскольку циклы for более элегантны в использовании и обычно быстрее, я делаю что-то не так - я тоже сделал циклы медленный и толстый. Я попытался обрезать его, но кажется, что операции * = и + = занимают слишком много времени, их слишком много. Я еще не проверял, насколько быстро numPy решает эту проблему, но я хочу стать лучше при написании эффективного кода. Любые идеи о том, как сделать эти петли быстрее?

Answer 1

Циклы - более элегантные и более общие, но они не "обычно быстрее", чем пара встроенных умножений в одном выражении.

С одной стороны, цикл for в python должен собрать объект, по которому вы будете взаимодействовать (вызов range), а затем вызвать метод этого итератора для каждого элемента в цикле.

Итак, в зависимости от того, что вы делаете, если встроенная форма достаточно быстра для того, чтобы вы ее сохранили - если она все еще слишком медленная (как это обычно бывает в случае, когда мы выполняем численные вычисления в Python), вам следует использовать числовая библиотека (пример NumpY), которая может вычислять детерминанты в нативном коде. В случае такого числового кода манипуляции вы можете запустить его в сотни раз быстрее, используя собственный код.

Если yo9u нужны числовые вычисления, которые не могут быть выполнены уже созданной библиотекой, если вы ищете скорость (например, для манипулирования пикселями при обработке изображений), вы можете написать расширение, которое выполняется в собственном коде ( используя C, Cython или что-то еще), чтобы быстро.

С другой стороны, если скорость не имеет решающего значения, и вы даже заметили, что встроенное выражение просто «немного быстрее», просто используйте полный цикл - вы получите более читаемый и поддерживаемый код - что является основными причинами использования Python в конце концов.

В приведенном вами конкретном примере вы можете получить некоторое увеличение скорости в коде цикла, жестко закодировав вызовы "range" для кортежей - например, изменив: for i in range(0, len(a)-2): до for i in (0, 1, 2) - обратите внимание, что, как и во встроенном случае, вы теряете возможность работать с матрицами разных размеров.

Answer 2

Во-первых, позвольте мне отметить, что оптимизация скорости на микроуровне должна проводиться на другом языке.Таким образом, вам лучше использовать библиотеку, которая использует c-письменную функциональность.

О ваших циклах for: это обычная техника для развертывания (маленьких) циклов для ускорения, поэтому не всегда быстрее позволить циклам делатьработа.Обычно это просто более универсальный (и большинство универсальных алгоритмов на самом деле медленнее, чем специализированные).

Как указано в комментариях, он не увеличит скорость в python, если заменить - на *, но этоможет увеличить скорость, если задействовано меньше арифметических операций.Поэтому я опубликую факторизованный термин здесь:

def dete(a):
    return (a[0][0] * (a[1][1] * a[2][2] - a[2][1] * a[1][2])
           -a[1][0] * (a[0][1] * a[2][2] - a[2][1] * a[0][2])
           +a[2][0] * (a[0][1] * a[1][2] - a[1][1] * a[0][2]))

Как вы можете видеть, есть 5 +/- и 9 *, где, как и в оригинальной версии, есть 5 +/- и 12 *.Также обратите внимание, что эта версия обращалась к a только 15 раз, тогда как исходная к ней обращалась 18 раз.

В итоге это дает 3 арифметических операции и 3 доступа к переменной меньше, чем у полностью умноженной версии.

Answer 3

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

Answer 4

Пока вы развертываете его, как предложено выше, вы также можете объединить два блока в один, так как быстрый взгляд не обнаружил зависимости между двумя блоками (поправьте меня, если я ошибаюсь)

Answer 5

вы можете развернуть циклы и воспользоваться тем, что вы обрабатываете матрицы 3x3, а не матрицы nxn.

С помощью этой оптимизации вы избавляетесь от определения размераматрица.Вы торгуете гибкостью с небольшим ускорением.Вы можете просто записать конкретные формулы для каждой ячейки матрицы результатов.КСТАТИ: (c ++) Компиляторы делают такие вещи оптимизации.

Я бы предложил сделать это, только если вы действительно уверены, что такая маленькая оптимизация стоит специализированного кода.Чтобы убедиться, что вы оптимизируете правильную часть своего кода, используйте, например, инструменты профилирования , см. http://docs.python.org/library/profile.html или timeit .