有没有更快的方法将任意大的整数转换为大端序列的字节？

Question

有没有更快的方法将任意大的整数转换为大端序列的字节？

8

我有这段Python代码来完成这个任务：

from struct import pack as _pack

def packl(lnum, pad = 1):
    if lnum < 0:
        raise RangeError("Cannot use packl to convert a negative integer "
                         "to a string.")
    count = 0
    l = []
    while lnum > 0:
        l.append(lnum & 0xffffffffffffffffL)
        count += 1
        lnum >>= 64
    if count <= 0:
        return '\0' * pad
    elif pad >= 8:
        lens = 8 * count % pad
        pad = ((lens != 0) and (pad - lens)) or 0
        l.append('>' + 'x' * pad + 'Q' * count)
        l.reverse()
        return _pack(*l)
    else:
        l.append('>' + 'Q' * count)
        l.reverse()
        s = _pack(*l).lstrip('\0')
        lens = len(s)
        if (lens % pad) != 0:
            return '\0' * (pad - lens % pad) + s
        else:
            return s

在我的计算机上，将2 ** 9700 - 1转换为字节字符串大约需要174微秒。如果我愿意使用Python 2.7和Python 3.x特定的bit_length方法，在最开始就预分配l数组的确切大小，并使用l[something] =语法而不是l.append，则可以将时间缩短至159微秒。

有什么办法可以使这个过程更快吗？这将用于转换用于加密的大型质数以及一些（但不多）较小的数字。编辑在Python < 3.2中，这是当前最快的选项，无论是向前还是向后，所需时间约为接受的答案的一半。

def packl(lnum, padmultiple=1):
    """Packs the lnum (which must be convertable to a long) into a
       byte string 0 padded to a multiple of padmultiple bytes in size. 0
       means no padding whatsoever, so that packing 0 result in an empty
       string.  The resulting byte string is the big-endian two's
       complement representation of the passed in long."""

    if lnum == 0:
        return b'\0' * padmultiple
    elif lnum < 0:
        raise ValueError("Can only convert non-negative numbers.")
    s = hex(lnum)[2:]
    s = s.rstrip('L')
    if len(s) & 1:
        s = '0' + s
    s = binascii.unhexlify(s)
    if (padmultiple != 1) and (padmultiple != 0):
        filled_so_far = len(s) % padmultiple
        if filled_so_far != 0:
            s = b'\0' * (padmultiple - filled_so_far) + s
    return s

def unpackl(bytestr):
    """Treats a byte string as a sequence of base 256 digits
    representing an unsigned integer in big-endian format and converts
    that representation into a Python integer."""

    return int(binascii.hexlify(bytestr), 16) if len(bytestr) > 0 else 0

在Python 3.2中，int类具有to_bytes和from_bytes函数，可以比上述方法更快地完成此操作。

- Omnifarious

2

pad 是什么作用？一个文档字符串会很方便地理解它的用法。 - Scott Griffiths

1

据我所知，输出结果在前面填充了零，直到达到下一个以pad字节数为倍数的字节数。 - Karl Knechtel

无论是本地变量，您都应避免使用变量名，例如“l” - 在大多数字体上它看起来太像“1”，以保持可读性。 - jsbueno

@Karl Knechtel - 没错。我想在需要将其转储到恰好为64位长、128位长或类似长度的插槽中的情况下使用它。 - Omnifarious

想让你知道，我已经将你的新方法作为优化借用到了 bitstring 模块中。谢谢！ - Scott Griffiths

显示剩余4条评论

4个回答

5

为了完整性和未来读者的参考：

从Python 3.2开始，有int.from_bytes()和int.to_bytes()两个函数，可以在不同字节顺序之间进行bytes和int对象的转换。

- Sven Marnach

谢谢！不过我在想字节序标志是否会减慢它的速度。我们拭目以待。 - Omnifarious

即使使用了大小端标志，它仍然比我到目前为止找到的最快方法快三分之一或更少的时间。 - Omnifarious

3

我想跟进Sven的回答（非常有效），但是从任意长的字节对象转换为Python整数对象需要以下操作（因为我找不到PyLong_FromByteArray() C API函数）：

