高效地将IEnumerable值合并在一起

Question

我想把一些IEnumerable的值“折叠”在一起，使相邻的相同元素折叠成一个元素。

我无法想到更好的描述问题的方式，除了举个例子：

数组[0,0,2,0,1,1,2,2,2,1,0,0,2,1,1,0,1,1,1]应该变成[0,2,0,1,2,1,0,2,1,0,1]

在我的用例中，这需要在关键循环中发生，因此必须尽可能快。我可以循环遍历数组并检查每个元素与前一个元素是否重复，如果是，则删除，但我希望有更快的方法。

我的使用仅限于相对较短的数组（<100个元素），并且仅使用int，但通用解决方案将不胜感激。

编辑：如下面指出的，问题基本上是O(n)复杂度，但我希望一些linqy的东西能够击败我的（可能笨拙的）实现。

- user3655934

Answer 1

如果您需要一个通用的解决方案，请编写一个扩展方法：

这应该可以很好地完成工作：

public static IEnumerable<T> DistinctConsecutive<T>(this IEnumerable<T> sequence)
    => sequence.DistinctConsecutive(EqualityComparer<T>.Default);

public static IEnumerable<T> DistinctConsecutive<T>(this IEnumerable<T> sequence, IEqualityComparer<T> comparer)
{
    if (sequence == null)
        throw new ArgumentNullException(nameof(sequence));
    if (comparer == null)
        throw new ArgumentNullException(nameof(comparer));

    return DistinctConsecutiveImpl(sequence, comparer);
}

private static IEnumerable<T> DistinctConsecutiveImpl<T>(IEnumerable<T> sequence, IEqualityComparer<T> comparer)
{
    using (var enumerator = sequence.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            yield break;

        var lastValue = enumerator.Current;
        yield return lastValue;

        while (enumerator.MoveNext())
        {
            var value = enumerator.Current;
            if (comparer.Equals(lastValue, value))
                continue;

            yield return value;
            lastValue = value;
        }
    }
}

或者，更“懒”的方法：

public static IEnumerable<T> DistinctConsecutive<T>(this IEnumerable<T> sequence, IEqualityComparer<T> comparer = null)
{
    if (comparer == null)
        comparer = EqualityComparer<T>.Default;

    using (var enumerator = sequence.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            yield break;

        var lastValue = enumerator.Current;
        yield return lastValue;

        while (enumerator.MoveNext())
        {
            var value = enumerator.Current;
            if (comparer.Equals(lastValue, value))
                continue;

            yield return value;
            lastValue = value;
        }
    }
}

如果您需要优化的解决方案，请放弃使用泛型并使用==代替IEqualityComparer<T>。如果这仍然是一个瓶颈，请使用普通的for循环来完成。

- Lucas Trzesniewski

---

你可以使用 null 作为比较器的默认值，而不是创建第二个重载函数。 - Servy

@Servy，这实际上是我在答案的第一个修订版本中所做的，但后来我改变了主意，以保持与Linq一致。 - Lucas Trzesniewski

Answer 2

我可以循环遍历数组并将每个元素与前一个元素进行比较，如果是重复的则删除，但我希望有一种更快的方法。

从算法上讲，基本上没有比这更快的方式了。使用相同算法的实现之间可能存在细微差别，但这已经是最好的方法了。无论你做什么，都无法避免检查每个项，因此操作的时间复杂度始终为O(n)。

- Servy

---

谢谢您指出这一点。我会接受下面的答案，因为它包含了一个实现。 - user3655934

@JackCoiley，所以你不知道如何循环遍历集合并获取与上一个不同的项吗？问题暗示你已经知道如何做到这一点。 - Servy

我已经有一个使用for循环实现的基本扩展程序。我主要是感谢您指出算法的复杂性，以便未来读者能够了解。 - user3655934

Answer 3

你可以使用MSDN提供的ChunkBy扩展。然后就很容易了：

var src = new[]{0, 0, 2, 0, 1, 1, 2, 2, 2, 1, 0, 0, 2, 1, 1, 0, 1, 1, 1};
var pruned = src.ChunkBy(x => x).Select(c => c.First());

- spender

---

我很感兴趣看到如何使这比一次循环集合并将每个值与前一个值进行比较更快（甚至同样快）。这段代码难道不是先遍历整个集合，然后再遍历缩小后的集合吗？ - user247702

@Stijn 嗯，从算法的角度来看，这确实是它正在做的事情。与明确地执行此操作相比，它很可能有更多的开销（因为它需要构建块的集合，即使只有前一个值实际上需要被记住）。如果这在紧密、性能关键的循环中使用，那么这种开销可能很重要，也可能不重要；它需要进行测试。 - Servy