Cython中的后缀计算器

问题描述：

嗨。

我想在Cython中开发一个后期计算器，从工作Numpy版本翻译。这是我第一次尝试。计算器函数在列表和样本矩阵中获取后缀表达式。然后，它必须返回计算的数组。

输入例：

postfix = ['X0', 'X1', 'add'] 
samples = [[0, 1], 
      [2, 3], 
      [4, 5]] 
result = [1, 5, 9]

example_cython.pyx

#cython: boundscheck=False, wraparound=False, nonecheck=False 

import numpy 
from libc.math cimport sin as c_sin 

cdef inline calculate(list lst, double [:,:] samples): 
    cdef int N = samples.shape[0] 
    cdef int i, j 
    cdef list stack = [] 
    cdef double[:] Y = numpy.zeros(N) 

    for p in lst: 
     if p == 'add': 
      b = stack.pop() 
      a = stack.pop() 
      for i in range(N): 
       Y[i] = a[i] + b[i] 
      stack.append(Y) 
     elif p == 'sub': 
      b = stack.pop() 
      a = stack.pop() 
      for i in range(N): 
       Y[i] = a[i] - b[i] 
      stack.append(Y) 
     elif p == 'mul': 
      b = stack.pop() 
      a = stack.pop() 
      for i in range(N): 
       Y[i] = a[i] * b[i] 
      stack.append(Y) 
     elif p == 'div': 
      b = stack.pop() 
      a = stack.pop() 
      for i in range(N): 
       if abs(b[i]) < 1e-4: b[i]=1e-4 
       Y[i] = a[i]/b[i] 
      stack.append(Y) 
     elif p == 'sin': 
      a = stack.pop() 
      for i in range(N): 
       Y[i] = c_sin(a[i]) 
      stack.append(Y) 
     else: 
      if p[0] == 'X': 
       j = int(p[1:]) 
       stack.append (samples[:, j]) 
      else: 
       stack.append(float(p)) 
    return stack.pop() 


# Generate and evaluate expressions 
cpdef test3(double [:,:] samples, object _opchars, object _inputs, int nExpr): 
    for i in range(nExpr): 
     size = 2 
     postfix = list(numpy.concatenate((numpy.random.choice(_inputs, 5*size), 
             numpy.random.choice(_inputs + _opchars, size), 
             numpy.random.choice(_opchars, size)), 0)) 
     #print postfix 

     res = calculate(postfix, samples)

main.py

import random 
import time 
import numpy 
from example_cython import test3 

# Random dataset 
n = 1030 
nDim=10 
samples = numpy.random.uniform(size=(n, nDim)) 

_inputs = ['X'+str(i) for i in range(nDim)] 
_ops_1 = ['sin'] 
_ops_2 = ['add', 'sub', 'mul', 'div'] 
_opchars = _ops_1 + _ops_2 
nExpr = 1000 
nTrials = 3 

tic = time.time() 
for i in range(nTrials): test3(samples, _opchars, _inputs, nExpr) 
print ("TEST 1: It took an average of {} seconds to evaluate {} expressions on a dataset of {} rows and {} columns.".format(str((time.time() - tic)/nTrials), str(nExpr), str(n), str(nDim)))

setup.py

from distutils.core import setup 
from distutils.extension import Extension 
from Cython.Distutils import build_ext 

ext_modules=[ Extension("example_cython", 
       ["example_cython.pyx"], 
       libraries=["m"], 
       extra_compile_args = ["-Ofast", "-ffast-math"])] 

setup(
    name = "example_cython", 
    cmdclass = {"build_ext": build_ext}, 
    ext_modules = ext_modules)

配置：

Python 3.6.2 |Anaconda, Inc.| (default, Sep 21 2017, 18:29:43) 
[GCC 4.2.1 Compatible Clang 4.0.1 (tags/RELEASE_401/final)] on darwin 

>>> numpy.__version__ 
'1.13.1' 
>>> cython.__version__ 
'0.26.1'

编译并运行：

