Upgrade to Pro — share decks privately, control downloads, hide ads and more …

PyCon Ireland 2013 Saturday Evening Keynote: Te...

PyCon Ireland 2013 Saturday Evening Keynote: Tendayi Mawushe (Demonware)

(via http://python.ie/pycon/2013/talks/mathematics__data_structures___artificial_intelligence__a_celebration_of_python_/)
Mathematics, Data structures & Artificial Intelligence (A celebration of Python)

A light hearted but information heavy look at the cool things that can easily achieved with Python.

PyCon Ireland

October 12, 2013

Transcript

32 slides
  1. x y a c c d a c b d

    w y x z + 0 6 3 5 -4 9 2 4 + x y a b c Vector Matrix
  2. Vector Addition and Subtraction u = [u 1 , u

    2 , ..., u n ] v = [v 1 , v 2 , ..., v n ] u + v = [u 1 + v 1 , u 2 + v 2 , ..., u n + v n ] u - v = [u 1 - v 1 , u 2 - v 2 , ..., u n - v n ] u = [0, 2, 4, 6, 8] v = [1, 3, 5, 7, 9] [ui + vi for ui, vi in zip(u, v)] [ui - vi for ui, vi in zip(u, v)]
  3. Vector-scalar multiplication α = 32 v = [v 1 ,

    v 2 , ..., v n ] α x v = [α x v 1 , α x v 2 , ..., α x v n ] a = 32 v = [1, 3, 5, 7, 9] [a * vi for vi in v]
  4. Dot Product u = [u 1 , u 2 ,

    ..., u n ] v = [v 1 , v 2 , ..., v n ] u·v = Σ k∈D u[k] v[k] u = [0, 2, 4, 6, 8] v = [1, 3, 5, 7, 9] sum(ui * vi for ui, vi in zip(u, v))
  5. 5z + 4y - x = 0 10y - 3x

    = 8 x = 3 Bitmapped Images Systems of Linear Equations
  6. 4z - 1y + 2x + 3w = 20 -2y

    + 7x - 4w = -7 6x + 5w = 4 3w = 6 w = 6/3 = 2 ⇒ x = (4 - 5*2)/6 = -1 ⇒ y = (-7 + 4*2 - 7*-1)/-2 = -4 ⇒ z = (20 + 1*-4 - 2*-1 -3*2)/4 = 3 ⇒
  7. 4z - 1y + 2x + 3w = 20 -2y

    + 7x - 4w = -7 6x + 5w = 4 3w = 6 4z - 1y + 2x + 3w = 20 0z - 2y + 7x - 4w = -7 0z + 0y + 6x + 5w = 4 0z + 0y + 0x + 3w = 6 ⇒
  8. 4 -1 2 3 0 -2 7 -4 0 0

    6 5 0 0 0 3 20 -7 4 6 Left Hand Sides Right Hand Sides
  9. Backward substitution def solve(lhs, rhs): x = [0] * len(lhs)

    for i in reversed(range(len(lhs))): x[i] = (rhs[i] - dot_product(lhs[i], x))/lhs[i][i] return x def dot_product(u, v): return sum(ui * vi for ui, vi in zip(u, v)) if __name__ == "__main__": lhs = [[5, 4, -1], [0, 10, -3], [0, 0, 1],] rhs = [0, 11, 3,] print solve(lhs, rhs)
  10. Backward substitution ~/pycon2013/matrix$ python triangular.py [-1, 2, 3] def solve(lhs,

    rhs): x = [0] * len(lhs) for i in reversed(range(len(lhs))): x[i] = (rhs[i] - dot_product(lhs[i], x))/lhs[i][i] return x 5z + 4y - x = 0 5z = 0 - 4y + x 10y - 3x = 11 ⇒ 10y = 11 + 3x x = 3 x = 3 rhs - x·lhs = 11 - [0, 0, 3]·[0, 10, -3] = 11 - (0*0 + 0*10 + -3*3) = 11 - (-9) = 20
  11. Comparing voting records Y = Yay N = Nay A

    = Abstained Free Childcare Solar Deathray Kang A N N Y N Y Y A Kodos N Y Y A N N Y N John Jackson N Y N N Y A A Y Jack Johnson Y N N Y Y Y N A
  12. Comparing voting records Free Childcare Solar Deathray Kang 0 -1

    -1 1 -1 1 1 0 Kodos -1 1 1 0 -1 -1 1 -1 John Jackson -1 1 -1 -1 1 0 0 1 Jack Johnson 1 -1 -1 1 1 1 -1 0 kang = [ 0, -1, -1, 1, -1, 1, 1, 0] kodos = [-1, 1, 1, 0, -1, -1, 1, -1] dot = sum(0, -1, -1, 0, 1, -1, 1, 0)
  13. import collections from itertools import product def compare(record): comparisons =

    {} for a, b in product(record, record): if a == b or (b, a) in comparisons: continue comparisons[(a, b)] = dot_product(record[a], record[b]) return comparisons def dot_product(u, v): return sum(ui * vi for ui, vi in zip(u, v)) def order(results): ordered = collections.OrderedDict() for k in reversed(sorted(results, key=results.get)): ordered[k] = results[k] return ordered
  14. kang = [ 0, -1, -1, 1, -1, 1, 1,

    0] kodos = [-1, 1, 1, 0, -1, -1, 1, -1] john = [-1, 1, -1, -1, 1, 0, 0, 1] jack = [1, -1, -1, 1, 1, 1, -1, 0] voting_record = {'Kang': kang, 'Kodos': kodos, 'John': john, 'Jack': jack} if __name__ == '__main__': print order(compare(voting_record)) ~/pycon2013/matrix$ python voting.py OrderedDict([(('Kang', 'Jack'), 2), (('Kang', 'Kodos'), -1), (('John', 'Kodos'), -1), (('John', 'Jack'), -1), (('Kang', 'John'), -2), (('Jack', 'Kodos'), -6)])
  15. Finding an audio clip sample_a = [12, 8, 7, 1,

    0, -14, -12, -5] sample_b = [17, 4, 6, 0, -1, -11, -10, -3]
  16. Finding an audio clip [12, 8, 7, 1, 0, -14,

    -12, -5] [ 7, 1, 0, -14] [12, 8, 7, 1, 0, -14, -12, -5] [7, 1, 0, -14] [12, 8, 7, 1, 0, -14, -12, -5] [7, 1, 0, -14]
  17. import array import collections import contextlib import struct import wave

    def find(clip, files): matches = {} clip_samples = get_samples(clip) for filename in files: file_samples = get_samples(filename) value = match(clip_samples, file_samples) if value: matches[filename] = value return matches def match(clip_samples, samples): expected = dot_product(clip_samples, clip_samples) for i in range(0, len(samples) - len(clip_samples) + 1): dot = dot_product(clip_samples, samples[i:]) if close_enough(expected, dot): return dot def dot_product(u, v): return sum(ui * vi for ui, vi in zip(u, v)) def close_enough(a, b, margin=0): return True if abs(a - b) <= margin else False def get_samples(filename): with contextlib.closing( wave.open(filename, 'r')) as f: number_of_frames = f.getnframes() frames = f.readframes(number_of_frames) samples = array.array('h', frames) return samples def order(matches): ordered = collections.OrderedDict() for k in reversed(sorted(matches, key=matches.get)): ordered[k] = matches[k] return ordered if __name__ == '__main__': ordered = order(find('bellclip.wav', ['bell1.wav', 'bell2.wav', 'drum1.wav', 'drum2.wav', 'fanfare1.wav', 'fanfare2.wav'])) print 'bellclip.wav: ', ordered
  18. def match(clip_samples, samples): expected = dot_product(clip_samples, clip_samples) for i in

    range(0, len(samples) - len(clip_samples) + 1): dot = dot_product(clip_samples, samples[i:]) if close_enough(expected, dot): return dot def dot_product(u, v): return sum(ui * vi for ui, vi in zip(u, v)) def close_enough(a, b, margin=0): return True if abs(a - b) <= margin else False
  19. Data structures & Algorithms • vector - list, array •

    matrix - list of lists • collections (OrderedDict) • itertools (product) *Fast Fourier Transform

More Decks by PyCon Ireland

Other Decks in Technology