python:如何找到一组中最接近另一组的子集

Question

我有以下优化问题，我可以通过“蛮力”解决，但我想知道是否有人已经实现了我可以用来更快、更优雅地完成它的求解器。

我有两个不相交的整数列表。这些实际上是独一无二的，所以我可以说这是两套。一个是短的 (s) 大约有 S=90000 个元素，另一个是长的 (l) 大约有 L=2.5M 元素。我需要的是从 l 中提取长度正好为 S 的子集 l2 以便 s 的元素之间的总体距离code> 和 l2 是长度为 S 的 l 的所有子集中最小的。 s 和 l 元素之间的成对距离就是它们差值的绝对值。

因此，如果 s 和 l 不相交并且 l 是 s 的超集，则结果 l2 与 s 完全相同。

由于数组很长，通过测试 l 的各个子集来使用蛮力方法是不切实际的。

是否有某种现有的优化库或其他包可以用来解决这个问题？

顺便说一句，可能有不同的方法来测量两个集合之间的距离，我真的不关心它是哪一个，只要它会为上面的极端超集示例给出 0 即可。

Answer 1

我知道你说这些是列表，但有什么理由不暂时将它们转换为 numpy 数组？这可以很简单(如果您不知道如何进行转换):

s = np.array(s)
l = np.array(l)

从那里，您可以使用“searchsorted”功能。我的测试运行时间不到 1.5 秒。

from __future__ import division, print_function

import numpy as np
import datetime as dt

# build numpy array
s = np.random.rand(90000)
l = np.random.rand(2.5E6)


# sort
s.sort()
l.sort()

# searchsorted finds where values in array2 should be inserted in array1 to 
# maintain the "sortedness" of a new list
# define index locations where "s" should be inserted in "l"
indices = np.searchsorted(l,s)

# build dummy list to store "s2"
# this is faster than repeatedly resizing an array
s2 = s*0


# using "indices" determine which adjacent value is the nearest match
# need to be careful here since we cannot look "below" the first index
# nor can we look "above" the last value

d1 = dt.datetime.now()
for r in np.arange(s.shape[0]):
    ix = indices[r]

    if indices[r]==0:
        s2[ix] = l[0]
    elif indices[r]==l.shape[0]:
        s2[ix] = l[r-1]
    else:
        tmp = l[ix:ix+2]
        s2[r] = tmp[ np.abs(s[r]-tmp)==np.min(np.abs(s[r]-tmp)) ]

print('Execution time: ',dt.datetime.now()-d1)

我已经进行了几次试验，看起来这可行，但你自己确认一下。如果这不起作用，则不应花费太多精力来调整它。

---

开始编辑

---

将 for 循环更改为:

for r in np.arange(s.shape[0]):
    ix = indices[r]

    if indices[r]==0:
        s2[ix] = l[0]
        l[0] = np.nan
    elif indices[r]==l.shape[0]:
        s2[ix] = l[r-1]
        l[r-1] = np.nan
    else:
        width = 0

        while width<min([10,r]) and np.isnan(l[ix-width:ix+2+width].mean()):
            width += 1

        tmp = l[ix-width:ix+2+width]
        s2[r] = tmp[ np.abs(s[r]-tmp)==np.nanmin(np.abs(s[r]-tmp)) ][0]
        l[l==s2[r]] = np.nan

这会做两件事:1. 它删除了 l 内最近的邻居，使其在未来的迭代中不被考虑2. 它在 l 内递增地增加搜索宽度以确保找到最近的邻居

同样，这可能需要调整才能拨入。