时间戳

首页 > 解决方案 > 如何在熊猫数据框列中找到与 O(logn) 中的输入值 x 最接近的 k 个值？

python - 如何在熊猫数据框列中找到与 O(logn) 中的输入值 x 最接近的 k 个值？

问题描述

我有一个包含两列的数据框：1）ID：代表样本 ID 的随机整数，2）A：浮点数

size_df1 = 1000
df1 = pd.DataFrame(np.random.random_sample((size_df1)), columns=list('A'))
df1['ID'] = random.sample(range(0, size_df1), size_df1)

给定一个像 x=0.21 这样的输入，如何在 log(n) 中找到 10 个（或任何其他整数，如 k）最接近df1['A']x 的值，其中 n 是 df1 中的行数。请注意，这应该在没有替换的情况下完成，每次我在 中找到这 10 个最接近的值时df1['A']，我都应该删除这些值或以某种方式标记它们，而不是将它们用于下一个 x。这可以在登录中解决吗？谢谢

标签： pythonpython-3.xpandassortingbinary-search-tree

解决方案

用 可以很容易地找到 k 个最小值.nsmallest()，最接近的值是绝对差值最小的值：

>>> (df1['A'] - 0.21).abs().nsmallest(10)
969    0.000014
889    0.000442
779    0.003299
259    0.003637
843    0.003700
84     0.003818
651    0.004264
403    0.004360
648    0.004421
543    0.005088
Name: A, dtype: float64

如果要访问匹配的行，则可以重用它的索引：

>>> df1.loc[(df1['A'] - 0.21).abs().nsmallest(10).index]
            A   ID
969  0.210014  237
889  0.210442  225
779  0.206701  127
259  0.213637  883
843  0.206300  330
84   0.206182   17
651  0.205736   64
403  0.205640  388
648  0.214421  964
543  0.204912  616

请注意，文档nsmallest说：

对于相对于 Series 对象大小的小 n，比 .sort_values().head(n) 快。

关于复杂性的一句话，因为您的值没有排序：

  • 最低限度的复杂性是O(n) 如果您想找到 1 个最接近的值
  • 你可以做一个类似于二分查找的方法来得到O(log(n))，但这需要先排序——所以实际上是O(n log(n))。

假设您的数据框按 A 排序：

>>> df1.sort_values('A', inplace=True)

然后我们可以尝试使用 sorted search 函数，它返回行号（不是索引值）：

>>> df1['A'].searchsorted(0.21)
197

这意味着我们可以使用它来找到k最接近的候选者，然后在这个2k数据帧上使用我们之前的方法：

def find_closest(df, val, k):
    return df.loc[df['A'].sub(val).abs().nsmallest(k).index]

def find_closest_sorted(df, val, k):
    closest = df['A'].searchsorted(val)
    if closest < k:
        return find_closest(df.iloc[:closest + k], val, k)

    return find_closest(df.iloc[closest - k:closest + k], val, k)

>>> find_closest_sorted(df1, 0.21, 10)
            A   ID
969  0.210014  237
889  0.210442  225
779  0.206701  127
259  0.213637  883
843  0.206300  330
84   0.206182   17
651  0.205736   64
403  0.205640  388
648  0.214421  964
543  0.204912  616

复杂性应该在这里：

  • O(n log(n))用于排序（可以在许多查找中摊销）
  • O(log(n))对于排序搜索
  • O(k)最后一步。

推荐阅读