University:
Boston University
Course:
MET CS 201 | Introduction to Programming
Academic year:

2021
Views:

142

Pages:

13
Author:

Koen Norman

Outline       Introduction Profiling Data Structures Syntax Generators Accelerators Data Structures  Algorithm implementation and performance is highly dependent on underlying data structures.  Python data structures:  List  Dictionary  Aka “associative array”  Wikipedia has a long list of established data structures.  Find Python implementations at https://pypi.org  Sets  Tuples  These are sufficient to underpin a vast variety of algorithms.  For manipulating numeric data use Numpy ndarrays or Pandas Dataframes. Python data structures are fast for….  Lists:     Appending Element getting/setting Removing from the end “pop()” Get length  Tuples (fixed lists):  Element getting  Get length  Dictionaries:  Element getting/setting  Element membership  Element insertion  Sets:  Element membership  Set operations (unions, intersections, etc) Let’s compare…  Sample data: names of finishers of the 2015 and 2017 Boston Marathons  Open files marathon_list.py and marathon_set.py  Question: Who finished both the 2015 and 2017 marathons?  Two implementations:  marathon_list.py loads the data into a pair of lists and then loops through them.  marathon_set.py loads the data into a pair of sets and intersects them. Performance  Test each script using the Spyder profiler.  What did you find?  Which one is faster?  Run it more than once – sometimes library or other code loading gives false timing.  Are the results the same? Lists A B  The list lookup is ~6300x slower than the set intersection! x  Algorithm: For each element in list A check to see if it’s in list B.  On average you need len(B)/2 comparisons for every element in A.  That’s approx. len(A) * len(B)/2 operations. Each comparison is pretty fast.  For 26000 runners that’s ~350M string comparisons. x Sets  Sets use a special data structure called a hash table to store elements.  Also used for dictionary keys.  The underlying hash function is very fast.  Lookup speed is nearly constant regardless of the size of the set.       Algorithm: For each element in set A check to see if it’s in set B.  You need len(A) lookups into B. Each lookup in B takes a constant time t.  That’s len(A) operations of time t.  For 26000 runners there are 26000 hash comparisons. How do you choose? Test your code on different problem sizes. Profile your code if testing reveals problems. Read the documentation for available tools and libraries. Email RCS for help. Exploit your data  Why were the results different?  Sets only store unique values so some names got dropped.  A better comparison would use a combination of factors to be more robust.  Example: name, city, country, and gender.  All part of the original dataset. Another solution…  How about a Python dictionary?  Key lookups are fast.  Convert each list to a dictionary of {'name_1':None,'name2':None}…  Use a loop as in the list solution and compare keys.  Definitely faster than a list.  But … the set intersection() does this exact operation already.  Don’t reinvent the wheel. Exploit the language. Algorithms  Think about your program…  Doing basic operations like lookups, sorting, comparisons, linear algebra, updating a collection, etc.?  There is certainly a data structure available that will help you.  Many Python implementations are available or you can build your own. https://en.wikipedia.org/wiki/Algorithm Numpy and Pandas  Numpy ndarrays are intended for high speed numeric calculations.  Pandas dataframes are composed of ndarrays – same pros & cons Optimal usage:  Use built-in numpy functions wherever possible  numpy.abs(x) can operate on a whole ndarray.  math.abs(x) requires a Python loop  Choose appropriate data types: float32, int, etc.  Pre-allocate ndarray to the correct size.  Overwrite values with left-hand slice notation. Avoid numpy.append()!  This also applies to pandas.Dataframe.append()  Numpy.append() for an ndarray with N elements:     Allocate a new ndarray of size N+1 Copy over the existing data Copy in the new element. Deallocate the old ndarray of N elements. x=numpy.ones(4) x x=numpy.append(x,2) new 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 copy: copy: x delete Some Numpy examples  Open numpy_solutions.py  Examples are provided for append(), pre-allocation, and proper use of library calls.