Fast way of converting parts of a bit numpy array to base 10

Question

Say I am given a numpy integer array of the form

a=np.array([0,0,0,1,1,0,1,0,1,0,1])

Now suppose I want to extract part of that array from positions i1:i2 and convert it to a base 10 representation. For instance, take i1=4 and i2=8. Then:

base_2=a[i1:i2] # base_2 = np.array([1,0,1,0])

And I would expect the function to return 10=2+8.

My question is the following : What is a fast way to achieve this in Python ?

Consider a function with the following signature:

def base_2_to_10_array(my_array,i1,i2):
    return """your awesome answer here"""

slicing numpy arrays *does not* make a copy. – juanpa.arrivillaga Dec 13 '17 at 00:39 — juanpa.arrivillaga, Dec 13 '17 at 00:39
Ha you are right, let me modify my question ! – VanillaSpinIce Dec 13 '17 at 00:42 — VanillaSpinIce, Dec 13 '17 at 00:42
For up to eight bits you could look into `np.packbits` – Paul Panzer Dec 13 '17 at 00:52 — Paul Panzer, Dec 13 '17 at 00:52

score 3 · Answer 1 · answered Dec 13 '17 at 01:25

3

One way (don't know if it is the fastest)

>>> a=np.array([0,0,0,1,1,0,1,0,1,0,1])
>>> int(''.join(map(str, a[4:8])), 2)
10

answered Dec 13 '17 at 01:25

percusse

3,006
1
14
28

This is concise, but very slow (15.122s vs 2.155s on length 10,000 array with 1,000 repetitions). – internet_user Dec 13 '17 at 04:08

internet_user · Accepted Answer · 2017-12-13T05:27:51.103

Another way, which I believe to be faster (benchmark), is:

def base_2_to_10_array(arr, i1, i2):
  res = 0
  for bit in arr[i1:i2][::-1]:
    res = (res << 1) ^ bit
  return res

This is probably faster because it is entirely binary operations (<< and ^), which are both fast (^ is faster because one of the operands is small, being 0 or 1).

percusse's answer is probably slower because of either mapping with str, or casting to int (might not be as optimized for binary).

type_none's is probably slower due to repeated calling of a lambda, multiplication instead of shifts and adding instead of oring.

Example benchmark results:

Size: 10

percusse: 0.016117284998472314
type_none: 0.004335935998824425
pycoder_3rd_fastest: 0.0028656079957727343
pycoder_2nd_fastest: 0.0033370210003340617
pycoder_fastest: 0.0031539250048808753

Size: 100

percusse: 0.13562769599957392
type_none: 0.04904397700011032
pycoder_3rd_fastest: 0.016703221001080237
pycoder_2nd_fastest: 0.021887271002924535
pycoder_fastest: 0.019885091001924593

Size: 1000

percusse: 1.358273936995829
type_none: 0.7615448830038076
pycoder_3rd_fastest: 0.18778558799385792
pycoder_2nd_fastest: 0.20695334099582396
pycoder_fastest: 0.18905453699699137

Size: 10000

percusse: 14.638380388998485
type_none: 7.554422806002549
pycoder_3rd_fastest: 5.3742733830004
pycoder_2nd_fastest: 2.2020759820006788
pycoder_fastest: 1.9534191700004158

Other attempts, one faster on shorter inputs, can be found in the benchmark link.

I like your answer, and I think it is pretty much the fastest you can do. I will modify the title of the question and give accept your answer. — VanillaSpinIce, Dec 13 '17 at 18:12

Abhijith Asokan · Answer 3 · 2017-12-13T13:19:51.467

0

I used reduce here. Unlike other answers this doesn't need conversion to string.

from functools import reduce # no need for import in python2
import numpy as np

def arrayToInt(l):
    return reduce(lambda x,y: (x<<1) + y, l)

a=np.array([0,0,0,1,1,0,1,0,1,0,1])
number = arrayToInt(a[4:8])
print(number)

edited Dec 13 '17 at 13:19

answered Dec 13 '17 at 03:39

Abhijith Asokan

1,865
10
14

Fast way of converting parts of a bit numpy array to base 10

3 Answers3