1

我有两个列表，每个列表都包含一组有序的数字。

一个列表很小（~ 5 - 20 个元素），另一个列表很大（~ 5000）。这些列表具有不同的“比例”，并且可能在一个或另一个列表中缺少点。一般来说，大多数元素都在两个列表中。

我正在寻找一种方法来检测两个列表之间的位置和“缩放”，以便两个列表之间的距离最小。

一个例子是：

l1 = [ 100.,  200., 400.]
l2 = [ 350., 1000., 2003., 3996., 7500., 23000.]

比例为 10。 l1 在 l2 中的位置为 1。

列表 10.*l1 出现在 l2 内的位置 1；列表的距离为 7（这取决于我选择的指标，这里我只是总结了所有元素之间的差异）。

我想知道是否已经有一些方法，例如我可以使用的模式识别（最好是在 python 中）。在我看来，在将模式与未知比例因子进行比较时，这可能是一个常见问题。但是我找不到一个好的关键字来描述我的问题。

其应用是通过将测量的光谱线与已知线的位置目录进行比较来识别测量的光谱线，从而将非物理单位“探测器上的像素”转换为实际波长。

原则上，我已经可以对两个列表的比例因子提供一个不错的猜测，但我想这不是必需的，因为在大多数情况下解决方案应该是唯一的。

任何帮助表示赞赏，

朱利安

4

1 回答 1

0

您要解决的问题是两度优化。第一个是比例，第二个是索引。您的问题的广义上通常很难有效地解决。然而，有一些事情可以简化计算。首先两个集合都排序了吗？其次，您是否要从第二个列表中寻找与第一个匹配的连续集？为了进一步解释，我将使用一个示例：1、2、3 和 2、3、4、6。 2（跳过第二个列表中的 3）或 1.something（不跳过 3）的比例更好? 第三，您想使用什么权重来衡量两者之间的差异（线性和、均方根等）？

如果你能提供其中一些细节，我也许可以让你更好地了解一些可以尝试的事情。

更新

因此，根据您的评论，您可以跳过值。这实际上使这个问题很难解决 O(2^n)。因为您基本上是在查看列表一和列表二的所有组合。

即使你可以优化这个问题的某些方面，因为它们是排序的，你仍然需要检查很多组合。

于 2014-06-02T19:52:05.303 回答