Как переиндексировать массив 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

Эта проблема известна как перестановка битов . Единственная сложная часть - обратить двоичное представление индекса. Здесь вы найдете способы сделать это. Я выбрал самый простой:

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)

Более быструю версию, основанную на наблюдении, что:

Каждая перестановка в этой последовательности может быть сгенерирована путем объединения двух последовательностей чисел: предыдущая перестановка, удвоенная, и та же последовательность с каждым значением, увеличенным на единицу.

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]

Answer 2

Например, вы можете использовать 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,9x