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

141–150 of 232 posts

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

#141

Post by aflag »

mark-r wrote: post #131
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,…

I once coded a bubble sort in an application where I expected the worst case to be n=4. Later that assumption was invalidated, but I had long ago moved on to something else. I hope the person who inherited my code doesn't still hate me.

Why bubble sort? I never understood its popularity. Selection sort feels a lot more intuitive to me and it's the same complexity.

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

#142

Post by ww520 »

mark-r wrote: post #131
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,…

I once coded a bubble sort in an application where I expected the worst case to be n=4. Later that assumption was invalidated, but I had long ago moved on to something else. I hope the person who inherited my code doesn't still hate me.

Ha. Have a beer!

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

#143

Post by thaumasiotes »

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

> If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation

O(2n) is not an abuse of notation. It's just as well defined as O(n). The fact that O(2n) is a subset of O(n) is a theorem, not part of the definition of the notation.

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

#145

Post by NateEag »

chousuke wrote: post #110
ComputerGuru wrote: post #35

Earlier quoted context omitted.

> 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.

When you leave out features and quality, you have a proof of concept.

Those are valuable things to build, IMO. Just make sure you leave out enough features that it cannot be pushed into production once someone else sees it running.

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

#146

Post by mehrdadn »

cogman10 wrote: post #134
mehrdadn wrote: post #130

Earlier quoted context omitted.

I'm confused what the variables are in this example—what's already in the container vs. what is being looked up. If we conceptually don't even have a proper mapping to begin with, then it doesn't make sense to ask whether it's hashable or comparable or not in the first place. If we do—then what is the "key" in this example?

Let me preface this by saying I work in finance and rules are weird. This comes up frequently when looking for fuzzy "duplicates". For example, sometimes you get data from 2 sources, one will send it through with 0.01 precision. Another will send it through with 0.001 precision. You can't hash or compare that. Things get more tricky when different finance institutes used different terms for the same entity. That does…

Right, so you have an application where you don't genuinely have a dictionary -- e.g., inserting items in a different order can result in a very different outcome even when all the keys are distinct, or even worse, inserting two keys and then removing a third can give entirely different results depending on the order in which you inserted the first two. (Or other arbitrary things depending on your application.) That can of course come up; it's just been quite confusing for me to see a fuzzy search scenario like this presented as a counterexample when (at least to me) the discussion seemed to be about proper mappings.

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

#147

Post by chx »

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.

> which a sort should never be

There's certainly a most awesome sort algorithm which is exponential...

https://www.dangermouse.net/esoteric/bogobogosort.html

They are not even sure what the complexity is but it's like O(n!^(n-k)) or O(n*(n!)^n).

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

#148

Post by brucedawson »

cross_wiber wrote: post #51
rcthompson wrote: post #3

Earlier quoted context omitted.

I think the other reason O(n^2) is a "sweet spot" is that it often arises from one O(n) algorithm calling another O(n) algorithm in each iteration, resulting in O(n^2) overall. Very often it's ultimately because the inner O(n) algorithm should have been implemented as O(1), but nobody bothered because it was never intended to be called in a loop.

That's a good point. It explains why you can very often unintentionally end up with an O(n^2) algorithm in the first place, and Dawson's law then explains why no one bothers to fix it until it's too late.

Hey, it's Dawson's first law of computing. I have more planned, and it's important to distinguish them.

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

#149

Post by thomasahle »

aflag wrote: post #108
BlackFingolfin wrote: post #96

Earlier quoted context omitted.

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.

It can cause more confusion though, if say you write O(kn), but the oh-notation hides a factor k^3, then it would be better to just write O(n). Or write O_k(n) to signify a hidden dependency on k. Or best of all, just write out k^4 n without any ohs at all.

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

#150

Post by brucedawson »

peter_d_sherman wrote: post #12

Excerpt: "I decided that the interactions were too complex to be worth analyzing in detail, especially without any thread names to give clues about what the 25 different threads in svchost.exe (3024) were doing." Future OS/Compiler Programming Note: It would be nice if threads could be individually named and those thread names shown/slowed/stopped/debugged in whatever tool implements Task Manager like functionality..…

The "thread names" clause was a hyperlink to an article I wrote a few years listing all of the problems with thread naming on Windows. Microsoft took the suggestions seriously and basically landed all of the features and fixes that I requested, so now when I'm profiling or debugging Chrome the threads all have nice names.

I just kinda like trolling Microsoft for not using their own thread naming API very much.

https://randomascii.wordpress.com/2015/10/26/thread-naming-i...

Post reply on HN