I implemented that algorithm (without any pre-computation in source) and I'm quite optimistic. Benchmark results (on mobile i7-3610QM) are: - 4R E12 - about 3ms - 4R E24 - about 12ms - 4R E96 - about 150ms - 4R E192 - about 500ms
My fork with the implementation is at https://gitlab.com/bwaclawik/kicad/-/tree/new-resistor-substitution-algorithm wtorek, 25 lipca 2023 o 21:55:14 UTC+2 [email protected] napisał(a): > You will probably gain by pre-computing 2COMB and storing the values in > the source. However, this would be quite large above E96 and would not be > realistic to store. You could pre-compute in source to reduce the time > after the first calculation. > > I'm skeptical of the gains to be made by this approach. Because 'n' is > never very large, your greatest time sink is going to be in the prefactor. > While the work may be of the order 'n', the multiplicative prefactor will > dominate. > > For that reason, if you are interested in improving the algorithm, I would > look at early escape metrics in the loops. We end up checking many value > combinations that we do not need and some smarter heuristics here will have > outsized impact. > > That said, if you have your heart set on the approach you laid out, I > don't see the harm in testing it. > > Seth > > [image: KiCad Services Corporation Logo] > Seth Hillbrand > *Lead Developer* > +1-530-302-5483 <(530)%20302-5483> > Long Beach, CA > www.kipro-pcb.com [email protected] > > > On Tue, Jul 25, 2023 at 11:15 AM bebidek <[email protected]> wrote: > >> I would like to improve the performance of the "E-series" tool in the PCB >> calculator. >> At the moment, the solution implemented in the code is basically a >> brute-force algorithm, reaching O(n^4) time complexity (where n is the >> number of basic resistance values). >> It can be easily improved to O(n^2 * log(n)) using a binary search >> approach, keeping current memory complexity of O(n^2). >> The draft of the new algorithm is as follows ('X' means "+ or |", 2COMB >> means "some combination of 2 resistors"): >> 1. Prepare an array of all combinations of two resistors (that is, >> all possible values of 2COMB) and sort it >> 2. For 2-solutions, use single binary search in our array to find the >> two closest values (one less and one greater) >> 3. For 3-solutions, all possible variants are of the form: "R1 X >> 2COMB". Thus, we iterate over all values of R1, for each value calculate >> "perfect" values of that combination in parenthesis and look for it >> (bin-search) in the array. >> 4. For 4-solutions, it is either "(2COMB X 2COMB)", "R1 + (R2 | >> 2COMB)" or "R1 | (R2 + 2COMB)". The first one can be solved by iterating >> over 2COMB array, the second and third one by iterating over pairs (R1, R2). >> >> Switching to this algorithm should make adding higher E-series possible >> (some people in other threads have suggested this, but performance issues >> made it impractical). >> I believe that this algorithm is not too far from the most optimal >> possible. The problem of finding "series only" combinations is basically a >> 3-SUM problem for which we believe there is no O(n^a) algorithm for a<2 >> (the "3-SUM hypothesis"). It appears that finding general solutions should >> be at least that hard. >> Additional benefit of that algorithm is that it correctly considers all >> possible combinations of up to 4 resistors, unlike the current one which >> cannot produce results of form R1 + (R2 | R3 | R4). >> >> I would like to implement that algorithm if approved. It would involve >> rewriting RES_EQUIV_CALC class almost from scratch (this would also fix >> some code quality issues in the current implementation). >> >> -- >> You received this message because you are subscribed to the Google Groups >> "KiCad Developers" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/a/kicad.org/d/msgid/devlist/f204c4cf-b90c-460c-a59d-7f593cab37f5n%40kicad.org >> >> <https://groups.google.com/a/kicad.org/d/msgid/devlist/f204c4cf-b90c-460c-a59d-7f593cab37f5n%40kicad.org?utm_medium=email&utm_source=footer> >> . >> > -- You received this message because you are subscribed to the Google Groups "KiCad Developers" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/a/kicad.org/d/msgid/devlist/030bceec-4548-4ae6-b4d4-f17830310d9cn%40kicad.org.
