Hacker News Reader

Comment by jillesvangurp | Hacker News Reader

Most of those you'd consume in library form. Most programmers shouldn't be writing their own lists, hash maps, b-trees, sort algorithms, etc. Or generally reinvent wheels. It's nice to understand how this stuff works and have a notion of complexity and other limitations. But, mostly we're just sticking things together that already works.

I've dabbled a bit over the years with reinventing wheels like this and it's fun. and of course I had an algorithms course when I did my CS degree, 30 years ago. But, I can't say I spend a lot of time obsessing about algorithm implementations. I mostly just use them in library form; just like everybody else.

View on HN

I don't think anyone is suggesting that every programmer implements their own list every time they use a list. But it's useful to have an understanding of how common data structures work, how basic algorithms operate, and what kind of things are out there.

Writing software is much easier when you know that things like B-Trees exist or how breadth-first search works. How do you know where to find things like this in your library if you don't even know they exist?

Yep, following rules like "never ever use goto" or "use design patterns and OOP everywhere" makes no sense, if (typical) software development itself is not exact. Some folks mix up software development with being super precise and mathematical, but it's not that exact. So do repeat yourself, if the alternative is not worthwhile. As a concrete example, I don't need to download an engine (such as Unreal/Unity) to make a retro-styled 3D game. All I need are software rendering algorithms, SDL2 and maybe Rust. That's it.

> I don't think anyone is suggesting that every programmer implements their own list every time they use a list. But it's useful to have an understanding of how common data structures work, how basic algorithms operate, and what kind of things are out there.

And, when you need to optimize or handle special cases on critical paths, you may end up needing to implement these algorithms yourself.

Case in point: I once lead development of a major competitor to Dropbox. We couldn't use "off the shelf" queues and lists to manage upload and downloads, because there were too many special cases. I also had to implement my own immutable collections (until a library was released and we switched to it.)

But otherwise, 99% of the product used off-the-shelf list and queues under the hood.

That’s why the title is “should know”, and not “should reimplement by themselves for production use all the time”. As the book description says, “This book will help you not only to develop the skills to select and use an algorithm to tackle problems in the real world but also to understand how it works.” Note “select”, “use”, and “understand”, not “write“.

Honest question: what's the point of knowing trivia on data structures and algorithms if you will never implement those or even be aware you're using them or not? In the real world you pick containers based on their traits, and you aren't bothered about how they're implemented under the hood.

It helps to make informed decisions, for example regarding memory locality, and it helps when they don’t perform as expected or required. It’s also difficult to get a good understanding of the properties of algorithms and data structures if you’ve never looked at how they are implemented under the hood. Learning how algorithms and data structures are implemented is probably the best way to learn the general principles.

And then there’s also some algorithms, like for example topological sorting, that are typically implemented as part of application-specific code, not by use of an existing stock implementation. When you know nothing about implementations, you might not notice that the code you’re writing happens to actually be an instance of a well-known algorithm or data structure.

I wouldn’t classify it as trivia to know the big-O complexity of an algorithm or to have some idea of the worst-case behaviors you may run into (like inserting already sorted data into a binary tree). You don’t need to memorize the source code, but you should at least be able to visualize the boxes and arrows in your head.

That said, this particular book is an expensive way to line your birdcage, and it should be an O(1) decision to reject it. Shame that ORA put their name on this trash.

> I wouldn’t classify it as trivia to know the big-O complexity of an algorithm or to have some idea of the worst-case behaviors you may run into (like inserting already sorted data into a binary tree).

It's trivia, and more often than not it's completely useless trivia.

Big-O complexity refers to asymptotic complexity which is only theoretically met with very large datasets which are already in the realm of a RDBMS. Until that point, performance is far more sensitive to cache locality and other implementation details. This means that all those trivia numbers don't even match with real world data you get from your own performance tests.

So what's the point of wasting time memorizing trivia that doesn't even match real-world observations?

Big-o of various data structures is typically trivia not worth remembering but it’s also easy to remember for the most common data structures.

For all the other data structure operations it up. But there’s a lot more to data structures than big-O and implementing it yourself is one way to expose yourself to those details (eg cache locality or other things). Crossing abstraction layers requires an understanding of what’s above and below an abstraction. It’s not trivial to have that knowledge and know how to apply it effectively.

It also is not relegated to RDBMS. It can come up when dealing with as few as 1M elements. For example, look up the Rockstar long loading time bug that applied an n^2 algorithm accidentally to something like a few thousand or hundred thousand elements.

But you seem to be pretty into the ignorance is a virtue mantra so not sure there’s any point in engaging further.

Big O notation is a description of algorithmic complexity, not “data structures” and it definitely isn’t trivia. One of the two biggest pain points I’ve dealt with with new devs (even experienced ones) is that they ignore time complexity and write god awful slow code.

(The other is adding network requests, eg database calls, in loops)

