{"id":178,"date":"2009-08-02T19:29:27","date_gmt":"2009-08-02T18:29:27","guid":{"rendered":"http:\/\/mehm.net\/blog\/?p=178"},"modified":"2009-10-31T14:46:21","modified_gmt":"2009-10-31T13:46:21","slug":"persona-3-fes-calculator-algorithmic-optimization-part-12","status":"publish","type":"post","link":"https:\/\/mehm.net\/blog\/?p=178","title":{"rendered":"Persona 3 FES Calculator – Algorithmic Optimization (1)"},"content":{"rendered":"

As noted earlier, in this post I want to have a look at how the general algorithm I used in the calculator can be optimized without applying any language-specific optimizations.<\/p>\n

Normal Spread Fusions
\n<\/strong><\/p>\n

In the case of regular fusions, when we simply try to fuse each Persona on the list with each other Persona on the list, we will have to try out n^{2} fusions. However, there are many unnecessary fusions in there. First, we don’t want to try to fuse the same Persona with itself, since this is invalid. This means we are not allowing all sequences of two elements (p_{1}, p_{2}), but we restrict us to all sequences where p_{1} \\neq p_{2}. This results in a number of slightly fewer fusion tries, namely n^{2}-n. However, we are still trying all orders, meaning that if we tested (p_{1}, p_{2}), we will also test (p_{2}, p_{1}), even though this results in the same result. Therefore, what we want to test are only the subsets of size 2, for which there are of course n \\choose 2\u00c2\u00a0 possibilites. We can reach this with the following bit of code:<\/p>\n

\r\nfor (int i = 0; i < persona.Count; i++) {\r\n    for (int j = i + 1; j < persona.Count; j++) {\r\n        Persona p1 = persona[i];\r\n        Persona p2 = persona[j];\r\n        Persona result = NormalSpreadFusion(p1, p2);\r\n    }\r\n}\r\n<\/pre>\n
Unfortunately, we have still quadratic complexity in the number of fusion tests, but we have managed to reduce the absolute number of comparisons quite a bit. For example, if we have about 150 Persona (which is close to the worst case of all but one Persona being in the list), the brute force approach would test 22500 fusions. With the reduced number of fusions, we are down to 11175 fusions.<\/p>\n
Triangle Spread Fusions<\/strong><\/p>\n
Triangle Spread fusions work a bit different than regular spread fusions. If we want to get the result of a triangle fusion, we have to sort the Persona by their level (and their Arcana’s number in case there is a draw). Then, a regular fusion is carried out on the first (lower) two Persona, followed by another two-Persona fusion (albeit with special rules) to get the final Persona. Again, a brute-force approach would put all possible sequences with three Persona to the test and internally sort them. This results in a cubic number of fusion tests, n^{3}. The 3 Persona must be distinct, therefore we can exclude tuples such as (p_{1}, p_{1}, p_{2}). This results in n (n-1) (n-2) possibilities. Again listing only unique subsets of size 3, we get n \\choose 3 possibilites, which we could achieve with an algorithm as described in the last section.<\/p>\n
However, we could do even better, not in terms of the number of fusion tests, but we can eleminate the internal sorting, and try to enumerate the Persona in lexicographical order. This means that for (p_{1}, p_{2}, p_{3}), p_{1} \\leq p_{2} and p_{2} \\leq p_{3} hold (using the ordering by level and arcana as mentioned above). As declared, we don’t decrease the number of fusion tests, but we save ourselves the trouble of having to order the set of three Persona each time we encounter a combination, since we are sure that the set is already sorted. If we assume again 150 Persona, a brute-force implementation would check 3375000 triples for fusion results. With the optimization, we test 551300 fusions, without the need to sort the results again internally, at the cost of sorting the array before each round.<\/p>\n
Iterations<\/strong><\/p>\n
One more possible optimization concerns the iterative nature of the approach of the calculator. Say we start with the set P_{1} of size k_{1}. We test all combinations of the Persona in the set, getting the set P_{2} with size k_{2} > k_{1}. If we continue in this fashion, we will be repeating a lot of the checks we already had in the smaller sets. Say the difference of P_{1} and P_{2} is P_{\\Delta}. We need to test all combinations of Persona in P_{\\Delta} as well as all combinations of one member of P_{\\Delta} and one of P_{1} to get to set P_{3}. This means we have to do \\frac{k_{\\Delta} (k_{\\Delta}-1)}{2} + k_{\\Delta} k_{1} tests. Let’s say that k_{1} is 70, k_{2} is 90, therefore k_{\\Delta} = 20. If using the naive approach to compute P_{3}, we would require (for the normal spread fusions only) 4005 checks. If we use this alternate approach, we need 1590 checks.<\/p>\n","protected":false},"excerpt":{"rendered":"
As noted earlier, in this post I want to have a look at how the general algorithm I used in the calculator can be optimized without applying any language-specific optimizations. Normal Spread Fusions In the case of regular fusions, when we simply try to fuse each Persona on the list with each other Persona on […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,3],"tags":[14],"_links":{"self":[{"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/178"}],"collection":[{"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=178"}],"version-history":[{"count":44,"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/178\/revisions"}],"predecessor-version":[{"id":623,"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/178\/revisions\/623"}],"wp:attachment":[{"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mehm.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}