O(n^2), again, now in Windows Management Instrumentation • Hacker News Board

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

#181

Post by paulddraper » Tue, Dec 10, 2019, 12:46 AM UTC

emn13 wrote: post #173

paulddraper wrote: post #155

Earlier quoted context omitted.

So the more precise term would be quadratic. "Exponential" is indeed misused. Half the time I hear it, it is lower, like quadratic or cubic. The other half the time is higher, like combinatorial.

Combinatorial? Seriously? The difference between exponential and cominatorial is essentially purely theoretical when it comes to computational complexity. In practice, even the difference between n and n log n is barely relevant, and the exponential and combinatorial are the exponentiation thereof. Nobody ever, ever deals with processes large enough where the difference both matters, and the process completes. Even a…

That's probably why it's misused so much.

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

#182

Post by kccqzy » Tue, Dec 10, 2019, 12:49 AM UTC

hhmc wrote: post #180

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,…

Quick sort can be made to be O(n log n) with careful choice of pivot - e.g. https://en.wikipedia.org/wiki/Median_of_medians

Generally it is preferable to choose the pivot randomly.

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

#183

Post by kccqzy » Tue, Dec 10, 2019, 1:01 AM UTC

mathgladiator wrote: post #113

vecter wrote: post #75

Earlier quoted context omitted.

Could you explain more? As the other commenter pointed out, 2^2^9 = 2^512 which is an astronomically large number (far more than the number of atoms of ordinary matter in the observable universe). Something doesn't seem right.

Why couldn't it be (2^2)^9 = 4^9 = 262144 ?

Because exponentiation associate to the right.

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

#184

Post by wesammikhail » Tue, Dec 10, 2019, 1:05 AM UTC

rcthompson wrote: post #3

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

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.

A useful heuristic from my CS professor: always treat every tab (indentation / complexity) to be equivalent to a cart that you are attaching your horse. Add enough carts (complexity) and you will soon be asking yourself why your horse isnt a nuclear reactor instead?

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

#185

Post by enedil » Tue, Dec 10, 2019, 1:07 AM UTC

thaumasiotes wrote: post #175

enedil wrote: post #172

Earlier quoted context omitted.

It's a subset, but also a superset.

Yes? But to replace O(2n) with O(n), you only need that it's a subset.

You have your point.

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

#186

Post by vengefulduck » Tue, Dec 10, 2019, 1:08 AM UTC

NeoBasilisk wrote: post #164

ynik wrote: post #161

Earlier quoted context omitted.

Bubble sort is popular because it's provably optimal... under extremely restrictive circumstances: https://stackoverflow.com/a/3274203 Those circumstances stopped being semi-relevant when even the cheapest computers started using (floppy) disk drives instead of tape drives, but somehow bubble sort is still being taught.

It's probably because the implementation of the algorithm is the simplest, because you don't need to modify the existing data structure. You don't need to merge or create new arrays. You just repeatedly loop and swap two elements when needed. Super easy by all metrics.

You don’t need to modify the data structure for most quadratic sorts though. Or even for quick sort.

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

#187

Post by lillecarl » Tue, Dec 10, 2019, 1:25 AM UTC

mark-r wrote: post #157

aflag wrote: post #141

Earlier quoted context omitted.

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

Bubble sort is the first one I learned, so I remember it the best. I never spent any time comparing any of the O(n^2) sorts so it never occurred to me to try a different one.

And here am I, just using what's in the standard library. of the language I'm writing. Never occured to me to try a different one.

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

#188

Post by ww520 » Tue, Dec 10, 2019, 1:26 AM UTC

sterlind wrote: post #162

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,…

You could also go with radix sort (O(N)), since your insertion times are presumably some kind of integer.

Yes, radix is faster. But at that point I was looking for stability and simplicity over all else. Merge sort was stable and simple to implement, with decent performance.

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

#189

Post by codetrotter » Tue, Dec 10, 2019, 1:39 AM UTC

I have over a 100,000 images on my iPhone and some apps used to be really really really slow when I selected browse album in them.

One of the apps that used to be maddeningly slow was Instagram, but Instagram has gotten better lately. No idea why though.

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

#190

Post by nitwit005 » Tue, Dec 10, 2019, 1:57 AM UTC

brucedawson wrote: post #150

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:…

I appreciate your efforts then. It's been a while since I was doing Windows development, but I remember staring at a bunch of hex values for thread IDs and despairing.