How to check the existence of a value with specific pattern in the dictionary?

user_7206268 0
Viewed 63

I would like to find value(s) in the dictionary that the first N characters are same as another string.

For example:

I would like to get all values that first 4 characters are "abcd" and return its key

string = "abcd"

dict = {'k1' : 'abcd4545', 'k2' : 'abab1234', 'k3' : 'abcd789456'}

Result: k1 and k3 should be returned

I think it can be done by looping all the values in the dictionary and getting the first N characters for comparing.

But I need to handle a dictionary with large amount of data, is there any better way to do this?

dictionary python
4 Answers

For sure, there are no other solution than parsing all your values and test each and every one of them, without more information about your data.

No solution can do better (i.e. do less operations) than looping through the whole dictionary because you need to parse them all to be sure to retrieve all of them.

user_120675600

No, there is no other solution than iterating over the values and checking the condition, the loop can be achieved with list comprehension:

[k for k, v in dict.items() if v.startswith(string)]
user_32864870

If you only want to do the operation once, then there is possibly no way other than looping through all of the values. But, if you need to do this operation repeatedly and you want to improve time performance, I would suggest to do some pre-processing here. For example, you can generate the reverse map of this dictionary i.e something like.

reverse_dict = {v:k for (k,v) in dict} Here, V can be an array of Ks like {v1 : [k1,k5], v2 : [k3], v3....}

Now, you may create buckets based on say first letter from the above reverseMap. If the first letter is only english alpha-numeric, you will only have (26 + 10) buckets. If you can do with two letters, that would be 36 * 36 buckets. I am talking about something of a Trie data structure. Then, you may search on linearly inside the buckets. This can give you almost constant time performance with some extra memory use. If you have a really large amount of data that you cannot hold in modern RAM sizes, then you may have to distribute these buckets across various systems and use the same technique. This can drastically improve performance. Simply distributing linear search task across a cluster of machines can also work in that case, where each machine upon completion returns the result of keys [k1, k2... kn] and you finally club the results.

user_26667080 
string = "abcd"
dic = {'k1' : 'abcd4545', 'k2' : 'abab1234', 'k3' : 'abcd789456'}

for key, val in dic.items():
    if string == "".join(list(val)[:len(string)]):
        print(key)
    else:
        pass

It looks through the first four letters in the dict values (does this by listing all the characters and joining only the first four). If it's equal to the desired string, it prints the key.

The complexity however grows with the length of the dictionary and the length of the values in it since it creates a list of all characters in the values. So I think the code can be improved and optimised.

Im sure you can optimise it but thats how I'd do it.

user_101493180
Related