计算百分位数

Question

4

我正在编写一个程序，将生成大量数据。我想找到这些数据的各种百分位数。

显然的方法是将数据存储在某种排序容器中。有没有Haskell库提供自动排序并提供快速随机访问任意索引的容器？

另一种选择是使用无序容器，在最后进行排序。我不知道那样会不会更快。无论哪种方式，我们仍然需要一个能够快速随机访问的容器。（也许是数组...）

有什么建议吗？

（另一种选择是构建直方图，而不是将整个数据集保留在内存中。但由于目标是非常精确地计算百分位数，我不愿意走这条路。我也不知道我的数据范围，直到我生成它...）

- MathematicalOrchid

2

流算法（如https://dev59.com/C3M_5IYBdhLWcg3wvV5w中所述）是否满足您的需求？ - Jeff Foster

@JeffFoster 这似乎与我正在尝试做的事情相关。我不确定这种方法是否可行，但值得调查一下。 - MathematicalOrchid

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Roman Cheplyaka · Accepted Answer

有没有Haskell库提供自动排序并快速随机访问任意索引的容器？

是的，就是您熟悉的Data.Map。请参见“Indexed”类别下的elemAt和其他函数。

Data.Set不提供这些功能，但您可以使用Data.Map YourType()来模拟它。