Fastest way to consume an iterator with conditions

Question

My iterator is composed of networkx subgraphs and is called subgraph_monomorphisms_iter.

I'm currently iterating through it with a for loop:

import networkx.algorithms.isomorphism as iso
gm = iso.MultiDiGraphMatcher(main_graph, SG, edge_match=iso.categorical_edge_match("label", None))

for subgraph in gm.subgraph_monomorphisms_iter(): # iterator
    print(subgraph)

Each element of this iterator (i.e., subgraph) is a dictionary that looks like:

subgraph_1 = {'1': 'entity1', '2': 'entity10'}
subgraph_2 = {'1': 'entity1', '2': 'entity122'}

I'm trying to set a condition where I'm only interested in subgraphs with new entities (the values of each subgraph):

used_entities = []
subgraphs = []
for subgraph in gm.subgraph_monomorphisms_iter(): # iterator
    entities = list(subgraph.values())
    if not any(elem in used_entities for elem in entities): # check that we haven't seen any of these entities/values before
        used_entities = used_entities + entities
        subgraphs.append(subgraph)

For example, since subgraph_1 and subgraph_2 both have entity1, I'm only interested in one of these subgraphs to be appended to subgraphs.

One issue is that this iterator is HUGE (~100M items), and a second problem is that many of the entities in these subgraphs repeat in order (i.e., one entity is fixed while the others change in some sequence):

subgraph_1 = {'1': 'entity1', '2': 'entity10'}
subgraph_2 = {'1': 'entity1', '2': 'entity122'}
subgraph_3 = {'1': 'entity1', '2': 'entity1223'}
subgraph_4 = {'1': 'entity1', '2': 'entity14'}
subgraph_5 = {'1': 'entity1', '2': 'entity15'}

So it's taking forever to find subgraphs that are unique according to my condition. I found that the fastest way to convert an iterator to a list from this SO is to use

[*iterator]

However, this is also taking forever since the iterator is so big, and it doesn't allow me to set the condition. I'm only interested in getting the first N elements in the iterator that fit my condition, so there's also no need to iterate through the entire thing if not needed.

I thought that an easy solution would be to shuffle the iterator if possible, since then I could hopefully find N elements just by using a for loop (again, it's currently producing elements that are in order). But from this SO I understand that "It's not possible to randomize the yield of a generator without temporarily saving all the elements somewhere". Another idea is to somehow iterate through the iterator in steps (i.e., only read every X elements). If X is sufficiently large then the ordering should not be an issue.

Fastest way to consume an iterator with conditions

0 Answers