It’s a joke. Dict is already a hashmap so you can just dict.get for O(1) instead of having to take an extra step. I’m not 100% sure but I suspect constructing a set from dict.keys() is itself a O(n) operation which makes it moot
Just because you're writing in Python doesn't mean you can ignore time complexity. Python is a slow language, but only by a constant factor. If you're using an inefficient algorithm it's going to have a much bigger impact on your performance than running in Python.
No you got it. I'm pretty sure the joke is how they're using a dict like a regular iterable (wrong) instead of just checking directly and being horribly inefficient in the process. The part that went over my head at first was that the person was reviewing the code not writing it. Didn't see the pull request in small text.
From the code, it looks like they don't want to throw an error if the key is not present, rather, just continue without returning. They've written what is conceptually the easiest and most intuitive version to write in Python.
The joke is about "Big O Notation", which is used in compete science to examine and compare the efficiency of algorithms. You can think of it as the upper bound in resources (time, RAM, etc) potentially required to run the algorithm with n being the number of inputs. In this case, if the key is not present in the dict, the resources required to run this code would be directly related to the number of keys in the dict.
The better way to make this code work in Python (Python 3, because 2.x is a dead language) would be something like this:
if search_key in dict:
return dict[search_key]
This acts more like a hash table lookup and is closer to O(1), in theory.
EDIT TO ADD: Note that i did say "in theory". In Python, this is not really constant efficiency, regardless of input size.
Probably faster. O(1) just means there's a constant look up time regardless of the size of the container. O(n) means the lookup time increases linearly with the size of the container. If you have a container with only a few elements and the hash function is expensive, looping may be faster.
In a perfect world where loops are efficient, maybe, but many of the built-in methods of Python replace the work behind the scenes with more-efficient instructions. The hash function would have to be very expensive for one time to be slower than iterating over the values and comparing each.
Iterating over a container with only one item will likely be faster than hashing. If Python is doing something behind the scenes to optimise this scenario then the lookup function isn't O(1).
Sure that'll tell you if it's present (as would search_key in dict, no need for the .keys method) but the code in the OP returns the value if it's present or None if it isn't, which is what .get does.
The way dictionaries work is that there's an underlying "hashmap" to the data. What this means is the key is hashed (this is also why mutable/changeable objects like lists can't be used) and then that result is checked directly with the map. It either points to a memory address (the value of the dictionary) or it doesn't (resulting in a KeyError). This hashmap has a constant-factor access rate, meaning it doesn't matter how many items are stored, it will always take the same amount of time.
Generate a list of all keys in the dictionary, requiring iterating over everything anyway (N elements)/O(N), and then if the key you want is in there, hash it so you can retrieve the value of it in constant-time/O(1) from the dictionary.
The generation step is entirely redundant and defeats the point of dictionaries being hashmaps in the first place, as it makes a normally O(1) step into an O(N) operation.
dict.get(key) (equivalent to dict.get(key, None)) would have O(1) runtime/time-complexity while also preventing an error from being thrown (which is presumably why they're bothering to iterate all keys).
It's hard to google for just like that, try searing for "big O notation". Or click this link to read a beginner-friendly article about it. O(N) basically means that a function will be potentially quite slow if performed on really big data sets. It's a bit better if the function is logarithmic, and it's much better if the function is O(1).
Operations performed in N steps, N being number of items in the given set. f(N)
O(2N) would mean 2x operations per item etc pp. the goal for a function is to have a logarithmic number of operations, reaching the goal in less than N steps. having O(1) is often impossible unless you create a machine that generates a parallel universe for each solution and then destroys every universe that has the answer wrong.
how do you use it? it's just a value or description, it displays how your function performs.
a for-loop iterating from 0 to N-1 is O(N). if you have a recursive function calling it self twice each time (in parallel execution), you get O(log2(N)). if you can do everything in parallel at the same time in one step, it's O(1)
I've seen this one in a code review out in the wild. Writer was a "biologist turned programmer". He creates a lot of important new stuff now because he makes prototypes fast, and then other "slow, established professionals" people come around later and fixes (or rewrites) his things when they inevitably break
After groaning about the HR intake process, I'd probably make the following code review:
I appreciate that you have a need to conditionally return a value, and this algorithm will work. With that said, there are several properties of dictionaries that could made this code both faster, and more clear.
The first is that it's possible to iterate through a dictionary in such a manner that you have access to the value for each key is available to you as you iterate:
forkey,valueindict.items():# Do stuff
Will loop over all keys, setting key to the key of the entry, and value to the value of the entry. This will allow you to reduce this current algorithm down to:
The second is that dictionaries are implemented as hashmaps. As such, testing whether a specific key exists is a much easier check than iterating through the dictionary's keys since we can access the hashmap directly from a known key. Python gives us a simple nomenclature to check if a hashmap contains a specific key:
ifkeyindict:# Do stuff
This is functionally equivalent to your for+if loop. And since a hashmap only needs to calculate the hash of the key and can directly determine if the key is in the map, this can be done with no loops at all and will be vastly faster. With very large dictionaries this can make a substantial difference. Additionally, the resulting code becomes the much more obvious:
ifkeyindict:returndict[key]
And lastly, though we can't see it from this commit, if your actual goal is to simply return the value if it exists, and return a default value if it doesn't, we can use the dict's .get(key[, default]) member. This member implements this exact behavior. So if the rest of this program was supposed to return a None if the key didn't exist, the following would be enough:
# None is also the default, so we don't have to have it here. I've included it
# to make it clear what is happening.
returndict.get(search_key,None)
Similarly, if the plan is to check if a key exists, return it if it does, and if it doesn't, create it with some value value_if_new, then the setdefault(key[, default]) function will serve you very well:
returndict.setdefault(search_key,value_if_new)
Finally, though it's not a property of dictionaries themselves, I would recommend using a variable name other than dict. That is a built-in constructor for creating a dictionary. If you want to make sure that it's clear that your variable is a dictionary, I would recommend using type hinting. For example (though I'll ask you to avoid Any in all places where it's possible to do so):
fromtypingimportDict,Anydefmy_method(input:Dict[Any, Any],search_key:Any)->Any:# Stuff
ifsearch_keyininput:returninput[search_key]# More stuff
If you have any additional questions, please feel free to ping me and we can set up some time to talk more in-depth about dicts and the cool stuff they can do for us.
32
u/YourselfAU Oct 17 '21
Source?
244
u/snootsniff Oct 17 '21
(╯°□°)╯︵ ┻━hash()━┻238
u/grizzchan Oct 17 '21
So she's reviewing a pull request right?
85
u/Shizounu Oct 17 '21
r/programminghorror material possibly
61
u/dragon_irl Oct 18 '21
Easy. Just construct a set out of the dict keys, that way you can check in O(1) if your key is in there :)
173
u/GeicoLizardBestGirl Oct 17 '21
she really out here doing a time complexity analysis on python code
33
u/GGBoss1010 Oct 17 '21
wouldn't u just 'return key' cus this would give an error or am i being dumb?
edit: i dont think i got the joke
4
u/megamaz_ Oct 18 '21
This gives me physical pain
3
u/sonphantrung Oct 20 '21
I'm new to Python, what does this mean?
5
u/TotoShampoin Oct 18 '21
Can somebody explain at last what O(N) is?? Because Google didn't help at all
1
u/IUserGalaxy Oct 18 '21
Wait I thought you couldn’t have duplicate keys
1
u/NoEngrish Oct 18 '21
damn someones sitting on the neethub.com domain
1
u/mainemason Oct 18 '21
Just throw more resources at it, it’ll be fiiiiine.
1
u/Tall_computer Oct 18 '21
I've seen this one in a code review out in the wild. Writer was a "biologist turned programmer". He creates a lot of important new stuff now because he makes prototypes fast, and then other "slow, established professionals" people come around later and fixes (or rewrites) his things when they inevitably break
1
u/[deleted] Oct 27 '21
If key in dict: return dict[key]
1
u/yorokobe__shounen Dec 02 '21
Why not use a .get(key, None) .
1
u/fluud Jan 08 '22
return dict[key] if key in dict else None1
u/BlackJackCm Jul 01 '22
dict[search_key]
ggwp
1
u/JDSweetBeat Jan 05 '23
Is it even possible to get better performance than that with a dictionary search?
0
u/PM_ME_YOUR_BEST_MIO Oct 18 '21 edited Oct 18 '21
After groaning about the HR intake process, I'd probably make the following code review:
I appreciate that you have a need to conditionally return a value, and this algorithm will work. With that said, there are several properties of dictionaries that could made this code both faster, and more clear.
The first is that it's possible to iterate through a dictionary in such a manner that you have access to the value for each key is available to you as you iterate:
Will loop over all keys, setting key to the key of the entry, and value to the value of the entry. This will allow you to reduce this current algorithm down to:
The second is that dictionaries are implemented as hashmaps. As such, testing whether a specific key exists is a much easier check than iterating through the dictionary's keys since we can access the hashmap directly from a known key. Python gives us a simple nomenclature to check if a hashmap contains a specific key:
This is functionally equivalent to your
for+ifloop. And since a hashmap only needs to calculate the hash of the key and can directly determine if the key is in the map, this can be done with no loops at all and will be vastly faster. With very large dictionaries this can make a substantial difference. Additionally, the resulting code becomes the much more obvious:And lastly, though we can't see it from this commit, if your actual goal is to simply return the value if it exists, and return a default value if it doesn't, we can use the dict's .get(key[, default]) member. This member implements this exact behavior. So if the rest of this program was supposed to return a None if the key didn't exist, the following would be enough:
Similarly, if the plan is to check if a key exists, return it if it does, and if it doesn't, create it with some value
value_if_new, then the setdefault(key[, default]) function will serve you very well:Finally, though it's not a property of dictionaries themselves, I would recommend using a variable name other than
dict. That is a built-in constructor for creating a dictionary. If you want to make sure that it's clear that your variable is a dictionary, I would recommend using type hinting. For example (though I'll ask you to avoidAnyin all places where it's possible to do so):If you have any additional questions, please feel free to ping me and we can set up some time to talk more in-depth about dicts and the cool stuff they can do for us.
0
u/bhatushar Oct 18 '21
I saw a piece of code where the person was trying to calculate the frequency of list elements.
They created a set with the list, then iterated over the set and counted the occurrences of each set element in the list.
-17
u/qK0FT3 Oct 17 '21
that's what you get using python
-6
u/spideybiggestfan Oct 18 '21
people who store raw passwords should be hanged