<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Code Optimization in Python
"Premature optimization is the root of all evil." - Donald Knuth
Get it right.
Test it's right.
Profile if slow.
Optimise.
Repeat from 2.
Measuring
Step1:  Profiling
Builtin library in Python providing deterministic profiling of Python programs. Contains two packages
Step2:  For more advanced tool on profiling check this
Step3:  Use available pre-optimized libraries
Step4:  Loops
Step5:  Wait, is this that much faster?
Step6:  Check these builtin functions
Step7:  Caching
Step8:  Name resolution speedups
Step9:  Both newlist.append and word.upper are function references that are reevaluated each time through the loop.
Step10:  Python accesses local variables much more efficiently than global variables.
Step11:  if vs try
trying is cheap, ifing is expensive (when the condition rarely happens to be true)
Step12:  But considering the example above, you might want to use again the stdlib.
Step13:  Imports
importing is very expensive
Step14:  Strings are immutables...
Step15:  So naive concatenating is very expensive, since each "+" creates a new string. Therefore, instead of "+"-ing things together you can use string formatting.
Interpreters
Pypy
"... is a Python interpreter and a just-in-time compiler. It focuses on speed, efficiency and compatibility with CPython. It currently support language versions 2.7.10 and 3.2.5."
Features
<ASSISTANT_TASK:>
Python Code:
import time
def dummy1():
    time.sleep(0.01)
def dummy2():
    time.sleep(0.02)
%%time 
dummy1()
%%time
dummy2()
%%timeit -n 10
dummy1()
%%timeit -n 10
dummy2()
Explanation: Code Optimization in Python
"Premature optimization is the root of all evil." - Donald Knuth
Get it right.
Test it's right.
Profile if slow.
Optimise.
Repeat from 2.
Measuring
End of explanation
import cProfile
cProfile.run('dummy1()',)
Explanation: Profiling
Builtin library in Python providing deterministic profiling of Python programs. Contains two packages: cProfile and profile. Tha former is faster to run, while the latter is easier to extend.
End of explanation
import random
random_list = [random.randint(0, 10000) for i in range(1000000)]
%%timeit -n 10
sorted(random_list)
Explanation: For more advanced tool on profiling check this: http://pycallgraph.slowchop.com/en/master/
Tips and tricks
Use the standard library
Several modules and functions are implemented effectively (in C).
End of explanation
%%timeit -n 10
sum(random_list) / len(random_list)
import numpy as np
random_array = np.array(random_list)
%%timeit -n 10
np.mean(random_array)
Explanation: Use available pre-optimized libraries
End of explanation
oldlist = ["alma"]*10000
%%timeit -n 10
newlist = []
for word in oldlist:
    newlist.append(word.upper())
%%timeit -n 10
newlist = map(str.upper, oldlist)
Explanation: Loops
End of explanation
%%timeit -n 10
newlist = list(map(str.upper, oldlist))
%%timeit -n 10
newlist = [w.upper() for w in oldlist]
Explanation: Wait, is this that much faster?
End of explanation
def firstn1(n):
    num, nums = 0, []
    while num < n:
        nums.append(num)
        num += 1
    return nums
sum_of_first_n = sum(firstn1(1000000))
def firstn2(n):
    num = 0
    while num < n:
        yield num
        num += 1
sum_of_first_n = sum(firstn2(1000000))
Explanation: Check these builtin functions:
* map
* filter
* zip
* range
* sum
* enumerate
* all
* any
... and these packages:
* functools
* itertools
Generators
Generators are a way of declaring a function that behaves like an iterator which evaluates its values lazily. It can save you a both running time and memory.
End of explanation
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)
%%time
x = [fib(n) for n in range(20)]
from functools import lru_cache
@lru_cache(maxsize=None)
def fib2(n):
    if n < 2:
        return n
    return fib2(n-1) + fib2(n-2)
%%time
x = [fib2(n) for n in range(30)]
fib2.cache_info()
Explanation: Caching
End of explanation
%%timeit
newlist = []
for word in oldlist:
    newlist.append(str.upper(word))
Explanation: Name resolution speedups
End of explanation
%%timeit
upper = str.upper
newlist = []
append = newlist.append
for word in oldlist:
    append(upper(word))
Explanation: Both newlist.append and word.upper are function references that are reevaluated each time through the loop.
End of explanation
def func():
    upper = str.upper
    newlist = []
    append = newlist.append
    for word in oldlist:
        append(upper(word))
    #return newlist
%%timeit
func()
Explanation: Python accesses local variables much more efficiently than global variables.
End of explanation
%%timeit
wdict = {}
for word in oldlist:
    if word not in wdict:
        wdict[word] = 0
    wdict[word] += 1
%%timeit
wdict = {}
for word in oldlist:
    try:
        wdict[word] += 1
    except KeyError:
        wdict[word] = 1
Explanation: if vs try
trying is cheap, ifing is expensive (when the condition rarely happens to be true)
End of explanation
from collections import defaultdict
%%timeit
wdict = defaultdict(int)
for word in oldlist:
    wdict[word] += 1
Explanation: But considering the example above, you might want to use again the stdlib.
End of explanation
def doit1():
    import os.path # import statement inside function
    os.path.split('python.py')
import os.path as p # import statement outside function
def doit2():
    p.split('Python')
%%timeit
for _ in range(100000):
    doit1()
%%timeit
for _ in range(100000):
    doit2()
Explanation: Imports
importing is very expensive
End of explanation
def concat1(strings):
    res = ""
    for s in strings:
        res+=s
    return res
def concat2(strings):
    return "".join(strings)
str_list = ["alma"]*10000000
%%timeit
concat1(str_list)
%%timeit
concat2(str_list)
Explanation: Strings are immutables...
End of explanation
from numpy import arange
def sum2d(arr):
    M, N = arr.shape
    result = 0.0
    for i in range(M):
        for j in range(N):
            result += arr[i,j]
    return result
a = arange(9).reshape(3,3)
from numba import jit
# jit decorator tells Numba to compile this function.
# The argument types will be inferred by Numba when function is called.
@jit
def sum2d_numba(arr):
    M, N = arr.shape
    result = 0.0
    for i in range(M):
        for j in range(N):
            result += arr[i,j]
    return result
%%time
sum2d(a)
%%time
sum2d_numba(a)
Explanation: So naive concatenating is very expensive, since each "+" creates a new string. Therefore, instead of "+"-ing things together you can use string formatting.
Interpreters
Pypy
"... is a Python interpreter and a just-in-time compiler. It focuses on speed, efficiency and compatibility with CPython. It currently support language versions 2.7.10 and 3.2.5."
Features:
(In most of the cases) faster than CPython
Eating up less memory.
Cython
"...is an optimistic static compiler for both the Python programming language and the extended Cython langeuage. It makes C extensions for Python as easy as Python itself."
<img src="https://upload.wikimedia.org/wikipedia/commons/e/e0/Cython_CPython_Ext_Module_Workflow.png">
def sum(int a, int b):
    cdef int sum = a+b
    return sum
Numba
Numba gives you the power to speed up your applications with high performance functions written directly in Python. With a few annotations, array-oriented and math-heavy Python code can be just-in-time compiled to native machine instructions, similar in performance to C, C++ and Fortran, without having to switch languages or Python interpreters.
Numba works by generating optimized machine code using the LLVM compiler infrastructure at import time, runtime, or statically (using the included pycc tool). Numba supports compilation of Python to run on either CPU or GPU hardware, and is designed to integrate with the Python scientific software stack.
End of explanation
<END_TASK>