Replace items in list with another items (small lists) depending on several conditions

Question

I have a list of numbers and I want to replace each number with a list binary pattern depending on several conditions. I have a working code for doing so, but I am wondering if there is a faster more efficient one because if I wanted to add more conditions.

Thanks

import numpy as np
n = []
z = np.linspace(0,5,8)
t = [3.8856, 4.1820, 2.3040, 1.0197, 0.4295, 1.5178, 0.3853, 4.2848, 4.30911, 3.2299, 1.8528, 0.6553, 3.3305, 4.1504, 1.8787]
for i in t:
    if i>=z[0] and i<z[1]:
        n.extend([0,0,0,0,0])
    elif i>=z[1] and i<z[2]:
        n.extend([0,0,0,0,1])
    elif i>=z[2] and i<z[3]:
        n.extend([0,0,0,1,0])
    elif i>=z[3] and i<z[4]:
        n.extend([0,0,0,1,1])
    elif i>=z[4] and i<z[5]:
        n.extend([0,0,1,0,0])
    elif i>=z[5] and i<z[6]:
        n.extend([0,0,1,0,1])
    elif i>=z[6] and i<z[7]:
        n.extend([0,0,1,1,0])
new_n = np.asarray(n).reshape(len(t),5) # new_n is the final pattern I want.

Have you seen [`np.where`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.where.html)? — pylang, Mar 12 '19 at 00:15
@pylang Yes, I can see using it makes it faster as I don't have to loop there `t` I can change several indices at once if they match the condition, but what about listing the conditions themselves? — motaha, Mar 12 '19 at 00:17
The condition statements are probably negligible compared to the O(n) loop and method calls. — pylang, Mar 12 '19 at 00:19

Kostas Mouratidis · Accepted Answer · 2019-06-12T18:06:03.477

This is not an answer per se, but it probably will be faster due to using numpy rather than python's for loop.

First, you want to perform some binning:

>> bins = np.digitize(t, z) - 1 # minus 1 just to align our shapes
array([5, 5, 3, 1, 0, 2, 0, 5, 6, 4, 2, 0, 4, 5, 2])

This tells you in what bin each of your values goes. Next, define your patterns, in order:

>> patterns = np.array([
    [0,0,0,0,0],
    [0,0,0,0,1],
    [0,0,0,1,0],
    [0,0,0,1,1],
    [0,0,1,0,0],
    [0,0,1,0,1],
    [0,0,1,1,0],
])

Now for some numpy magic, instead of appending/extending, create an array full of zeros (this should be almost always faster). This array will have shape (len(t), len(z)-1). Using this SO answer, we will also do one-hot encoding:

>> inds = np.zeros((len(t), len(z)-1))
>> inds[np.arange(len(t)), bins] = 1
>> inds
array([[0., 0., 0., 0., 0., 1., 0.],
       [0., 0., 0., 0., 0., 1., 0.],
       [0., 0., 0., 1., 0., 0., 0.],
       .....,
       [0., 0., 0., 0., 0., 1., 0.],
       [0., 0., 1., 0., 0., 0., 0.]])

Finally, all we need to is a matrix multiplication

>> inds @ patterns
array([[0., 0., 1., 0., 1.],
       [0., 0., 1., 0., 1.],
       [0., 0., 0., 1., 1.],
       ....
       [0., 0., 1., 0., 1.],
       [0., 0., 0., 1., 0.]])

I did not perform a quality timing test, but from my minor experimentation here are my results:

Your loop: 17.7 µs ± 160 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) My implementation: 8.49 µs ± 125 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Which may or may not scale well to larger datasets. Hope this helps :)

Edit: Following Alexander Lopatin's answer I was interested to see that my method was significantly slower. Upon further investigation one of the conclusions I arrived at was that numpy's functions have some significant overhead which is not a cheap price to pay for few values of t. For larger lists, the numpy overhead is insignificant, but the performance gain is not:

timings = {
    10: [7.79, 24.1, 21.7],
    16: [10.7, 29.9, 22.9],
    24: [14.6, 40.5, 23.4],
    33: [19.1, 48.6, 23.4],
    38: [21.9, 55.9, 23.9],
    47: [26.7, 66.2, 24.1],
    61: [33, 79.5, 24.7],
    75: [40.8, 92.6, 25.8],
    89: [47.6, 108, 26.2],
    118: [60.1, 136, 27.4],
    236: [118, 264, 33.1],
    472: [236, 495, 40.9],
    1000: [657, 922, 52],
    10000: [6530, 9090, 329]
}

