Efficient way to merge two dimensional array

Question

I want to merge two lists which contain same number.
Each list contains unique number and never matches more than one row of the other list.
([2, 1, 3, 4, 5] of listA only match a single row [1, 4, 3, 10] of listB)

I wrote my code below in Python. Is there more efficient way to merge two lists? Though the sample code has only 3 length of list, I expect the length of the list is much more like 1k, so I want to find more efficient way.

listA = [
  [2, 1, 3, 4, 5],
  [50, 56, 60, 51],
  [101, 112, 115, 110],
]

listB = [
  [50, 63, 70],
  [1, 4, 3, 10],
  [120, 112, 116, 113],
]

mapA = {}

for idx, list_a in enumerate(listA):
    for item in list_a:
        mapA[item] = idx

result = []

for list_b in listB:
    for item in list_b:
        if item in mapA:
            idx_of_listA = mapA[item]
            nums = set(listA[idx_of_listA] + list_b)
            result.append(nums)
            break

print(result)
# [{70, 50, 51, 56, 60, 63}, {1, 2, 3, 4, 5, 10}, {101, 110, 112, 113, 115, 116, 120}]

But you don't quite merge them? `{1, 2, 3, 4}` where are 5 and 10? — yatu, Mar 12 '20 at 14:10
The result you indicate is not the result that this code actually produces. What is the desired output? It'd be helpful if you spent a few sentences on explaining the "merging" algorithm. — a_guest, Mar 12 '20 at 14:12

score 2 · Accepted Answer · answered Mar 12 '20 at 14:11

2

This looks like a connected components problem, you can use networkX to find them (just adapting my answer from the dupe):

import networkx as nx 

G=nx.Graph()
for l in [listA, listB]:
    for sl in l:
        nx.add_path(G, sl)
list(nx.connected_components(G))

[{1, 2, 3, 4, 5, 10},
 {50, 51, 56, 60, 63, 70},
 {101, 110, 112, 113, 115, 116, 120}]

answered Mar 12 '20 at 14:11

yatu

86,083
12
84
139

This seems to work for the example in the OP but only since rows are not interconnected. If they were then that would add another item to the resulting list for the OP's code but not in your example. For example add `[51, 52]` to `listB`. – a_guest Mar 12 '20 at 14:16
Yes that is true, this works under these specific conditions mentioned by OP `never matches more than one row of the other list.` @a_guest – yatu Mar 12 '20 at 14:17
Ah, I missed that specification. Thanks for clarifying. But is it actually faster than OP's code? – a_guest Mar 12 '20 at 14:18
In that case, implementation via connected components seems like an overkill. Using a map would be much easier. – nice_dev Mar 12 '20 at 14:19
1

@yatu No wait, adding `[51, 52]` actually doesn't infringe that requirement. Each number still matches at most one row of the other array, but yet the outputs are different. – a_guest Mar 12 '20 at 14:21

Efficient way to merge two dimensional array

1 Answers1