按值对 TreeMap 进行排序的最佳方法

Question

我的程序需要对 TreeMap 值进行排序。但值可以在 100,000 以内。我打算为此使用合并排序。计算需要多少gas/dollar？找到 N 个最高数字的最佳和有效方法是什么？ TreeMap 按键而不是值排序。 https://docs.rs/near-sdk/2.0.0/near_sdk/collections/struct.TreeMap.html#method.iter_rev

Answer 1

暂时忽略区块链部分。

如果除了键的顺序之外还需要值的顺序，您可以使用另一种数据结构，例如 TreeSet<(Value, Key)>，它使用 Value 和 Key 的元组作为排序键。更新 TreeMap 时，您也会更新 TreeSet。要以相反的顺序迭代值，您可以使用 TreeSet 的反向迭代器。拥有一对而不只是一个 Value 可以让您消除相同值的歧义，而且每个值都有一个关联的 Key。

现在在 NEAR 上实现它。

由于我们目前没有 TreeSet，您可以使用另一个 TreeMap<(Value, Key), ()>

Answer 2

一个完整的 re-sort 按值很可能是一个 O(K log K) 操作，其中 K = 原始 TreeMap 中的条目数，我认为它被表述为大约 100,000。

所以K log K大约是170万次操作（log 100,000略小于17），如果我的松散算法是正确。

如果我们要查找的条目数 N 与 K 相比较小，那么我们可能会做得更好.

伪代码：

 top N := first N elements from original collection
 min value := smallest value of the top N
 for each remaining element in original collection:
     if element value > min value:
          replace corresponding element in top N
          min value := smallest value now in top N

因此，这使我们可以通过原始集合。假设 (hand-wave) 大约有一半时间我们会遇到 'element value > min value' 条件，因此必须找到新的最小元素。

每个 'locate the smallest' 是 O(log N) 假设排序集合。我们这样做 K/2 次，所以 K/2 log N 操作总数，加上K 用于遍历原始集合。

让我们把 N = 10。所以这是 50,000 log 10 + 100,000，或大约 300,000，比 170 万有所改进。

但这的可行性在很大程度上取决于 N 是什么。

按值对 TreeMap 进行排序的最佳方法

Best way to sort the TreeMap by values

nearprotocol