内存中的高效矢量位数据 "Rotation" / "Rearrangement" [例如在 Python, Numpy]

Question

如何从一个 8 元素长的数组（例如uint8s 变成它的 "rotated" 对应物，例如第一个元素的原始 8 位作为 MSB 分布在所有向量元素中，倒数第二个元素分布在第二个 MSB 中，依此类推：工作和慢速示例：

import numpy as np

original = np.random.randint(0, 255, 8).astypye(np.uint8) # some random example vector
[np.binary_repr(i, width=8) for i in original]            # original data
=>['01111111',
   '00100111',
   '01110111',
   '00100010',
   '00111101',
   '10010000',
   '10000100',
   '10101000']

rotated = np.packbits(np.unpackbits(original).reshape(-1,8).T) # <= SLOW ROTATION
[np.binary_repr(i, width=8) for i in rotated]                  # this is should be the result
=>['00000111',                                                 # what where rows originally
   '10100000',                                                 # are now columns
   '11111001',
   '10101100',
   '10001001',
   '11101010',
   '11110000',
   '11101000']

所以最后，我想将 BITS "filed" 的布局重新排序到 RAM 中。如您所见，我在 Numpy 中得到了一个工作示例，它不是很慢（此处为 ~ 21 µs），但是我想以 ~2k * 1 mio 位的顺序使用数据结构进行此练习。因此，使用 numpy 或 C bool dtype 是浪费（8 倍开销）。

欢迎任何 C 位改组魔术或 SSE 说明或一般答案！

Answer 1

我建议查看提供的来源 here

特别是 calcperm.cpp。这是一个简单的位排列问题。

Answer 2

如果旋转是针对平方数的行和列，那么这是一个解决方案，然后它只对位进行 t运行spose。

我在问题中使用了8位元素。此外，第 7 位是最左边的位，而第 0 位是最右边的位。我将按以下格式引用列和行中的位（仅仅是因为这是我可以最快打印位的方式——因此索引比最好的情况更棘手，但可以适当修改） :

    | col : 7 6 5 4 3 2 1 0
--------------------------
row:| 0     0 1 1 1 1 1 1 1
    | 1     0 0 1 0 0 1 1 1 
    | 2     0 0 0 0 0 1 0 0
    | 3     0 0 0 0 1 0 0 1
    | 4     0 0 0 0 1 1 0 0
    | 5     0 1 1 0 0 1 0 0
    | 6     1 1 0 0 1 0 0 0
    | 7     1 0 0 1 0 1 1 0

然后我定义了以下结构来包装8位元素，并执行位操作和打印：

struct Element {
    Element(uint8_t E) : e(E) {}

    // Just for convienience
    static constexpr int size = 8;
    uint8_t e;

    // Get a bit from the element
    inline uint8_t get(uint8_t i) {
        return (e >> i & 0x01);
    }

    // Flip a bit in the element
    inline void flip(uint8_t i) {
        e ^= (0x01 << i);
    }

    // Just for convienience
    void print() {
        std::cout << std::bitset<8>(e) << "\n";
    }
};

以及以下在两个 Element 中翻转位的函数——请注意，您只需翻转不相同的位，因为元素是二进制的。

inline void swap(Element& a, Element& b, int a_offset, int b_offset) {
    if (a.get(a_offset) != b.get(b_offset)) {
        a.flip(a_offset); b.flip(b_offset);
    }
}

那么就是循环遍历上三角（对角线以上）的元素，并将它们与下三角（对角线以下）的元素交换如下：

int main() {
  std::vector<Element> array = { 127, 39, 4, 9, 12, 100, 200, 150 };

  for (auto& a : array) a.print(); std::cout << "\n"; // Before

  // Do the swapping
  for (size_t row = 0; row < array.size(); ++row) {
    for (size_t col = Element::size - 1 - row; col >= 1; --col) {
      swap(array[row], array[Element::size - col], col - 1, Element::size - 1 - row);
    }
  }

  for (auto& a : array) a.print(); // After
}

产生问题中的 t运行形式：请参阅显示输入和输出的 live demo。在大约 1.1 微秒内使用 -O3 运行进行编译（只是 t运行信息，不包括打印）。

您还可以很容易地将 t运行变形更改为向右或向左旋转 90 度，只需修改索引即可。

Answer 3

这是 8x8 情况下的 C 语言简单实现：

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char byte;

void dump(const char *name, const byte *p, int size) {
    int len = printf("%s => ['", name) - 1;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < 8; j++) {
            putchar('0' + ((p[i] >> (7 - j)) & 1));
        }
        if (i < 7) {
            printf("',\n%*s'", len, "");
        }
    }
    printf("']\n");
}

int main(int argc, char **argv) {
    byte original[8], rotated[8];
    int repeat = 1;

    if (argc > 1)
        repeat = atoi(argv[1]);

    for (int i = 0; i < 8; i++) {
        original[i] = rand() & 255;
    }
    for (int r = 0; r < repeat; r++) {
        /*-------- this is the core of the rotation --------*/
        for (int i = 0; i < 8; i++) {
            rotated[i] = 0;
        }
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                rotated[j] |= ((original[i] >> (7 - j)) & 1) << (7 - i);
            }
        }
        /*-------- end of the rotation code --------*/
    }
    if (repeat == 1) {
        dump("original", original, 8);
        dump("rotated", rotated, 8);
    }
    return 0;
}

运行它没有样本随机测试的参数：

chqrlie@mac ~/dev/Whosebug > ./rot8x8
original => ['10100111',
             '11110001',
             '11011001',
             '00101010',
             '10000010',
             '11001000',
             '11011000',
             '11111110']
rotated => ['11101111',
            '01100111',
            '11010001',
            '01100011',
            '00110111',
            '10000001',
            '10011001',
            '11100000']

运行它带有时间的数字参数：

chqrlie@mac ~/dev/Whosebug > time ./rot8x8 20000000
real    0m0.986s
user    0m0.976s
sys     0m0.004s

在 MacbookPro 上，clang -O3，这个简单的程序执行一次旋转需要 不到 50ns，400 倍 比你的 Numpy 例子。我敢肯定有更快的方法，但这已经好得多了。

内存中的高效矢量位数据 "Rotation" / "Rearrangement" [例如在 Python, Numpy]

Efficient Vector Bit-Data "Rotation" / "Rearrangement" in Memory [e.g. in Python, Numpy]

python

c++

c

arrays

bit-manipulation