添加范围以计算重叠 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

可能可以做一些更高效的事情，但这个解决方案的优点是严重依赖 numpy 的速度。对于 10k 范围，这在我的笔记本电脑上运行大约 600 毫秒。

from collections import defaultdict

import numpy as np


# 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
starts, stops = np.array([[range.start, range.stop] for range in ranges]).T

# Set of all numbers we should test
n = np.arange(starts.min(), stops.max() + 1)[:, None]

# Test those numbers
counts = ((n >= starts[None, :]) & (n < stops[None, :])).sum(axis=1)

# Wrap the result into a dict
d = defaultdict(int, dict(zip(n.flatten(), counts)))

Answer 2

改进了我之前的回答，该算法解决了 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())

添加范围以计算重叠 python

Adding ranges to count overlap python

python

performance

range