import binascii

def unpack_bytes(stringbytes):
    #binascii.hexlify will be obsolete in python3 soon
    #They will add a .tohex() method to bytes class
    #Issue 3532 bugs.python.org
    return int(binascii.hexlify(stringbytes), 16)

- bk0

1

实际上有一个_PyLong_FromByteArray函数（至少在Python 2.7和Python 3中）。我正在使用它。但你的方法也可能非常快。 - Omnifarious

事实上，这比使用ctypes调用_PyLong_FromByteArray更快。多么奇怪啊。更好的是，我不必检查输入是否为“memoryview”，因为hexlify会处理它们，而且如果值足够小而不需要成为“long”，我也不必在Python 2.7中将其转换为“int”以使其成为直接的“int”。 - Omnifarious

此外，使用 hex(lnum) 和 binascii.unhexlify（再加上一些额外的粘合剂）也比 ctypes 选项更快。 - Omnifarious

奇怪。我查看了Python 3.1.x C API参考文档，但找不到PyLong_FromByteArray()函数。 - bk0

3

我认为你应该使用numpy，我相信它内置了一些东西可以完成这个任务。使用array模块进行hack可能会更快。但是我还是会尝试一下。

在我的经验中，创建一个生成器并使用列表推导式和/或内置求和比追加到列表的循环更快，因为追加操作可以在内部完成。哦，对于一个大字符串来说，执行'lstrip'操作肯定是代价高昂的。

另外，一些风格要点：特殊情况不够特殊；而且你好像没有收到有关新的'x if y else z'结构的备忘录。:)虽然我们不需要它。;)

from struct import pack as _pack


Q_size = 64
Q_bitmask = (1L << Q_size) - 1L


def quads_gen(a_long):
    while a_long:
        yield a_long & Q_bitmask
        a_long >>= Q_size


def pack_long_big_endian(a_long, pad = 1):
    if lnum < 0:
        raise RangeError("Cannot use packl to convert a negative integer "
                         "to a string.")
    qs = list(reversed(quads_gen(a_long)))
    # Pack the first one separately so we can lstrip nicely.
    first = _pack('>Q', qs[0]).lstrip('\x00')
    rest = _pack('>%sQ' % len(qs) - 1, *qs[1:])
    count = len(first) + len(rest)
    # A little math trick that depends on Python's behaviour of modulus
    # for negative numbers - but it's well-defined and documented
    return '\x00' * (-count % pad) + first + rest

- Karl Knechtel

我不应该给你点赞，你的代码有很多错误。 - Omnifarious

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sven Marnach · Accepted Answer

以下是使用 ctypes 调用 Python/C API 的解决方案。目前，它使用了 NumPy，但如果没有 NumPy 也可以纯粹地使用 ctypes 实现。

import numpy
import ctypes
PyLong_AsByteArray = ctypes.pythonapi._PyLong_AsByteArray
PyLong_AsByteArray.argtypes = [ctypes.py_object,
                               numpy.ctypeslib.ndpointer(numpy.uint8),
                               ctypes.c_size_t,
                               ctypes.c_int,
                               ctypes.c_int]

def packl_ctypes_numpy(lnum):
    a = numpy.zeros(lnum.bit_length()//8 + 1, dtype=numpy.uint8)
    PyLong_AsByteArray(lnum, a, a.size, 0, 1)
    return a

在我的机器上，这种方法比你的方法快了15倍。

编辑: 这里是使用ctypes的相同代码，并返回一个字符串而不是 NumPy 数组：

import ctypes
PyLong_AsByteArray = ctypes.pythonapi._PyLong_AsByteArray
PyLong_AsByteArray.argtypes = [ctypes.py_object,
                               ctypes.c_char_p,
                               ctypes.c_size_t,
                               ctypes.c_int,
                               ctypes.c_int]

def packl_ctypes(lnum):
    a = ctypes.create_string_buffer(lnum.bit_length()//8 + 1)
    PyLong_AsByteArray(lnum, a, len(a), 0, 1)
    return a.raw

这次又快了两倍，总共在我的机器上加速了30倍。