python - 自定义大小数组

Question

简单问题陈述:

是否可以在 C 或 Cython 中使用自定义大小数据类型(3/5/6/7 字节)的数组？

背景:

我在尝试编写复杂算法时遇到了内存效率低下的问题。该算法需要存储数量惊人的数据。所有数据都排列在一个连续的内存块中(如数组)。数据只是一长串 [通常] 非常大的数字。给定一组特定的数字，此列表/数组中的数字类型是常量(它们几乎作为常规 C 数组运行，其中所有数字在数组中的类型相同)

问题:

有时以标准数​​据大小存储每个数字效率不高。通常正常的数据类型是 char、short、int、long 等...但是，如果我使用 int 数组来存储仅在可以存储在 3 个字节的范围内的数据类型，则在每个数字上我丢失 1 个字节的空间。这会导致极低的效率，当您存储数百万个数字时，会破坏内存。不幸的是，没有其他方法可以实现算法的解决方案，我相信自定义数据大小的粗略实现是唯一的方法。

我尝试了什么:

我曾尝试使用 char 数组来完成此任务，但在大多数情况下，在不同的 0 - 255 值位之间转换以形成更大的数据类型效率很低。通常，有一种数学方法可以获取字符并将它们打包成一个更大的数字，或者获取那个更大的数字，然后划分它的各个字符。这是我尝试使用 Cython 编写的一种极其低效的算法:

def to_bytes(long long number, int length):
    cdef:
        list chars = []
        long long m
        long long d
    
    for _ in range(length):
        m = number % 256
        d = number // 256
        chars.append(m)
        number = d
    
    cdef bytearray binary = bytearray(chars)
    binary = binary[::-1]
    return binary

def from_bytes(string):
    cdef long long d = int(str(string).encode('hex'), 16)
    return d

请记住，我并不完全想要改进此算法，而是一种声明特定数据类型数组的基本方法，因此我不必进行此转换。

Answer 1

我认为重要的问题是您是否需要同时访问所有数据。

如果您只需要同时访问一个数据 block

如果您一次只需要访问一个数组，那么 Pythonic 的一种可能性是使用数据类型为 uint8 并根据需要使用宽度的 NumPy 数组。当您需要对数据进行操作时，将压缩数据扩展(这里是 3 个八位字节数字到 uint32):

import numpy as np

# in this example `compressed` is a Nx3 array of octets (`uint8`)
expanded = np.empty((compressed.shape[0], 4))
expanded[:,:3] = compressed
expanded[:, 3] = 0
expanded = expanded.view('uint32').reshape(-1)

然后对 expanded 执行操作，它是 N 个 uint32 值的一维 vector 。

完成后，数据可以保存回来:

# recompress
compressed[:] = expanded.view('uint8').reshape(-1,4)[:,:3]

在上面的示例中，每个方向所花费的时间(在我使用 Python 的机器中)大约为每个元素 8 纳秒。在这里使用 Cython 可能不会带来太大的性能优势，因为几乎所有时间都花在了在 NumPy 的黑暗深处某处的缓冲区之间复制数据。

这是一个很高的一次性成本，但如果您计划至少访问每个元素一次，那么支付一次性成本可能比为每个操作支付类似成本要便宜。

---

当然在C中也可以采用同样的做法:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <sys/resource.h>

#define NUMITEMS 10000000

int main(void)
    {
    uint32_t *expanded;
    uint8_t * cmpressed, *exp_as_octets;
    struct rusage ru0, ru1;
    uint8_t *ep, *cp, *end;
    double time_delta;

    // create some compressed data
    cmpressed = (uint8_t *)malloc(NUMITEMS * 3);

    getrusage(RUSAGE_SELF, &ru0);

    // allocate the buffer and copy the data
    exp_as_octets = (uint8_t *)malloc(NUMITEMS * 4);
    end = exp_as_octets + NUMITEMS * 4;
    ep = exp_as_octets;
    cp = cmpressed;
    while (ep < end)
        {
        // copy three octets out of four
        *ep++ = *cp++;
        *ep++ = *cp++;
        *ep++ = *cp++;
        *ep++ = 0;
        }
    expanded = (uint32_t *)exp_as_octets;

    getrusage(RUSAGE_SELF, &ru1);
    printf("Uncompress\n");
    time_delta = ru1.ru_utime.tv_sec + ru1.ru_utime.tv_usec * 1e-6 
               - ru0.ru_utime.tv_sec - ru0.ru_utime.tv_usec * 1e-6;
    printf("User: %.6lf seconds, %.2lf nanoseconds per element", time_delta, 1e9 * time_delta / NUMITEMS);
    time_delta = ru1.ru_stime.tv_sec + ru1.ru_stime.tv_usec * 1e-6 
               - ru0.ru_stime.tv_sec - ru0.ru_stime.tv_usec * 1e-6;
    printf("System: %.6lf seconds, %.2lf nanoseconds per element", time_delta, 1e9 * time_delta / NUMITEMS);

    getrusage(RUSAGE_SELF, &ru0);
    // compress back
    ep = exp_as_octets;
    cp = cmpressed;
    while (ep < end)
       {
       *cp++ = *ep++;
       *cp++ = *ep++;
       *cp++ = *ep++;
       ep++;
       }
    getrusage(RUSAGE_SELF, &ru1);
    printf("Compress\n");
    time_delta = ru1.ru_utime.tv_sec + ru1.ru_utime.tv_usec * 1e-6 
               - ru0.ru_utime.tv_sec - ru0.ru_utime.tv_usec * 1e-6;
    printf("User: %.6lf seconds, %.2lf nanoseconds per element", time_delta, 1e9 * time_delta / NUMITEMS);
    time_delta = ru1.ru_stime.tv_sec + ru1.ru_stime.tv_usec * 1e-6 
               - ru0.ru_stime.tv_sec - ru0.ru_stime.tv_usec * 1e-6;
    printf("System: %.6lf seconds, %.2lf nanoseconds per element", time_delta, 1e9 * time_delta / NUMITEMS);
    }

此报告:

Uncompress
 User: 0.022650 seconds, 2.27 nanoseconds per element
 System: 0.016171 seconds, 1.62 nanoseconds per element
Compress
 User: 0.011698 seconds, 1.17 nanoseconds per element
 System: 0.000018 seconds, 0.00 nanoseconds per element

代码是用 gcc -Ofast 编译的，可能相对接近最佳速度。系统时间花费在 malloc 上。在我看来，这看起来相当快，因为​​我们正在以 2-3 GB/s 的速度进行内存读取。 (这也意味着虽然使代码成为多线程很容易，但可能不会带来太多速度优势。)

如果您想获得最佳性能，您需要为每个数据宽度分别编写压缩/解压缩例程。 (我不保证上面的 C 代码在任何机器上绝对是最快的，我没有看机器代码。)

如果您需要随机访问单独的值

相反，如果您只需要在这里访问一个值，在那里访问另一个值，Python 将不会提供任何合理快速的方法，因为数组查找开销很大。

在这种情况下，我建议您创建 C 例程来获取和放回数据。请参阅 technosaurus 的回答。技巧有很多，但对齐问题还是无法避免。

读取奇数数组时的一个有用技巧可能是(这里从一个八位组数组压缩中读取 3 个八位组到 uint32_t value ):

value = (uint32_t *)&compressed[3 * n] & 0x00ffffff;

然后其他人会处理可能的错位，最后会有一个八位字节的垃圾。不幸的是，这不能在写入值时使用。并且 - 再一次 - 这可能会或可能不会比任何其他替代方案更快或更慢。