自定义大小数组

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

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

如果您只需要同时访问一大块数据

如果您一次只需要访问一个数组，那么一种 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。

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

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

对于上面的示例，每个方向所需的时间（在我使用 Python 的机器中）每个元素大约为 8 ns。使用 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 个八位位组compressed到 a 中uint32_t value）：

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

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