No, it is definitely trivia. You can just as easily look it up on an as-needed basis.

Whether or not developers choose to observe time complexity is orthogonal.

Look up what? If I ask a dev the time complexity of a function they’ve just written, what are you expecting them to lookup? They should be able to tell me on the spot and we can discuss if it’s optimal

That’s not what this thread chain is about where we’re saying the time complexity for various operations on more obscure but still common data structures (eg btree, trie etc) are trivia that is typically documented by the library providing said data structure. That is distinctly different from being able to perform a big-o analysis on a given piece of code.

How does that meme go? Oh yeah: Tell us you haven't read the thread without telling you haven't read the thread.

But, okay, let's entertain your random tangent. Such a request is emblematic of junior managers/junior manager hopefuls misguidedly trying to wedge their knowledge into the function of the operation. In reality, you don't want to have to build a team that requires discussion about such matters. You need to define clear performance requirements upfront and let the benchmarks speak for themselves. Even if a function is O(N!), but measures successfully within the needs of the application, good enough.

It is especially important to encode these requirements in benchmarks as it documents for future developers the same requirements, and ensures they stay within them as code gets modified. The reality is that you won't be around forever. Keeping a team that relies on you to ask such questions is a failing on you.

But let's accept, for the sake of discussion, that you have failed your team. One still does not need to remember that kind of information. The function they wrote contains what they need to know, and they can consult the function to ascertain that information as needed – just as you could all by yourself in this scenario. If you like keeping such trivia in active memory, good on ya, but it is never necessary.

You’re being a tad pedantic and more annoyingly also wrong.

Big-o notation can also describe space complexity which is a property of the data structure itself and not the algorithmic operations. What I said was a catch all.

As for trivia, it 100% is when literally ever good data structure documentation says the big-o of that operation (+ a lot more details that can sometimes be more relevant). It’s trivia worth knowing for arrays and hash tables but not worth remembering for the various trees because there’s so many of them and they’re used so infrequently (+ implementation decisions can matter which is why reading docs is more important).

I don’t know what problem domains you are working with but algorithmic complexity is not the most common slow code reason I’ve seen new devs run across because the sane generic defaults tend to be relied on for that exact reason (+ code review by someone with experience will catch obvious problems)

> I don’t know what problem domains

The addendum about network calls in a loop makes it sound like his domain uses some kind of SDK with a bad API design. There are some notorious examples which are known to fool new and uninitiated developers who haven't read the fine print into writing code that looks perfectly reasonable on the surface, but does dumb things under the hood.

My experience with new devs is more towards obsessive concern with respect to time complexity, at least where isn't hidden behind a bad API design, fearing an algorithm with high complexity that when measured under its practical use would be just fine. It can be difficult for new (and even old) developers to grasp just how fast computers actually are.

I work in multiple problem domains as I lead teams on multiple projects across orgs. My comment about network requests is because one of the most common issues I see in inexperienced engineers is writing database code locally where they add a lookup and insert on some dataset inside of a loop. Regardless of language this is unacceptably slow when a real network is involved.

Yeah, a lot of database management systems have really bad API designs, often mirroring the underlying database API directly to the user over the network without any further consideration towards the network having different constraints.

Said database APIs are typically not unreasonable when the database is running in the same memory space as the application, where latency is unnoticeable, as historically was the case when a lot of these APIs were designed. But, as you know, the model breaks as soon as you find yourself in a high latency environment, like over a network.

So then you get some weird bulk operators bolted onto the system to work around the latency issue, but they don't fit the mental model of the rest of the API designed around the idea of single unit operations. Save catching it in the fine print, they go unnoticed. Indeed, the naive programmer who hasn't yet been burned will not be able to fathom that another developer could design such a bad API and will put faith in the idea that the underlying system will somehow automatically mitigate the problem you describe. And in small scale testing it works fine, so there is no reason to doubt that notion. That is, until it is too late...

The experienced developer has learned to stop trusting other developers and bring a heavy skepticism when using another's API. This is a blessing as it means they (usually) stop making those kinds of mistakes when they encounter a bad API, but it is curse as it means they see no reason to fix the problem. "Why don't the junior devs just know better?!" they say. And so, the cycle repeats.

A dev being able to tell you the time complexity of their code isn’t trivia it’s a very important tool to be able to document, discuss trade offs and generally plan for time complexity at scale.

I’ve worked and led teams in multiple problem domains. Devs not understanding how to optimize to avoid slow time complexity is definitely one of the first nuts you have to crack in a new engineer.

