python - 函数速度提升 : Convert ints to list of 32bit ints

Question

我正在寻找我的功能的快速替代品。目标是根据任意长度的整数制作一个 32 位整数列表。长度在 (value, bitlength) 的元组中明确给出。这是异步接口(interface)的位分解过程的一部分，每个总线事务采用 4 个 32 位整数。

所有整数都是无符号的、正数或零，长度可以在 0 到 2000 之间变化

我的输入是这些元组的列表， 输出应该是隐式 32 位长度的整数，位按顺序排列。不适合 32 的剩余位也应返回。

input: [(0,128),(1,12),(0,32)]
output:[0, 0, 0, 0, 0x100000], 0, 12

我花了一两天时间用 cProfile 进行分析，并尝试不同的方法，但我似乎有点受困于一秒钟内需要 ~100k 元组的函数，这有点慢。理想情况下我想要 10 倍的加速，但我没有足够的经验知道从哪里开始。此速度的最终目标是超过每秒 4M 元组。

感谢任何帮助或建议。

我能做的最快的是:

def foo(tuples):
    '''make a list of tuples of (int, length) into a list of 32 bit integers [1,2,3]'''
    length = 0
    remlen = 0
    remint = 0
    i32list = []
    for a, b in tuples:
        n = (remint << (32-remlen)) | a #n = (a << (remlen)) | remint
        length += b
        if length > 32:
            len32 = int(length/32)
            for i in range(len32):
                i32list.append((n >> i*32) & 0xFFFFFFFF)
            remint = n >> (len32*32)
            remlen = length - len32*32
            length = remlen
        elif length == 32:
            appint = n & 0xFFFFFFFF
            remint = 0
            remlen = 0
            length -= 32
            i32list.append(appint)
        else:
            remint = n
            remlen = length
    return i32list, remint, remlen

这具有非常相似的性能:

def tpli_2_32ili(tuples):
    '''make a list of tuples of (int, length) into a list of 32 bit integers [1,2,3]'''
#    binarylist = "".join([np.binary_repr(a, b) for a, b in inp]) # bin(a)[2:].rjust(b, '0')
    binarylist = "".join([bin(a)[2:].rjust(b, '0') for a, b in tuples])
    totallength = len(binarylist)
    tot32 = int(totallength/32)
    i32list = [int(binarylist[i:i+32],2) for i in range(0, tot32*32, 32) ]
    remlen = totallength - tot32*32
    remint = int(binarylist[-remlen:],2)
    return i32list, remint, remlen

Answer 1

到目前为止，我能想到的最好结果是提速 25%

from functools import reduce

intMask = 0xffffffff

def f(x,y):
    return (x[0] << y[1]) + y[0], x[1] + y[1]

def jens(input):
    n, length = reduce( f , input, (0,0) )
    remainderBits = length % 32
    intBits = length - remainderBits
    remainder = ((n & intMask) << (32 - remainderBits)) >> (32 - remainderBits)
    n >>= remainderBits

    ints = [n & (intMask << i) for i in range(intBits-32, -32, -32)]
    return ints, remainderBits, remainder

print([hex(x) for x in jens([(0,128),(1,12),(0,32)])[0]])

它使用一个long 将元组值根据它们的位长求和，然后从这个数字中提取 32 位值和剩余位。总长度的计算(对输入元组的长度值求和)和大值的计算在单个循环中完成，reduce 以使用内部循环。

运行 matineau 的基准线束打印，我看到的最好的数字是:

Fastest to slowest execution speeds using Python 3.6.5
(1,000 executions, best of 3 repetitions)

          jens :  0.004151 secs, rel speed  1.00x,     0.00% slower
 First snippet :  0.005259 secs, rel speed  1.27x,    26.70% slower
Second snippet :  0.008328 secs, rel speed  2.01x,   100.64% slower

如果您使用一些实现位数组的 C 扩展，您可能会获得更好的加速。