running build_ext 
skipping 'example_cython.c' Cython extension (up-to-date) 
building 'example_cython' extension 
/usr/bin/clang -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -fwrapv -O2 -Wall -Wstrict-prototypes -march=core2 -mtune=haswell -mssse3 -ftree-vectorize -fPIC -fPIE -fstack-protector-strong -O2 -pipe -march=core2 -mtune=haswell -mssse3 -ftree-vectorize -fPIC -fPIE -fstack-protector-strong -O2 -pipe -I/Users/vmelo/anaconda3/include/python3.6m -c example_cython.c -o build/temp.macosx-10.9-x86_64-3.6/example_cython.o -Ofast -ffast-math 
example_cython.c:2506:15: warning: code will never be executed [-Wunreachable-code] 
    if (0 && (__pyx_tmp_idx < 0 || __pyx_tmp_idx >= __pyx_tmp_shape)) { 
       ^~~~~~~~~~~~~ 
example_cython.c:2506:9: note: silence by adding parentheses to mark code as explicitly dead 
    if (0 && (__pyx_tmp_idx < 0 || __pyx_tmp_idx >= __pyx_tmp_shape)) { 
     ^
     /* DISABLES CODE */ () 
example_cython.c:2505:9: warning: code will never be executed [-Wunreachable-code] 
     __pyx_tmp_idx += __pyx_tmp_shape; 
     ^~~~~~~~~~~~~ 
example_cython.c:2504:9: note: silence by adding parentheses to mark code as explicitly dead 
    if (0 && (__pyx_tmp_idx < 0)) 
     ^
     /* DISABLES CODE */ () 
2 warnings generated. 
/usr/bin/clang -bundle -undefined dynamic_lookup -Wl,-pie -Wl,-headerpad_max_install_names -Wl,-rpath,/Users/vmelo/anaconda3/lib -L/Users/vmelo/anaconda3/lib -Wl,-pie -Wl,-headerpad_max_install_names -Wl,-rpath,/Users/vmelo/anaconda3/lib -L/Users/vmelo/anaconda3/lib -arch x86_64 build/temp.macosx-10.9-x86_64-3.6/example_cython.o -L/Users/vmelo/anaconda3/lib -lm -o /Users/vmelo/Dropbox/SRC/python/random_equation/cython_v2/example_cython.cpython-36m-darwin.so 
ld: warning: -pie being ignored. It is only used when linking a main executable 

TEST 1: It took an average of 1.2609198093414307 seconds to evaluate 1000 expressions on a dataset of 1030 rows and 10 columns.

大约需要1.25秒，在我的i5 1.4GHz的运行。但是，类似的C代码需要0.13秒。

上面的代码评估1000个表达式，但我的目标是1,000,000。因此，我必须大幅度加速这个Cython代码。

正如我在一开始写的，Numpy版本工作正常。也许，在这个Cython版本中，我不应该使用列表作为堆栈？我仍然没有检查这个Cython代码生成的结果是否正确，因为我专注于提高速度。

有什么建议吗？

谢谢。

答

目前唯一经过优化的操作是索引samples[:, j]。（几乎）其他所有东西都是无类型的，所以Cython无法优化它。

我并不想真正重写你的（相当大的）程序，但这里有一些关于如何改进它的简单想法。

修正了一个基本的逻辑错误 - 你需要你的内循环线路Y = numpy.zeros(N)。 stack.append(Y)不会复制Y，所以每次修改Y时，还要修改放入堆栈的所有其他版本。
设置一个类型a和b：
```
cdef double[:] a, b # at the start of the program 
```
这将显著但是加快
```
Y[i] = a[i] * b[i] 
```
索引，就会造成像a = stack.pop()行是为慢一点它需要检查你的结果是否可以用作内存视图。您还需要更改行
```
stack.append(float(p)) 
```
，以确保你把可用的东西用memoryview在栈上：
```
stack.append(float(p)*np.ones(N)) 
```

更改堆到2D memoryview。我建议你过度分配它，只保留number_on_stack的计数，然后在需要时重新分配堆栈。然后，您可以更改：

stack.append(samples[:, j])

到：

if stack.shape[1] < number_on_stack+1: 
    # resize numpy array 
    arr = stack.base 
    arr.resize(... larger shape ..., refcheck=False) 
    stack = arr # re-link stack to resized array (to ensure size is suitably updated) 
stack[:,number_on_stack+1] = samples[:,j] 
number_on_stack += 1

和

a = stack.pop()

到

a = stack[:,number_on_stack] 
number_on_stack -= 1

其他的变化遵循类似的模式。此选项是最有效的工作，但可能会获得最佳结果。

使用cython -a生成有色HTML给你一个合理的思路，其中位很好的优化（黄码一般是雪上加霜）

Cython中的后缀计算器

相关推荐