I don’t know. I generally haven’t seen these be a problem. I think I’ve seen accidental n^2 complexity a couple of times at most and it wasn’t code written by juniors but rather just an oversight in adding nested loops somewhere they didn’t need to be. Now I have seen juniors who couldn’t figure out what was n^2 and how to fix it when given it in an interview, but slowness and big-o being related is generally rare. As you mention poorly considered sequences of network calls are more common). Additionally, the relation between the big o of a data structure and the big o of the overall algorithm solving some higher level problem tends to be more decoupled except for some very specific problem domains. I’m a systems engineer having worked in OS, embedded, mobile, and distributed systems and have seen big-O analysis of the high level code documented about 0 times (and it would have been helpful about as many).

Again, not saying it’s irrelevant and it might be highly relevant in some problem domains. But in general big-O of the common data structures should be memorized with the rest being trivia that should be accessible in the documentation for the data structure (or by looking at the implementation and doing it yourself).

> A dev being able to tell you the time complexity of their code isn’t trivia

I take it that you didn't bother to read the thread you are replying to? There is no reason why you need to have the time complexity of any given function memorized should someone ask. You can – better yet, they can – read the documentation or, failing that, read the code to answer the question. If you happen to have it on hand, that's great and all, but it is only necessary if the asking party see themselves as a trivia master.

> Devs not understanding how to optimize to avoid slow time complexity is definitely one of the first nuts you have to crack in a new engineer.

You never really crack that nut, no matter how experienced, as many problems have no known faster time complexity solution to provide the 'how'. To begin to try to crack that nut you're going to down the road of researcher, not writing day-to-day software, and even then your research is not guaranteed to yield results.

A much shorter, less amazing answer: it’s hard to know what you don’t know! This sort of background knowledge is exactly what big tech claims to look for in applicants, because it comes up in tiny little ways at unexpected times.

Whatever you work in, chances are you run into situations where you need to choose between multiple solutions, optimize things or generally find out why things aren’t optimal. Your needs are always your needs, and if you are informed about how different tradeoffs compare, it helps to understand how they work.

To keep things more substantial, consider facing issues storing data at your company. Maybe the nature of your data flow causes constant slowness, because your B-Tree indices are being constantly rebalanced on writes. You knew this because you understand how B-Trees work and you also know LSM trees might be a better data structure for your needs.

And so what I mean is that understanding the big blocks you use in high level often requires understanding data structures and algorithms, even though you don’t need to implement them

I think implementing some data structures like hash tables, lists and trees is the best way to get a feel for when one is suitable and what their traits actually are apart from just “has O(1) insert”. You can accomplish the same by lots of use, benchmarking, studying their source code etc too. But implementing at least to me is the quick and fun way of developing this gut feeling. It’s also not that rare to suddenly have the need to implement something you’d usually find in a library because you need some unique variation of an algorithm/data structure.

Whether this is truly fun I guess depends on where you are on the developer spectrum. I’d much rather develop low level libraries than app code so any chance I get is just a great opportunity to dig into the low level stuff.

As a concrete example, it sometimes happens that I'm working on existing code trying to make it faster, because it just isn't up to it's task at the moment. Looking over the code, I can see that it has some code that does a LOT of lookups to see if something is in a collection. And I can see that the collection is using a linked list; which is horrible for lookups. This is something I can notice just browsing through the code because I _already_ know the implementation (and performance) details of a linked list.

At this point, I can take a look at the rest of the code and see if there's some specific reason a linked list was chosen, or if it was just that the developer didn't put much thought into it. If there is a reason (order matters, etc), I can consider what other structures might _also_ suit that need, but also give faster lookups. And, because I know of a variety of data structures, how they're implemented, and what their characteristics are; coming up with some initial choices (or starting points) happens fairly rapidly.

So yes, I could get all this done without knowing all that information. But it happens a LOT faster because I know it. I notice the issue faster. I have some starting points for options faster. Etc.

Not having that information would not prevent me from doing my job. But having that information makes me _better_ at my job. Faster, more efficient, safer, etc.

I came across concrete examples like this before, and solved them, so here's a slightly different take: I'm principally an engineer. In general it doesn't even matter what topic though obviously there are some which I know a lot more about because of experience. Programming is one of them. I don't have a CS degree, I've seen terms like b-tree a ton of times but couldn't even begin to explain what it is, you get the point.

