如何使用反向二进制表示重新索引 numpy 数组?

Question

如何改进以下代码？

1 (->传递长度2**n的一维数组

2 (-> 对于数组的每个索引，获取二进制表示

3 (-> 反转二进制引用并将其用作相应值的新整数索引

例：

[56,209,81,42]

[00,01,10,11] (指数的二进制表示(

-> 反向：[00,10,01,11]

-> 变为：[56,81,209,42]

法典：

def order_in_reversed_bits(data: np.ndarray) -> np.ndarray:
tobinary = lambda t: np.binary_repr(t, width=len(np.binary_repr(data.shape[0]-1)))[::-1]
func = np.vectorize(tobinary)
a = func(np.arange(0,data.shape[0]))
t = np.zeros(data.shape,dtype='float64')
for i,k in enumerate(a):
t[int(k,2)] = data[i]
return t

Numpy或Python的哪个内置功能很方便？

Answer 1

例如，您可以将sorted与自定义键一起使用(感谢@hpaulj改进了bin()键功能(：

lst = [56,209,81,42]
def order_in_reversed_bits_python(lst):
return [v for _, v in sorted(enumerate(lst), key=lambda k: bin(k[0])[:1:-1])]
print(order_in_reversed_bits_python(lst))

指纹：

[56, 81, 209, 42]

---

计时：

import timeit
from random import randint
def order_in_reversed_bits_python(lst):
return [v for _, v in sorted(enumerate(lst), key=lambda k: bin(k[0])[:1:-1])]
def order_in_reversed_bits(data):
tobinary = lambda t: np.binary_repr(t, width=len(np.binary_repr(data.shape[0]-1)))[::-1]
func = np.vectorize(tobinary)
a = func(np.arange(0,data.shape[0]))
t = np.zeros(data.shape,dtype='float64')
for i,k in enumerate(a):
t[int(k,2)] = data[i]
return t
# create some large array:
lst = np.array([randint(1, 100) for _ in range(2**16)])
t1 = timeit.timeit(lambda: order_in_reversed_bits_python(lst), number=1)
t2 = timeit.timeit(lambda: order_in_reversed_bits(lst), number=1)
print(t1)
print(t2)

指纹：

0.05821935099811526
0.22723246600071434

这是改进~3.9倍

Answer 2

这个问题称为位反转排列。唯一困难的部分是反转索引的二进制表示。在这里，您将找到执行此操作的方法。我选择最简单的一个：

def bit_reversal_permutation(n):
indices = range(2**n)
rev_bits = lambda x: int(format(x, f'0{n}b')[::-1], 2)
return np.fromiter(map(rev_bits, indices), dtype=int)

更快的版本，基于以下观察

：

此序列中的每个排列都可以通过连接两个数字序列来生成：前一个排列、加倍和每个值增加 1 的相同序列。

def bit_reversal_permutation(n):
indices = range(2**(n-1))
rev_bits = lambda x: int(format(x, f'0{n-1}b')[::-1], 2)
rev_indices = np.fromiter(map(rev_bits, indices), dtype=int)
return np.concatenate([2*rev_indices, 2*rev_indices + 1])

例：

n = 4
a = np.random.randn(2**n)
inds_rev = bit_reversal_permutation(n)
a[inds_rev]