代码之家 › 专栏 › 技术社区 › dtb

排序的可枚举项的N向交集

.net-3.5 linq c#

dtb · 技术社区 · 15 年前

鉴于 n 以升序返回不同元素的相同类型的可枚举项,例如:

IEnumerable<char> s1 = "adhjlstxyz";
IEnumerable<char> s2 = "bdeijmnpsz";
IEnumerable<char> s3 = "dejlnopsvw";

我希望有效地查找所有可枚举元素的所有值:

IEnumerable<char> sx = Intersect(new[] { s1, s2, s3 });

Debug.Assert(sx.SequenceEqual("djs"));

这里的“高效”意味着

每个输入可枚举项只应枚举一次,
只应在需要时检索输入可枚举项的元素,以及
该算法不应递归地枚举自己的输出。

我需要一些关于如何接近解决方案的提示。

这是迄今为止我(天真)的尝试:

static IEnumerable<T> Intersect<T>(IEnumerable<T>[] enums)
{
    return enums[0].Intersect(
        enums.Length == 2 ? enums[1] : Intersect(enums.Skip(1).ToArray()));
}

Enumerable.Intersect 将第一个可枚举的集合收集到哈希集中,然后枚举第二个可枚举的集合并生成所有匹配的元素。 Intersect 然后递归地将结果与下一个可枚举的相交。这显然不是很有效(它不符合限制条件)。它根本没有利用元素被排序的事实。

这是我试图与两个可枚举的相交。也许它可以概括为 n 枚举数?

static IEnumerable<T> Intersect<T>(IEnumerable<T> first, IEnumerable<T> second)
{
    using (var left = first.GetEnumerator())
    using (var right = second.GetEnumerator())
    {
        var leftHasNext = left.MoveNext();
        var rightHasNext = right.MoveNext();

        var comparer = Comparer<T>.Default;

        while (leftHasNext && rightHasNext)
        {
            switch (Math.Sign(comparer.Compare(left.Current, right.Current)))
            {
            case -1:
                leftHasNext = left.MoveNext();
                break;
            case 0:
                yield return left.Current;
                leftHasNext = left.MoveNext();
                rightHasNext = right.MoveNext();
                break;
            case 1:
                rightHasNext = right.MoveNext();
                break;
            }
        }
    }
}

2 回复 | 直到 15 年前

Marc Gravell 15 年前

好的;更复杂的答案:

public static IEnumerable<T> Intersect<T>(params IEnumerable<T>[] enums) {
    return Intersect<T>(null, enums);
}
public static IEnumerable<T> Intersect<T>(IComparer<T> comparer, params IEnumerable<T>[] enums) {
    if(enums == null) throw new ArgumentNullException("enums");
    if(enums.Length == 0) return Enumerable.Empty<T>();
    if(enums.Length == 1) return enums[0];
    if(comparer == null) comparer = Comparer<T>.Default;
    return IntersectImpl(comparer, enums);
}
public static IEnumerable<T> IntersectImpl<T>(IComparer<T> comparer, IEnumerable<T>[] enums) {
    IEnumerator<T>[] iters = new IEnumerator<T>[enums.Length];
    try {
        // create iterators and move as far as the first item
        for (int i = 0; i < enums.Length; i++) {
            if(!(iters[i] = enums[i].GetEnumerator()).MoveNext()) {
                yield break; // no data for one of the iterators
            }
        }
        bool first = true;
        T lastValue = default(T);
        do { // get the next item from the first sequence
            T value = iters[0].Current;
            if (!first && comparer.Compare(value, lastValue) == 0) continue; // dup in first source
            bool allTrue = true;
            for (int i = 1; i < iters.Length; i++) {
                var iter = iters[i];
                // if any sequence isn't there yet, progress it; if any sequence
                // ends, we're all done
                while (comparer.Compare(iter.Current, value) < 0) {
                    if (!iter.MoveNext()) goto alldone; // nasty, but
                }
                // if any sequence is now **past** value, then short-circuit
                if (comparer.Compare(iter.Current, value) > 0) {
                    allTrue = false;
                    break;
                }
            }
            // so all sequences have this value
            if (allTrue) yield return value;
            first = false;
            lastValue = value;
        } while (iters[0].MoveNext());
    alldone:
        ;
    } finally { // clean up all iterators
        for (int i = 0; i < iters.Length; i++) {
            if (iters[i] != null) {
                try { iters[i].Dispose(); }
                catch { }
            }
        }
    }
}

Marc Gravell 15 年前

您可以使用LINQ:

    public static IEnumerable<T> Intersect<T>(IEnumerable<IEnumerable<T>> enums) {
        using (var iter = enums.GetEnumerator()) {
            IEnumerable<T> result;
            if (iter.MoveNext()) {
                result = iter.Current;
                while (iter.MoveNext()) {
                    result = result.Intersect(iter.Current);
                }
            } else {
                result = Enumerable.Empty<T>();
            }
            return result;
        }
    }

这将是 简单的 尽管它确实多次构建散列集;一次推进所有n(利用排序)是很困难的,但是您也可以构建一个散列集并删除缺少的内容?