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

211–220 of 232 posts

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

#211

Post by 72deluxe »

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 had this on Magento 2.3.3 for a "custom stock" module that was running loops to grab data for a product and its child configurable products. As Magento is written in a modular way, asking a subcomponent for data can involve a database lookup so it is really slow to use and painful to debug.

Anyway, it was running 29000 database queries as it was repeatedly using an "in" clause of 1 item across hundreds of queries, instead of 1 query with hundreds of items in the "in" clause.

I replaced them with 1 query that fetched all it needed instead of the 29000 queries (and 8000+ which were duplicates).

Terrible code.

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

#212

Post by 72deluxe »

aneutron wrote: post #33

Reminds me of the time we found out a team was running O(n^2) code, but in terms of SQL Queries, that is to say, not O(n^2) of comparisons or anything, and were trying to blame the other team when a client sent a request that never ended. And they tried blaming them for migrating data to a new server with an SSD that shaved 20 minutes from their processing time. And if you're wondering, they refused to fix it because…

Funny that you used the word "team" when the outcome is anything but teamwork.

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

#213

Post by mantap »

esoterica wrote: post #196
bsder wrote: post #125

Earlier quoted context omitted.

Asymptotically, that's true. In reality, O(n) and O(2n) can be quite different for small n. As can O(n)+k0 and O(2n)+k1. Or worse, O(n^2)+k2 where sufficiently large k0 and k1 make the quadratic system better because it's k2 constant is so much smaller. Setup time matters. Nowadays, you rarely have enough elements that the asymptotic behavior is the defining performance characteristic.

O notation is asymptotic by definition. The sentence “O(n) for small n” is completely meaningless. O(n) cannot never be different from O(2n) because they refer to the exact same set of algorithms.

Theoretically yes but practically no. Theoretically Big O notation is defined as a limit that goes to infinity but in practice there's no such thing as infinity and saying that an algorithm's runtime is in O(n) implies certain things about its behaviour for finite n, that's kind of the point. And it's perfectly possible for an algorithm to be defined piecewise on the input size and so saying it has runtime O(n) for small n is a statement that has practical significance.

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

#214

Post by BubRoss »

vengefulduck wrote: post #186
NeoBasilisk wrote: post #164

Earlier quoted context omitted.

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.

Most people get the partition algorithm wrong on their first try if they write it themselves.

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

#215

Post by _fbpt »

monoideism wrote: post #65
masklinn wrote: post #54

Earlier quoted context omitted.

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

When was this story from? From my limited knowledge, I think persistent hashmaps have been available since Clojure 1.0 (2009) or before? (hash-map, https://clojure.github.io/clojure/clojure.core-api.html#cloj...).

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

#216

Post by monoideism »

_fbpt wrote: post #215
monoideism wrote: post #65

Earlier quoted context omitted.

> 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

When was this story from? From my limited knowledge, I think persistent hashmaps have been available since Clojure 1.0 (2009) or before? (hash-map, https://clojure.github.io/clojure/clojure.core-api.html#cloj... ).

He was working in OCaml, which even now isn't fortunate to have a persistent O(1) hashmap like Clojure (and Scala, I think) does in the standard library.

It's true that there are a few 3rd party implementations that I've noticed before, but not sure how robust and well-tested these are. I'd hesitate to use them or something I wrote in production without careful review.

In any case, persistent HAMTs are a relatively new phenomenon that are just starting to catch on, and this story is described as being "back in the day". It's unlikely this option was available to him even if he were willing to write an implementation himself or use an untested 3rd-party implementation.

Maybe one will be added eventually to one of the OCaml standard libraries, which would be great.

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

#217

Post by ygra »

vortico wrote: post #198
concerned_user wrote: post #120

Earlier quoted context omitted.

It can be correct if you are talking about subprocesses/subshells of another batch script/command then yes, separate shell process will be spawned in each iteration.

No, I recall reading that the batch processor closes/re-opens the file, scans for n carriage returns where n is the current line number, executes that line, and repeats. These are the sources I found. http://xset.tripod.com/tip3.htm "COMMAND.COM reads and executes batch files one line at a time; that means that it reads one line, execute it and rereads the file from the beginning to the next line." Perhaps this is a…

Seeking to a file offset is a constant-time operation (assuming no fragmentation), so re-opening the file and skipping to where you left off isn't that bad.

And you can certainly write self-modifying batch files, but only appending at the end is safe, not changing lines before you're currently executing.

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

#218

Post by vortico »

ygra wrote: post #217
vortico wrote: post #198

Earlier quoted context omitted.

No, I recall reading that the batch processor closes/re-opens the file, scans for n carriage returns where n is the current line number, executes that line, and repeats. These are the sources I found. http://xset.tripod.com/tip3.htm "COMMAND.COM reads and executes batch files one line at a time; that means that it reads one line, execute it and rereads the file from the beginning to the next line." Perhaps this is a…

Seeking to a file offset is a constant-time operation (assuming no fragmentation), so re-opening the file and skipping to where you left off isn't that bad. And you can certainly write self-modifying batch files, but only appending at the end is safe, not changing lines before you're currently executing.

>re-opening the file and skipping to where you left off

That's what Windows does now. But I think in the past it wasn't that way (as suggested by the sources). In my tests it appears that the command processor caches the byte offsets of each line, so it's possible to GOTO any line in the past without rescanning the whole file.

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

#219

Post by Graham24 »

chx wrote: post #147
vecter wrote: post #99

Earlier quoted context omitted.

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

The very idea of O(n*(n!)^n) is going to give me nightmares.

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

#220

Post by RomanBob »

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

>and the exponential O(n^2)

You need to look up what exponential means.

Post reply on HN