201–210 of 232 posts
Earlier quoted context omitted.
O(N^2) is strictly better than O(2^N). Per the article, this algorithm fell over at 3 billion bytes of data, but wasn't especially noticeable at 300 million bytes of data.
Better from an theoretical perspective. Depending on n and any constant factors, one or the other may end up winning in reality.
Earlier quoted context omitted.
What? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)
Actually, that should be: whoops(n): for i in n: whoops(n-1) Your version is merely quadratic.
that is not exponential, that is actually factorial, which is superexponential. Uh, or close to factorial, I'm not sure exactly. Testing it in python right now, incrementing a counter each time whoops is called, I'm seeing a relationship that looks like whoops(n) == n * whoops(n-1) + 1 That is interesting.
Earlier quoted context omitted.
I'm aware of bogosort and its crazy variants, but let's not be ridiculous here. You could make any "sorting" algorithm arbitrarily bad if you'd like by doing such silly but useless things.
I propose Boltzmann sort: wait around until the heat death of the universe, and a Boltzmann brain will emerge from the cosmos, and sort your values while contemplating infinity.
Ten years ago the hash-map implementation in Internet Explorer was also O(n2). I had to inject javascript into some vendor code to avoid this after our production environment died. I ended up replacing the underlying hash-map into multiple smaller maps based on a hash of the items. So I'd have 50 maps of 1000 items instead of one map of 50000 items.
I'm interested to know, what practical application did you load 50.000 items into the frontend for 10 years ago?
It was a data visualization tool which let users make dashboards based on your data-warehouse. You could add filters to let users "slice-and-dice" the data in the dashboard.
Needless to say one of the measures had a large number of parameters. The dashboard in question allowed users to see the change in measurements of [X] over time where [X] was one of 50k poisons that the Environment Agency were measuring.
It a pretty reasonable question and - in browsers with O(n) hash lookup in their hashmaps - performed excellently.
Ten years ago the hash-map implementation in Internet Explorer was also O(n2). I had to inject javascript into some vendor code to avoid this after our production environment died. I ended up replacing the underlying hash-map into multiple smaller maps based on a hash of the items. So I'd have 50 maps of 1000 items instead of one map of 50000 items.
I'm interested to know, what practical application did you load 50.000 items into the frontend for 10 years ago?
We also regularly had grid containing millions of items (or snapshots thereof).
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…
I'm curious if the rise of quantum computers will make the differences between exponential and combinatorial meaningful in a practical sense.
Earlier quoted context omitted.
> 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.
I took strictly stronger to mean a^n + b^n is O(a^n) so the a^n term holds more weight. The comment didn't mention anything about guarantees.
I actually thought the most likely intended meaning was that an algorithm in O(a^n) must take asymptotically longer than one in O(b^n) as n goes to infinity (if a > b), which isn't true. (For example, when a > b, then every algorithm in O(b^n) is also in O(a^n), but obviously no algorithm can asymptotically require more time than itself.)
Earlier quoted context omitted.
It's sort of unclear why 3 billion bytes needs to be processed in an O(N^2) algorithm in the first place, but seems especially egregious in that it also blocks other processes from running. One other aspect of the issue is that it's unclear why that database is now so large. It seemed like different machines had different sized databases — perhaps one angle of the solution is trimming and vacuuming.
Well, it doesn't block all other processes, but it sure did block a lot of them. I agree that finding out why the repository is huge seems worthwhile. I think it's been growing lately which means it might eventually get to an unsustainable size. As far as I can tell Microsoft doesn't ship any tools to make repo-size analysis easy. An open-source tool was suggested in one of the comments on my blog.
Exactly. It's 1.9 GB on your machine, whereas on a plain home-use computer it's less than 50 MB, i.e 40 times smaller. Something produces all that data there, what is that, and what's that that's being stored?
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,…
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…
Depends on whether your database is reasonable or not.
Sometimes "foo IN (1,2,3,4,5)" will do five index lookups, while a JOIN will check every single "foo" in the table.
For bonus points it will also convert "IN ([independent subquery])" into the same JOIN. So just by reminding the database that a thing inside parentheses gets evaluated first, you can make it go a thousand times faster. Not a single other change to the query.