分段合成平均流

Question

我有一个n浮点流的列表，每个流都有不同的大小。

可以使用以下规则将流组合在一起：

您可以将流放在任何时间点(它在开始之前为零)。您可以多次使用同一个流(它可以自己重叠，甚至几次处于同一位置)，并且允许您根本不使用某个流。

例如：

输入流：

1 2 3 4
2 4 5 6 7
1 5 6

可以像这样组成：

  1 2 3 4
1 5 6
        1 5 6

在放置之后，输出流由这样的规则组成，即每个输出浮点数等于每个项的平方和的平方根。

例如：

如果某个位置的流是：

1
2
3

输出为：

sqrt(1*1 + 2*2 + 3*3) = sqrt(14) = 3.74...

因此，对于示例组合：

  1 2 3 4
1 5 6
        1 5 6

输出为：

1 5.09 6.32 3 4.12 5 6

我拥有的是输出流和输入流。我需要计算导致该输出的成分。精确的构图不一定要存在--我需要一个尽可能接近输出的构图(最小累积差)。

例如：

输入：

要模拟的流：

1 5.09 6.32 3 4.12 5 6

和一个列表：

1 2 3 4
2 4 5 6 7
1 5 6

预期输出：

Stream 0 starting at 1,
Stream 2 starting at 0,
Stream 2 starting at 4.

这似乎是一个NP问题，有没有什么快速的方法来解决这个问题？它可能有些蛮力(但不完全是，这不是理论问题)，只要足够接近，它就不能给出最好的答案。

该算法通常与流一起使用，以模拟非常长的长度(可以是几兆字节)，而它将有大约20个流组成，而每个流将大约千字节长。

Answer 1

我认为你可以加快贪婪的搜索速度，而不是显而易见的。首先，对所有涉及到的流中的每个元素进行平方。然后，您将寻找与平方目标流非常相似的平方流的总和。假设“看起来像”是两个平方流之间的欧几里得距离，被认为是向量。

然后我们有(a-b)^2 = a^2 + b^2 - 2a.b。因此，如果我们可以快速找到两个向量的点积，并且我们知道它们的绝对大小，我们就可以快速找到距离。但是使用快速傅立叶变换和http://en.wikipedia.org/wiki/Convolution_theorem，我们可以计算出a.b_i，其中a是目标流，b_i是在i的某个偏移处的流b，通过使用快速傅立叶变换对b的反向版本进行卷积-对于对a进行快速傅立叶变换的成本，对反向b进行快速傅立叶变换，并对结果进行快速傅立叶变换，我们得到每个偏移i的a.b_i。

如果我们进行贪婪搜索，第一步是找到使( a - b_i )^2最小的流，并从a中减去它。然后我们寻找使(a-b_i- c_j )^2尽可能小的流c_j。但这是一个^2+ b_i^2 + c_j^2 - 2a.b_i - 2a.c_j + 2b_i.c_j，我们已经计算了上面步骤中除b_i.c_j之外的所有内容。如果b和c是较短的流，则计算b_i.c_j将很便宜，我们可以像以前一样使用快速傅立叶变换。

因此，我们有一种不太可怕的方法来进行贪婪搜索-在每个阶段，从调整后的目标流中减去到目前为止使残差最小的流(被认为是欧几里德空间中的向量)，然后从那里继续。在某个阶段，我们会发现，我们可用的流都不会使残差变得更小。我们可以到此为止，因为我们上面的计算表明，同时使用两个流也没有帮助-这是因为b_i.c_j >= 0，因为b_i的每个元素都是>= 0，因为它是一个正方形。

如果您执行贪婪搜索，但不满意，但有更多的cpu要消耗，请尝试有限差异搜索。

Answer 2

如果我可以使用C#，LINQ和Rx框架的System.Interactive扩展，那么这是可行的：

首先，为允许的数组定义一个交错数组。

int[][] streams =
    new []
    {
        new [] { 1, 2, 3, 4, },
        new [] { 2, 4, 5, 6, 7, },
        new [] { 1, 5, 6, },
    };

需要一个整数上的无限迭代器来表示每一步。

IEnumerable<int> steps =
    EnumerableEx.Generate(0, x => true, x => x + 1, x => x);

需要一个随机数生成器随机选择哪些流添加到每个步骤。

var rnd = new Random();

在我的LINQ查询中，我使用了这些运算符：

any any扫描^-对序列运行累加器函数，为每个输入值生成输出值，其中-根据predicate

• Empty过滤序列-返回空的sequence

• Concat -连接两个sequences

• Skip -跳过序列中指定数量的元素

• true -如果序列包含任何选择器，则返回true-使用选择器函数对序列进行投影

• Sum-对序列中的值求和

^-来自Rx System.Interactive库

现在来看执行所有繁重工作的LINQ查询。

IEnumerable<double> results =
    steps
        // Randomly select which streams to add to this step
        .Scan(Enumerable.Empty<IEnumerable<int>>(), (xs, _) =>
            streams.Where(st => rnd.NextDouble() > 0.8).ToArray())
        // Create a list of "Heads" & "Tails" for each step
        // Heads are the first elements of the current streams in the step
        // Tails are the remaining elements to push forward to the next step
        .Scan(new
        {
            Heads = Enumerable.Empty<int>(),
            Tails = Enumerable.Empty<IEnumerable<int>>()
        }, (acc, ss) => new
        {
            Heads = acc.Tails.Concat(ss)
                .Select(s => s.First()),
            Tails = acc.Tails.Concat(ss)
                .Select(s => s.Skip(1)).Where(s => s.Any()),
        })
        // Keep the Heads only
        .Select(x => x.Heads)
        // Filter out any steps that didn't produce any values
        .Where(x => x.Any())
        // Calculate the square root of the sum of the squares
        .Select(x => System.Math.Sqrt((double)x.Select(y => y * y).Sum()));

每一步都很好的懒惰评估--尽管很可怕……