0

I understand that for loops on dynamic arrays are a big no no in Solidity, so I am trying to find an alternative to this problem.

Goal:

From a dynamic array of numbers, I am trying to extract the index of the element that is "closest" to another number (number). In JavaScript terms, this would look like:

let number = 21;
let closest;
let array = [5, 10, 15, 20, 25]; // using fixed size as an example, but array could be 1000+ in length
for (let i = 0, i < array.length, i++) {
  let difference = Math.abs(number - array[i]); // remove integer sign for comparison
  if ( !closest || difference < closest )
    closest = i;
  }
}

Looking through Solidity docs and other questions here, it seems that this may be an extremely gas expensive task with no alternative.

Is there another way of looking at this problem with a Solidity hat on?

3
  • Are items removed from the array at some point?
    – sea212
    Feb 20, 2020 at 16:23
  • The next step would be to 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.
    – Nick
    Feb 20, 2020 at 16:25
  • Unless your array is sorted (which also is expensive and dangerous on dynamic arrays), I see no method to improve the search. If your array is sorted you can use a divide and conquer algorithm to reduce the time complexity of the search to O(n log n)
    – sea212
    Feb 20, 2020 at 16:32

1 Answer 1

2

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.