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

61–70 of 232 posts

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

#61

Post by vanderZwan »

stevefan1999 wrote: post #30
savingGrace wrote: post #14

Earlier quoted context omitted.

I often see O(n^2) algorithms that can be reduced to O(2n) at the very least. One of the best things I gained from school was the red flag that fires off in my mind any time I see a loop nested in a loop.

you shouldn't call it O(2n), as there is already a constant inside of O(n), because it becomes 0 <= f(x) <= c*2n given a random f(x)

Eh, you're technically correct but when used as a point of relative comparison to an O(n²) algorithm I think there's some merit to it, because it actually gives some sense of constant overhead within the context.

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

#62

Post by rcthompson »

Probably the most important thing I learned about algorithmic complexity analysis in grad school was that N is not constant, but rather it grows over time (probably at an exponential rate). That is, as our computing power increases, we continue to aspire to analyze larger and larger data sets. So anything beyond O(n*log(n)) that works right now is more or less guaranteed to blow up in the not-so-distant future, if it remains in use that long.

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

#63

Post by jandrese »

JonathonW wrote: post #9

Honestly, O(n^2) is probably okay for a diagnostic tool that's only meant to be run occasionally-- I'd like to know why Google's IT department felt the need to schedule it to run so frequently.

That's the part that seemed insane to me. Dial it back so it only runs at 4AM every day and nobody would have noticed. Running it every hour seems like outright paranoia by the IT staff.

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

#64

Post by mixmastamyk »

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?

Same here. WMI and perf counters have been around a long time though.

I recently used Win10 for work and was amazed at the combination of awe-inspiring tech and plain awe-full complexity. Just the control panel goes four layers deep attempting to make things easier but in practice is several times harder to find options than it was in Win2k.

If there were a distribution with all the corporate goals stripped out I'd jump on it.

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

#65

Post by monoideism »

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…

> apparently significant loss of elegance would come from.

In a word, you're losing a persistent data structure[1]. And this can go beyond just loss of elegance. Sometimes, functional programs will depend on immutability of data structures for performance optimizations and even for functionality (like keeping a version history).

1. https://en.wikipedia.org/wiki/Persistent_data_structure

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

#66

Post by TravHatesMe »

vanderZwan wrote: post #61
stevefan1999 wrote: post #30

Earlier quoted context omitted.

you shouldn't call it O(2n), as there is already a constant inside of O(n), because it becomes 0 <= f(x) <= c*2n given a random f(x)

Eh, you're technically correct but when used as a point of relative comparison to an O(n²) algorithm I think there's some merit to it, because it actually gives some sense of constant overhead within the context.

What if the constant were massive? Then the coefficient might not be significant in practise. O(2n) might be worse than O(n+99999999), they both reduce to O(n) though. It is a classification.

Personally I would prefer to use different semantics to express that. It seems big O notation often carries a separate meaning in parlance.

I thought big O notation was about classifying function growth irrespective of the coefficient/constant. Does it not grow at all with respect to n? great you are O(1). Does it grow linearly? cool you are O(n). Logarithmically? Quadratically? In my mind, this kind of analysis aligns with big O notation.

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

#67

Post by ihaveajob »

This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) It was much easier to understand than a faster alternative, and 2) I could mathematically guarantee that the largest value of n was something like 8 or 9, so you could argue that it was in fact a constant time operation.

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

#68

Post by Google234 »

ihaveajob wrote: post #67

This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) It was much easier to understand than a faster alternative, and 2) I could mathematically guarantee that the largest value of n was something like 8 or 9, so you could argue that it was in fact a constant time operation.

2^2^9 is 1.340781e+154

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

#69

Post by protomikron »

vanderZwan wrote: post #61
stevefan1999 wrote: post #30

Earlier quoted context omitted.

you shouldn't call it O(2n), as there is already a constant inside of O(n), because it becomes 0 <= f(x) <= c*2n given a random f(x)

Eh, you're technically correct but when used as a point of relative comparison to an O(n²) algorithm I think there's some merit to it, because it actually gives some sense of constant overhead within the context.

> Eh, you're technically correct [...]

The best kind of correct. Calling it O(n) then is the best way to express the performance improvement - I think that's the whole point of Big-O notation.

However I agree that for smaller n one should not underestimate the constant factor impact.

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

#70

Post by the-rc »

retrovm wrote: post #15
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..…

POSIX threads can be individually named. They inherit the name of their creator if you don't set one.

As an aside, POSIX/Linux thread names have a limit of 16 bytes, which means 15 characters plus NULL. Speaking from experience, this can and will bite you when you need the names the most, if e.g. they are long, have just one or a handful of common prefixes and their creation is not entirely under your control.
Post reply on HN