如何在 Pandas 数据框列中找到与 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 这样的输入，如何df1['A']在 log(n) 中找到 10 个（或任何其他整数，如 k）最接近x 的值，其中 n 是 df1 中的行数。请注意，这应该在不替换的情况下完成，每次我在中找到这 10 个最接近的值时df1['A']，我应该删除这些值或以某种方式标记它们而不是将它们用于下一个 x。这可以在logn中解决吗？谢谢

金巴利

您可以使用轻松找到 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 个最接近的值
你可以做一个类似二分搜索的 get 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 = df1['A'].searchsorted(val)
    return find_closest(df1.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

复杂性应该在这里：