添加范围以计算重叠

Question

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

一个不好的计算方法是：

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())