在動態數組中搜尋值

我知道動態數組上的 for 循環在 Solidity 中是一個很大的禁忌，所以我試圖找到一個替代這個問題的方法。

目標：

從數字的動態數組中，我試圖提取“最接近”另一個數字（number）的元素的索引。在 JavaScript 術語中，這看起來像：

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;
 }
}

通過這裡的 Solidity 文件和其他問題，這似乎是一項非常耗氣的任務，別無選擇。

戴上 Solidity 帽子有沒有另一種方法來看待這個問題？

避免迭代是正確的。訣竅是確保任何規模的有限最大成本。一般來說，這意味著組織事物，以便數據在有限的迭代和遞歸中很方便。

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.
        */
   }
}

該庫維護平衡的 b 樹（紅黑）。https://github.com/rob-Hitchens/OrderStatisticsTree

b-tree 是一個 O(log n) 結構，您希望它對於 EVM 是 O(1)。限制最大成本是應用程序級別的問題。有多種方法可以做到這一點，因此自述文件中建議了一些處理它的策略。主要問題是限制樹中的最大節點數（深度）。該庫在設計和實現級別進行了合理的性能優化。

這些庫中有很多內容，如果您不需要它們，您可以刪除多餘的功能。“統計”方面展示瞭如何使用元數據填充樹以啟用不同類型的分析。或者，嘗試它所基於的https://github.com/bokkypoobah/BokkyPooBahsRedBlackTreeLibrary 。它是一個純粹的分類器，沒有鍵、計數、等級等。

你會注意到bytes32鑰匙。這些可以幫助將排序值與應用程序數據綁定。它們通常指向某處的記錄，例如 orderId。對於 Nearest.sol 範例，鍵並不重要，因此請發送任何有效輸入，但要確保所有鍵/值對都是唯一的。

通過觀察您的範例，我得到了您想要匹配或最接近的較低數字的印象。庫返回最接近的較高數字，因此如果需要，我做了一點軟糖以將其推低，而不改變庫本身。

關於正在發生的事情的解釋器：https ://hackernoon.com/binary-search-trees-and-order-statistics-for-ethereum-db47e2dd2c36

希望能幫助到你。

引用自：https://ethereum.stackexchange.com/questions/79992