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

Я пишу большую программу, и очень важно, чтобы детерминанты матриц 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 решает эту проблему, но я хочу стать лучше при написании эффективного кода. Любые идеи о том, как сделать эти петли быстрее?

Источник

5 ответов

Решение

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

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

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

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

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

В приведенном вами конкретном примере вы можете получить некоторое увеличение скорости в коде цикла, жестко закодировав вызовы "range" для кортежей - например, изменив:for i in range(0, len(a)-2): в for i in (0, 1, 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 обращения к переменной меньше, чем полностью умноженная версия.

Источник

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

Источник

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

Источник

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

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

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

Источник
Другие вопросы по тегам