As announced, this week the last posts on this project will be published before it will be released and I can start something new.

A quick recap from the last post: with some optimizations, we can reduce the number of checks for valid fusions from respectively to and . In this post I’d like to demonstrate that we can, as so often, reduce this at the cost of increasing the memory footprint of the program.

Caching Persona levels

The first thing to notice is that we can predict the level a Persona we fuse will get irrespective of the current Persona in the inventory, since it is only influenced by the social link associated with the Persona’s arcana. Therefore, we can cache the levels of all possible Persona, which will come in handy for triangle fusions.

Caching fusions

A brute-force implementation of a caching scheme for fusion results would use a two-dimensional array (three-dimensional for triangle fusions) to save the results of each possible fusion. However, due to the rules of the fusions, a large part of the combinations of Persona are actually invalid. For normal spread fusions, the number of possible combinations is , with only 9998 of them resulting in a valid Persona. This effect is even more pronounced in the case of triangle fusions, where the possible combinations amount to . The number of valid fusions when starting from the Persona the user currently owns is dependent upon the levels of the Persona, if we use the base level of each Persona, there are only 13344 combinations resulting in a new Persona.

Goal-directed lookup

During the filling of the cache, we can save the fusions in such a fashion that we can get a list of all fusions which result in a given Persona. Therefore, now that we don’t have to check all combinations as previously, we can omit those fusions which would result in a Persona we already have in the set of created Persona. Additionally, we could cache the lists of Persona which appear as ingredients for a specific Persona, so we could check this list against the available Persona to see if it’s even possible to create the Persona from the available ones. However, I would guess that in this case it’s simpler to just check all of them and get almost the same speed.

Costs

The caching scheme of course comes at a memory cost. For each normal spread fusion, we need to save the two ingredient Persona as well as the resulting Persona. Since there are 169 Persona in the game, a reference to a Persona will fit into a byte. Therefore, we need 3 byte to cache one fusion result. As mentioned above, there are 10580 valid fusions possible on the set of all Persona, therefore we have 3 * 10580 bytes which is about 31 KB. For the triangle spread fusions, we can’t give an exact number without using the actual levels of the user’s Persona. My assumption is that the number resulting from all Persona at their base levels, 13986, is close to the worst case, which means that we will need (with the additional byte for the third Persona) 4 * 13986 bytes = 55 KB. (The Persona Calculator uses more memory due to not implementing a sparse array and saving information about Persona using object references (32/64 bit) and not the numbers).

Caching Triangle Fusion Results

One important thing about caching triangle fusion results is the following: In triangle fusions, the highest actual (not base) level of the three involved Persona is required to find out in which order to fuse them. Therefore, a cache for triangle fusions needs to use the levels of the Persona in the user’s current compendium. In order to be able to forego the sorting each time an arbitrary set of 3 Persona is tested, we can save the same result for each permutation of the fusion in the cache. For the Persona which are not yet in the player’s compendium, we can predict their levels based on the social link ranks. This way, the Persona can be entered in an arbitrary order, at the cost of using more memory for the redundant information for permutations.