2 ms·

> Pretty much everyone I know will throw down an O(n^2) algorithm or whatever in their first pass and replace it with something more thought out once they have

> Pretty much everyone I know will throw down an O(n^2) algorithm or whatever in their first pass and replace it with something more thought out once they have the time to think deeply about it. Most of the times I've seen this, the faster algorithm is literally just a dictionary with a well-defined key. I honestly do not understand why that's not the first solution most devs think of and why n^2 seems to dominate. As an example, I've seen code like this quiet a bit result = [] for (item: items) { for (item2: items) { if (item != item2 && item.foo == item2.foo) { result.add(item) } } } Easily replaced and massively easier to read as result = [] itemFoo = HashSet() for (item: items) { if (itemFoo.contains(item.foo)) result.add(item) else itemFoo.add(item.foo) } The mindset of re-looking for values in a collection you are already iterating through is just foreign to me. The first solution for something like this in my mind is always utilizing dictionaries.

YZF 2y ago
For many people performance optimization really starts with your second version. I'm not even sure what this is supposed to do exactly but the O(N^2) is just bad/sloppy code. Optimization is usually more about getting the right algorithms to execute faster. At least that's how I think about it.
- cogman10 2y ago
  Yet, as you'll see in this thread at least 1 other commentor is arguing that option 1 is better. What you and I see as bad/sloppy code, they see as the ideal starting point. A pretty common attitude that I've ran into. People take the "premature optimization" quote to mean "Never think about big oh when writing code".
  - 9rx 2y ago
    Beware of microbenchmarks, but at least on my machine under the specific circumstances I ran it under, the double loop algorithm is about two times faster than the hash map algorithm while n < 100. That might not mean much if you spend your days working with large datasets, but in my day-to-day datasets with 100 entires or less is the norm. Readability is subjective, but at least from a performance perspective it is a reasonable starting point unless you know upfront that you are going to be working with large datasets – but in that case the optimization isn't premature, is it?
    - cogman10 2y ago
      Here's the main issue I have with this reasoning. It builds in a fault to the program that doesn't need to be there. If n is usually less than 100 then sure maybe it does make sense to do the more brute force approach. However, what's the impact of using the hash table first? If n is usually less than 100, now this method is slower usually, but is that a problem? Well, you should use a profiler to find out if it is or isn't. However, that may be entirely tolerable performance wise. On the other hand, if your assumption that "n < 100" doesn't hold up and, indeed you start seeing n > 100, or 1000, or 10000. Now all the sudden this method becomes a fault in the application you developed that needs to be rewritten. What's devious about the "n > 100" problem is when you first write the code, you may have very well been correct that "n < 100". But time and inputs change the way code is executed. A lot of the code I've fixed has been due to this. I've seen the counter where really searching a list/array was the better option only a handful of times. To me, premature optimization is using a known algorithmically inferior approach, of the same complexity as the superior approach, because you know that for small n, it is faster without knowing whether or not that will be the case.
      - 9rx 2y ago
        > It builds in a fault to the program that doesn't need to be there. Not really. You're just exploring an unknown frontier. Once the frontier is known and you actually understand what you are trying to solve you're still going to put in the right algorithm. I mean, you might not if you're vibe coding, which I guess is apparently a thing somehow, but I'm assuming we're talking about actual engineering here, not speaking the sordid tales of cowboys. The "premature optimization" line was definitely not directed at those who think code is a feeling. When the frontier is unknown, whatever algorithm gets something operating as soon as possible is the right one. The given example may be so contrived that the hash map would be what you see as the quickest and dirtiest solution anyway, but with a little more complexity loops do tend to be easier to reason about on a first-pass basis. > Now all the sudden this method becomes a fault in the application you developed that needs to be rewritten. In the same way that finding out that a blue button doesn't resonate with users, requiring you to rewrite your application to make the button green. Such is the life of building software. But that's why engineers get paid the big bucks – nobody else is stupid enough to do it. > A lot of the code I've fixed has been due to this. You're not really fixing it, you're updating it to reflect the information you gleaned during the exploratory phase. I mean, unless you're coding on vibes or something, but, again, assuming actual engineering is taking place here. Nobody should be coding non-prototypes by the guide of their feelings.
