时间戳

首页 > 解决方案 > 在另一个成对的 bin 数组中获取数据数组最小值的最快方法

python - 在另一个成对的 bin 数组中获取数据数组最小值的最快方法

问题描述

我有三个一维数组：

这是我目前使用的方法idxs来检查weights在哪个 bin 中调用的数据，然后计算 binned weights 的最小/最大值：

插图

  1. 获取slices显示每个idxs元素属于哪个 bin。
  2. 排序slices和weights同时。
  3. 计算weights每个 bin（切片）中的最小值。

numpy 方法

import random
import numpy as np

# create example data
out_size = int(10)
bins = np.arange(3, out_size-3)
idxs = np.arange(0, out_size)
#random.shuffle(idxs)

# set duplicated slice manually for test
idxs[4] = idxs[3]
idxs[6] = idxs[7]

weights = idxs

# get which bin idxs belong to
slices = np.digitize(idxs, bins)

# get index and weights in bins
valid = (bins.max() >= idxs) & (idxs >= bins.min())
valid_slices = slices[valid]
valid_weights = weights[valid]

# sort slice and weights
sort_index = valid_slices.argsort()
valid_slices_sort = valid_slices[sort_index]
valid_weights_sort = valid_weights[sort_index]

# get index of each first unque slices
unique_slices, unique_index = np.unique(valid_slices_sort, return_index=True)
# calculate the minimum
res_sub = np.minimum.reduceat(valid_weights_sort, unique_index)

# save results
res = np.full((out_size), np.nan)
res[unique_slices-1] = res_sub

print(res)

结果：

array([ 3., nan,  5., nan, nan, nan, nan, nan, nan, nan])

如果我将 1e7 增加到out_size1e7 并随机播放数据，则速度（从 np.digitize 到结尾）很慢：

13.5 s ± 136 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

而且，这是每个部分的消耗时间：

np.digitize: 10.8 s ± 12.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
valid: 171 ms ± 3.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
argsort and slice: 2.02 s ± 33.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
unique: 9.9 ms ± 113 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
np.minimum.reduceat: 5.11 ms ± 52.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

np.digitize()花费最多时间：10.8 秒。并且，下一个是argsort：2.02 秒。

mean我还检查了计算所消耗的时间np.histogram：

counts, _ = np.histogram(idxs, bins=out_size, range=(0, out_size))
sums, _ = np.histogram(idxs, bins=out_size, range=(0, out_size), weights = weights, density=False)
mean = sums / np.where(counts == 0, np.nan, counts)

33.2 s ± 3.47 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

这类似于我计算最小值的方法。

scipy方法

from scipy.stats import binned_statistic
statistics, _, _ = binned_statistic(idxs, weights, statistic='min', bins=bins)

print(statistics)

结果略有不同，但对于较长（1e7）的混洗数据，速度要慢得多（x6）：

array([ 3., nan,  5.])

1min 20s ± 6.93 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

概括

我想找出一个更快的方法。如果该方法也适用于dask，那就太好了！

用户案例

这是我的真实数据（1D）的样子： 真实数据

标签： pythonpandasnumpyscipydask

解决方案

实现此目的的一种快速方法是使用dask.dataframeand pd.cut，我首先显示pandas版本：

import numpy as np
from scipy.stats import binned_statistic as bs
import pandas as pd

nrows=10**7

df = pd.DataFrame(np.random.rand(nrows, 2), columns=['x', 'val'])

bins = np.linspace(df['x'].min(), df['x'].max(), 10)

df['binned_x'] = pd.cut(df['x'], bins=bins, right=False)

result_pandas = df.groupby('binned_x')['val'].min().values
result_scipy = bs(df['x'], df['val'], 'min', bins=bins)[0]

print(np.isclose(result_pandas, result_scipy))
# [ True  True  True  True  True  True  True  True  True]

现在要从pandasto 开始dask，您需要确保 bin 在分区之间保持一致，因此请看这里。一旦每个分区都被一致地分箱，您想要应用所需的操作（最小/最大/总和/计数）：

import dask.dataframe as dd
ddf = dd.from_pandas(df, npartitions=10)

def f(df, bins):
    df = df.copy()
    df['binned_x'] = pd.cut(df['x'], bins=bins, right=False)
    result = df.groupby('binned_x', as_index=False)['val'].min()
    return result

result_dask = ddf.map_partitions(f, bins).groupby('binned_x')['val'].min().compute()

print(np.isclose(result_pandas, result_dask))
# [ True  True  True  True  True  True  True  True  True]

在我的笔记本电脑上，第一个代码大约需要7 3 秒，第二个代码大约快10倍（忘记了我在重复计算 pandas 和 scipy 执行相同的操作）。分区有一定的空间，但这取决于上下文，所以你可以尝试优化你的数据/硬件。

更新：请注意，这种方法适用于最小值/最大值，但意味着您需要计算总和和计数，然后将它们相除。可能有一种很好的方法可以在一次完成此计算时跟踪权重，但这可能不值得增加代码复杂性。

推荐阅读