You are right about avoiding iteration. The trick is to ensure a finite maximum cost at any scale. Generally, that means organizing things so data is handy with limited iteration and recursion.
pragma solidity 0.5.16;
import "./HitchensOrderStatisticsTree.sol";
contract Nearest {
using HitchensOrderStatisticsTreeLib for HitchensOrderStatisticsTreeLib.Tree;
HitchensOrderStatisticsTreeLib.Tree tree;
/**
* It sorts key/value pairs.
* You may have duplicate keys or duplicate values,
* but you cannot have dublicate key/value pairs.
*/
function insert(uint value, bytes32 key) public {
tree.insert(key,value);
}
function nearest(uint search) public view returns (uint value) {
uint rank = tree.rank(search);
value = tree.atRank(rank);
/**
* We have a match or the nearest higher number.
* Will return the highest number if the search is out of range.
* Quick hack to switch to next lower:
*/
if(search != value && rank > 0) rank -= 1;
value = tree.atRank(rank);
/**
* We have a match or the nearest lower number.
* will return the lowest number if the search is out of range.
*/
}
}
This library maintains a balanced b-tree (red-black). https://github.com/rob-Hitchens/OrderStatisticsTree
A b-tree is an O(log n) structure and you want it to be O(1) for the EVM. Constraining the maximum cost is an app-level concern. There are multiple ways to do that, so some strategies for handling it are suggested in the README. The main concern is limiting the maximum number of nodes (depth) in the tree. The library is reasonably performance-optimized at the design and implementation levels.
There is a lot going on in those libraries and you can remove superfluous functions if you don't need them. The "Statistics" aspect demonstrates how to populate the tree with metadata to enable different kinds of analysis. Alternatively, try https://github.com/bokkypoobah/BokkyPooBahsRedBlackTreeLibrary which it is based on. It is a pure sorter without keys, counts, ranks, etc.
You'll notice the bytes32
keys. Those are there to help bind sorted values with application data. They usually a point to a record somewhere, e.g. orderId. Keys are not important for the Nearest.sol example so send any valid input but make sure all key/value pairs are unique.
From eyeballing your example, I got the impression you want the match or the nearest lower number. The library returns the nearest higher number, so I made a little fudge to nudge it lower, if needed, without altering the library itself.
An explainer about what's going on: https://hackernoon.com/binary-search-trees-and-order-statistics-for-ethereum-db47e2dd2c36
Hope it helps.
delete
the array and start again - likely to be once a week or daily. But no upper limit on the number of numbers that can fill the array.