Merge list into sparse list efficiently

Question

I have two lists:

a = [None, None, 1, None, 4, None, None, 5, None]
b = [7,8,2,3,6,9]

I want to merge them, either to create a new list or just update a, by filling in the Nones with the values from b, so

a = [7,8,1,2,4,3,6,5,9]

What's the most efficient way of doing this?

For extension, I'll be wanting to do this with every permutation of b. Does this allow shortcutting the technique at all?

Can `b` contain less or more elements than necessary? – Mr. T Jun 13 '18 at 08:20 — Mr. T, Jun 13 '18 at 08:20
No - we can assume b is the right size – xorsyst Jun 13 '18 at 08:24 — xorsyst, Jun 13 '18 at 08:24

score 6 · Accepted Answer · answered Jun 13 '18 at 07:24

This is one approach. Using a list comprehension and converting b to a iterator object.

Demo:

a = [None, None, 1, None, 4, None, None, 5, None]
b = [7,8,2,3,6,9]
b = iter(b)

print( [next(b) if i is None else i for i in a] )

Output:

[7, 8, 1, 2, 4, 3, 6, 5, 9]

Sraw · Answer 2 · 2018-06-13T08:03:12.257

3

for reversed_index in range(len(a) - 1, -1, -1):
    if a[reversed_index] is None:
        a[reversed_index] = b.pop()

It should be efficient as it modifies a in place and right popping a list is also efficient. As far as I think, it is an O(len(a)) solution.

edited Jun 13 '18 at 08:03

answered Jun 13 '18 at 07:27

Sraw

18,892
11
54
87

score 3 · Answer 3 · answered Jun 13 '18 at 07:32

3

With list.pop() method on reversed 2nd b list:

a = [None, None, 1, None, 4, None, None, 5, None]
b = [7,8,2,3,6,9]
tmp = b[::-1]

result = [tmp.pop() if i is None else i for i in a]
print(result)    # [7, 8, 1, 2, 4, 3, 6, 5, 9]

answered Jun 13 '18 at 07:32

RomanPerekhrest

88,541
4
65
105

Great solution. In my testing the iterator one is faster still, but it's close. – xorsyst Jun 13 '18 at 10:22

score 1 · Answer 4 · answered Jun 13 '18 at 08:04

Recursive apporach:

a = [None, None, 1, None, 4, None, None, 5, None]
b = [7,8,2,3,6,9]

def recursion_approach(first_list,second_list):

    for index,value in enumerate(first_list):
            if value!=None:
                first_list[index]=value
            else:
                first_list[index]=second_list[0]
                recursion_approach(first_list,second_list[1:])

    return first_list

print(recursion_approach(a,b))

output:

[7, 8, 1, 2, 4, 3, 6, 5, 9]

Nice elegant solution - as you might expect, it's not very fast though. — xorsyst, Jun 13 '18 at 09:58

score 1 · Answer 5 · answered Sep 26 '18 at 08:50

For performance with large lists, you may find 3rd party libraries more efficient, for example via Pandas or NumPy.

pandas

Create 2 series and use assignment with Boolean indexing:

import pandas as pd

a = pd.Series([None, None, 1, None, 4, None, None, 5, None])
b = pd.Series([7,8,2,3,6,9])

a[a.isnull()] = b.values

print(a.values.astype(int).tolist())

# [7, 8, 1, 2, 4, 3, 6, 5, 9]

numpy

Similarly with NumPy provided you use np.nan instead of None:

import numpy as np

a = np.array([np.nan, np.nan, 1, np.nan, 4, np.nan, np.nan, 5, np.nan])
b = np.array([7,8,2,3,6,9])

a[np.isnan(a)] = b

# array([ 7.,  8.,  1.,  2.,  4.,  3.,  6.,  5.,  9.])

See also What are the advantages of NumPy over regular Python lists?.

Merge list into sparse list efficiently

5 Answers5

pandas

numpy