How to reindex a numpy array with reversed binary representation?

Question

How to improve the following code?

1 )-> pass a 1-dimensional array of length 2**n

2 )-> for every index of the array get the binary representation

3 )-> reverse the binary represenation and use it as new integer index for the corresponding value

EXAMPLE:

[56,209,81,42]

[00,01,10,11] (binary representation of the indices)

-> REVERSE:[00,10,01,11]

-> BECOMES:[56,81,209,42]

Code:

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

Which built-in functionality of Numpy or Python is handy?

`vectorize` isn't going make applying `np.binary_repr` any faster. It still generates one string per number. — hpaulj, Jan 31 '20 at 01:23
@hpaulj Thank you! Those hints are always helpful! And it shows my lack of understanding what happens and what I do. — user2853437, Feb 01 '20 at 01:33
The name of `np.vectorize` causes a lot of misunderstandings. It does operate on whole arrays, but not in idealized the way that produces 10x speedups. Others use `vectorize` to mean using multiprocessing and and fast hardware engines. Your accepted answer gains speed simply because `'{:b}'.format` is faster than `np.binary_repr`. — hpaulj, Feb 01 '20 at 02:01
I just realized `np.binary_repr` is Python code, which we can study and potentially modify. The core action is `bin(n)`, which produces a string like '0b10001'. It just cleans it up and adjusts for width. — hpaulj, Feb 01 '20 at 02:06
@hpaulj I don't know how np.fft() is implemented, but this request is part of calculating it — user2853437, Feb 01 '20 at 15:21

Andrej Kesely · Accepted Answer · 2020-02-01T10:13:18.057

You could use sorted with custom key, for example (thanks to @hpaulj for improved key function with 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))

Prints:

[56, 81, 209, 42]

Timings:

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)

Prints:

0.05821935099811526
0.22723246600071434

which is improvement ~3.9x

I get further speedup by using `bin` in the `key`: `key=lambda k: bin(k[0])[:1:-1]`. With the reversal, the width isn't important. — hpaulj, Feb 01 '20 at 02:28
@hpaulj Thanks, that seems too be significant speed-up (I edited my answer)! The `bin()` was indeed my first thought, but went with the `str.format` (I couldn't figure out how to use it with `sorted` - but your version did it :) — Andrej Kesely, Feb 01 '20 at 10:10

Andreas K. · Answer 2 · 2020-02-01T16:27:36.323

1

This problem is known as bit-reversal permutation. The only difficult part is to reverse the binary representation of an index. Here you will find ways to do it. I choose the simplest one:

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)

A faster version, based on the observation that:

Each permutation in this sequence can be generated by concatenating two sequences of numbers: the previous permutation, doubled, and the same sequence with each value increased by one.

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])

Example:

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

a[inds_rev]

edited Feb 01 '20 at 16:27

answered Jan 31 '20 at 07:17

Andreas K.

9,282
3
40
45

I don't know if I compared the code in the right way, but it runs slower and I also run into a prolem for high n: 'values: lst = np.array([randint(1, 100) for _ in range(2 ** 8)])' I receive: rev_indices = np.fromiter(map(rev_bits, indices), dtype=int) OverflowError: Python int too large to convert to C long, probably because of dtype. – user2853437 Feb 01 '20 at 01:31
@user2853437 how did you test it? For n = 8 there shouldn't be any problems. For `lst = np.array([randint(1, 100) for _ in range(2 ** 8)])` you should use `n = 8`, `inds_rev = bit_reversal_permutation(n)` and `lst[inds_rev]`. – Andreas K. Feb 01 '20 at 17:04
Of course for n > 64 you will have problem with numpy. – Andreas K. Feb 01 '20 at 17:05

How to reindex a numpy array with reversed binary representation?

2 Answers2