0

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

4

2 回答 2

2

暂时忽略区块链部分。

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

现在在 NEAR 上实现这个。

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

于 2020-09-17T16:46:18.980 回答
0

一个完整的按值重新排序可能是一个 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

因此，这使得一个通过原始集合。假设（挥手）大约一半的时间我们达到了“元素值>最小值”条件，因此必须找到新的最小元素。

假设已排序集合，每个“找到最小的”都是 O(log N )。我们这样做了K /2 次，所以总共有K /2 log N次操作，加上遍历原始集合的K。

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

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

于 2020-09-17T22:29:30.860 回答