61A Lecture 34November 21st, 2011Monday, November 21, 2011Last weekDistributed computingClient-serverPeer-to-peerMessage passingModularityInterfacesParallel computingThreadsShared memoryProblems: Synchronization and stale dataSolutions: Locks, semaphores (and conditions)Deadlock2Monday, November 21, 2011Sequential dataSome of the most interesting real-world problems in computer science center around sequential data.DNA sequencesWeb and cell-phone traffic streamsThe social data streamSeries of measurements from instruments on a robotStock prices, weather patterns3Monday, November 21, 2011So far: the sequence abstractionSequences haveLengthElement selectionIn python• Membership testing• SlicingData structures that support the sequence abstractionNested tuplesTuplesStringsLists (mutable)4Monday, November 21, 2011Problems with sequencesMemoryEach item must be explicitly representedEven if all can be generated by a common formula or functionUp-front computationHave to compute all items up-frontEven if using them one by oneCan’t be infiniteWhy care about “infinite” sequences?•They’re everywhere!•Internet and cell phone traffic•Instrument measurement feeds, real-time data•Mathematical sequences5Monday, November 21, 2011Finding prime numbersSieve of ErastothenesFind prime numbers by walking down integersFor each integer, eliminate all multiples of that integerLeft with indivisible numbers2 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 132 3 4 5 6 7 8 9 10 11 12 136Monday, November 21, 2011Working example: finding prime numbers7def primes_sieve(limit):# mark all numbers as prime at first prime = [True] * (limit+1) primes = [] # eliminate multiples of previous numbers for i in range(2, limit+1): if prime[i]: primes.append(i) multiple = i*i while multiple <= limit : prime[multiple] = False multiple += i return primesprimes_sieve(1000000000) anyone?1 billioneach number = 64 bits = 8 bytes8 bytes * 1 billion * 2 = 16 billion bytes = ~14.9 GB of memorysequencesequenceMonday, November 21, 2011Iterators: another abstraction for sequential dataIteratorsStore how to compute items instead of items themselvesGive out one item at a timeSave the next until asked (lazy evaluation)Compared with sequencesLength not explicitly definedElement selection not supported•Element selection -- random access•Iterators -- sequential accessNo up-front computation of all itemsOnly one item stored at a timeCAN be infinite8Monday, November 21, 2011Implementation: nested delayed evaluation9Nested pairsStreamfirst restnow, explicitstore how to compute itcompute when askedMonday, November 21, 2011Streams10class Stream(object): def __init__(self, first, compute_rest, empty= False): self.first = first self._compute_rest = compute_rest self.empty = empty self._rest = None self._computed = False @property def rest(self): assert not self.empty, 'Empty streams have no rest.' if not self._computed: self._rest = self._compute_rest() self._computed = True return self._restempty_stream = Stream(None, None, True)first restMonday, November 21, 2011Sequential data: nested streams11Nest streams inside each otherOnly compute one element of a sequence at a timedef make_integer_stream(first=1): def compute_rest(): return make_integer_stream(first+1) return Stream(first, compute_rest)live exampleMonday, November 21, 2011Prime numbers with nested streams12def primes(positive_ints): def not_divible(x): return (x % positive_integers.first) != 0 def sieve(): return primes(filter_stream(not_divible, positive_ints.rest)) return Stream(pos_stream.first, sieve)def filter_stream(filter_func, stream): def make_filtered_rest(): return filter_stream(filter_func, stream.rest) if stream.empty: return stream if filter_func(stream.first): return Stream(s.first, make_filtered_rest)else: return filter_stream(filter_funct, stream.rest)Monday, November 21, 2011Prime numbers with nested streams13def primes(positive_ints): def not_divible(x): return (x % positive_integers.first) != 0 def sieve(): return primes(filter_stream(not_divible, positive_ints.rest)) return Stream(pos_stream.first, sieve)>>> p = primes(make_integer_stream(5))>>> p.first5>>> p.rest>>> p.rest.first7<Stream instance at ... >Monday, November 21, 2011Native python iteratorsPython natively supports iteratorsThe Iterator interface in python:__iter__ •should return an iterator object__next__•should return a value ORraise StopIteration•when end of sequence is reached•on all subsequent calls14Monday, November 21, 2011Native python iterators: example15class Letters(object): def __init__(self, start, finish): self.current = start self.finish = finish def __next__(self): if self.current > self.finish: raise StopIteration result = self.current self.current = chr(ord(result)+1) return result def __iter__(self): return self>>> letters = Letters('a', 'd')>>> letters.__next__()'a'>>> letters.__next__()'b'>>> letters.__next__()'c'>>> letters.__next__()'d'>>> letters.__next__()Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 12, in nextStopIterationMonday, November 21, 2011From a native python iterator to a nested stream16empty_stream = Stream(None, None, True)def iterator_to_stream(iterator): def streamify(): try: first = iterator.__next__() return Stream(first, streamify) except: return empty_stream stream = streamify() return streamMonday, November 21, 2011More support: for loops!“for” loops use iteratorsStep 1: get an iteratoriterator = obj.__iter__()Step 2: try iterator.__next__() assign value to “item” do body of loop until StopIteration is raised17def for_each(sequence, function): iterator = sequence.__iter__() try: while True : element = iterator.__next__() function(element) except StopIteration as e: passfor item in obj:do stufflive exampleMonday, November 21, 2011Even more support: generator functions18class Letters(object): def __init__(self, start, finish): self.current = start self.finish =
View Full Document
Unlocking...