[HN Gopher] Challenging algorithms and data structures every pro...
___________________________________________________________________
Challenging algorithms and data structures every programmer should
try
Author : whack
Score : 188 points
Date : 2022-12-24 16:41 UTC (6 hours ago)
(HTM) web link (austinhenley.com)
(TXT) w3m dump (austinhenley.com)
| TheEndIsNigh wrote:
| Not exactly challenging, they're covered in a decent undergrad
| Algorithms course.
| taeric wrote:
| Fun list! Other things I'd recommend trying:
| Huffman coding Binary decision diagrams Simplex
| method General modeling of a problem to SAT
|
| The last one there is particularly fun. Finding a way to solve a
| problem fast by mapping it to a silly large set of variables is
| surprisingly fun.
| koinedad wrote:
| Thanks for the list. First time I coded a Trie I thought it was
| super cool. Topological sort is such a useful one as well.
| Turing_Machine wrote:
| Tries are probably the one I've used the most in the real
| world, so I guess if I were making such a list it'd be on the
| main one, not in the honorable mention section. I'm not sure
| which one I'd remove to make space for it, though.
|
| I second the recommendation for Jeff Erickson's book. He is an
| awesome in-person instructor, too.
| TrackerFF wrote:
| Call me cynical, but every time I see interesting threads like
| these - I can't help but to think that somewhere, a hiring
| manager is thinking to himself _" Nice, I'll add these to the
| technical (interview) questions"_
| PaulDavisThe1st wrote:
| Although it is somewhat embarrassing to admit this, when I wrote
| JACK [0] I was unaware of topological sort, mostly due to a lack
| of any formal CS education. This was a major error/failing on my
| part, because that codebase was more or less made for TS. There
| have been few other instances where a lack of formal CS training
| has been an impediment, but not knowing that there was a well-
| known algorithm for ordering node execution in a directed graph
| was ... bad.
|
| [0] https://jackaudio.org/
| Xeoncross wrote:
| > Google asked me two interview problems involving these back
| when I was in college. Have I ever needed this in practice? Nope!
|
| This is the shame of the Big Tech. I've used bloomfilters, tries,
| and many other of these multiple times on side projects with
| constraints, but would something like this ever make it into a
| deployed system at FAANG by all the regular devs?
|
| No, just use dynamo, spanner or a bigger cluster + more workers,
| more queues, add more k8s nodes, plus whatever cloud tech you
| should be using to "horizontally scale" and be "distributed".
|
| Not that there aren't awesome devs at these companies which do
| code responsibly, but I don't often see it.
|
| I can't believe how unperformant the systems I've often seen in
| Big Tech are. I want more people to read the article about
| fitting the whole level into a single byte[1] and stop using big
| budgets as a way to be irresponsible.
|
| 1: https://news.ycombinator.com/item?id=34095954
| didibus wrote:
| They're different problems, you've got programming in the
| small, medium and large.
|
| Computer Science tends to focus on programming in the small to
| medium, and software engineering tends to focus more on
| programming in the medium to large.
|
| It's one thing to optimize a small piece of functionality
| fully, but it's another thing to put together a product that
| has thousands of live users, hundreds of features, multitude of
| configuration modes, distributed globally, etc.
|
| If I ask you to clean a bathroom in 3 hours, and then I ask you
| to clean the whole house in 3 hours, your approach to the
| cleaning will be very different between the two, and the first
| thing that will be cut is your attention to details.
| Jensson wrote:
| I think the problem with slow user interfaces is that the
| programmers who knows how to make things fast usually want to
| work on more interesting algorithms instead of optimising UI
| interactions. I built model evaluators at Google so I used a
| lot of these algorithms, specifically topological sort is
| useful in so many places and you can't really make a generic
| solution for it to put in a library, and different parsing
| methods. When doing this I had to look at how many nanoseconds
| different ways to do things costs, because things are run
| billions of times on large models in production so it is very
| expensive.
|
| The people on that team were really good at making things run
| fast, but I haven't seen that kind of people doing user
| interfaces, instead even at Google some internal pages took
| minutes to load with barely any data, I could run a batch job
| spinning up thousands of servers over terabytes of data in the
| time it took just to view my account in that service. The
| silver lining is that Google has many alternatives for
| everything so I could use something else instead.
|
| I guess a part of it is that Google pays for server compute,
| but not client compute, so your computer running slowly isn't a
| big deal compared to their server costs, so the optimizing
| programmers gets placed on backends. I did work on message
| routers as well, they have to be blazing fast, so I know how to
| make network requests fasts, the only reason the UI's are slow
| is that the companies aren't prioritizing it.
| armchairhacker wrote:
| Bloom filters, skiplists, tries, recursive descent, etc. are
| actually used in many systems and I think it's important to
| understand how they work at a high-level
|
| Now, implementing one of them on a whiteboard or without access
| to internet, knowing all of their intricacies and edge
| cases...that is stuff I doubt anyone needs to know except a
| very specific type of developer. If i want an optimized trie I
| use a library, and when it breaks and i need to fix the low-
| level implementation, i look it up online
| mythhouse wrote:
| > system at FAANG by all the regular devs?
|
| dynamo, spanner ect were written by devs at FAANG . Do they
| have special interview channels for 'regular devs' and another
| for people who can write dynamo ?
| taeric wrote:
| I took the point to be that maybe scale of database engine
| can get you passed a lot of nuance.
|
| Not much different from databases of old. Writing a good
| sorting algorithms feels excessive in many applications. The
| number of such algorithms that the planner of a database
| picks between is rather large.
| ahh wrote:
| > Do they have special interview channels for 'regular devs'
| and another for people who can write dynamo ?
|
| Not special interviews, but certainly different pieces of
| headcount. There are Googlers and there are _Googlers_. Being
| the second is a lot more work, but a lot more interesting.
| taeric wrote:
| I mean, you aren't wrong. But there is more diversity and
| challenge in five minutes of many modern games than all of pit
| fall.
|
| Same goes for many of these algorithms. They are amazing, but
| also require a simplicity of problem that is hard to pull back
| to. Worse, they often solidify the program into something that
| is very rigidly defined and not conducive to change.
| rrgok wrote:
| I like algorithms and data structures. One of the thing I,
| personally, find hard about Algos and DS, is that I don't know
| when to use which. For example, I could never ever come up with
| my own, that the traveling salesman problem can have a good
| solution with ant colony optimization or simulated annealing. How
| do I learn that skill? I still don't know when to use a graph for
| what kind of problem.
|
| I hope someone can shed some light on this.
| TheEndIsNigh wrote:
| You need to solve hard problems. Code Jam is an amazing source
| for this. Just don't expect to knock them out in 5 minutes.
| Pick a hard problem and stay a week with it trying different
| ideas and compare the time complexity.
| djur wrote:
| So far most of the resources I've found for this kind of
| thing don't really provide enough guidance in what algorithms
| to choose and why, mostly because they're usually designed as
| competitions. I'm not interested in competing with other
| programmers, I want to learn from them.
| Jensson wrote:
| You get good at this from a long life of curiosity in the
| subject. Basically, if you spent your life testing many
| different ways to do things, think thousands of different ways
| to compute or parse or view data etc, then you have that huge
| knowledge bank to aid you when you see a new problem, so you
| compose a few of those things to solve it.
|
| It is the same process as learning the elementary algebra in
| math. You learn a few basic techniques, like moving numbers and
| variables from one side to the other, and then you compose
| those to solve expressions you haven't seen before. The only
| difference is that algorithms is a much larger space, there are
| way more techniques and problems there so it takes longer to
| get to a point where it is useful to you.
| jpitz wrote:
| The Algorithm Design Manual, which maybe should have been named
| The Algorithm Selection Manual.
|
| https://www.goodreads.com/book/show/425208.The_Algorithm_Des...
| djur wrote:
| What I would be interested in is some kind of resource (book,
| video series, etc.) where someone presents a reasonably "real-
| world" problem, discusses the thought process in choosing an
| implementation, and steps through the process of implementing,
| testing, and iterating on the solution. It's easy to find sources
| for hard problems to solve, and it's easy to find sources for
| explanations of algorithms and data structures, but I haven't
| found much to bridge the gap.
| charlieyu1 wrote:
| Thank you. Never really figure out how parser works but maybe I
| should try and write one
| anigbrowl wrote:
| Nicely written. Hits a spot that a lot of instructional and
| documentary material misses - telling the reader up front what
| common problem each technique solves.
| samsquire wrote:
| Wikipedia is sometimes enough to implement an algorithm. I
| implemented multiversion concurrency control and btrees due to
| Wikipedia which do not have pseudocode. If you can implement an
| algorithm from an English description that is really useful. It
| relies on the algorithm being well explained.
|
| I also suggest trying to implement a btree, they're really useful
| data structures for data retrieval and many database products use
| them extensively for indexes.
|
| With any algorithm, I think there is a critical insight (that
| might be different for each person) where the algorithm clicks.
|
| I didn't understand mergesort properly until I worked on
| implementing it but I understood quicksort. When the underlying
| mental model of the problem being solved becomes clear, we can
| reason about the algorithm and write code to implement what we
| want to do.
| todd8 wrote:
| This is an interesting list. I'd add hashing and hash tables to
| the list. There are lots of interesting variations of these as
| well.
|
| I would put hash tables ahead of piece tables because of their
| generality. For text editors I've always thought that gap buffers
| were so straightforward that ropes and piece tables seemed like
| extra unnecessary work. I see that VS Code uses piece tables so
| perhaps someone can explain the performance differences to me.
|
| I've never sat down and benchmarked various implementations of
| text buffers. However, it seems to me that memmove(3) on modern
| processors would be so fast that moving a buffer gap on even a
| 1GB file wouldn't be perceptible, and in return operations over
| the whole buffer like string searching or parsing would be much
| more efficient in a gap buffer because the program could count on
| the buffer being in contiguous memory locations (after closing
| the gap). In buffers implemented using a part table or ropes,
| every character access involves extra layers of indirection.
| Furthermore, gap buffers are going to be more cache friendly for
| the way that most editing operations take place in a text editor.
|
| Perhaps someone that has actually done some comparisons could
| enlighten me.
| ComputerGuru wrote:
| At this point, everyone knows about bloom filters simply because
| it's _the_ thing to write about any time someone asks "lesser
| known data structures /algorithms?" - it's hard to find a list
| that _doesn't_ feature them!
|
| Still some good entries in that list. I would add skip lists, not
| because they're structurally anything special but because they
| open your mind to the possibly entirely-new-to-the-reader world
| of probabilistic data structures.
|
| As someone that's been around the block, something I've learned
| to be less surprised by is how often simply adding an element of
| randomness to a difficult problem can sometimes give you results
| comparable to a 10- or 100-times more complicated solution, with
| the advantage of being more maintainable, making better use of
| the i$, and avoiding a lot of work. (Eg compare a cache dropping
| randomly selected items to LFU or LRU caches.)
| Jensson wrote:
| Randomness is very useful to handle edge cases, quicksort is
| the poster child here, it has some edge cases were it runs
| extremely slowly but randomising how you apply the algorithm
| means that you can ignore them since they are so unlikely. If
| you try to use deterministic code then those rare edge cases
| often comes up in the real world.
| zelphirkalt wrote:
| I often find myself thinking: "But how would I do any of these
| without reaching for mutation? So that I can later parallelize
| them?" And then I come up empty. I still need to work through
| "Purely Functional Data Structures" by Okasaki. Hopefully then I
| will have an idea, of how to come up with a functional version to
| mostly single-core algorithms or at least locking-requiring
| algorithms.
|
| I skipped ahead once and looked at functional red-black trees and
| the solution was to involve one more color! How ingenious is
| that?! I have no idea, how people got to these solutions.
|
| In many places algorithms are described implicitly with mutation
| assumed. However, this can be very hard to parallelize later and
| might hit you in the future. In the times of many cores, this
| seems no longer appropriate to me. I wish we spent more time on
| learning how to get it done without mutation.
|
| Another great post that was linked at some point on HN was this:
| https://nullprogram.com/blog/2020/04/30/ -- A comparatively
| simple change in approach and yet it allows for massive
| parallelization without locks! This is the kind of stuff we
| should learn more about and then make more use of our many
| available cores, moving on from the single core world of
| algorithms.
| samsquire wrote:
| I am deeply interested in parallelism. Would enjoy talking to
| you about it. I think the parallelism provided by Haskell is
| really interesting. And its software transactional memory.
|
| I think parallelisation can be generalised but we need to study
| it further to understand it better. There must be a set of
| primitives that parallelise very well but they've not been
| found out yet. Rather than trying to parallelise something that
| was invented to be sequential, we parallelise something that is
| parallelisable.
|
| I'm today working on parallelising a total ordered list view
| over X sorted lists that are maintained by separate threads or
| independent computer servers. My idea is to use N way mergesort
| to retrieve up to N items sorted items. Servicing requests is
| extremely fast since there is no synchronization needed within
| a thread or server but if you need total order, you need to use
| the N way mergesort. I'm thinking you have a cluster for
| ordered views and a cluster for within-a-thread view.
|
| My other problem I'm working on is how to paralellise integer
| updates. If you have 8000000000 accounts (which DOES fit on a
| single machine) but you have more operations overall than a
| single machine can process? You could shard by account but I
| think there's an approach that shards by integer and per
| server. You store a portion of the integer on each machine,
| hopefully enough to handle operations. Then when you need to
| check if account integer > deduction amount I just need to
| learn how to a strongly consistent read cheaply. Essentially we
| load balance the integer in the account.
|
| For example, fibonacci is often used as an example to
| parallelise something but it's never implemented in a
| parallelisable manner. It just does the same calculation in
| different threads. If we knew the formula of fibonacci that
| didn't depend on previous iterations, we could parallelise
| fibonacci. But I'm not a mathematician so I I'm not sure how to
| find out that formula.
| Jensson wrote:
| Sorting is a standard distributed algorithm, it is basically
| quicksort but you move some data between servers between the
| steps. The aim is to create ordered buckets of data that you
| then send to servers. The first step is to find good pivots,
| so sort the data and select data points at the median and
| different percentiles from each server, then fan out those
| pivot candidates to every server. Now since all servers has
| the same pivots they can create the same buckets, and send
| the data they have of each bucket to the corresponding
| server. The buckets wont have perfect balance, so you
| typically want a few times more buckets than you have servers
| to ensure that you don't overload one of them, that is the
| fast way. Alternatively you can do another fan out step
| computing the number of items in each bucket among the
| servers, and split large ones into smaller buckets using the
| same technique as before, this will always work but requires
| a bit more communication between the servers.
|
| As for distributing heavy computations, Google has done that
| to compute your search results since almost the beginning.
| Fan out a request to a huge cluster of servers that all have
| different parts of their data in ram, then they filter and
| return the parts of the data that is relevant to you. It is
| totally possible to do it and return a response to the user
| in a fraction of a second. Typically it takes a few
| milliseconds to send data between servers in a data center,
| you can easily fan out a request to a few hundred servers,
| let them compute and return something 15 milliseconds later.
| It costa bit to run that though, Google can afford it since
| search is worth so much per request, so you got figure out if
| your usecase is worth that much compute. But it doesn't cost
| that much more than running the same work on a single server,
| it depends a bit on how well your servers are collocated.
|
| Btw, frameworks for distributed computing like Apache Spark
| are way too slow for this, you have to hand roll those. But
| it really isn't that hard to do, there are programming
| competitions involving those, a correct solution to these
| kind of things takes like 30 minutes to write if you know
| what to do and you have done all the boring infrastructure
| work to ensure you can contact servers and access the data.
| That is why most programmers never work with complex
| algorithms, because the boring and tedious work on all the
| other parts takes up most of the time and manpower.
| convolvatron wrote:
| assuming that local access is cheaper than distribution,
| wouldn't a merge sort be better?
| mrkeen wrote:
| Often mutation on a single core is faster than persistence on
| multiple cores.
| samsquire wrote:
| This is the problem I'm working on.
|
| Independent threads are as independently fast as a single
| core and they slow down overall when synchronization is
| introduced. Amdahls law means that the cost of sequential
| tasks approaches the majority of time compared to the
| parallel speed up.
|
| My design is to shard by thread. Each thread or machine
| maintains a sorted shard of the data. Erlang takes a similar
| approach. If you want a total order view, then you N way
| mergesort.
|
| I have a lock free algorithm that can do about 1.2 million
| synchronizations a second across 11 threads. My lock
| benchmark does 3,444,152 3.4 million requests per second with
| 11 threads so my lock free algorithm isn't as good as locks.
| My lock free algorithm doesn't block though.
|
| I'm thinking of calibrating message rate by increasing
| latency to increase throughput and limit interference for the
| lock. If I increase message rate to 2500-25000 messages then
| more messages get transferred per synchronization event.
| Jensson wrote:
| You can parallelize with mutations, just split the data and do
| a tiny bit of extra work when the data overlaps. There aren't
| that many real world cases where you want to run expensive
| computations on highly connected data, and in those cases you
| mostly just write GPU code instead of bothering with functional
| CPU languages. That is what the engineers who works on the
| extreme end of performance does, if you want to learn
| functional programming that is efficient and performant then go
| and learn GPU programming, the techniques you learn there also
| works for many CPU applications, there are decades of top end
| industry practices behind those techniques.
| melony wrote:
| I recommend https://web.stanford.edu/class/cs168/index.html
| waynecochran wrote:
| I would add KD-Tree and BSP-Tree as generalizations of a binary
| search tree in higher dimensions.
___________________________________________________________________
(page generated 2022-12-24 23:00 UTC)