Zoom:

I was trying to incorporate your answer in my code: inds = np.zeros((len(t), len(z) - 1), **dtype=int** inds = **inds** @ patterns The results and times are also not the same: Time CPU for 100000 loops 1.7117 1.7052 Alexander 4.6044 4.5888 Kotlas — Alex Lopatin, Mar 14 '19 at 02:59
I wouldn't trust my timings over yours, I just used the `%%timeit` in jupyter. Still, the difference amazes me, but anyhow thanks for including those in your answer! Edit: I also noticed that I had a few mistakes in the `patterns` variable, fixing these too. — Kostas Mouratidis, Mar 14 '19 at 09:04
I forgot to mention that using your code the timings are roughly the same as the ones you reported. I was interested though as why the difference in performance, and decided to do some more testing. It seems the problem does not lie with the timing method. I tried the following: I increased the size of `t` from 15 to 100 and the timings are: me 2.54, you 4.92, original 11.53, but I also noticed another thing: wrapping it in a function nearly doubles the time it takes (from 12.2μs to 26.5μs). I tried using `cProfile` and `dis.dis` but couldn't find the source of that. Any ideas? — Kostas Mouratidis, Mar 14 '19 at 09:29
If you don't wrap in a function you may be reusing something that was created in the global scope. The green time is just flat? Check your code and provide it. so I can test it too :-) — Alex Lopatin, Mar 14 '19 at 10:24
It's not flat, it simply grows slower (I've also attached the timings in a dictionary). The code is exactly the same as yours with only one difference: instead of `t = [...]` I used `t = np.repeat([...], n_repeats)`. I ran it with multiple n_repeats and logged the results, but do check it out in case I missed something (again...). — Kostas Mouratidis, Mar 14 '19 at 13:16

Alex Lopatin · Answer 2 · 2019-03-14T07:04:54.390

My new version is three-time faster than the original:

Time    CPU for 100000 loops
1.7444  1.7400 proposed by Alexander Lopatin
5.2813  5.2770 original by motaha
4.6203  4.6117 proposed by Kostas Mouratidis

I simplified the elifs to make the original code smaller (11 lines) and then added some 57 lines (66..123) for speed and correctness testing :-) Tried also to use z = np.linspace(0,5,8) or precalculate z outside the for in loop 'if z[j] < y < z[j+1]:' instead of 'if xj < y < x(j+1):', but got big time penalty - don't know why. I also added the code proposed here by Kostas Mouratidis. It didn't produce the exact result, see the output at the end.

import numpy as np
import itertools
import time
import platform


def f1():  # answered by Alexander Lopatin #####################################
    n = []
    t = [3.8856, 4.1820, 2.3040, 1.0197,  0.4295,
         1.5178, 0.3853, 4.2848, 4.30911, 3.2299,
         1.8528, 0.6553, 3.3305, 4.1504,  1.8787]
    x = 5./7.
    p = list(itertools.product([0, 1], repeat=5))
    for y in t:
        j = int(y/x)
        if x*j < y < x*(j+1):
            n.append(p[j])
    return np.asarray(n).reshape(len(t), 5)


def f2():  # original post by motaha ###########################################
    n = []
    t = [3.8856, 4.1820, 2.3040, 1.0197, 0.4295,
         1.5178, 0.3853, 4.2848, 4.30911,3.2299,
         1.8528, 0.6553, 3.3305, 4.1504, 1.8787]
    z = np.linspace(0,5,8)
    for i in t:
        if i>=z[0] and i<z[1]:
            n.extend([0,0,0,0,0])
        elif i>=z[1] and i<z[2]:
            n.extend([0,0,0,0,1])
        elif i>=z[2] and i<z[3]:
            n.extend([0,0,0,1,0])
        elif i>=z[3] and i<z[4]:
            n.extend([0,0,0,1,1])
        elif i>=z[4] and i<z[5]:
            n.extend([0,0,1,0,0])
        elif i>=z[5] and i<z[6]:
            n.extend([0,0,1,0,1])
        elif i>=z[6] and i<z[7]:
            n.extend([0,0,1,1,0])
    return np.asarray(n).reshape(len(t),5)


