python - 添加范围来计算重叠Python

Question

我有一个范围列表。我现在想计算一个字典键:值，其中键是数字，值是数字存在的范围的数量。

计算此值的一个糟糕方法是:

from collections import defaultdict
my_dict = defaultdict(int)
ranges = [range(-4200,4200), range(-420,420), range(-42,42), range(8,9), range(9,9), range(9,10)]

for singleRange in ranges:
    for number in singleRange:
        my_dict[number] += 1
sort_dict = sorted(my_dict.items(), key=lambda x: x[1], reverse=True)
print(sort_dict)

您如何更有效地做到这一点？

Answer 1

改进了我之前的答案，该算法解决了 O(n + m) 中的问题，其中 n 是总范围的长度，m 是子范围的数量。

基本思想是仅迭代 n 个数字一次，并保留当前数字所属范围数的计数器。在每一步中，我们都会检查是否已经通过了范围起点，在这种情况下，计数器会递增。相反，如果我们已经超过了范围止损，计数器就会递减。

下面的实际实现使用 numpy 和 pandas 来完成所有繁重的工作，因此算法的迭代性质可能看起来不清楚，但它基本上只是一个矢量化版本我所描述的。

与我之前回答的 600 毫秒相比，我们在笔记本电脑上将 10k 范围的时间减少到 20 毫秒。此外，这里的内存使用量也是 O(n + m)，而那里的内存使用量是 O(nm)，所以 n 和 m 成为可能。您可能应该使用此解决方案而不是第一个版本。

from collections import defaultdict

import numpy as np
import pandas as pd


# Generate data
def generate_ranges(n):
    boundaries = np.random.randint(-10_000, 10_000, size=(n, 2))
    boundaries.sort(axis=1)
    return [range(x, y) for x, y in boundaries]


ranges = generate_ranges(10_000)


# Extract boundaries
boundaries = np.array([[range.start, range.stop] for range in ranges])

# Add a +1 offset for range starts and -1 for range stops
offsets = np.array([1, -1])[None, :].repeat(boundaries.shape[0], axis=0)
boundaries = np.stack([boundaries, offsets], axis=-1)
boundaries = boundaries.reshape(-1, 2)

# Compute range counts at each crossing of a range boundary
df = pd.DataFrame(boundaries, columns=["n", "offset"])
df = df.sort_values("n")
df["count"] = df["offset"].cumsum()
df = df.groupby("n")["count"].max()

# Expand to all integers by joining and filling NaN
index = pd.RangeIndex(df.index[0], df.index[-1] + 1)
df = pd.DataFrame(index=index).join(df).fillna(method="ffill")

# Finally wrap the result in a defaultdict
d = defaultdict(int, df["count"].astype(int).to_dict())