Linq IEnumerable扩展方法 - 如何提高性能？

Question

我编写了下面的扩展方法，用于查找满足传递给它的谓词的连续项序列。序列中连续项的数量由参数“sequenceSize”确定。

例如，我可能有一个整数的IEnumerable，并且想要找到10个连续的大于100的值。这个扩展方法将确定是否存在这样的序列。

这个方法运行良好。但是，由于它必须执行的操作，如果IEnumerable中有相当数量的元素，它可能会很慢，因为它必须从第一个元素开始，查找满足谓词的连续值，然后转到第二个元素并执行相同的操作等等。

我正在寻求加快速度的建议。我尝试使用AsParallel()，但没有影响。

public static IEnumerable<IEnumerable<T>> FindSequenceConsecutive<T>(this IEnumerable<T> sequence, 
                                                                     Predicate<T> predicate, 
                                                                     int sequenceSize)
{
    IEnumerable<T> current = sequence;

    while (current.Count() > sequenceSize)
    {
        IEnumerable<T> window = current.Take(sequenceSize);

        if (window.Where(x => predicate(x)).Count() >= sequenceSize)
            yield return window;

        current = current.Skip(1);
    }
}

- Randy Minder

Answer 1

这种方法速度变慢的最可能原因是重复调用.Count()，这将立即枚举序列以确定元素数量。

你最好明确地测试标准并跟踪计数，而不是重复使用Where()和Count()。

总的来说，这种方法正在大量枚举序列。如果您调用.ToList()一次枚举序列，然后在生成的列表上执行操作，您可能会体验到很好的加速。（请注意，如果您希望在无限长度的序列上使用此方法，则无法使用该方法。） 更新: 即使window.Count() == sequenceSize，您仍在测试>= sequenceSize。换句话说，您只需要All():

if (window.All(x => predicate(x)))
    yield return window;

我不确定这会有多大帮助，但至少在语义上更清晰了。

进一步编辑：考虑使用这种方法：

public static IEnumerable<IEnumerable<T>> FindSequenceConsecutive<T>(this IEnumerable<T> sequence, Predicate<T> predicate, int sequenceSize)
{
    List<T> list = sequence.ToList();
    List<bool> matchList = list.Select(x => predicate(x)).ToList();

    int start = 0;
    int count = list.Count;

    while (start + sequenceSize <= count)
    {
        var range = matchList.GetRange(start, sequenceSize);
        if (range.All(x => x))
            yield return list.GetRange(start, sequenceSize);

        start++;
    }
}

它会对序列进行一次评估，然后对所需的列表进行分区。

- dlev

---

无论All是否会产生可衡量的影响，我不能确定，但至少它意味着您不会命中序列中的每个元素。如果您有一长串不符合过滤谓词的元素，则可能是一个巨大的优势。 - Paul Phillips

@dlev - 我不明白你的解决方案如何工作。我正在寻找连续的值。你的“matchList”实现似乎使查找连续值变得不可能。 - Randy Minder

它绝对有效；我已经测试过了 :) matchList 本质上是调用谓词在序列的每个成员上的结果的缓存。matchList[i] == predicate(list[i]) - dlev

@dlev - 确实很有效，而且速度非常快。干得好！谢谢。 - Randy Minder

Answer 2

我认为这种方法可能适合你，因为你可以遍历一次列表，并基本上维护一个通过谓词的连续项队列，需要时进行清除（所有）和出队（一个）操作。

public static IEnumerable<IEnumerable<T>> FindSequenceConsecutive<T>(this IEnumerable<T> sequence, Predicate<T> predicate, int sequenceSize)
{
    var queue = new Queue<T>();

    foreach (T item in sequence)
    {
        if (predicate(item))
        {
            queue.Enqueue(item);
            if (queue.Count == sequenceSize)
            {
                yield return queue.ToList();
                queue.Dequeue();
            }
        }
        else
        {
            queue.Clear();
        }
    }
}

因此，写作

int[] array = { 1, 2, 3, 4, 5, 2, 8, 3, 5, 6 };
foreach (var seq in array.FindSequenceConsecutive(i => i > 2, 3))
{
    Console.WriteLine(string.Join(",", seq));
}

产量

3,4,5
8,3,5
3,5,6

- Anthony Pegram

Answer 3

我相信这个解决方案会提供最佳的性能，并且在序列越来越大时会更好地扩展，因为它不会分配任何额外的缓冲区（列表或队列），也不必将结果转换为列表或对结果缓冲区进行任何计数。此外，它只需要遍历序列一次。

public static IEnumerable<IEnumerable<T>> FindSequenceConsecutive<T>(this IEnumerable<T> sequence,
    Predicate<T> predicate, int sequenceSize)
{
    IEnumerable<T> window = Enumerable.Repeat(default(T), 0);

    int count = 0;

    foreach (var item in sequence)
    {
        if (predicate(item))
        {
            window = window.Concat(Enumerable.Repeat(item, 1));
            count++;

            if (count == sequenceSize)
            {
                yield return window;
                window = window.Skip(1);
                count--;
            }
        }
        else
        {
            count = 0;
            window = Enumerable.Repeat(default(T), 0);
        }                
    }
}

- Jim

---

这是一个不错的尝试，但是它缺少序列。如果您有5个连续的项目通过谓词（[a，b，c，d，e]），并且正在寻找3个序列，则会得到[a，b，c]，但不会得到[b，c，d]和[c，d，e]。其次，我不确定可扩展性的声明，但我不能太苛刻，因为我绝不是专家。但是像Enumerable.Repeat这样的方法也会创建垃圾，类被创建和填充。Linq不是免费的。 - Anthony Pegram

@Anthony Shoot，你说得对。还需要添加一个Skip()或其他东西。唉，我会回滚的，Jim可以处理它。 :) - dlev

@Anthony - 我实际上查看了“concats”和Enumerable.Repeat的底层代码，发现它似乎正在使用链表，即仅是指向项目的指针。对我来说，这将是一种精益捕获信息的方式，因为它仅在实际迭代结果时才实现序列。不过我会继续研究这个错误，谢谢！ - Jim

@Anthony- 已经修复了这个 bug，现在它与你的解决方案本质上是相同的，但更冗长 :-( ，你的更优雅。我对两者进行了性能测试，在非常大的序列中它们实际上是相同的，但使用你的解决方案，在原始序列中有26K个元素以上时，会快1ms！所以我想这将取决于结果呈现的偏好。在你的解决方案中，“窗口”已经在返回的序列中实现，在我的解决方案中，它们还没有渲染，直到有人迭代它们。确定哪种方法更好真的超出了我的时间 :-) 两者都很好。 - Jim

@Jim - 两者都很好。然而，我实际上更喜欢在迭代之前不实现序列，因为有许多情况下我并不关心序列中的内容，我只需要知道序列是否存在。 - Randy Minder