13

I have a dict that has string-type keys whose exact values I can't know (because they're generated dynamically elsewhere). However, I know that that the key I want contains a particular substring, and that a single key with this substring is definitely in the dict.

What's the best, or "most pythonic" way to retrieve the value for this key?

I thought of two strategies, but both irk me:

for k,v in some_dict.items():
    if 'substring' in k:
        value = v
        break

-- OR --

value = [v for (k,v) in some_dict.items() if 'substring' in k][0]

The first method is bulky and somewhat ugly, while the second is cleaner, but the extra step of indexing into the list comprehension (the [0]) irks me. Is there a better way to express the second version, or a more concise way to write the first?

9
  • Both of them look pretty concise as compared to most othe languages. But I think the first one is more readable.
    – Keith
    Commented Aug 13, 2011 at 7:54
  • 1
    Why do you know about the substring? Is there any more information available to you? Could you do some kind of parsing/transformation on the dict? Will you be doing a lot of similar lookups on the same dict? Commented Aug 13, 2011 at 8:09
  • You should try k.startswith('substring') or k.endswith('substring') if it's at the beginning or end; they may be faster.
    – agf
    Commented Aug 13, 2011 at 8:21
  • 1
    If that lookup all what you have the some_dict for then it's entirely useless and a list would be better. If you have a list of substrings you want to match you'll have a time complexity of O(N**2). You'd need a index over the keys to do this efficiently though, full text search engines like Sphinx do that basically. Commented Aug 13, 2011 at 9:41
  • 1
    first method is bulky and somewhat ugly, while the second is cleaner small comment here: second is not cleaner, it just has less \n characters. There is some strange belief that single-liners work faster and are more readable. They are not.
    – Jakub M.
    Commented Aug 13, 2011 at 10:21

5 Answers 5

10

There is an option to write the second version with the performance attributes of the first one.

Use a generator expression instead of list comprehension:

value = next(v for (k,v) in some_dict.iteritems() if 'substring' in k)

The expression inside the parenthesis will return an iterator which you will then ask to provide the next, i.e. first element. No further elements are processed.

10
  • Definitely use iteritems on Python 2; otherwise this is my preferred way.
    – agf
    Commented Aug 13, 2011 at 8:07
  • @agf: thanks for catching the glitch. Using items() would make no sense at all, actually.
    – blubb
    Commented Aug 13, 2011 at 8:09
  • 1
    This is a neat trick. I would be tempted to write first = next somewhere to make it read even more clearly... although the first = next line itself would be kind of a WTF I suppose o_O Commented Aug 13, 2011 at 8:10
  • @Karl made me laugh out loud. Do you have a separate account you use while not at home? Why?
    – agf
    Commented Aug 13, 2011 at 8:13
  • @agf I'm paranoid about using anything I need a login for, when not on my own computer. So this is just a temporary ID, not even registered. Probably not worth worrying about but you never know really.... Also I'm not entirely sure what password I'm using for SO, I think it might be a randomly generated one... should check my notes when I get home >_< Commented Aug 13, 2011 at 8:17
1

How about this:

value = (v for (k,v) in some_dict.iteritems() if 'substring' in k).next()

It will stop immediately when it finds the first match.

But it still has O(n) complexity, where n is the number of key-value pairs. You need something like a suffix list or a suffix tree to speed up searching.

2
  • This is something I considered, but I personally found it "more ugly" than the list comprehension I presented. Simon's answer solves the ugliness problem, but you're right that this solution is better than the one I presented, at least in terms of performance. Commented Aug 13, 2011 at 17:37
  • The free next function can also be used to specify a default value to return if the .next() call upon the iterator raises StopIteration. Commented Aug 13, 2011 at 21:59
1

If there are many keys but the string is easy to reconstruct from the substring, then it can be faster reconstructing it. e.g. often you know the start of the key but not the datestamp that has been appended on. (so you may only have to try 365 dates rather than iterate through millions of keys for example). It's unlikely to be the case but I thought I would suggest it anyway. e.g.

>>> names={'bob_k':32,'james_r':443,'sarah_p':12}
>>> firstname='james' #you know the substring james because you have a list of firstnames
>>> for c in "abcdefghijklmnopqrstuvwxyz":
...     name="%s_%s"%(firstname,c)
...     if name in names:
...             print name
... 
james_r
1
  • Thankfully, I don't have quite so huge of a dict that this kind of strategy would be necessary, but it is a novel idea I hadn't thought of. +1 Commented Aug 13, 2011 at 17:38
1
class MyDict(dict):
    def __init__(self, *kwargs):
        dict.__init__(self, *kwargs)

    def __getitem__(self,x):
        return next(v for (k,v) in self.iteritems() if x in k)



# Defining several dicos ----------------------------------------------------    
some_dict = {'abc4589':4578,'abc7812':798,'kjuy45763':1002}

another_dict = {'boumboum14':'WSZE x478',
                'tagada4783':'ocean11',
                'maracuna102455':None}

still_another = {12:'jfg',45:'klsjgf'}



# Selecting the dicos whose __getitem__ method will be changed -------------       
name,obj = None,None
selected_dicos = [ (name,obj) for (name,obj) in globals().iteritems()
                   if type(obj)==dict
                   and all(type(x)==str for x in obj.iterkeys())]

print 'names of selected_dicos ==',[ name for (name,obj) in selected_dicos] 



# Transforming the selected dicos in instances of class MyDict -----------
for k,v in selected_dicos:
    globals()[k] = MyDict(v)



# Exemple of getting a value ---------------------------------------------      
print "some_dict['7812'] ==",some_dict['7812']

result

names of selected_dicos == ['another_dict', 'some_dict']
some_dict['7812'] == 798
4
  • What doesn't please to the downvoter in my answer ?? SO shouldn't allow downvotes without a comment
    – eyquem
    Commented Aug 13, 2011 at 11:57
  • @Jakub Mikians Thank you, but I would like even more to understand what is reproached to my answer
    – eyquem
    Commented Aug 13, 2011 at 13:25
  • I think this is a pretty interesting idea, but you were a bit more verbose than necessary. I'm fairly sure that defining the __init__ function for MyDict is superfluous, since MyDict will use dict's __init__ if it doesn't have one of it's own. Since your solution utilizes the same basic answer as Simon's, I think it has merit for anyone who wants a more complicated solution to a problem like this. Commented Aug 13, 2011 at 17:43
  • This answer basically takes the simple approach and somewhat dubiously wraps it in a class, then shows a bunch of boilerplate usage of a class whose usage ought to be self-explanatory, using what is normally considered fairly deep magic in order to transform a dict in place. Oh, and there's a list comprehension that's then fed directly to a for-loop where it would have been simpler to just loop directly, and the decision of which dicts to wrap is based on explicit type-checking (frowned upon in general). In short, this is horribly un-Pythonic. Commented Aug 13, 2011 at 22:04
0

I prefer the first version, although I'd use some_dict.iteritems() (if you're on Python 2) because then you don't have to build an entire list of all the items beforehand. Instead you iterate through the dict and break as soon as you're done.

On Python 3, some_dict.items(2) already results in a dictionary view, so that's already a suitable iterator.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.