def f3(): # answered by Kostas Mouratidis ######################################
    n = []
    t = [3.8856, 4.1820, 2.3040, 1.0197, 0.4295,
         1.5178, 0.3853, 4.2848, 4.30911,3.2299,
         1.8528, 0.6553, 3.3305, 4.1504, 1.8787]
    z = np.linspace(0,5,8)
    bins = np.digitize(t, z) - 1  # minus 1 just to align our shapes
    patterns = np.array([
        [0, 0, 0, 0, 1],
        [0, 0, 0, 0, 1],
        [0, 0, 0, 1, 0],
        [0, 0, 0, 1, 1],
        [0, 0, 1, 0, 0],
        [0, 0, 1, 0, 1],
        [0, 0, 1, 1, 1],
    ])
    inds = np.zeros((len(t), len(z) - 1), dtype=int)
    inds[np.arange(len(t)), bins] = 1
    inds = inds @ patterns
    return inds

# Testing ... ##################################################################


def correct_cpu(cpu_time):
    pv1, pv2, _ = platform.python_version_tuple()
    pcv = platform.python_compiler()
    if pv1 == '3' and '5' <= pv2 <= '8' and pcv == 'Clang 6.0 (clang-600.0.57)':
        cpu_time /= 2.0
    return cpu_time


def test(test_function, test_loops, test_name):
    t = time.perf_counter()
    c = time.process_time()
    test_result = []
    for j in range(0, test_loops):
        test_result = test_function()
    t = time.perf_counter() - t
    c = correct_cpu(time.process_time() - c)
    print('%.4f  %.4f %s' % (t, c, test_name))
    return test_result

print('Python version  :', platform.python_version())
print('       build    :', platform.python_build())
print('       compiler :', platform.python_compiler())
print()
loops = 100000
f2test = [(f1, 'proposed by Alexander Lopatin'),
          (f2, 'original by motaha'),
          (f3, 'proposed by Kostas Mouratidis')]
print('Time    CPU for', loops, 'loops')

results = []
for func, name in f2test:
    results.append(test(func, loops, name))

original = 1
_, name = f2test[original]
print('\nthe final pattern I want! ' + name)
print(results[original])
for order, result in enumerate(results):
    if order == original:
        continue
    _, name = f2test[order]
    error = False
    for i_row, row in enumerate(result):
        for j_column, value in enumerate(row):
            if value != results[original][i_row][j_column]:
                error = True
                print('\n*** Check for ERRORS in (%d,%d) %s '
                      % (i_row, j_column, name))
                break
        if error:
            break
    if error:
        print(result)
    else:
        print('The same ' + name)

Output:

Python version  : 3.8.0a2
       build    : ('v3.8.0a2:23f4589b4b', 'Feb 25 2019 10:59:08')
       compiler : Clang 6.0 (clang-600.0.57)

Time    CPU for 100000 loops
1.7444  1.7400 proposed by Alexander Lopatin
5.2813  5.2770 original by motaha
4.6203  4.6117 proposed by Kostas Mouratidis

the final pattern I want! original by motaha
[[0 0 1 0 1]
 [0 0 1 0 1]
 [0 0 0 1 1]
 [0 0 0 0 1]
 [0 0 0 0 0]
 [0 0 0 1 0]
 [0 0 0 0 0]
 [0 0 1 0 1]
 [0 0 1 1 0]
 [0 0 1 0 0]
 [0 0 0 1 0]
 [0 0 0 0 0]
 [0 0 1 0 0]
 [0 0 1 0 1]
 [0 0 0 1 0]]
The same proposed by by Alexander Lopatin

*** Check for ERRORS in (4,4) proposed by Kostas Mouratidis 
[[0 0 1 0 1]
 [0 0 1 0 1]
 [0 0 0 1 1]
 [0 0 0 0 1]
 [0 0 0 0 1]
 [0 0 0 1 0]
 [0 0 0 0 1]
 [0 0 1 0 1]
 [0 0 1 1 1]
 [0 0 1 0 0]
 [0 0 0 1 0]
 [0 0 0 0 1]
 [0 0 1 0 0]
 [0 0 1 0 1]
 [0 0 0 1 0]]

This gives me the exact same time as my implementation, but the use of itertools was nice to see. +1 — Kostas Mouratidis, Mar 12 '19 at 10:06

score 0 · Answer 3 · answered Mar 12 '19 at 00:35

In Python there isn't really a way to condense unlike the Java switch case. If you really want to spend some time, there's this tutorial to build your own switch case in Python.

Otherwise the only real improvement that can be made is condensed comparisons like z[0]<=i<z[1].

Replace items in list with another items (small lists) depending on several conditions

3 Answers3