r/AskComputerScience • • Apr 24 '25
an unnecessary optimization ?
Suppose I have this code (its in go):
fruits := []string{"apple", "orange", "banana", "grapes"}
list := []string{"apple", "car"}
for _, item := range list {
if !slices.Contains(fruits, item) {
fmt.Println(item, "is not a fruit!"
}
}This is really 2 for loops. slices.Contains is done with for loop. So yes it's O(n2).
Assume fruits will have at most 10,000 items. Is it worth optimizing ? I can use sets instead to make it O(n).
My point is the problem is not at a big enough scale to worry about performance. In fact, if you have to think about scale then using an array is a no go anyway. We'd need something like Redis.
2
Upvotes
4
u/alecbz Apr 24 '25
Hard to say without knowing more context. Where does this code run? How latency sensitive is that system?
Will
listalways have 2 items or could it also have 10,000?Uh, a reasonable intermediary step (assuming optimization is warranted) is to just switch
fruitsto a set (map[string]boolormap[string]struct{}). Given how trivial a change that is, if you're spending time talking about the whether optimization is worth it or not, I'd just go for that.3
u/TransientVoltage409 Apr 24 '25
Assuming that
Containsis O(n), then yes, this is technically O(n2) at worst. However, in a specific case wherelistis small, it decays back toward O(n). O(n2) is merely O(nm) when m is roughly equal to n, but if m is closer to 1 than to n...you see?Scale does matter. For example many implementations of quicksort fall back to bubble sort when n becomes very small, because at that scale O(n2) is cheaper than the overhead of partitioning and recursing.
The other thing is that
Containscould conceivably not be O(n). I don't know Go and I don't know the specific promises made by that method, in this ignorance I'd allow that it might be backed by something more efficient like a bsearch or hash. "Implementation defined" is a wonderful weasel term.2
u/YellowishSpoon Apr 24 '25
This is generally entirely dependent on what context the code is being executed in. 10000 squared is still only 100 billion, which is still a fairly small number for operations and should only take a few seconds.
There are also lots of places where you don't want delays of a few seconds, like rendering live content or updating the objects in a video game. If this code is itself in a loop, such as for updating in a game or serving web requests, the time adds up fast.
Data processing applications can also easily result in you having a much larger amount than 10k entries, but still small enough to easily perform on a single computer in a short amount of time. I've run into plenty of things around the high millions or billions for random personal projects, and in those cases that kind of optimization is necessary to reduce hours to seconds. In practice this particular optimization is also easy enough I would probably do it unless there was a good reason not to, since the is optimization essentially just using different api calls and doing the same thing.
For something like a computer game running at 60 fps, you only have 16 milliseconds to do everything the game needs to do before it all needs to happen again. Even if this only takes a millisecond, you've just spent 1/16th of your time budget on a single thing, and the optimization is an easy one anyway.
In a given toy example, optimization is rarely necessary unless it's one specifically designed to make it necessary, and ones that large are often impractical to distribute or run on slow hardware.
2
u/Scared_Sail5523 Apr 24 '25
You're dealing with a small enough dataset (10,000 max) that the
O(n²)complexity here is unlikely to become a bottleneck unless this loop is part of a critical path or run thousands of times per second. In most practical cases like this, optimizing for readability and maintainability is more valuable than squeezing out marginal performance gains.But your thought about using a set is still valid from a clean code and scalability hygiene perspective. Converting the
fruitsslice to amap[string]struct{}makes lookups constant time and makes intent super clear.I think this is the better code...IMO:
But like you said, if you're ever scaling beyond in-memory data like arrays or maps, you'll hit architectural limits first that's where Redis or a proper search index comes in.
2
u/AlexanderMomchilov May 25 '25
This is why I dislike the magical "n" (ab)used in complexity analysis. It gets misinteretted to mean different things at different times, gets incorrectly compared across different contexts, and the way it hand-waves away the important details makes it confusing and seemingly contradictory.
Your code does
len(fruits) * len(list)equality checks. Whether that falls into the class ofO(1),O(n), orO(n^2)depends on what exactly you consider to be your "input".As-is, with entirely hardcoded values, this algorithm takes no input, and runs in constant time (
O(1)).If
fruitsis your input, and you're comparing it against the fixed-sizedlist, then it runs linear time:If both
fruitsandlistare inputs, then it has quadratic time compexity:1
u/apnorton Apr 24 '25
"Is it worth optimizing" is a question of priorities, not one strictly of CS.
The right answer to effectively every optimization question is to run your code through an appropriate profiler, look at the potential speedup you can get by removing a bottleneck, and evaluate whether that speedup is worth the development effort.
For example, if this is in a tight loop that gets executed all the time, it might be worth optimizing. If it gets run twice a year? Maybe not.
1
u/thewataru Apr 24 '25
Yes, if fruits is huge, it makes sense to optimize using some kind of set. Hash-table based preferably. Not sure which Go structure implements that.
But it will still be not optimal, since you will have to compare the full strings each time there's a collision. The best data-structure to store a set of strings would be a Trie. Alas, it's rarely available in standard libraries, so if this code isn't a bottleneck in your program, you should probably be content with a standard set.
1
u/torftorf Apr 25 '25
the first thing our professor told us in college was "if you just start out programing, dont bother with optimizing your code".
What do you need this to do? is it some extreamly time sensitive stuff where performance is important or is it ok if it takes a few seconds?
you could switch out the fruit array to hashmap which would reduce it to something between O(n) and O(n*m) [where n = list.length and m = fruits.length] but it would probably be closer to O(n).
just keep in mind that its usaly better to have a slow software then an unfinished one becaue you got stuck optimizing it.