I'm trying to make an addon that would calculate the optimal reforging given your gear, and I'm stuck because of lua's extremely inefficient data structures. I have a working c++ code that gives the result almost instantly, but I'm running out of memory in lua version if I have 2 capped stats (it gives the result instantly with 1 cap). Basically I need a large array for dynamic programming, containing around a million integers or so. Has anyone thought of a better algorithm that does this?
If you were doing this even partially "offline", I'd suggest doing a custom data structure in C/C++/etc, registering it as a Lua userdata type, and then continuing to do the logic part of the algorithm in Lua as you are now. As you've discovered, the WoW sandbox of Lua makes certain kinds of programs rather ugly.
Not really, it uses a greedy algorithm, which is far from optimal. From project description, it reforges items one by one in whatever order until a cap is reached, then it stops. Usually it puts you far above the hit/exp caps, wasting precious stats.
Precise algorithms such as wowreforge.com can get you almost exactly to your caps, at the same time trying to maximize your other important stats. Wowreforge.com seems to do an exhaustive search and takes a bit of time to calculate everything. After some thought I found a pretty simple dynamic programming algorithm which finishes instantly when coded in c++, but in lua it runs out of memory.
Anyhow, I made a hacky fix that loses some precision by dividing all capped stats by N and rounding off all intermediate values. With N=5 it gives decent results and finishes in a few seconds. I made it add a random number between 0 and 1 before rounding, which makes it always give slightly different results, so you can click the calculate button multiple times if you're not satisfied with your initial result.
However, I was hoping someone could think of a better way to do it.
Edit: didn't see Farmbuyer's post until much later.
If I was doing it offline, surely I won't be using lua? There's an addon (forgot the name) that can display reforging methods generated by offline tools, if that's what you meant.
The current algorithm is straightforward: I keep a 2d table where cell (i, j) stores the best (in terms of weighted sum of uncapped stats) possible way to reforge first N items to make first capped stat equal i and second equal j. N starts at 0, then I add items one by one and generate N+1st table from Nth by going through all nonzero cells in Nth table and all ways to reforge the current item (we discard the obviously non optimal ones, there are at most 5).
Wait, why do you keep so many useless numbers when really you only need to keep two reforge states in memory: current and best calculated so far? Yes, it will be a greedy algorithm, but it should take only a few seconds on any modern PC to go through all permutations and you can pre-sort input based on score of stat gains to throw away some incoming data without calculation at all.