Algorithmic improvements

[Freaky]

So, with the help of a friend with experience in this sort of thing, I've made some significant improvements to my Rust version.

In short: I'm now filtering the booster list using a small k-d tree to eliminate pairwise combinations which can always be beaten by other pairs. This cuts the search space by about 90%, and stacks well with simple naive filtering when damage types are 0.

In short, I can now calculate optimal 8-booster configurations in 30-300 milliseconds, on a single, relatively slow CPU core, which makes it great for my web version.

I've thrown over 100,000 random scenarios at it and found no difference with the exhaustive version, so this approach seems quite sound.

[vanderaj]

Fantastic work. Let me see if I can port your Rust code to Go tonight or whatnot. I was pretty happy when I got to less than a second, but this is amazeballs.

[Thurion]

No idea how you implemented your Rust program but I found a couple of ways to increase the performance of the application which at least worked for the Python program:

• The loadout stats including resistances for the boosters are calculated for each shield generator. This has to be done only once and then apply the shield booster bonuses to the shield generator. My guess is that this is how you built your k-d tree?
• When testing each shield generator against the booster variations, the LoadOut object only needs to be generated when a better one is found for each shield generator and not for all of them.

I noticed, when I took a quick look over the Rust code, that the calculation for the actual DPS are more efficient because they only multiply 2 numbers. The 1 - resistance part is done when reading the CSV. That way it has to be done only once instead of several million times.

The funny thing is that the Python program now runs slower when using multiple cores because Python launches processes when dealing with multiple cores. But at least the single core computation runs now as fast as the previous 8 core computation: about 6 seconds for 8 boosters.
I think that's pretty good considering it uses bytecode at execution.

[Freaky]

Good point on the booster stats being separable from shield, that cuts out a lot of work. Now down to 140ms for an 8 booster search.

The k-d tree is built by generating a list of every pairwise combination of boosters and plotting their combined stats in 4-space into the tree. That's then used to quickly eliminate pairs which are strictly worse than other pairs in all dimensions.

It's then a matter of teaching the combinations function to only return those matching the pairs filter - using an array of bitmaps in this case.

[Thurion]

I might also copy that k-d tree algorithm. Haven't decided yet.
But at least I managed to get the program down to about 30 seconds when using the longer list and 8 cores. Not too bad considering it has to run 100 million test cases.

@vanderaj Remember what I wrote on Youtube about generating the booster variation list? I tried to get it into a non-recursive loop and after I got somewhat stuck, I found out that Python has a way to do it in 1 line of code...

booster_combinations = list(itertools.combinations_with_replacement(range(1, len(self._shield_booster_variants) + 1), test_data.number_of_boosters))

[vanderaj]

As I was having incorrect output whilst fixing the DPS issue, I chose not to implement this, but the speed of the Go port is more than satisfactory without it. I might have a go at some other time, but I need to catch up with the Lost Souls expedition in my second account, and re-fit my Chieftain using these results on my main account. i.e. gone fishing