有效地将IEnumerable值折叠在一起

本文关键字：折叠 在一起 IEnumerable 有效地 | 更新日期: 2023-09-27 18:21:09

我想将某些IEnumerable中的值"折叠"在一起，以便将相同的相邻元素折叠为单个元素。

我想不出比举个例子更好的方法来描述这个问题了：

数组[0,0,2,0,1,1,2,2,1,0,2,1,0,0,1,0,1,1,1,1]应变为[0,2,0,1,2,1,0,2,1,0,1]

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

我的使用将仅用于相对较短的阵列（<100个元素），并且仅使用int，然而，将赞赏通用解决方案。

编辑：正如下面所指出的，问题从根本上来说是O（n）复杂性，但我希望linqy可以击败我（可能很笨拙）的实现。

有效地将IEnumerable值折叠在一起

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

这应该做得很好：

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;
        }
    }
}

或者，lazier方法：

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循环来完成它。

我可以循环遍历数组，并对照前一个元素检查每个元素，如果它是重复的，则删除它，但我希望有一种更快的方法。

从根本上讲，永远不会有一种方法在算法上更快。使用相同算法的实现可能会有细微的差异，但这是最好的。没有办法避免检查每个项目，所以无论你做什么，操作都将是O（n）。

您可以使用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());
相关文章：