5 ms·
One thing I find generally worth improving with these sorts of introductions is that they always seem to introduce data structures as a pick-and-mix bag of preb
by Veedrac 9y ago
One thing I find generally worth improving with these sorts of introductions is that they always seem to introduce data structures as a pick-and-mix bag of prebuilt parts, rather than a set of techniques which allow you to enforce properties which allow you to build objects that do what you want efficiently. Teaching the former is like teaching a physicist all the different kinds of gear systems, rather than the math that lets you model them.
Knowing how binary heaps and hash maps work is great, because binary heaps and hash maps are very useful data structures, but knowing the fundamental reasons behind them in a way that composes to building new things is much more useful. What happens when you want properties that someone hasn't already built a data structure for, at least as far as you can find? (Pet example: ordered container with efficient append and the ability to query the maximum of any subslice length k in O(log k). Extension: what are the minimal assumptions you need to do better, eg. amortized O(1)?)
I think this contributes to the attitude where programs are built out of monolithic, ill-fitting parts rather than actually looking at the problem and building the solution which does the right thing, the right way. (Pet example: if you designed websites as data structures and the browser to support doing so efficiently, 90% of requests on a site like Reddit would be a single `memcpy`.)
What I would attempt is rather than saying
"Here's one way we could do it: <explaination of pre-baked hash table>."
talk about the underlying tool first
"One tool that can help us is hashing: <explaination of general technique and why its properties are useful>. In this example we want <these properties> but can't immediately get it because our data has <these properties>. But we can apply hashing to get <technique that looks decent but has caveats>. Handling the caveats by doing <hash table things> gives us a data structure called a hash table."
Yes, this is probably a harder way to handle things, but I'd like to think it'd be worth the trouble.
- chrisweekly 9y agoThat was a clearly-written, knowledgable, info-dense and effective bit of writing you just did, @Veedrac. Ever considered doing more of the same, and delivering the kind of educational material you just described?
- Veedrac 9y agoI was expecting a far more mixed reaction, so I'm glad to hear this engaged people. Writing educational material to takes more work (and expertise) than I'd be willing to guarantee, but I'll keep the sentiment in mind :).
- trishume 9y agoYou can subscribe to Veedrac's HN comments on RSS like I do. I've found a bunch of people like Veedrac regularly write really interesting things in HN comments, so I wrote an app that lets you subscribe to them: http://hnblogs.thume.ca/ http://hnblogs.thume.ca/
- catnaroek 9y ago> Teaching the former is like teaching a physicist all the different kinds of gear systems, rather than the math that lets you model them. Most programming work is less like theoretical physics and more like car repairing.
- scottLobster 9y agoI'm all for stuff like this in theory, but in my experience I never use said knowledge for any productive purpose and eventually it degrades... until I read a post like this, feel a surge of professional inadequacy and go re-learn it. :P
- Dylan16807 9y ago> (Pet example: if you designed websites as data structures and the browser to support doing so efficiently, 90% of requests on a site like Reddit would be a single `memcpy`.) You'd still want a compressed form, even if you had a good way to bypass parsing.
- Veedrac 9y agoAh, yes, I botched that description, since there has to be more to support things like encryption. A more accurate claim is that the bulk of the work currently done would be replaced with a memcpy.
- petra 9y agoCan this be done using software ? can i ask some software/expert-system - i need this and that properties, and it can tell me - "use this structure" ?
- devonkim 9y agoI’ve wondered why we don’t typically use algorithms that will self-adjust when we have so many VMs that can do all sorts of statistical analysis. We know that quicksort is inefficient on smaller and mostly-sorted lists so we oftentimes switch to selection sort below 20 items or so, but we typically have libraries that have statically picked this behavior as directed by their developers instead of over time selecting the more appropriate algorithm. Sure, if you’be never seen the data before there’s not a lot you can assume, but if over a lot of executions your VM can perform native code substitution and replace certain sections of code out based upon runtime profiling in HotSpot why can’t we come up with heuristics that say “just use a list instead of a hash table until runtimes to access start getting slower than n, in which case reallocate the data to a hash table, btree, or a heap depending upon which operations are most sensitive to system design parameters.” A lot of problems seem like we’re repeating ourselves writing the base algorithms and gluing things together when we really should be investing problems around resource constraints and system trade-offs and priorities. Then we could run test suites against these systems to determine how well they’d meet certain guarantees programmed in.
- petra 9y agoYep, great idea. >> A lot of problems seem like we’re repeating ourselves writing the base algorithms and gluing things together when we really should be investing problems around resource constraints and system trade-offs and priorities What's the minimal platform that would enable library developers to monetize such things ? and does it or something close to it exist ? because that seems like the fastest way to make this happen.
- amelius 9y ago> (Pet example: if you designed websites as data structures and the browser to support doing so efficiently, 90% of requests on a site like Reddit would be a single `memcpy`.) Formatting a webpage cannot be done by a simple memcpy, especially since you don't know the size of the browser window in advance. But perhaps I didn't understand the point you were trying to make.
- Veedrac 9y agoI mean on the server-side. Right now the process between "I want thread 35va5k" and "I want to render this html" makes extremely inefficient use of both servers and network.