Hey, i was wondering if anyone knows or has any ideas on how to make a faster item stacking function than the one i currently have here : https://blueprintue.com/blueprint/byr0-t4f/
Currently the time complexity is O(n^2), but i need it to be quicker for sorting my inventory, i already implemented merge sorting for the item types, priorities, and amounts but now i need something to stack all the items together that doesnt take so long because i have alot of slots and sorting them is essential for my game.
Just wanted to say I ended up making a faster and honestly simpler stacking function. It basically checks if a slot’s item count is less than its max stack size. If it is, it adds that item to a local map to keep track of how much extra there is, and clears the slot.
Then, after looping through all the slots, it loops through them again and tries to add whatever it can from the map recursively, clamped to each item’s max stack size.
This avoids unnecessary loops over the array by instead of looping over the array for every single array element (O(n²)), this just loops over the array twice (O(n)).
This is easy to understand with a simple example of having 100 slots, the original method would do 10,000 checks versus this new method would just do 200.
I would also argue its a bit simpler and easier to read.
Using this combined with merge sorting for a sort inventory function seems to give the quickest possible sort time and i will be using this for my game as a result.