Now: the way I approach an example like this is similar to what you do, but the difference is that I'm merely aware there's a bunch of different containers out there which behave in different ways wrt lookup/add/remove/... and for the vast majority of them I have no clue about the implementation. I don't need such implementation knowledge to realize that another container might be the trick here. I also don't really need that knowledge to decide which container that eventually might be, nor to come to conlusions fast (since you're stressing that): that's a couple of minutes to lookup moreover the final decision stage will be through performance testing anyway, because measuring under actual usage is the only way I'll ever be convinced one is effectively better than the other. That's usually what is going to take time, not picking one out of x. In the extreme it might even be so that I'd first need to write a wrapper to then have a configurable container type just to be able to have people test it under different workload types, etc.

Obviously I've been through this a couple of times and by doing so did become aware of main traits of various containers/algorithms/... and yes that will be somewhat faster in the decision process. Likewise there have been certain domains in which I did dig down all the way to the very bottom and obviously having to sort out problems in that domain will be faster for me. But in the end: for me personally 'x algorithms programmers should know' is useless. Job-dependent perhaps, on the other hand I've seen enough people struggle to come up with actual and practically useful software aspects exactly because they kept on getting lost in implementation details.

> But in the end: for me personally 'x algorithms programmers should know' is useless.

I guess for me, it boils down to something like "Given a software developer A, adding more experience to them will generally make then a _better_ software developer; and most of that is the knowledge they gained in that experience". Knowledge makes one a better software developer. And knowing more algorithms and data structures is one form that knowledge can take.

Do you just eye it up, or run a profiler to narrow down where the hot spots are?

I'm working in Java atm, and my general steps are

- Take a quick look at the symptoms and code and see if it's obvious

- Take a look at the jstacks and see if there's anything that stands out (lots of code stuck in the same place)

- Take a more thorough look at the code to see if anything stands out

- See if I can reproduce the issue locally

- From here it various wildly

I rarely run a profiler just because it's difficult to put it into place in a production environment (which is generally the only place these issue come into play unless you set up the conditions artificially on a lower environment). That's not to say never; I just try to identify the issue other ways first.

It is much easier to remember the traits of data structures if you know how they are implemented.

Not really. There are two key traits one needs to memorize for general purpose programming: time and space complexity. Literally a “cheat sheet” with a list of order notations is sufficient to memorize.

Just because they are general and are relevant to almost every problem, doesn’t mean there aren’t traits you need to be aware of that might be relevant to your problem.

It’s like the Microsoft Word problem. 10% of functionality is used by everyone (eg saving a file, opening a file, changing the font). Those are baseline “everyone should know this”. The remaining 90% is still valuable and used by distinct subsets of customers. If Microsoft started deprecating the long tail of features without careful cohort analysis they’d start losing swathes of customers.

So for the most common operations of the most common structures I’d expect memorization of complexities just because of repetition of use (or deriving/guessing it from first principles cause it’s easy for the most common ones). But there’s much more traits and it would be important to understand that (eg what are the primary drivers of CPU time when accessing a hash map? An array? A linked list?).

What you describe are relatively niche or uncommon uses of these algorithms and data structures. Further, the specific implementation details of a given algorithm become relevant in these contexts. Different implementations of a hashtable can lead to substantially different operational performance, and no textbook understanding (including the toy implementations performed as part of a CS curriculum, for example) of what a hashtable is will lead to the kind of understanding you discuss.

Of course. That’s why good libraries will describe the specific implementation. Not just hash table but whether or not there’s open or closed addressing, how buckets are chosen (eg cuckoo hashing, Robin Hood, etc). A text book implementation is simply meant to give you a starting point understanding of the design space but you need continuing education to become more of an expert to understand when this stuff matters. But this expertise is valuable across problem domains and levels up your technical expertise. At my level all the engineers I’ve ever interacted with have a solid grounding in the fundamentals.

I think in C++ it can help to know how they're implemented under the hood just to be aware of when it's allocating heap memory

If you don't understand how they work, you may end up choosing a wrong container for the job (e.g. a list instead of a dictionary), and you will be tied to finding modules that do a specific job in a case when it would be trivial to just write something yourself.

In many cases it will be impossible for you to write certain parts of code, or you will end up mashing random libraries together, ending up with a program that works 1000x too slow, instead of just writing a few lines of code that solves the issue.

This is especially true for graphs/BFS/DFS and binary trees/search algorithms.

Also, without training your understanding of basic algorithms, you may be unable to write a lots of code that goes beyond wrapping over basic libraries. Not to mention being able to write the libraries themselves.

I think you're asking a far more general question than you realize about things like professional standards, bodies of knowledge, what is or should be considered canon or foundational, how a curriculum should be constructed, how training programs should work, whether or not specific careers should require licenses, how they should be given. This doesn't apply only to software developers. If you're going to end up being a vascular surgeon, do you really need to know or understand anything about physics and chemistry? Does a contract lawyer need to know anything about legal theory or criminal law? Should a prison warden study ethics and social theory? Should a homebuilder learn about materials science and Newtonian static dynamics? A skyscraper builder? A bridge builder? Where exactly lies the divide between researcher and implementer? Engineer and hacker? Engineer and technician? Technician and hobbyist? Should someone who is good enough to make something themselves that basically works on the happy path be allowed to advertise and sell what they create to others? Should that practice be regulated at all and, if so, how? Most professions have better, widely-agreed upon answers to these questions than software development because they have existed for longer.

I would personally say there is definitely no answer to "what should all programmers know" other than at least one programming language along with its associated tooling and enough about a platform software can run on to deploy it. Beyond that, across the full spectrum of software lifecycle careers, I'd say we've started converging on somewhat of a hodgepodge depending on role and where the standards are coming from. IT technician type careers have various certifications coming from platform providers like Cisco, Redhat, and Microsoft, and industry groups like CompTIA. Corporate security gets things like CISSP. If you go to a university, majors in computer science will give you what we expect academics in the subject to know before they can run labs or teach, and software engineering majors some idea what we might expect team leaders in large software organizations to know about how more general engineering principles and practices get applied specifically to software. These tend to have a lot of commonality in terms of at least being familiar with the basics of operating systems and networking, information security, discrete math, data structures and algorithms, programming language paradigms and constructs, possibly some bit of how compilers and maybe processors work.

Then you get what large and well-known employers expect implicitly from their interview and promotion processes. This seems to have also converged largely on at least including basic common programming language constructs, data structures and algorithms, and possibly some minutiae related to specific languages, toolchains, platforms, ecosystems, and possibly larger principles related to things like distributed systems, databases, how the Internet and web work, depending on the nature of the major product lines.

No single person needs to know all of that, but if you do, you're probably reasonably well-prepared to understand the hows and whys of any well-known or largely-used software system. It definitely doesn't mean your daily life as a developer will ever involve directly using that knowledge any more than a practicing psychiatrist remembers and can recite the exact details of the Krebs cycle. But having to learn it still might help guard a bit against susceptibility to bullshit quackery from drugmakers trying to tell them a miracle cure can do something that is metabolically impossible.

People will come up with their reasons, but the thing is that even if you do learn these algos once in your life, and implement all these structures, unless you use them often, you'll very likely forget them. I did a lot of them 20 years ago, but completely forgot.

Depends on what you want to work on. But if you’re picking data structures without understanding the implementation details, then you’re not grokking the decision but instead comparing traits you happen to know about and ignoring the ones that aren’t explicitly thought to be called out. Basically the trait everyone things about is O(1) or not. But the design space for data structures is vast and CPUs they run on complex. Heck, sometimes the available abstractions are readily available just because it provides a simple general propose API that we’ve iterated in through trial and error over a long time. That doesn’t mean that design is actually optimal for your problem. Now in many problems you might not care. But there are definitely problems where you do start to care. All your answer is saying “I work at a very high level of abstraction” which is fine for you but there is real value in being able to cut through layers of abstraction (performance, bug hunting etc) and discarding that as trivia is myopic. It may not be valuable to you but it is valuable knowledge I’ve used countless times in my career.

Think about ECS in games - that requires a knowledge of data structure that transcends big-O trait comparison to exploit CPU architecture for drastically better efficiency.

You might ignore memory allocations but the under the hood allocations can be important in some cases to make sure they play friendly. Or understanding cache impact and why using a linked list may not be a great idea. Or when sorting+searching may make more sense than just searching.

The more you know the better able you are to make effective decisions and people who work strictly in abstractions tend to be limited in their ability to solve problems that cross abstractions.

> what's the point of knowing trivia on data structures and algorithms if you will never implement those or even be aware you're using them or not?

Because:

1: Sometimes you need to choose the algorithm, even if it's implemented for you. (Many languages provide many different kinds of collection types, varying on some small details that appear unimportant, until they are very important to your specific need or use case.)

2: Sometimes knowing details of the algorithm helps you avoid edge cases and other inefficient behavior.

3: Sometimes if you know the algorithm exists, you know what kind of library to search for, instead of reinventing the wheel.

To be honest, normally I'd agree with you--there's a core set of important algorithms and data structures that pretty much every programmer should be aware of and understand well enough to be able to figure out how to look for them should they need to use it. And while I normally have a visceral reaction against "XYZ every programmer should know" because it's almost invariably far more detail than what every programmer should know, your basic data structures and algorithms actually are important enough to fall into that category, and there's a reason that a course on the topic is essentially course #2 in a CS curriculum.

But after reading the table of contents here, I'm thoroughly convinced that this book is not about that. About halfway through, I gave up trying to count the algorithms it was covering because it seems like it randomly decides it wants to be an AI textbook instead. Its focus on AI is weird; if you've got time for Naïve Bayes classifiers, where's convex hull? Where's simplex [1]? Fast Fourier Transform? Union-find? Constraint satisfaction? Hell, where's quicksort?

Another harbinger of quality: there's a section on "Choosing between MD5 and SHA". If you have an entire section on that in a book published in 2023, something is wrong. Then again, an algorithms book needing to have a section on that topic is itself... o_O-worthy.

[1] Okay, there's a section on linear programming. A section. Which, based on the section headings, seems entirely focused on "here's how to use a linear programming solver" and not anything on the actual algorithm itself. My algorithms textbook has an entire chapter on simplex, with instructions on how to code the algorithm itself.

Thanks for the comment. What books would you recommend?

CLRS remains canon.

As noted by sibling, CLRS (https://mitpress.mit.edu/9780262046305/introduction-to-algor...) is perhaps the reigning king of algorithms textbooks.

I haven't read it myself, but Algorithm Design Manual (https://www.amazon.com/Algorithm-Design-Manual-Computer-Scie...) also tends to rank high on recommendation lists, and from looking at its table of contents, it does complement CLRS nicely--there looks to be a better selection of things like constraint satisfication or computational geometry.

Skiena is great, and is very different from CLRS --- I actually enjoyed reading through Skiena, where CLRS is a reference (and I'd just use the Internet instead of CLRS at this point).

Yes, I haven’t looked deeper into that particular book and really only wanted to respond to the general notion.

I'm going to somewhat agree with your assertion, because I'm one of those developers that builds my business by simply plugging what are essentially legos together and googling stackoverflow solutions to my architecture problems.

However, a small anecdote. I recently obtained my pilots license, and one of the things you'll quickly learn in aviation is that there is a massive amount of information that you are required to learn that you will almost certainly never need, except possibly for that one moment in 1000 hours of flying when something happens in the air, and you simply can't pull over to the side of the road.

Developers who have an understanding of the how -and- why when they are required to solve a problem vs just plugging a library in will have a much better career developing solutions and leading teams that do exceptional work. Back to my anecdote about aviation, understanding the "how -and- why" could mean life or death.

> (...) there is a massive amount of information that you are required to learn that you will almost certainly never need, except possibly for that one moment in 1000 hours of flying when something happens in the air, (...)

I don't think this logic applies to software development in general and algorithms in particular.

When you need to roll out a b-tree from scratch, just crack open a book and read up. The worst thing it can happen is that somr acceptance test fails and you roll back a change. That is hardly a life-or-death scenario.

The word "soft" in "software" has meaning.

Gp's point is about how there are many things worth learning even if you can't immediately see how they will be useful, and not about urgency or timing. Sure you can pick up a book and learn about b-trees if you have to but you might not even know that a b-tree is what you need in a particular problem if you never learnt it in the first place. Most algorithmic problems in the wild don't present themselves cleanly with a signpost saying 'this is an X algorithm problem'

> When you need to roll out a b-tree from scratch, just crack open a book and read up.

How would you know you need to use (or implement) a B-Tree in your solution VS some other data structure?

> Developers who have an understanding of the how -and- why when they are required to solve a problem vs just plugging a library in will have a much better career developing solutions and leading teams that do exceptional work.

Will they? Or do you just like the idea of a world where that is true?

Programming is (almost) never life or death and honestly is rarely even in the same ballpark.

Most people don’t need (or want) to do exceptional work.

Realistically, do most pilots remember these things?

I also don’t understand the career claim. How does that work?

Yes, as they’re literally life-and-death in many cases. Getting a pilot license requires one to demonstrate the ability to do certain “not common but not exactly uncommon either” recovery things from memory. And different bits of those “1000 things” play a role in different scenarios. If you’re lucky and at high enough altitude to have time to look up a checklist in the POH it’s great. When you have seconds because you just took off or something screws up on final you don’t have time to go through the POH or futz around with the checklists in your avionics (if they’re even there).

The pilots that don’t remember these things when they’re needed are dead.

That is probably right for most jobs in the industry. But it is not always so. You can use these algorithms in side projects (I did so for Go for instance, because it didn't have sets implemented and wanted to understand the language better).

Or maybe you lust for a career in the gaming industry, which yes have their own engines ready to use, but you might have to do optimisations of your own. Or work with SOC and embedded systems. Maybe you would like to work with Linux core tools one day.

I think there is a broader world than that of the common jobs in the silicon valley.

Go still doesn't have Set types. The usual thing to do is using a map of your type to either an empty struct, or maybe a bool, if I got that correctly (have only been using Go for a couple months so far)

Did you implement your own Set type and primitive functions?

Most languages implement sets using maps. The only major difference you can optimise for is the fact that in majority usage, keys in maps are likely to exist, whereas sets are used for membership checks. Bar that, you can just as well use a map with a dummy value.

Can you give a reference for that? It sounds very unlikely to me, although I've only read/gone through two relevant standard library implementations: F# and OCaml.

Neither of them use dummy values as you suggest. They have similar implementations (both are AVL trees) but sets really do contain only one value while maps contain two. I would be surprised if many other languages did as you suggest.

Python, Ruby, Perl. Languages where hashmaps are a builtin.

Python has its own set type not based on hashmap/dict, and that's been the case for years.

The set implementation points out some of the differences, at https://github.com/python/cpython/blob/main/Objects/setobjec... :

   Unlike the dictionary implementation, the lookkey function can return
   NULL if the rich comparison returns an error.

   Use cases for sets differ considerably from dictionaries where looked-up
   keys are more likely to be present.  In contrast, sets are primarily
   about membership testing where the presence of an element is not known in
   advance.  Accordingly, the set implementation needs to optimize for both
   the found and not-found case.

Java as well: https://github.com/pengisgood/jdk-source-code/blob/master/sr...

EDIT : and Rust: https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.ht... (this is used by the default implementation of HashSet).

Rust's HashSet is a HashMap mapping to "()", which is Rust's equivalent to "void".

That is true for the internal implementation details but HashSet provides a different API, it is not just a type alias. So you don't have to worry about semantics of what the values mean (like the bools in Go), and it has no size overhead.

Update: Looks like I had good reason to be surprised. Thanks everyone for the examples.

Yes in Go I think I’m mostly tempted to reinvent the wheel every few lines of code, for the sheer lack of stdlib abstractions I’ve grown used to.

This is funny to me, because Go is often touted as a language that has "everything you need" in the stdlib. Of course, I'm coming from the nodejs world, where before you can start working you first need to evaluate and choose: typescript or not typescript and if yes what build tool chain, which test runner, which assertion lib, which mocking lib, etc etc. Not really that long ago when you had to choose which async lib (now you just need to choose which async color).

Thankfully a lot of that stuff is in nodejs now, and there's a commitment to maintain parity with Web APIs which also helps, but there's still a lot of half-done work and path-dependencies on outside libs.

> This is funny to me, because Go is often touted as a language that has "everything you need" in the stdlib.

My usual example of something missing from the standard library is

    func max(a, b int) int {
      if a > b {
        return a
      } else {
        return b
      }
    }

math.Max only operates on two float64s (due to the absence of function overloads; many standard library functions such as this predated generics), so if you want to avoid casting (and/or potential loss of precision if you're working with int64), you need to reinvent the wheel.

Go has had generic forms of the `min` and `max` functions as builtins since 1.21. https://pkg.go.dev/builtin#max

Go 1.21 is the version from which it is noticeable that they are pushing towards (re)implementing things that were lacking before due to missing support for generics.

Like the new slices package, meant to do common operations on slices, that is brand new on 1.21.

I wouldn't be surprised to see more and more new additions leveraging generics in next releases.

Good to know! I admittedly haven't written much Go in the past year, and while min / max were some of the most egregious examples, I'm sure there are plenty more that still exist.

You actually don't need any of that stuff, you can just write .js files and run them in node. The node.js standard library is quite extensive.

It's much much better now, especially if you are willing to adopt the experimental modules.

I did it using maps and generics and implemented a subset of the convenience methods that python has in sets.

> a broader world than that of the common jobs in the silicon valley.

I'd hope it was the opposite: common jobs outside the valley ought to be all the plumbing of comesouttas into goesintos, and the valley ought to be concentrating on the fewer problems where deeper skills yield much higher values?

(I left the valley in the 1980s, so this may be just rose-coloured nostalgia)

I always joke that the best thing I learned in university is the ability to learn. Most of the actual things that were taught there were pretty standard stuff (compilers, algorithms, a bit of functional programming, monads, formal methods, linear algebra and other math, etc.).

Almost none of that is stuff I use on a daily basis and I've frankly forgotten most of it. And I work with successful programmers that skipped college entirely and never learned any of that. I don't find myself building compilers that often and while I enjoy the functional programming renaissance in languages in the last ten or so years, I had to relearn a lot of that stuff as I hadn't touched any of it in 20 years. A lot of the expert systems and Bayesian belief network stuff in the nineties got obsoleted by machine learning later.

While I've forgotten most of that stuff, I remember enough to get back into it when I need to. Which has happened a couple of times. Mostly, I just hit Wikipedia, read up on a bunch of things and then figure out what tools and libraries are appropriate.

And there are a bunch of things that I was taught that didn't click until I learned it properly by doing it in practice. Like dealing with concurrency. Which, as it turns out is less about formal methods (and temporal logic, which was a pet topic of my teacher) and more about engineering practical solutions to very real problems which my teacher had never experienced because he was an academic. I knew all the lingo but hadn't really experienced any of the pain. Nothing like debugging a misbehaving system where you can see all this play out in real life.

I never cease to be amazed by the amount of stuff I have to learn on new projects and have dealt with some amazingly niche stuff over the years. That's stuff from computer science, medical stuff, material science, legal stuff, and more. If you do software for companies working in some niche field, you end up absorbing a lot of knowledge about what they do, how they do it, and why.

> I always joke that the best thing I learned in university is the ability to learn.

I hope no one laughs -- it's not a joke.

i thought the same -

I was told early on at uni that you're going to forget almost everything here or things change and you won't need this info

but hopefuly you'll develop an engineering mindset

It’s explicitly the point of an undergrad degree.

Traditionally the masters degree is where you start specializing and becoming an industry expert.

The undergrad degree is intended to teach you how to learn and then how to learn within your specific specialization without becoming an expert in the specialization.

This was one of the main lessons they hammered into us at UIUC in the early 90's.

> And I work with successful programmers that skipped college entirely and never learned any of that.

I also noticed this and questioned what I have to offer more. But once and a while there is this complex problem, and then you can see that some developers run into their limits, while others (mostly university degrees) can go further.

While I agree with using libraries and not reinventing the wheel, we should not ignore the fact that the latest sorting algorithms introduced in Go, C, CPP, and Rust, if I’m not mistaken, were introduced between 2020 and 2022. New algorithms and data structures are refined almost every year to adapt to new hardware and specifications.

A good engineer must understand the hardware, the data, and the algorithm.

And 99.999% of all SDE do not need to implement these algorithms. Or ever understand them. And those that do, should seek that knowledge of their specific circumstance when the need arises.

99.999% of all SWE don’t know that algorithms and data structures evolve. How can you they choose the right library? That was my point.

They know (I hope), but it is completely irrelevant for the vast majority of work they do. And if it becomes relevant with the use of profiling, they can dive down in the details.

> Most programmers shouldn't be writing their own lists, hash maps, b-trees, sort algorithms, etc. Or generally reinvent wheels.

Of course one should not reinvent the wheels. But understanding tricks and idioms used in these algorithms are useful elsewhere and in general helps you grow as a programmer.

I figured the point was learning a mental model of the solution or how it was arrived at, so this can be reused as a template for different problems.

As an aside, for non-programming mental models I found the Personal MBA by Josh Kaufman to be fantastic. Its title and marketing cheapen it a bit but the content is on point, extracting the best reusable patterns from graduate business education.

In order to consume such algorithmus in any form, one should first know whether such algorithms exist at all. Moreover they should be able to figure out which one applies to their problem best.

Depends strongly on how you define “know”-in that context I perceive it as referring to having or gaining some basic conceptual comprehension of the concept or algorithm, particularly in order to eschew reinventing the wheel in a squared shape, and thereby unnecessarily exhibiting exponential complexity.

It also depends on your field of work.

“Knowing” of them would tell one where to look and how to think.

> Most of those you'd consume in library form

It seems having great libraries is both a blessing and a curse to software engineers. On one hand, we get to build increasingly more powerful systems with these libraries without being bogged down by re-inventing the wheels -- some of which are nearly impossible to implement anyway, such as BLAS. On the other hand, it seems a waste of time to spend years studying the fundamental algorithms and data structures -- or in a narrow view our CS background is not necessarily a moat for us nor a foundation for us to build our expertise on. Of course, a lucky or talented few can build their careers on deepening their CS background, but many of us end up spending majority of time integrating various libraries and systes.

Likewise, most algorithms and data structures is to give the developer an idea how expensive it is to run. And these are often the things that people who studied CS has an edge over the self-taught ppl. However, I have too not written those things since college a long time ago.

Understanding time & space complexity is tablestakes for many software engineer roles. It sounds naive to think that self-taught ppl would lack that knowledge

One person's "naive" is another's "statistical conclusion after having worked with enough self-taught or bootcamp-educated people".

There are some good self-taught devs and a select few bootcamp-educated devs in the same sense that there are a few unwarped 2x4s available at your local Home Depot - the fact that the exceptions exist does not disprove that the majority are not worth your time.

I think for anything more complicated than (maybe) sorting, appreciating the subtleties in these algorithms goes a long way in helping you decide when to use them vs not.

Still good to know how they work. Helps with mental modeling.

“Reinventing wheels is how we get better wheels.” - Source Unknown

If they come in a library or as part of the language, that's an even better reason why you should understand how they work.

If you live in a world where a line of code assigns a variable or dereferences a pointer or emits adds and imuls, you can probably get what's happening just looking at the code.

If each line of code manipulates complex structures, sends queries to the database, interfaces with the network etc, you'd better know what you're doing and you'd better know it well.

One thing about learning algorithms from scratch is you learn how to measure code in terms of various resource costs (cpu, men, I/O). Being able to understand the cost of a given code block is very valuable.

It doesn't seem that people actually learn those things in many cases. I encounter programmers fairly regularly who struggle to grasp CPU vs memory vs I/O trade-offs and have no mastery of tools for measuring them.

This is unfortunate because the tools can often be a cheat code. It's painful to see people fixate on one possible cause without going to fundamentals and making a proper assessment. These people all pass the traditional programming interview filters for algorithms.

Srsly

With technology moving faster than ever, I believe we need to cultivate more acceptability for simply using existing stuff

while rudimentarily understanding how it works, obviously ...

Sometimes the general purpose implementations just don’t cut it, depending on the data access patterns, the hardware, etc., neither do they exhibit sufficient tuning capabilities. Sometimes people find out how embarrassingly inefficient a stdlib implementation under the hood is.

Even if you’re not trying to reinvent them, understanding how wheels work is useful.

you must be able to code them manually for new jobs,leetcode style,though

Reply on news.ycombinator.com