Разница в производительности при вставке-сортировке в C и Python

Question

Мне было интересно узнать производительность сортировки вставкой с использованием C и python, но полученные результаты заставляют меня задуматься, если я что-то сделал не так. Я подозревал, что С будет быстрее, но не намного.

Я профилировал оба кода, а функция вставки-сортировки - это место, где время тратится больше всего.

Вот функция C:

void
insert_sort (vec_t * vec)
{
    int j;
    for (j = 1 ; j < vec->n ; j++){
        int key = vec->v[j];
        int i = j - 1;
        while (i >= 0 && vec->v[i] > key){
            vec->v[i+1] = vec->v[i];
            i--;
        }
        vec->v[i+1] = key;
    }
}

Вот функция Python:

def insert_sort (ln):
    for j in range(1, len(ln)):
        key = ln[j]
        i = j-1
        while i >= 0 and ln[i] > key:
            ln[i+1] = ln[i]
            i-=1
        ln[i+1] = key

Тест был выполнен с 10000 целыми числами, каждое из которых случайным образом генерировалось между 0 и 10000.

Результаты за время, потраченное на каждую функцию:

• C время: 0,13 секунды
• время питона: 8,104 секунды

Я что-то здесь не так делаю? Как я уже сказал, я ожидал увидеть код C быстрее, но не быстрее.

Я не хочу использовать встроенные функции или что-то еще. Я хотел бы реализовать алгоритм. Есть ли pythonic способ делать вещи, которые я мог бы использовать во вставке-сортировке?

Answer 1

Python - это динамический язык, и стандартная реализация использует интерпретатор для оценки кода. Это означает, что там, где скомпилированный код C может выйти с одной машинной инструкцией, например, присвоив vec-> v [i + 1], интерпретатор Python должен найти переменную последовательности из локальной области видимости, найти ее класс, найти метод установки элемента в классе, вызовите этот метод. Аналогично для сравнения, дополнение. Не говоря уже о том, что выполнение почти каждого байт-кода приводит к ошибочному прогнозированию косвенного перехода в ЦП, что вызывает пузырь конвейера.

Этот вид кода выиграл бы от компиляции JIT до нативного кода и специализации типов времени выполнения, как unladen-swallow и PyPy.

В противном случае код в значительной степени является pythonic в том смысле, что если нужно реализовать сортировку вставкой, это то же самое, что и в Python. Это также очень нелепо, потому что вы должны использовать очень эффективную встроенную сортировку.

Answer 2

Моей первой мыслью было, что ноутбук, который у меня под рукой, Macbook Pro, должен быть сопоставим, но немного лучше вашего компьютера - мне не хватает вашего окружающего кода, чтобы попробовать ваш пример C (что vec_t и т. д., и т. д.), но запуск Python, который вы написали, дает мне:

$ python -mtimeit -s'import inso' 'inso.insort(inso.li)'
10 loops, best of 3: 7.21 msec per loop

против ваших 8,1 секунд. Вот вам код, вставленный в insort.py, которому предшествует:

import random
li = [random.randrange(10000) for _ in xrange(10000)]

array не помогает - на самом деле все немного замедляется. Затем я установил psyco , JIT-помощник Python (только для x86, только для 32-битной версии), далее добавил:

import psyco
psyco.full()

и получил:

$ python -mtimeit -s'import inso' 'inso.insort(inso.li)'
10 loops, best of 3: 207 usec per loop

так что ускорение примерно на 7,21 / 0,000207 = 34830 раз - против 8,04 / 0,13 = 62 раза, которое вас так удивило; -).

Конечно, проблема в том, что после первого раза список уже отсортирован, поэтому insort становится быстрее. Вы не дали нам достаточно окружающего тестового жгута, чтобы точно знать, что вы измерили. Более реалистичный пример (где фактический список не затрагивается, поэтому он остается неупорядоченным, сортируется только копия ...), без psyco:

$ python -mtimeit -s'import inso' 'inso.insort(list(inso.li))'
10 loops, best of 3: 13.8 sec per loop

Упс - значит, ваша машина ПУТЬ быстрее, чем Macbook Pro (помните, ядро ​​не в счет: мы здесь используем только одну ;-) - вау ... или вы ошибаетесь. Во всяком случае, с психо:

$ python -mtimeit -s'import inso' 'inso.insort(list(inso.li))'
10 loops, best of 3: 456 msec per loop

Таким образом, ускорение psyco составляет всего 13.8 / 0.456, в 30 раз - примерно вдвое больше, чем в 60+ раз, когда вы используете кодирование на чистом C. Итак, вы ожидаете, что python + psyco будет в два раза медленнее, чем чистый C. Это более реалистичная и типичная оценка.

Если вы пишете достаточно высокоуровневый код, его ускорение может снизиться с (скажем) в 30 раз до гораздо меньшего - но также и преимущество Си по сравнению с Python. Например,

$ python -mtimeit -s'import inso' 'sorted(inso.li)'
100 loops, best of 3: 8.72 msec per loop

без психо (в данном случае психо на самом деле - незначительно - замедляет исполнение ;-), так что это еще один фактор - 52 по сравнению с психо, 1582 в целом по сравнению с непсихопсихологами.

Но когда по тем или иным причинам вам нужно написать крайне низкоуровневые алгоритмы на python, а не использовать всестороннюю поддержку со стороны buildins и stdlib, psyco может помочь уменьшить боль.

