Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

O(n^2), again, now in Windows Management Instrumentation

randomascii.wordpress.com

Post reply on HN
Print view View original

101–110 of 232 posts

Re: O(n^2), again, now in Windows Management Instrumentation

#101

Post by cogman10 »

mrec wrote: post #16
leetcrew wrote: post #11

Earlier quoted context omitted.

sometimes it was correct to choose O(n) instead of O(1). if you know you're only going to have very few elements, linear search on a vector can be faster than a hashtable lookup or rb-tree traversal and use less memory for the data structure. later on some clown decides to expose your private function for their own convenience and starts calling it with thousands of elements.

You're not wrong, but IMHO the proper place for that sort of optimization is inside the dictionary class/module/whatever. It knows why the optimization is there and the conditions under which it makes sense. For application code it's probably better to express clearly what you're trying to do, in this case keyed lookup. Throwing in a linear search at that level isn't just dangerous, it's potentially confusing to peop…

Depends. Sometimes the key isn't easily hash or comparable. For example, I know of a few case where the keys looks something like "if (a > b and c Now, that doesn't mean you can't hash a, b, c, and d. It just means that the logic around doing the lookups is nontrivial.

When you are talking about < 100 elements, sometimes the consideration is "Welp, this is < 100, so lets just n^2 it".

Re: O(n^2), again, now in Windows Management Instrumentation

#102

Post by mehrdadn »

cogman10 wrote: post #101
mrec wrote: post #16

Earlier quoted context omitted.

You're not wrong, but IMHO the proper place for that sort of optimization is inside the dictionary class/module/whatever. It knows why the optimization is there and the conditions under which it makes sense. For application code it's probably better to express clearly what you're trying to do, in this case keyed lookup. Throwing in a linear search at that level isn't just dangerous, it's potentially confusing to peop…

Depends. Sometimes the key isn't easily hash or comparable. For example, I know of a few case where the keys looks something like "if (a > b and c Now, that doesn't mean you can't hash a, b, c, and d. It just means that the logic around doing the lookups is nontrivial. When you are talking about < 100 elements, sometimes the consideration is "Welp, this is < 100, so lets just n^2 it".

> where the keys looks something like "if (a > b and c Confused, what do you mean when you say the key is an "if" statement?

Re: O(n^2), again, now in Windows Management Instrumentation

#103

Post by nabnob »

masklinn wrote: post #54
cogman10 wrote: post #42

Earlier quoted context omitted.

The one benefit of n^2 is it is really easy to do without any additional memory or data structure requirements. To make an n^2 algorithm n (or n log n), you pretty much always need to add in some constant time or logarithmic data structure. That requires tracking that structure, usually generating a good key, etc. I'm not saying that's really all that extreme. It just means your previous 5 line algorithm will often "…

That still makes no sense. The GP is literally just talking about switching from an association list to a hashmap : > Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. […] After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant. You're not tracking more things (just tracking a has…

Not OP, but I'm guessing it's because linked lists are recursive and hashtables are not, so in a functional programming language you can do lots of clever things in a recursive way.

Re: O(n^2), again, now in Windows Management Instrumentation

#104

Post by jacobolus »

retrovm wrote: post #10
pjc50 wrote: post #8

Earlier quoted context omitted.

> Identification of critical API calls and respective timings would be integral to continue building the GUI elements. But we all know how waterfall is poo-pooed these days. If you've worked out which API calls are happening and how often, you've already written most of the application. It's just that it might be on paper or in pseudocode. Waterfall was abandoned because getting to that level of detail takes far too…

That presupposes that you can start with a big pile of bad APIs and somehow incrementally approach something worth having. That's not consistent with my experience. In my experience the innermost APIs, the ones that get written down first, are effectively cast in stone and dictate the quality of the whole product, forever. The first draft of a system is the one that should have all its APIs worked out with a pencil b…

You are right. It is typically more effective to write one implementation as a hacky prototype, play with it a bit, throw it away, and then rewrite a production implementation from scratch, so that the mistakes of a design made by someone inexperienced don’t get baked in forever.