Sesse__ 2y ago
The first version is more readable, faster for small n (which is the common case), can not run out of memory due to the hash table, compiles to less code, does not need item to be hashable and cannot accidentally copy elements (depending on language). It _should_ be your default. (Well, except you should start from the items after item1, so that you don't need the item1 != item2 test.)
- cogman10 2y ago
  > The first version is more readable Disagree > faster for small n (which is the common case) How can you know that? And for smaller n, the choice hardly matters. > can not run out of memory due to the hash table If n gets large enough that hash table size becomes a problem, n is large enough that you need the hash table or some other structure that reduces the complexity down from O(n^2). > compiles to less code This is just nonsense. Any codebase of significant size already has a hashtable setup and unless you are using a language like C++, the code size of using a hash table anywhere is constant. The cost is already paid. The actual amount of compiled code from the switch is identical. > does not need item to be hashable True. There would be reasons not to choose option 2, but it should be default until it's been proven to be a problem. And even then, the next step is almost certainly not going to be option 1. But then this could also be language and application specific. I deal primarily with backend services/Java where memory is plentiful, and allocation is fast. Algorithmic complexity is for my applications very often the better indicator of what good code should be.

YZF 2y ago

For many people performance optimization really starts with your second version. I'm not even sure what this is supposed to do exactly but the O(N^2) is just bad/sloppy code. Optimization is usually more about getting the right algorithms to execute faster. At least that's how I think about it.

cogman10 2y ago
Yet, as you'll see in this thread at least 1 other commentor is arguing that option 1 is better. What you and I see as bad/sloppy code, they see as the ideal starting point. A pretty common attitude that I've ran into. People take the "premature optimization" quote to mean "Never think about big oh when writing code".
- 9rx 2y ago
  Beware of microbenchmarks, but at least on my machine under the specific circumstances I ran it under, the double loop algorithm is about two times faster than the hash map algorithm while n < 100. That might not mean much if you spend your days working with large datasets, but in my day-to-day datasets with 100 entires or less is the norm. Readability is subjective, but at least from a performance perspective it is a reasonable starting point unless you know upfront that you are going to be working with large datasets – but in that case the optimization isn't premature, is it?
  - cogman10 2y ago
    Here's the main issue I have with this reasoning. It builds in a fault to the program that doesn't need to be there. If n is usually less than 100 then sure maybe it does make sense to do the more brute force approach. However, what's the impact of using the hash table first? If n is usually less than 100, now this method is slower usually, but is that a problem? Well, you should use a profiler to find out if it is or isn't. However, that may be entirely tolerable performance wise. On the other hand, if your assumption that "n < 100" doesn't hold up and, indeed you start seeing n > 100, or 1000, or 10000. Now all the sudden this method becomes a fault in the application you developed that needs to be rewritten. What's devious about the "n > 100" problem is when you first write the code, you may have very well been correct that "n < 100". But time and inputs change the way code is executed. A lot of the code I've fixed has been due to this. I've seen the counter where really searching a list/array was the better option only a handful of times. To me, premature optimization is using a known algorithmically inferior approach, of the same complexity as the superior approach, because you know that for small n, it is faster without knowing whether or not that will be the case.
    - 9rx 2y ago
      > It builds in a fault to the program that doesn't need to be there. Not really. You're just exploring an unknown frontier. Once the frontier is known and you actually understand what you are trying to solve you're still going to put in the right algorithm. I mean, you might not if you're vibe coding, which I guess is apparently a thing somehow, but I'm assuming we're talking about actual engineering here, not speaking the sordid tales of cowboys. The "premature optimization" line was definitely not directed at those who think code is a feeling. When the frontier is unknown, whatever algorithm gets something operating as soon as possible is the right one. The given example may be so contrived that the hash map would be what you see as the quickest and dirtiest solution anyway, but with a little more complexity loops do tend to be easier to reason about on a first-pass basis. > Now all the sudden this method becomes a fault in the application you developed that needs to be rewritten. In the same way that finding out that a blue button doesn't resonate with users, requiring you to rewrite your application to make the button green. Such is the life of building software. But that's why engineers get paid the big bucks – nobody else is stupid enough to do it. > A lot of the code I've fixed has been due to this. You're not really fixing it, you're updating it to reflect the information you gleaned during the exploratory phase. I mean, unless you're coding on vibes or something, but, again, assuming actual engineering is taking place here. Nobody should be coding non-prototypes by the guide of their feelings.

Sesse__ 2y ago

The first version is more readable, faster for small n (which is the common case), can not run out of memory due to the hash table, compiles to less code, does not need item to be hashable and cannot accidentally copy elements (depending on language). It _should_ be your default. (Well, except you should start from the items after item1, so that you don't need the item1 != item2 test.)

cogman10 2y ago
> The first version is more readable Disagree > faster for small n (which is the common case) How can you know that? And for smaller n, the choice hardly matters. > can not run out of memory due to the hash table If n gets large enough that hash table size becomes a problem, n is large enough that you need the hash table or some other structure that reduces the complexity down from O(n^2). > compiles to less code This is just nonsense. Any codebase of significant size already has a hashtable setup and unless you are using a language like C++, the code size of using a hash table anywhere is constant. The cost is already paid. The actual amount of compiled code from the switch is identical. > does not need item to be hashable True. There would be reasons not to choose option 2, but it should be default until it's been proven to be a problem. And even then, the next step is almost certainly not going to be option 1. But then this could also be language and application specific. I deal primarily with backend services/Java where memory is plentiful, and allocation is fast. Algorithmic complexity is for my applications very often the better indicator of what good code should be.