Еще один момент, когда вы проводите тестирование, пожалуйста, опубликуйте ВСЕ код, чтобы другие могли точно увидеть, что вы делаете (и, возможно, заметили ошибки) - ваши "леса" такие хитрые и могут скрыть ловушки, как код, который вы думаете вы измеряете! -)

Answer 3

Итак, вот некоторые уроки, которые вы должны извлечь из этого:

• Интерпретируемый Python находится на медленной стороне. Не пытайтесь написать свой собственный FFT, кодировщик MPEG и т. Д. На Python.

• Даже медленно интерпретируемый Python, вероятно, достаточно быстр для небольших задач. Время выполнения в 8 секунд не является ужасным, и вам понадобится гораздо больше времени на написание и отладку C, чем на Python, поэтому, если вы пишете что-то для запуска один раз, Python выигрывает.

• Для скорости в Python, попробуйте использовать встроенные функции и модули C. Пусть чей-то код на C делает тяжелую работу. Я работал на встроенном устройстве, где мы работали на Python; несмотря на медленный встроенный процессор, производительность была приличной, потому что большую часть работы выполняли модули библиотеки C.

Для развлечения и образования, пожалуйста, повторите ваш тест Python, на этот раз используя встроенный метод .sort() в списке; это, вероятно, не будет так быстро, как C, но это будет близко. (Хотя для действительно больших наборов данных это будет лучше, чем C, потому что сортировка вставок - отстой. Если вы переписали C, чтобы использовать функцию библиотеки C qsort(), это было бы быстрым шагом.)

Распространенный «шаблон» проектирования Python: во-первых, напишите свое приложение на Python. Если это достаточно быстро, остановитесь; вы сделали. Во-вторых, попробуйте переписать, чтобы улучшить скорость; посмотрите, есть ли модуль C, который вы можете использовать, например. Если это все еще не достаточно быстро, подумайте о написании собственного модуля C; или, напишите программу на C, используя код прототипа Python в качестве основы для вашего дизайна.

Answer 4

Какой метод вы использовали для измерения времени?
Делая подобные вещи, я обнаружил, что Python по крайней мере в 30 раз медленнее, чем C
Компилятор C может использовать некоторые оптимизации, которые Python даже не пытается

Если вам может быть интересно попробовать psyco, этот тип кода хорошо подходит для него.

Опираясь на ответ Алекса, я попробовал Cython. В его случае cython превращает цикл for и все в чистый C, так что теперь я могу сравнить C, python и psyco

теперь у меня есть этот insort.py

import psyco
import random
li = [random.randrange(10000) for _ in xrange(10000)]

def insort (ln):
    for j in range(1, len(ln)):
        key = ln[j]
        i = j-1
        while i >= 0 and ln[i] > key:
            ln[i+1] = ln[i]
            i-=1
        ln[i+1] = key

#psyco.bind(insort)

import pyximport; pyximport.install()
import pyxinsort

def pyx_setup():
    pyxinsort.setup(li)

def pyx_insort():
    pyxinsort.insort(li)

и этот pyxinsort.pyx

cdef int ln[10000]

def insort(li):
    cdef int i,j,key
    for j in range(1, len(li)):
        key = ln[j]
        i = j-1
        while i >= 0 and ln[i] > key:
            ln[i+1] = ln[i]
            i-=1
        ln[i+1] = key

def setup(li):
    cdef int i
    for i in range(1, len(li)):
        ln[i]=li[i]

Код для сортировки практически идентичен. li передается для его длины. ln - это массив, который отсортирован и предварительно заполнен настройкой, поэтому я могу изолировать построение списка от сортировки

питон

$ python2.5 -mtimeit -s'import inso' 'list(inso.li)'
10000 loops, best of 3: 84.5 usec per loop
$ python2.5 -mtimeit -s'import inso' 'inso.insort(list(inso.li))'
10 loops, best of 3: 21.9 sec per loop

1022 * Психо * $ python2.5 -mtimeit -s'import inso' 'list(inso.li)' 10000 loops, best of 3: 85.6 usec per loop $ python2.5 -mtimeit -s'import inso' 'inso.insort(list(inso.li))' 10 loops, best of 3: 578 msec per loop Cython (это работает точно такой же алгоритм, преобразованный в C и скомпилированный)

$ python2.5 -mtimeit -s'import inso' 'inso.pyx_setup()'
10000 loops, best of 3: 141 usec per loop
$ python2.5 -mtimeit -s'import inso' 'inso.pyx_setup();inso.pyx_insort()'
10 loops, best of 3: 46.6 msec per loop

Cython побеждает психо в 16 раз, а Python в 470 раз!

Для полноты я включил соответствующий фрагмент кода C, сгенерированный Cython

  for (__pyx_v_j = 1; __pyx_v_j < __pyx_1; __pyx_v_j+=1) {
    __pyx_v_key = (__pyx_v_9pyxinsort_ln[__pyx_v_j]);
    __pyx_v_i = (__pyx_v_j - 1);
    while (1) {
      __pyx_2 = (__pyx_v_i >= 0);
      if (__pyx_2) {
        __pyx_2 = ((__pyx_v_9pyxinsort_ln[__pyx_v_i]) > __pyx_v_key);
      }
      if (!__pyx_2) break;
      (__pyx_v_9pyxinsort_ln[(__pyx_v_i + 1)]) = (__pyx_v_9pyxinsort_ln[__pyx_v_i]);
      __pyx_v_i -= 1;
    }
    (__pyx_v_9pyxinsort_ln[(__pyx_v_i + 1)]) = __pyx_v_key;
  }

Answer 5

Что не так с:

ln.sort()