Testing Is Better Than Data Structures and Algorithms

Property-Based Testing with PropEr, Erlang, and Elixir by Fred Hebert. While a book about a particular tool (PropEr) and pair of languages (Erlang and Elixir), it's a solid introduction to property-based testing. The techniques described transfer well to other PBT systems and other languages.

Test-Driven Development by Kent Beck.

https://www.fuzzingbook.org/ by Zeller et al. and https://www.debuggingbook.org/ by Andreas Zeller. The latter is technically about debugging, but it has some specific techniques that you can incorporate into how you test software. Like Delta Debugging, also described in a paper by Zeller et al. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=988....

I'm not sure of other books I can recommend, the rest I know is from learning on the job or studying specific tooling and techniques.

The Art of Software Testing, Second Edition. with Tom Badgett and Todd M. Thomas, New York: Wiley, 2004.

It is by Glenford Myers (and others).

https://en.m.wikipedia.org/wiki/Glenford_Myers

From the top of that page:

[ Glenford Myers (born December 12, 1946) is an American computer scientist, entrepreneur, and author. He founded two successful high-tech companies (RadiSys and IP Fabrics), authored eight textbooks in the computer sciences, and made important contributions in microprocessor architecture. He holds a number of patents, including the original patent on "register scoreboarding" in microprocessor chips.[1] He has a BS in electrical engineering from Clarkson University, an MS in computer science from Syracuse University, and a PhD in computer science from the Polytechnic Institute of New York University. ]

I got to read it early in my career, and applied it some, in commercial software projects I was a part of, or led, when I could.

Very good book, IMO.

There is a nice small testing-related question at the start of the book that many people don't answer well or fully.

The boil down the tests I like to see. Structure them with "Given/when/then" statements. You don't need a framework for this, just make method calls with whatever unit test framework you are using. Keep the methods small, don't do a whole lot of "then"s, split that into multiple tests. Structure your code so that you aren't testing too deep. Ideally, you don't need to stand up your entire environment to run a test. But do write some of those tests, they are important for catching issues that can hide between unit tests.

[1] https://cucumber.io/docs/bdd/

> People should spend less time learning DSA, more time learning testing.

And reading it as "More total time should be spent on learning testing than the total time spent learning DSA". That's one reading, another is that people are studying DSA too much, and testing too little. The ratio of total time can still be in favor of studying DSA more, but maybe instead of 10:1 it should be more like 8:1 or 5:1.

I've not ran into a case where I can apply a bloom filter. I keep looking because it always seems like it'd be useful. The problem I have is bloom filter has practically reverse characteristics from what I want. It gives false positives and true negatives. I most often want true positives and false negatives.

What's more concerning is "engineers" incurious about how lower levels of the stack work, or aren't interested in learning breadth, depth, or new things.

The article is saying that it's more important to write tests than it is to learn how to write data structures. It specifically says you should learn which data structures you should use, but don't focus on knowing how to implement all them.

It calls out, specifically, that you should know that `sort` exists but you really don't need to know how to implement quicksort vs selection sort.

The reverse also happens frustratingly often. One could spend a lot of time obsessing over theoretical complexity only for it to amount to nothing. One might carefully choose a data structure and algorithm based on these theoretical properties and discover that in practice they get smoked by dumb contiguous arrays just because they fit in caches.

The sad fact is the sheer brute force of modern processors is often enough in the vast majority of cases so long as people avoid accidentally making things quadratic.

Sometimes people don't even do that and we get things such as the GTA5 dumpster fire.

https://news.ycombinator.com/item?id=26296339

Not if the user can, say, farm 1,000,000 different rows 100 times over an hour and a half while gossiping with their office mates. I over Excel as Exhibit A.

that's an edgy take and a red flag

I think that a lot of people dislike testing because a lot of tests can run for hours. In my case it is almost 6 hours from start to finish. However as a software developer I have accumulated a lot of computers which are kind of good and I don't want to throw them out yet but they are not really usable for current development - i.e. 8GB of RAM, 256GB SSD, i5 CPU from 2014 - That would be a punishment to use it with Visual Studio today. But it is a perfect machine for compiling in console i.e. dotnet build or msbuild and running tests via vstest glued together with PowerShell script. So this dedicated testing machine is running on changes over night and I will see if it passed or not and if not fix tests which did not passed.

This setup may feel clunky, but it allows me to make sweeping changes in a codebase and be confident enough, that if the tests pass, it will very likely work for the customer too. The most obvious example where tests were carrying me around has been moving to .NET8 from .NET Framework 4.8. I have went from 90% failure rate on tests to all tests clear in like 3-4 iterations.

