Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Shurikane]

Well, poor ol' me decided to use the stocks screen to find out the composition of my mountain audit.

I have exactly 548,114 units of stone.

I'm 2.5 hours in and the game is still calculating.

Oh, and it's taking 1.25 GBs of RAM.

Not even Java is that slow.  Just how long is it supposed to take just to find out the number of entities that correspond to the stone category?!


UPDATE! The calculation has finished.  It went on for roughly 4 hours.

[Draco18s]

Yeah.  We're not sure what exactly it's doing, but it does a lot of it.  20,000 is "too much" for most people.

[Gertack]

I suspect it asks, "how many granite are there?", followed by "how many talc are there?", and so on and so on, traversing the entire list of stones (or worse, all items) for every type of stone there is: O(n^2)

So with 548,114 stone that works out to roughly, assuming no "c", 300,428,956,996 calculations, which means Shuri's computer handled about 20,863,122 stone checks per second.

Easiest way to count: sort the list first.  Can also use a hash table.

But yeah, it's waaaaaaay slow.

(On a related note, my 0 FPS fort would love the same sort of attention to game scaling outside the stocks screen.)

[Nadaka]

sorry, sort then iterate is a horrible way to count stones.

You are looking at an omega(NlogN) and omega(N) operation.

Using K buckets, one for each type of item (you don't even need a real bucket, just an integer counter), you can count all types of items in omega(NK) time.

If you do use real buckets as the items container with insertion at item creation, you can reduce that to an average omega(N/K) or even omega(1) if the bucket manages its count dynamically.

[profit]

I created a mod to handle this problem... By melting it all down....

[Derakon]

Part of the issue is that the game has to check each stone to see if it's used for a building, forbidden, designated to be dumped, etc.

Profit: Shurikane said he was performing an audit. He wants the stone around; he just wants to know exactly how much of it he has. Making it go away doesn't solve anything.

[numerobis]

Part of the issue is that the game has to check each stone to see if it's used for a building, forbidden, designated to be dumped, etc.

Half a million is pretty tiny for anything near-linear-time, so something wonky is up.  Even O(nm) is fast when m isn't very big (hundreds of types, say).  So that's not what's going on.

[Shaostoul]

Maybe it's just not handled as well as it could? I've noticed that any amount of "stone" (large = longer times) causes a slight pause to a long wait.

Stone could be substituted by say, crafts.