"Today we'll look at what it takes to handle truly **huge** amounts of data, as one often would when dealing with scientific data.\n",
"\n",
"As we've seen, with most algorithms & data structures the limiting factor will be the amount of data.\n",
"\n",
"Everything is \"easy\" when the data is small.\n",
"\n",
"### Example O(1) Operations\n",
"\n",
"- add/remove on linked list\n",
"- modify array at the end\n",
"- array access\n",
"\n",
"### Example O(n) Operations\n",
"\n",
"- A linear search for a record in sequence.\n",
"- Always *some* operations on a linked list/array type, depending on which is chosen.\n",
" - insert at start/middle of array\n",
" - access random element in linked list\n",
"- Memory-move type operations (list/hashtable outgrows allocated memory)\n",
"- String concatenation with `__add__`\n",
"\n",
"### Example O(log2 n) Operations\n",
"\n",
"- Binary search/sort.\n",
"- Grow slower, but overhead & memory complexity can still limit large data sets.\n",
"\n",
"### Example O(n^2) / O(n*m) Operations\n",
"\n",
"- Comparing every item to every other item. (Simple checking for duplicates.)\n",
"- Generally: Nested O(n) operations. (for each of N files, for each of M words in file...)\n",
"\n",
"**And remember, to get better performance we are often spending extra memory**. \n",
"\n",
"So what happens when data gets too big?\n",
"\n",
"## Strategies for \"big\" data.\n",
"\n",
"I am avoiding the term of art \"Big Data\" which often has specific connotations. Our \"big data\" would encompass \"Big Data\" but also any data where performance starts to become an issue.\n",
"\n",
"### \"Premature Optimization is the Root of All Evil\"\n",
"\n",
"(-Donald Knuth)\n",
"\n",
"A halllmark of an \"intermediate\" programmer is that they have all of the tools of the experienced programmer, but they lack the wisdom to know when to use which one. \n",
"\n",
"A common mistake stems from attempts to optimize code that was never going to be the bottleneck.\n",
"\n",
"Generally, when there is a straighforward way to do something, do it first!\n",
"\n",
"Write your code in an organized way and you'll be able to fairly easily adapt if it turns out that you need to optimize it with one of the techniques introduced below.\n",
"\n",
"For example, if you need to do something 1,000,000 times.\n",
"\n",
"Start with a function that performs that task. And call it on a subset of that data:\n",
"\n",
"```\n",
"for item in full_data_set[:10000]:\n",
" do_something(item)\n",
"```\n",
"\n",
"If this takes 1 minute to run, then your full data set will take 100 minutes. \n",
"\n",
"- Will it save you more than that to rewrite?\n",
"- What if it needs to run every week?\n",
"- What if it takes 1 hour?\n",
"\n",
"Let's say it is still too slow: what then?\n",
"\n",
"### Strategy 1: Better Algorithms & Data Structures\n",
"\n",
"Before employing the strategies below, it is generally advisable to think about what portions of your code are slow.\n",
"\n",
"Sometimes, for a simple enough program, or an experienced enough dev, you can reason this out, but if in doubt you should **profile** your code to determine the slowest portions and work to optimize them. The results can be surprising, perhaps you are calling a method that does a `deepcopy` that you didn't realize was there, or using an array where a linked list would be more appropriate.\n",
"Python's flexibility comes with costs. Python has a reputation for slowness in some contexts. Other implementations of the Python interpreter attempt to overcome some of the default implementation's shortcomings (e.g., Cython, PyPy, Numba).\n",
"\n",
"> The relative sluggishness of Python generally manifests itself in situations where many small operations are being repeated—for instance, looping over arrays to operate on each element.\n",
"> It turns out that the bottleneck [...] is not the operations themselves, but the type-checking and function dispatches that CPython must to at each cycle of the loop.\" [This is where compiled code has an advantage.]\n",
"\n",
"**-Jake VanderPlas, Python Data Science Handbook**\n",
"\n",
"Solution: *vectorized* functions via \"ufuncs\" that circumvent problems of this nature.\n",
"\n",
"These functions execute in the C-layer instead of the Python layer. They bypass type checking, dunder lookups, and other overhead, allowing the full speed of the CPU (and GPU) to be utilized.\n",
"\n",
"Data will still be the limiting factor, but if we can get a 10-100x speedup, that's another order of magnitude or two worth of data we can process per machine. (So when combined with parallelization, can drastically save on costs.)"
]
},
{
"cell_type": "markdown",
"id": "8bf94429-34c4-4f45-b912-e13aa895ed79",
"metadata": {},
"source": [
"### Strategy 2: Parallelization\n",
"\n",
"Depending on the needs of the program, your next bet may be to paralellize the operations.\n",
"\n",
"This means splitting the data up into smaller pieces, and have multiple processing pipelines handle subsets of the data.\n",
"\n",
"This can mean multiple computers on a network, or on modern machines, multiple threads or processes on the same machine.\n",
"\n",
"A full exploration of this is beyond the scope of what we can cover in this class, but here are some techniques:\n",
"Python has a feature known as the \"global interpreter lock\" which prevents two Python threads from modifying the same data structure at the same time.\n",
"\n",
"This means that two threads can't accidentally remove the same item from a list, or set the same key in a dictionary to two different values. It comes at the expense of performance, since you lose the ability to use these data structures concurrently whatsover.\n",
"\n",
"Some languages give much more finely grained control, which comes with more responsibility & room for error.\n",
"\n",
"For this reason, most Python programs prefer subprocesses to subthreads. (If you take parallel programming or an operating systems course you will likely explore the differences.)\n",
"\n",
"Python 3.13 supports an experimental GIL-free mode, something that's been considered unlikely for 20+ years. This could be the biggest change to the language in decades."
]
},
{
"cell_type": "markdown",
"id": "8214e0f8-0467-477f-909d-cf447107c6d3",
"metadata": {},
"source": [
"### Strategy 3: Vectorization\n",
"\n",
"Another approach that can help in tandem with parallelization, and which can be easier to reach for without refactoring your code, is to take advantage of modern hardware's support for vectorization.\n",
"\n",
"Vectorization takes advantage of the fact that it is often cheap to do the same operation to adjacent memory locations.\n",
"\n",
"With a large array, instead of adding +1 to each item, the array could instead be merged with [+1, +1, +1, +1, +1, +1, +1, +1...] incrementing many items simultaneously."
"Python's dynamic typing makes it extremely flexible, but this flexibility comes at a cost.\n",
"\n",
"Python's built in types are often cleverly disguised C structures containing the data associated with the object as well as header information.\n",
"\n",
"Every Python `object` has a header:\n",
"\n",
"- `ob_refcnt`: reference count used for garbage collection\n",
"- `ob_type`: type of the object (how to interpret underlying bytes)\n",
"- `obj_size`: size of data in bytes\n",
"\n",
"Lists (for example) are extremely flexible and can hold any `object`, we've said these things are in adjacent memory, but how does that work if the items are a different size?\n",
"Python's `array` object provides efficient storage on array-based data, **NumPy** adds efficient operations on that data as well as a nicer interface.\n",
"\n",
"NumPy will upcast data if there is data of different types in a single array. For example:"
"np.linspace(0, 6, 5) # divides space [0,6] into 5 equally-sized increments"
]
},
{
"cell_type": "markdown",
"id": "e28b82d7-49e5-4ed2-9a5a-38cb50708559",
"metadata": {},
"source": [
"### Reshaping NumPy Arrays\n",
"\n",
"Allows us to reinterpret the existing memory as a different shape. Must be the same total size.\n",
"\n",
"`reshape` - reshape to new dimensions\n",
"\n",
"`ravel` - flatten to rank 1\n",
"\n",
"`T` - transpose (note: property, not method)\n",
"\n",
"`resize` - reshape in place"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "c5a68743-ad95-4cf3-b4ca-0cc56f239925",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[0 1 2 3]\n",
" [4 5 6 7]]\n"
]
}
],
"source": [
"ta = np.array([range(4), range(4, 8)])\n",
"print(ta)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "f6f5e273-9c0b-4dac-943e-f91cd398fa26",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[0, 1],\n",
" [2, 3],\n",
" [4, 5],\n",
" [6, 7]])"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ta.reshape(4, 2)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "c2a366f7-7204-4768-b439-8c694c82055f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([0, 1, 2, 3, 4, 5, 6, 7])"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ta.ravel()"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "31425a7d-f14b-409d-b4f9-2581e2a6ad93",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[0, 4],\n",
" [1, 5],\n",
" [2, 6],\n",
" [3, 7]])"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ta.T # note this is a property"
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "fc80d1ad-cc4e-4bee-b6bf-d782e3107ad3",
"metadata": {},
"outputs": [],
"source": [
"ta.resize(4, 2) # modifies ta in-place (no return value, but ta is modified)"
]
},
{
"cell_type": "markdown",
"id": "7adeb79b-1b73-4532-b034-12ea0280901f",
"metadata": {},
"source": [
"### pandas\n",
"\n",
"For about a decade, one of the most popular libraries in Python was `pandas`. `pandas` build on top of NumPy arrays, introducing 2D data types called `DataFrame`. \n",
"\n",
"You can think of a DataFrame as a cross between a list of dictionaries and an spreadsheet.\n",
"\n",
"DataFrame objects consist of columns of similar data. They can take advantage of memory locality to be vectorized. "
"A few years ago, `polars` was released, and is becoming the preferred DataFrame library. It provides a mostly-compatible `DataFrame` type with a few key advantages:\n",
"\n",
"- Implemented in Rust, which is a memory-safe language with low overhead, comparable to C.\n",
"- Uses the 'Arrow' memory structure for columnar data. This is an evolution of Pandas' work on column-based data formats, allowing high-speed performance & cross-language sharing of memory.\n",
"- `pandas` took ~10 years to reach a stable interface and accumulated a lot of \"baggage\" -- methods that can't easily be fixed/changed for backwards compatibility reasons, `polars` started with a fresh take on the API & is generally easier to learn as a result."
" .catch(err => showError(`Javascript Error: ${err.message}<br>This usually means there's a typo in your chart specification. See the javascript console for the full traceback.`));\n",
