[Tutor] Program gets stuck after a creating a list from dictinary items!

[Steven D'Aprano]

Ali Torkamani wrote:
> I could resolve it by defining a small function:
> 
> def getValue(mydict,keys):
>     A=[];
>     for i in keys:
>         A=A+[mydict[i]]
>     return A


That will be terribly, painfully inefficient for large amounts of data. Do you 
understand Big O notation? The above is O(N**2), compared to O(N) for a list 
comprehension. That means that the amount of work it does increases like the 
square of the number of keys:

- if you double the number of keys, the list comp will do twice as much
   work, but getValue will do four times as much work;

- if you increase the number of keys by 100, the list comp has to do
   100 times more work, but getValue has to do ten thousand times more!


You really want to avoid O(N**2) algorithms.

http://www.joelonsoftware.com/articles/fog0000000319.html

You can fix that and make it O(N) by using list append instead:

def getValue(mydict, keys):
     A=[];
     for key in keys:
         A.append(mydict[key])
     return A

which is a literally translation of the list comprehension
A = [mydict[key] for key in keys]



P.S. please improve your naming conventions. If you have a list of keys, you 
should not use "i" for each key. "i" should only be used for iterating over 
lists of integers.



-- 
Steven