Tests give the freedom to refactor which results in better code.

>So, testing has its place, but testing is really no better than simulation

Testing IS simulation and simulation IS testing.

>And in simulation, the outputs are only as good as the inputs. It cannot guarantee code safety

Only juniors think that you can get guarantees of code safety. Seniors look for ways to de-risk code, knowing that you're always trending towards a minima.

One of the key skills in testing is defining good, realistic inputs.

This is the crux of the debate. If you work on CRUD apps, you basically need to know hash maps, and lists, but getting better at SQL and writing clean code is good. But there are many areas where writing the right code vs the wrong code really matters. I was writing something the other day where one small in loop operation was the difference betweeen a method running in miliseconds and minutes. Or choose the right data structure can simplify a feature into 1/10th the code and makes it run 100x better than the wrong one.

- What you want to do is probably trivially O(kn).

- There isn't a <O(kn) algorithm, so try to reduce overhead in k.

- Cache results when they are O(1), don't when they are O(n).

- If you want to do something >O(kn), don't.

- If you really need to so something >O(kn), do it in SQL and then go do something else while it's running.

None of that requires any DSA knowledge beyond what you learn in the first weeks of CS101. Instead, what's useful is knowing how to profile to optimize k, knowing how SQL works, and being able to write high quality maintainable code. Any smart algorithms that have a large time complexity improvement will probably be practically difficult to create and test even if you are very comfortable with the underlying theoretical algorithm. And the storage required for an <O(n) algorithm is probably at least as expensive as the compute required for the naive O(n) algorithm.

My general impression is that for small-scale problems, a trustworthy and easy algorithm is fine, even if it's inefficient ($100 of compute < $1000 of labor). For large-scale problems, domain knowledge and data engineering trumps clever DSA skills. The space between small- and large-scale problems is generally either nonexistent or already has premade solutions. The only people who make those "premade solutions" obviously need to feel it in their bones the way you describe, but they're a very very small portion of the total software population, and are not the target audience of this article.

CRUD apps are the ones that become more complex, not less. The idea that a "CRUD app" is the poster child of simplicity is mega-misleading.

Building a ERP or similar will eat you alive in forms that making a total OS from scratch with all the features and more of linux not. (Probably the only part that is hard as "crud apps" is the drivers, and that is because you see what kind of madness is interface with others code)

(Alternatively you could just argue it's a false dichotomy)

In software development hiring, everyone tests for DSA whether it is useful or not in the actual job description.

Anyways, now I’m a full-time lecturer teaching undergraduate CS courses (long story) and I’m actually shaping curriculum. As soon as I read this article I thought “I need to tell my data structures students to read this” because it echoes a lot of what I’ve been saying in class.

Case in point: right after two lectures covering the ArrayList versus LinkedList implementations of the Java List interface, I spent an entire lecture on JUnit and live-coded a performance test suite that produced actual data to back up our discussions of big-O complexity. The best part of all? They learned about JIT compilation in the JVM firsthand because it completely blew apart the expected test results.

Every programmer should know enough to at least avoid accidentally making things quadratic.

https://news.ycombinator.com/item?id=26296339

While understanding algorithms and data structures is important, the only way you really know how well it works, and how well it's implemented is by thoroughly testing it. There are an infinite amount of clever algorithms out there with terrible implementations.

You need both.

I like a more uniform distribution in my testing efforts. Start earlier, end later than most, and it’s experiences like this that inform that preference. And also production bugs in code with supposed 100% test coverage.

Which is something I've always agreed with, so, I never understand articles that seek to eschew an important part of releasing software because they believe their approach elsewhere is enough to overcome these intentionally suboptimal choices.

There's a blog post I read once and that I've since been unable to locate anywhere, even with AI deep research. It was a blow-by-blow record of an attempt to build a simple game --- checkers, maybe? I can't recall --- using pure and dogmatic test driven development. No changes at all without tests first. It was a disaster, and a hilarious one at that.

Ring a bell for anyone?

A classic example of invariant I can think of is the min-heap - node N is less than or equal to the value of its children - the heap property.

Five years from now, you might forget the operations and the nuanced design principles, but the invariants might stay well in your memory.

That's the same as the blog post: you need to know enough DSA to be able to understand how to look for the right solution if presented with a problem. But Batchelder's point is that, beyond that knowledge, learning testing as a skill will be more valuable to you than learning a whole bunch of individual DSA tricks.

The point of the article is that knowing how to test well is more useful than memorizing solutions to algo problems. You can always look those up.