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

161–170 of 232 posts

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

#161

Post by ynik »

aflag wrote: post #141
mark-r wrote: post #131

Earlier quoted context omitted.

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.

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.

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

#162

Post by sterlind »

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.

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

#163

Post by [deleted] »

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.

[deleted]

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

#164

Post by NeoBasilisk »

ynik wrote: post #161
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 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.

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

#165

Post by _wldu »

kortilla wrote: post #88
jtolmar wrote: post #59

Earlier quoted context omitted.

Programming languages have native support for O(n) algorithms in the form of for loops. You can compose as many of those as you want to get a huge polynomial, but you have to go out of your way and do something a bit weird to get an exponential run time.

What? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)

Two for loops, one nested under the other, both upto N is clearly O(N^2) in the worst case. Three for loops (in the same manner) is O(N^3).

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

#166

Post by mntmoss »

Etheryte wrote: post #49
masklinn wrote: post #43

Earlier quoted context omitted.

10 years ago is 2009. Large web applications had been breaking out of intranets (where they'd lived for quite some time at that point) for years at that point. GMail was launched in 2004, Google Maps in 2005 (that's also the year "AJAX" was coined) the JS library war was done and over with (jquery, prototype, mochikit, mootools, dojo, YUI, … were all released between 2005 and 2006). IE7 was 3 years old, Google Chrome…

You seem to be missing the crux of the issue I was trying to address — even today, loading 50.000 items into a frontend application would be a very, very niche edge case. 10 years ago even more so. Tacking on arbitrary reference points from Wikipedia doesn't change any of that.

I can think of plenty of tasks where a 2009 frontend will potentially be exposed to workloads in the 10k-100k elements range:

* Editing objects in a 3D scene(e.g. a AAA open-world game or a CGI film)

* Plotting events in a long-running log on a graph

* Scraping and presenting data from web sources

The common thread here is that you have most of your data in application memory but not necessarily in a formal database system, and so you shoulder the full burden of managing it properly. In most cases the solution is to define a real backend and filter it there, paginate or otherwise reduce the amount that gets presented because data at that scale won't be usable by humans to begin with. But sometimes you do have a reason to explicitly want a "big list of everything," and equally as often you end up with the big list of everything just by accident. It just comes with the territory of report generation tasks.

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

#167

Post by sedatk »

AaronFriel wrote: post #57
jedberg wrote: post #37

The thing that impresses me most about this writeup is how much instrumentation there is on Windows now. I stopped using Windows about 15 years ago, but I don't think this kind of analysis was possible back then. Or maybe I just didn't know the tools well enough?

15 years ago? You might have just missed it. Event Tracing for Windows gained a lot of functionality in Windows Vista, which some[1] have described as the most forward-looking and instrumental release in Windows history. Vista had a lot of flaws, but it introduced almost everything fundamental to Windows 7 to Windows 10, save perhaps the more recent developments in virtualization and containerization. From differenti…

Vista's importance in Windows history can't be overstated. It's regarded as a failure in the end but it provided a great baseline for the releases following it. Windows 10 has a much better networking stack, update mechanism, device driver model, GUI etc, all thanks to Vista.

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

#168

Post by hnick »

At work we had a daily script that took about 30 minutes to run, and about 3 hours on the weekend due to more data. One day we got a report that a downstream service was missing SLA because the script wasn't finishing. I'd come onto the team late so wasn't aware this was abnormal.

It turns out it was now taking about 1-2 hours daily and 6-12 hours on the weekend depending on data size. This had been going on for months but gradually getting worse as the data grew, to the point it was unbearable so finally reported.

A senior programmer had removed the shell call to sort on an indexed text file and written their own ad-hoc sorter through every fresh programmer's favourite (you guessed it) bubble sort. To make things worse, this was perl which has a perfectly functional sort itself if you really have to do it that way. I still have no idea why this was done, I don't think asking would have been productive in that place at that time.

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

#169

Post by blattimwind »

aliceryhl wrote: post #136
blattimwind wrote: post #128

Earlier quoted context omitted.

2^n (by the virtue of Big-O, m^n is in O(2^n) for any fixed m).

This is untrue: There's no constant k such that k*2^n > 3^n for all n. In general O(a^n) is strictly stronger than O(b^n) if a > b. This is why you sometimes see complexities that are e.g. O(1.3894732894^n) in wikipedia articles on the best known cases for various algorithms.

Thanks for the correction.

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

#170

Post by enedil »

oneplane wrote: post #138
w0utert wrote: post #129

Earlier quoted context omitted.

Quadratic complexity causes the runtime to grow quadratically ;-) - Quadratic = x^2, e.g. 0,1,4,9,16,25,36,49,64,81 - Exponential = n^x, for example 2^x, e.g. 1,2,4,8,16,32,64,128,256 Already very bad for small x even if n=2, but for n higher than 2 you can imagine you will run out of time very, very quickly ;-P

I always thought of Quadratic to be exponential but specifically 'N to the 2nd'. I suppose that does actually make no sense whatsoever. Thanks.

That is wrong, because quadratic means that the variable is in the base, while exponential will tell you, that the variable is in the exponent (just as the name tells).
Post reply on HN