Python

Question

我正在对数百 GB 的数据进行大规模分析，但它是流式传输的，我想要计算模式和百分位数的最有效解决方案。我目前的做法是将数字（有小数点的 ping 时间，例如 55.4381 或 33.97818）四舍五入到最接近的十分位，并在字典中记录这些出现的次数。例如：

a = {48.8: 5, 42.3: 24, 56.1: 3}

这是我发现的最好的方法，它足够准确，可以满足我的需要，同时还能提高内存效率。我想到的最佳方法是使用有序字典，计算字典中的键数，然后按排序顺序获取第 k 个键。因此，如果有意义的话，获得上述数据的第 50 个百分位数将是 a[(32*0.5)-1] -> a[15] -> 42.3。本质上是获取列表的第 k 个元素，如果在这种情况下该列表是 [42.3, 42.3, ..., 42.3, 48.8, 48.8, 48.8, 48.8, 48.8, 56.1, 56.1, 56.1]，但不需要为该列表分配内存。

所以，我想知道是否有人对执行此操作的最有效方法有任何想法。我目前正在使用 Python 3.5.2。感谢阅读。

Answer 1

# We want this percentile.
pct = 0.25

# Data.
a = {48.8: 5, 42.3: 24, 56.1: 3}

# Find that percentile in this data.
def pctile(a, pct):
    # Convert to list of tuples, sort
    LofT = list(a.items())
    LofT.sort()

    # Sum of counts.
    ct = sum(a.values())

    # Index corresponding to percentile. Don't subtract 1; e.g. ct = 100,
    # 25th pctile, 25% are below, we want index 25, below which there are
    # 25 values. But do round to nearest integer.
    pcti = int(ct * pct + 0.5)

    # Traverse sorted list until this index is reached.
    for v, c in LofT:
        pcti -= c
        if pcti < 0:
            return v

    # Still here? Then pct was >= 1, just return the maximum value.
    return LofT[-1][0]

时间复杂度为 O(n log n) 其中 n = len(a)，由于排序步骤。

Python - 从（扩展）字典中获取 select 第 k 个值的最有效方法

Python - Most efficient way to select kth value from (expanded) dictionary

dictionary

percentile

python-3.x