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
– hpaulj, Commented Jan 31, 2020 at 1:23
@hpaulj Thank you! Those hints are always helpful! And it shows my lack of understanding what happens and what I do. — user2853437
– user2853437, Commented Feb 1, 2020 at 1: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
– hpaulj, Commented Feb 1, 2020 at 2: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
– hpaulj, Commented Feb 1, 2020 at 2:06
@hpaulj I don't know how np.fft() is implemented, but this request is part of calculating it — user2853437
– user2853437, Commented Feb 1, 2020 at 15:21

Andrej Kesely · Accepted Answer · 2020-02-01 10:13:18Z

1

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

edited Feb 1, 2020 at 10:13

answered Jan 31, 2020 at 0:58

Andrej Kesely

196k15 gold badges60 silver badges105 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

hpaulj Over a year ago

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.

Andrej Kesely Over a year ago

@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 :)

kuzand · Accepted Answer · 2020-02-01 16:27:36Z

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 1, 2020 at 16:27

answered Jan 31, 2020 at 7:17

kuzand

9,8864 gold badges48 silver badges50 bronze badges

3 Comments

user2853437 Over a year ago

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.

kuzand Over a year ago

@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].

kuzand Over a year ago

Of course for n > 64 you will have problem with numpy.

Collectives™ on Stack Overflow

How to reindex a numpy array with reversed binary representation?

2 Answers 2

2 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related