Unfortunately there are cultural/psychological factors which often preclude or discourage this method, even if it would save time and produce better code in the medium term than either exhaustive planning up front uninformed by practice OR just iterating the initial broken version to continually meet new requirements.

Re: O(n^2), again, now in Windows Management Instrumentation

#105

Post by actuator »

stevefan1999 wrote: post #26

Well, now this show how polynomial time isn't necessarily any better than O(2^n), or exponential time in reality. Once the k grew bigger in O(n^k), our modern machine will still struggle to run it.

Not really. The n is huge, there is an enormous difference between an exponential complexity like O(2^n). Many algorithms are O(N^2) and are perfect for their use case.

To see the difference.

  - 100^2 -> 10^4, 2^100 -> 10^10
  - 1000^2 -> 10^6, 2^1000 -> 10^100
Look at the difference in order of growth. Just to give a very simplified comparison, your individual processor core can run about 10^9 simple instructions in a second.

Re: O(n^2), again, now in Windows Management Instrumentation

#106

Post by toast0 »

gameswithgo wrote: post #46

In the world of database backed web apps a related pattern is asking the database for some rows for a table, and then asking the database from some more rows, based on each row you just got. Rather than joining it together into one query. Makes it into production but falls down eventually!

I've actually had a lot of success going the other way. A database query with a join takes down production, so do a client side join, query one: get a bunch of ids from table A, query two: get a bunch of rows from table B, often as get one row from table B UNION get next row from table B etc.

You can try using IN on the second query, but usually if that was going to work in a reasonable amount of time, your join would have also worked in a reasonable amount of time.

The real problem people run into with the client side join is making it query one get a bunch of ids from table A, query two through N, get one row from B, with each query requiring a round trip. Even a pretty small client to server roundtrip of 1 ms gets nasty quick with repeated queries.

Re: O(n^2), again, now in Windows Management Instrumentation

#107

Post by mehrdadn »

harikb wrote: post #2

A gem > Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there

Speaking of O(n^2) algorithms (if it's OK for me to promote my own writing on this recently?):

I recently illustrated how they can even occur as a result of algorithms being slow by a constant factor.

I thought it might be useful for others, so I posted it here: https://news.ycombinator.com/item?id=21745911

Re: O(n^2), again, now in Windows Management Instrumentation

#108

Post by aflag »

BlackFingolfin wrote: post #96
aflag wrote: post #74

Earlier quoted context omitted.

The point was that you can often convert nested loops into two loops that are not nested. O(2n) conveys that, O(n) does not.

Actually O(2n) did not convey this for me at all, all it did for me was cause confusion. If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation

Interesting, I hear people spelling out constants all the time when using the O notation to put emphasis where they want. I guess that's not really as universal as I thought, but I still think it's a good way to express.

Re: O(n^2), again, now in Windows Management Instrumentation

#109

Post by Craighead »

vecter wrote: post #99
ww520 wrote: post #79

Ah, this brings back the memory of my O(n^2) fiasco. I wrote a low level file system storage driver in the past. In the caching layer, there's a need to sort by LRU time for cache eviction. It's a minor thing not run often and I wanted to move quickly. Also since it's low level kernel mode code, I wanted the code to be simple and correct. The number of cache entries was not big. Bubble sort was adequate for small N,…

n^2 is polynomial, not exponential. If it was truly exponential (which a sort should never be unless you've decided to solve an arbitrary 3-SAT problem while sorting a list), then it would've blown up in your face much sooner.

What does exponential look like then?

Re: O(n^2), again, now in Windows Management Instrumentation

#110

Post by chousuke »

ComputerGuru wrote: post #35
crankylinuxuser wrote: post #4

Earlier quoted context omitted.

This is absolutely the better analysis. Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. And that usually means O(n) as it is perfectly acceptable for a single call... But when an O(n) calls another O(n) is where you run into trouble. But at the beginning, nobody was planning for that call to be fast - implicit requirements lead it that way. In some ways, being abl…

> Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. Which has led to the ridiculous software bloat we have today. This always MVP, break fast, break often garbage needs to die.

I feel like the concept of an MVP is often abused. It shouldn't be a thing that somehow works with bubblegum and luck; it should still be "solid". The point ought to be to leave out features, not quality.
Post reply on HN