Efficient method to go through 2 lists and build a relative-Dictionary

user_6604134 0
Viewed 74

Say I have 2 lists:

list_a=[1, 5, 10, 11]
list_b = [2, 3, 4, 6, 7, 8, 9, 12, 13]

I want to create the following dictionary:

[{1: [2, 3, 4]}, {5: [6, 7, 8, 9]}, {10: []}, {11:[12,13]}]

such that any numbers in list_b that are higher than an item in list_a but less than a succeeding item in the same list are appended together in a list.

Please let me know if you have any doubts about the question.

My attempt:

for x in range(len(list_a)-1):
    temp=[]
    for y in range(x,len(list_b)):
        if list_b[y] < list_a[x+1] and list_b[y]>list_a[x]:
            temp.append(list_b[y])


result.append({list_a[x]:temp})
python-3.x list python
4 Answers

An inefficient two-liner, without requirement for B to be sorted:

A = [1, 5, 10, 11]
B = [2, 3, 4, 6, 7, 8, 9, 12, 13]

d = {
    x: [v for v in B if x < v < y]
    for x, y in zip(A, A[1:] + [float('inf')])
}

print(d)

More verbose and more efficient:

A = [1, 5, 10, 11]
B = [2, 3, 4, 6, 7, 8, 9, 12, 13]

cur, nxt = A[0], A[1]
k = 1
i = 0
d = {}

while i < len(B):
    d[cur] = []
    
    while i < len(B) and B[i] < nxt:
        d[cur].append(B[i])
        i += 1

    cur = nxt
    k += 1
    nxt = A[k] if k < len(A) else float('inf')

print(d)

If you want a list of dicts instead of a single dict, you can convert it later on:

list_of_dicts = [{k: v} for k, v in my_dict.items()]
user_9891210

I'd use this approach. Using those lists, so you can check boundary elements:

list_a = [1, 5, 10, 11, 14]
list_b = [1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 15]

First define a method that returns consecutive elements from the list, as generator:

def each_cons(iterable, n = 2):
    if n < 2: n = 1
    i, size = 0, len(iterable)
    while i < size-n+1:
        yield iterable[i:i+n]
        i += 1

It works this way (remember that you can use the variable containing the generator once, that's why I commented out the second line here below):

cons_a = each_cons(list_a)
# list(cons_a)
#=> [[1, 5], [5, 10], [10, 11], [11, 14]]

Then use the generator to chunk list_b as desired:

chunks = []
for start, stop in cons_a:
    chunks.append([e  for e in list_b if e > start and e < stop])
    last_stop = stop
# maybe check if the last chunk is missing
chunks.append([e  for e in list_b if e > last_stop])

The variable chunks now contains:

#=> [[2, 3, 4], [6, 7, 8, 9], [], [12, 13], []]

Finally just zip list_a with chunks and call dict() on it:

dict(zip(list_a, chunks))
{1: [2, 3, 4], 5: [6, 7, 8, 9], 10: [], 11: [12, 13], 14: [15]}
user_52390300

O(n) solution with only 1 for loop. Idea is to keep 2 pointer's and add items using those 2 pointers.

a = [1, 5, 10, 11]
b = [2, 3, 4, 6, 7, 8, 9, 12, 13]

i, j = 0, 1
result = {}
temp = []
while i <= len(b):
    if j == len(a):
        result[a[j-1]] = b[i:]
        break
    elif b[i] < a[j]:
        temp.append(b[i])
        i += 1
    else:
        result[a[j-1]] = temp
        temp = []
        j += 1

print(result)
user_154380330

You could try to iterate over the lists from right to left, as shown in the following example.

list_a = [1, 5, 10, 11]
list_b = [2, 3, 4, 6, 7, 8, 9, 12, 13]

dct = dict()
for a in reversed(list_a):
    dct[a] = list()
    for b in reversed(list_b):
        if b > a:
            dct[a].append(list_b.pop())
        else:
            break

print(dct)
#Out[21]: {11: [13, 12], 10: [], 5: [9, 8, 7, 6], 1: [4, 3, 2]}
user_119717850
Related