0

I have an iterable of unique numbers:

lst = [14, 11, 8, 55]

where every value is somewhere among numbers of dict's iterable-values, say lists:

dict_itms.items() = dict_items([(1, [0, 1, 2, 3]), (2, [11, 14, 12]), (3, [30, 8, 42]), (4, [55, 6])])

I have to find each lst element in a dict such a way that, finally, I would have a list of keys pairwise against each element in lst.

This method:

keys_ = []
for a in lst:
    for k, v in dict_itms.items():
        if a in v:
            keys_ += [k]
            break
        else:
            continue

gives: [2, 2, 3, 4]

Is there more efficient way to find every key pairwise against each number to find?

Yerbol Sapar
  • 31
  • 1
  • 8
  • As I understood the question is to see if two lists shares any element(s). See: https://stackoverflow.com/a/17735466/2681662. This way you can get rid of one of loops (first looop) – MSH Nov 04 '21 at 06:44
  • all list numbers are unique – Yerbol Sapar Nov 04 '21 at 07:01

3 Answers3

2

You can use any in a list comprehension:

print([k for k,v in dict_itms.items() if any(x in lst for x in v)])

Output:

[2, 3, 4]
Update

According to this answer not set(v).isdisjoint(lst) is the fastest:

print([k for k,v in dict_itms.items() if not set(v).isdisjoint(lst)])
Tranbi
  • 11,407
  • 6
  • 16
  • 33
  • thanks, but looks not as efficient – Yerbol Sapar Nov 04 '21 at 07:04
  • try replacing `any()` with `not set(v).isdisjoint(lst)`. is it much more efficient in your case? – Tranbi Nov 04 '21 at 07:17
  • I see, but it is required "to find every key against each number to find", i.e., there has to be a key in a list against each value to find: len([2, 2, 3, 4]) == len(lst). This concerns Grismar's answer as well – Yerbol Sapar Nov 04 '21 at 08:02
  • Given those requirements I don't know how to further improve your solution. – Tranbi Nov 04 '21 at 09:57
1

A simple and Pythonic implementation:

d = dict([(1, [0, 1, 2, 3]), (2, [11, 14, 12]), (3, [30, 8, 42]), (4, [55, 6])])

xs = [14, 11, 8, 55]

keys = [k for k, v in d.items() if set(v).intersection(xs)]
print(keys)

However, this doesn't duplicate the 2 key, which your example does - not sure if that's behaviour you need?

Grismar
  • 27,561
  • 4
  • 31
  • 54
1

It's unclear what you mean by 'efficient'; do you need this to be efficient in a given pass or in aggregate? The reason I ask is that typically the best way to handle this in aggregate is by doing a pre-processing pass that flips your key-value relation:

reverse_lookup = dict()
for k,v in d.items():
  for i in v:
    keys = reverse_lookup.get(i, [])  # Provide an empty list if this item not yet found
    keys.append(k)
    reverse_lookup[i] = keys

Now that you have your reverse lookup processed, you can use it in a straightforward manner:

result = [reverse_lookup.get(i) for i in lst]
# `result` is actually a list of lists, so as to allow duplicates. You will need to flatten it, or change the reverse lookup to ignore dupes.

The initial processing for the reverse lookup is O(n*m), where n*m is the total length of the original dictionary values summed. However, each lookup for the lst portion is O(1), so if you squint and have enough lookups this is O(p), where p is the length of lst. This will be wildly more efficient than other approaches if you have to do it a lot, and much less efficient if you're only ever passing over a given dictionary once.

Nathaniel Ford
  • 20,545
  • 20
  • 91
  • 102
  • Surely, efficient in aggregate, thanks, it is good idea to get the dict flipped at initial dict creation stage. As we are free to structure 2d data (presented in a dict here) as we like, what would your choice? I thought to compose 2d numpy array and use row index as a dict key here, but np.argwhere(np.isin(d, lst))[:,0] would not work on the ragged array. – Yerbol Sapar Nov 05 '21 at 06:44