– –

View Github Repository Open presentation in a new window

hotienvu

See all presentation from hotienvu

– –

0 0

pyconjp-fun-with-algorithms

presentation slides for pycon japan 2012

On Github hotienvu / pyconjp-fun-with-algorithms

Fun with Algorithms and Data Structures in Python

Ho Tien Vu

htvu.net

htvu@tuyt.vn

github.com/hotienvu

Readability counts

def sort(alist):
    if not alist:
        return []
    else:
        pivot = alist[0]
        left = sort([x for x in alist[1:] if x<pivot])
        right = sort([x for x in alist[1:] if x>=pivot])
        return left + [pivot] + right
                                
# qsort(list)
#    if list is empty
#        return empty list
#    else
#        pivot <-- any element inside list
#        left <-- all elements less than pivot
#        right <-- all elements greater than pivot
#        return (left + pivot + right)
        
                                

def partition(alist, left, right):
    pivot = right
    pivotValue = alist[right]
    idx = left
    for i in xrange(left, right):
        if alist[i] < pivotValue:
            alist[i], alist[idx] = alist[idx], alist[i]
            idx += 1
    alist[idx], alist[right] = alist[right], alist[idx]
    return idx

def qsort2(alist, start, end):
    if start < end:
        idx = partition(alist, start, end)
        qsort2(alist, start, idx-1)
        qsort2(alist, idx+1, end)

Simple is better than complex

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, 
by definition, you will not be smart enough to debug it."
Brian W. Kerninghan

Fundamental data types: list

  • Implemented using dynamic size array
    • append(), pop(), random access: O(1)
    • index(), remove(), insert(): O(n)
  • Can be used to implement a stack, queue.
    • Queue
    • deque
  • List vs Array
  • List can store arbitrary object
  • Array is a thin wrapper of the the C array

Fundamental data types: dict

  • Implemented using hash table
    • insert, retrieve, update ~O(1)
    • array starts with 8 elements, double once 2/3 are full
    • open adressing(random probing) for handling collision

Fundamental data types: dict

Applications: collections of unique entities graph, trie, hashmap, etc collections.Counter 
from collections import Counter
c = Counter('abcbacbdef')
print c
Counter({'b': 3, 'a': 2, 'c': 2, 'e': 1, 'd': 1, 'f': 1})

The python way: dynamic programming

class memoized(object): 
    def __init__(self, func):
        self.func = func
        self.cache = {}
    def __call__(self, *args):
        try: 
            if args in self.cache:
                return self.cache[args]
            else:
                value = self.func(*args)
                self.cache[args] = value
                return value
        except KeyError, TypeError:
            return self.func(*args)
    def __get__(self, obj, objtype):
        return functools.partial(self.__call__, obj)

The python way: dynamic programming

# nth fibonacci number
@memoized
def fibonacci(n):
   if n in (0, 1):
      return n
   return fibonacci(n-1) + fibonacci(n-2)
                    

#longest increasing subsequence
@memoized
def lis(alist, n):
    if n==0:
        return 1 
    result = 0
    for i in xrange(n+1):
        if alist[i]<alist[n]:
            result = max(result, lis(alist, i))+1
    return result

The python way: sorting

# sorting list of tuples
students = [('Andy', 'C', 1), ('Dave', 'B', 3), ('Peter', 'A', 2)]
sorted(students)
sorted(students, key=lambda student: (student[1], 
                                      student[0], 
                                      student[2]))
sorted(students, key=student.name)
from operator import itemgetter, attrgetter
sorted(students, key=itemgetter(0,1))
sorted(students, cmp=compare(s1, s2)) # deprecated in 3+

Conclusion

◄ ► ▲ ▼