Comments 7
Уровень: простой.
Сегодня поговорим о подпроцессах.
У меня такое ощущение что если бы вы воспользовались cdef результат был тот же
Можно было бы ещё cython попробовать
Хорошая статья, спасибо! Я думал, что это всё (c ext, например, делается сильно более заморочено). Добавлю ещё метод, но для совсем ленивых: numba
import numba
import numpy as np
@numba.jit(numba.int64(numba.types.unicode_type, numba.types.unicode_type), nopython=True, nogil=True)
def lev_numba(a, b):
n, m = len(a), len(b)
if n == 0:
return m
if m == 0:
return n
prev = np.arange(m + 1, dtype=np.int64)
curr = np.zeros(m + 1, dtype=np.int64)
for i in range(1, n + 1):
curr[0] = i
for j in range(1, m + 1):
cost = 0 if a[i - 1] == b[j - 1] else 1
curr[j] = min(prev[j] + 1, curr[j - 1] + 1, prev[j - 1] + cost)
prev = curr.copy()
return prev[m]
результаты скромные, конечно:
Benchmark: Pythonvs VS LLVM (numba)
n=2000 m=2000
Python : 1.872s -> 1768
LLVM : 0.253s -> 1768
n=4000 m=4000
Python : 7.698s -> 3513
LLVM : 1.086s -> 3513
Да, не 100 раз, но зато делается левой ногой с закрытыми глазами (настолько быстро и просто, что я не пожалел времени на комментарий). У меня были примеры более хорошие, где тоже в сравнении с голым питоном разница была в нескольких порядках. numba работает так, что на лету код на питоне транслирует в промежуточное представление LLVM и потом как-то встраивает это всё в процесс исполнения. Чёрная магия, не иначе. Из плюсов недоступных расширениям я придумал такие доводы:
- возможность дебажить получившийся код
- всё хранится в одной кодовой базе и на условно одних технологиях
- там есть всякие фишки, вроде тривиально создаваемых параллельных циклов или интеграция с CUDA
- всё сцеплено с numpy и значит из коробки могут работать всякие научные пакеты вроде scipy
- в общем это целая экосистема, не просто на коленке что-то накидать, люди постарались
C/C++ уже не модно, сам Гвидо предлагает уезжать на rust https://discuss.python.org/t/pre-pep-rust-for-cpython/104906/12
Си-код тормозит почти в 10 раз - можно ведь считать параллельно (по диагонали):
levenshtein sse_variant len
103535 113 12863 113 125 uint16
440665 221 41669 221 250
1670380 445 151093 445 500
6740058 896 967752 896 1000
28449713 1769 2670073 1769 2000 7.5 vs 0.7ms
112313687 3517 9621706 3517 4000 29.5 vs 2.5ms
417518031 7034 40077041 7034 8000
1709693702 14038 166281964 14038 16000
6812783553 28117 730058352 28117 32000 uint16
... ... ... ... ... ... ...
103583 113 7589 149 125 uint8
Вариант с длиной в uint8 применим только если коротка строка короче 128 символов - иначе будет переполнение. Железо Intel(R) Core(TM) i7-2600K CPU @ 3.80GHz время при желании можно пересчитать из тактов.
Ключи сборки gcc -O3 -mavx -msse4 test.cpp -o test && ./test , если применить avx2/avx512 можно наверно ещё 2-4 раза ускорить (-mavx погоды особой не делает - у него для целых нужных команд нет).
Оптимизированный код (короткая строка должна быть короче 32К символов):
#define sseLen 16
#define sseNum 8
typedef uint16_t sseType;
typedef sseType sseReg __attribute__ ((vector_size (sseLen),aligned(1)));
static int sse_variant(const char* _s1, const char* _s2) {
int n1 = strlen(_s1), n2 = strlen(_s2);
if(n1>n2) return sse_variant(_s2,_s1);
if(!n1) return n2;
sseType* a = (sseType*)malloc((n1+2*sseNum) * sizeof(*a));
sseType* b = (sseType*)malloc((n1+2*sseNum) * sizeof(*b));
sseType* c = (sseType*)malloc((n1+2*sseNum) * sizeof(*c));
sseType* s1 = (sseType*)malloc((n1+2*sseNum)*sizeof(*s1));
sseType* s2 = (sseType*)malloc((n2+2*sseNum)*sizeof(*s2));
if (!a || !b || !c || !s1 || !s2) {
free(a); free(b); free(c); free(s1); free(s2); return -1;
}
for(int i=0;i<n1;++i) s1[n1-1-i]=_s1[i];
for(int i=0;i<n2;++i) s2[i]=_s2[i];
b[0]=a[0]=a[1]=0;
for(int n=1;n<n1+n2;++n){
sseType *d=c; c=b; b=a; a=d;
int nn=n<n1?n:(n<n2?n1:n1+n2-n);
int o=0;
if(n<n1) a[o++]=0;
int i1=n1-(n<n1?n:n1);
int i2=n>n1?n-n1:0;
#if 1
const sseReg one={1,1,1,1,1,1,1,1};
for(int i=0,j=n>n1;i<nn;i+=sseNum,o+=sseNum){
sseReg v1=*(sseReg*)(s1+i1); i1+=sseNum;
sseReg v2=*(sseReg*)(s2+i2); i2+=sseNum;
sseReg t1=*(sseReg*)(c+j)+one-(v1==v2); j+=sseNum;
v1=*(sseReg*)(b+i);
v2=*(sseReg*)(b+i+1);
sseReg t2=v1>v2?v1:v2;
*(sseReg*)(a+o)=t1>t2?t1:t2;
}
#else
for(int i=0,j=n>n1;i<nn;++i,++o){
int t1=(s1[i1++]!=s2[i2++]?1:2)+c[j++];
int t2=b[i]>b[i+1]?b[i]:b[i+1];
a[o]=t1>t2?t1:t2;
}
#endif
if(n<n2) a[nn+(n<n1)]=0;
}
int ans=n1+n2-a[0];
free(a); free(b); free(c); free(s1); free(s2);
return ans;
}
Ускорение Python в 150 раз с использованием C