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

131–140 of 232 posts

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

#131

Post by mark-r »

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.

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

#132

Post by ammen99 »

blattimwind wrote: post #128
Craighead wrote: post #109

Earlier quoted context omitted.

What does exponential look like then?

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

This is not true, consider taking the limit 3^n/2^n as n goes to infinity, the limit is infinity, hence 3^n is not O(2^n)

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

#133

Post by jgalar »

albertzeyer wrote: post #22
muststopmyths wrote: post #18

Earlier quoted context omitted.

This already exists. Windows had a janky way of naming threads before 10, but it has a supported API now. The problem is that svchost is a host that runs a thread pool with various services being invoked as needed. You'd have to rename each thread every time you ran a function for a service. That's probably more doable now with the supported API. The previous way involved raising an exception, so I can see why it was…

For reference, this was the old API: https://docs.microsoft.com/en-us/visualstudio/debugger/how-t... This was well known, and many applications actually used that. Of course it was very ugly. I don't think it would have been a problem to also rename a given thread multiple times, but not sure.

It's very ugly, but at least it doesn't seem to limit you to 15 characters like on Linux (prctl/pthread_set_name_np).

That limit makes it pretty hard to provide meaningful identifiers in a non-trivial application.

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

#134

Post by cogman10 »

mehrdadn wrote: post #130
z92 wrote: post #121

Earlier quoted context omitted.

He probably meant, the lookup in the list is a conditional lookup based on a logic, instead of a simple key string.

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 doesn't mean you can't avoid n^2 duplicate searches. It just means you have to be smart about how you group things.

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

#135

Post by tedunangst »

Someone1234 wrote: post #80
JonathonW wrote: post #60

Earlier quoted context omitted.

'winmgmt.exe /verifyrepository', the tool with the O(n^2) behavior, is a diagnostic tool-- it verifies the consistency of the WMI repository.

He used that to manually reproduce, but the original behaviour wasn't caused by manually calling the winmgmt executable with the /verifyrepository switch. Instead the repo was being verified as a side effect of another WMI operation.

It sure sounded like they had a scheduled task to run it manually every hour. "Until then our IT department has promised to stop running the /verifyrepository command every hour, which should avoid the worst symptoms."

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

#136

Post by aliceryhl »

blattimwind wrote: post #128
Craighead wrote: post #109

Earlier quoted context omitted.

What does exponential look like then?

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.

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

#137

Post by flugaflusen »

blattimwind wrote: post #128
Craighead wrote: post #109

Earlier quoted context omitted.

What does exponential look like then?

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

This isn't quite right. For example, 3^n is not O(2^n) (see, e.g., https://stackoverflow.com/questions/19081673/big-o-notation-...)

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

#138

Post by oneplane »

w0utert wrote: post #129
oneplane wrote: post #122

Earlier quoted context omitted.

Would it be correct to say it's a quadratic complexity causing the run time to grow exponentially? Or is the word exponential still wrong here. My Mathematics terminology is rather.. dusty.

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.

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

#139

Post by ht85 »

toast0 wrote: post #106
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 woul…

After going through every pattern this is also my favorite one.

While it can add some perceivable latency if you have many levels of depth, it is usually a lot lighter on CPU and memory than one big query.

The reason I really like it is because it is very easy to strongly type results coming from a single table, and processing the data in your application code allows you to keep the typings through the process of stitching everything back together.

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

#140

Post by thaumasiotes »

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.

> In general O(a^n) is strictly stronger than O(b^n) if a > b.

Typo: O(a^n) is a stronger guarantee than O(b^n) if a b.

Post reply on HN