, computers.
Concept: A fast logarithmic complexity approach would be to use the average of all values as a pivot, and remove all items below it from the list.
To avoid requiring too much space, I only use one instance of this algorithm and feed it 15 times per second; once a second I save the output and provide the new current values.
Performance:
* Worst Case: We remove the smallest element 14 times, and repeat. (When larger numbers are more likely)
* Average Case: We remove half the items (When numbers are evenly distributed in a range)
* Best Case: We remove everything except the maximum in the first step. (When larger numbers are the exception)
Advantages:
* Small
* Item Quantity does not matter
* You can tweak precision by providing more calculation time -- increase the two "60" values to any number multiple of 4.
* Performs well with large quantities of few unknown items.
Disadvantages:
* Item Varietiy does matter:
* Slow: Requires up to 4n ticks with n different items, hardcoded binary selection for known items can run in constant time of 2 ticks (while requiring n+n^2 comparators).
* Currently does not support negative numbers -- you might be able to fix this by using !=0 instead of >0 in one buffers, and maybe by fixing the rounding upon division. For known negative numbers, simply negate the input inbefore.
* Size: For best-efford-situations (e.g. unloading the
- JETAFXY.jpg (719.97 KiB) Viewed 5357 times
* On the top left is a memory cell, with two inputs instead of the usual one -- this improves performance over an input selector and a standard cell. See viewtopic.php?f=193&t=31341
* The "Above average filter" calculates the average M := ceil(Sum(Items)/Count(Items) using an integer arithmetic hack -- using ceil() is important here, otherwise the filter would not be able to eliminate the not-maximum out of {9,10}, since both are equal to or above the floored average of 9. This is the part that probably does prevent use of negative numbers -- negative numbers are untested, check for yourself whether factorio does integer calculations or floating-point-floor()s the result instead. See https://stackoverflow.com/questions/274 ... ion-in-c-c
* The output buffer prevents not-maxima from reaching the output.
* The clock buffer does nothing, except ensuring matching timing paths.
Alternative approaches:
* Rightshift i times until zero, Leftshift 1 by i again, XOR to original, filter, repeat -- also slow. Since bitscan operation is missing, we would need to bitscan ourselves, which would probably make this even slower at O(ld(quantity_items)^2). Advantage: This becomes slow with large quanties of items; but would perform well with large varieties of items.
* Using multiple of the shown average comparators: Not much faster, the comparator itself takes a lot of time and repetitions.
