Coding Interview Universitycurated list on GitHubRecommends
Under “Additional Learning”
MIT 6.851 - Memory Hierarchy Models (video)
0:00 / 0:00
#b-tree#cache-oblivious#externalmemorymodel
7. Memory Hierarchy Models
MIT OpenCourseWare
6.5M subscribers • 36 videos on Hallway • University channel
- Recommended by 2 people: 1 in engineering communities and 1 curated list.
- Presented by Erik Demaine, Professor at MIT
Advanced. Deep dive for people who know the field.
24K views12 years ago2 recommendations
Computer scienceSystems programmingData structuresAlgorithmsPerformance and optimization
Erik Demaine explains memory hierarchy models and cache-efficient data structures like B-trees to optimize data transfers between cache and main memory.
MIT 6.851 Advanced Data Structures, Spring 2012 View the complete course: ocw.mit.edu/6-851S12 Instructor: Erik Demaine Cache-efficient structures. B-trees are good at data transferred in blocks between cache and main memory, main memory and disk, and so on, achieving O(logB N) insert/delete/predecessor/successor for N items and memory block transfers of size B. License: Creative Commons BY-NC-SA More information at ocw.mit.edu/terms More courses at ocw.mit.eduWhy it's here
2 people recommend thisWhat people say. Recommended as an excellent resource for analyzing algorithms under memory hierarchy constraints and understanding cache-efficient data structures.
u/zombiecalypsein r/compsci • Recommends
On “What cs classes in school are actually useful as a software engineer?”
In broad terms – saying that continuous chunks of data will be faster to handle, then giving a few examples: an array backed list will almost always be faster than a linked one, quicksort is practically better than others because of locality, a few strategies to put a hash map in a single array, …. But it lacked the tools to analyse algorithms with these constraints; it was just a collection of anecdotes.
When I watched Data Hierarchy Models by Erik Demaine, it actually gave tools to abstract away the specific machine, but keep the memory hierarchy in the analysis of algorithms. Even if I haven't analysed anything with the models since then, it gave me a much clearer picture of what to lo…