将IEnumerable分成三个部分：“above”，“item”和“below”，并保持效率

Question

IEnumerable<int> list = new[] { 1, 2, 7, 3, 11, 5 };
int item = (from x in list where (x == list.Max()) select x).First();
IEnumerable<int> above = from x in list where list.ToList().IndexOf(item) > list.ToList().IndexOf(x) select x;
IEnumerable<int> below = from x in list where list.ToList().IndexOf(item) < list.ToList().IndexOf(x) select x;

我想在一个 IEnumerable 中查找一个元素，并将该 IEnumerable 分成不再包含我找到的元素的 IEnumerables。上面的代码展示了我想要实现的结果，但是我需要将 IEnumerable 转换为 List 才能运行。

我感觉使用 LinQ 和 IEnumerable 应该有一种方法可以做到这一点。怎么做呢？

- Johannes

---

首先，您可以简单地使用 int item = list.Max()。 - dee-see

其次，听起来你想要使用 Except？ - default

@Default 我研究了一下 Except - 它似乎是从列表中移除一个项目 - 我无法看到如何在拆分点将结果拆分为两个IEnumerable。 - Johannes

Answer 1

所以我们有几个子问题。第一个问题是返回集合中某个元素的 某个投影 的最高值。 Max 只比较元素本身，或者如果给定投影，则返回该投影的结果。

public static TSource MaxBy<TSource, TKey>(this IEnumerable<TSource> source
    , Func<TSource, TKey> selector
    , IComparer<TKey> comparer = null)
{
    if (comparer == null)
    {
        comparer = Comparer<TKey>.Default;
    }
    using (IEnumerator<TSource> iterator = source.GetEnumerator())
    {
        if (!iterator.MoveNext())
        {
            throw new ArgumentException("Source was empty");
        }

        TSource maxItem = iterator.Current;
        TKey maxValue = selector(maxItem);

        while (iterator.MoveNext())
        {
            TKey nextValue = selector(iterator.Current);
            if (comparer.Compare(nextValue, maxValue) > 0)
            {
                maxValue = nextValue;
                maxItem = iterator.Current;
            }
        }
        return maxItem;
    }
}

这使我们能够更有效地获取具有最大值的项的索引：

var splitPoint = list.Select((index, number) => new { index, number })
    .MaxBy(pair => pair.number)
    .index;

接下来，您可以使用跳过（skip）/获取（take）来分割集合：

var firstHalf = list.Take(index);
var secondHalf = list.Skip(index + 1);

你的代码存在一些问题，这里进行了解决。

在查询中，你对每个项都计算了Max值，而不是计算一次并使用该计算出的值。

然后，你又针对列表中的每个项，将所有项都复制到一个新列表中两次，搜索该列表以尝试找到最大项的位置，然后再尝试找到当前项的位置。你整个过程重复了两次。这意味着你会为每个项四次拷贝整个数组到一个列表中，在集合中为每个项四次搜索最大项的位置，并且通过线性搜索来找到当前项的索引（你可以通过简单地计数来近似计算），对于每个项需要执行两次。随着项目数量的增加，这种方式的效率会变得很低。

这里的代码通过单次遍历集合来查找最大项的索引，然后创建表示每半部分的序列，这些序列除了迭代各项之外几乎没有任何开销。

- Servy

---

对于 Take() 和 Skip()，我会给予 +1。虽然创建扩展可能看起来有些过度，但我更倾向于使用Filipe的答案并使用Take()和Skip()。 - Ricardo Souza

@rcdmk 这样做增加了复杂性，但换来的是一个有广泛应用的有用通用方法，并且消除了将整个集合实例化为列表，然后迭代该列表以查找您之前已经找到的项目的需要。如果集合足够小，不会出现问题，那就没事了，但这个问题的整个重点是优化查询，避免不必要的操作。 - Servy

我对 Skip() 有些怀疑。在集合的前面部分很小而后面部分很大的情况下，使用 Skip 可能比枚举所有内容到列表中更好，但如果前面的部分很大，每次尝试枚举后面的部分都必须遍历它之前的所有内容。如果集合已知实现了 IList，最好用一个从指定索引开始产生该列表项的方法来替换 Skip。 - supercat

@supercat Skip 已经在内部进行了优化。如果序列传递实现了 IList 接口，它将使用索引器访问项，从该索引开始并一直到末尾。 - Servy

@supercat 对，我总是忘记它不支持，尽管它应该支持。希望他们最终会添加它。在那种情况下，手动进行优化并使用for循环从特定索引迭代到结尾可能是值得的。 - Servy

Answer 2

尽可能在可以使用索引的地方使用扩展方法。请看下面带有注释的示例。

// define the list
IEnumerable<int> list = new[] { 1, 2, 7, 3, 11, 5 };

// define some value (max in your sample)
int value = list.Max();

// get the index of the value you want
int indexValue = list.ToList().IndexOf(value);

// find collections
IEnumerable<int> above = list.Where((value, index) => index < indexValue);
IEnumerable<int> below = list.Where((value, index) => index > indexValue);

- Felipe Oriani

---

编译器会将其内联，因此您不必每次都承担查找成本。 - Mrchief

不，它不会。它无法知道集合没有发生变化。 - Servy

@Mrchief编译器无法知道这一点（或者至少无法证明它），因此它无法省略这些操作。 - Servy

@Mrchief 哦，顺便说一下，内联并不是你所认为的意思。内联只是指将短方法的主体代码“内联”到调用该方法的位置中。这避免了为非常短和简单的方法创建堆栈帧。你似乎把它用来表示缓存方法的结果，并返回缓存的结果而不是重新计算它。那应该是记忆化。内联确实经常发生（尽管这个方法足够复杂，我怀疑它会在这里发生），但编译器/运行时几乎不进行记忆化。 - Servy

@Servy：我知道内联和记忆化的区别，在这种情况下，我说错了话。不知怎么搞的，我混淆了。 - Mrchief

Answer 3

首先，您需要找到最大元素的（第一个）索引。作为Servy答案的变体，可以使用Select和Aggregate来完成此操作。然后枚举该索引之前和之后的元素：

        var indexOfMax = list
            .Select((value, index) => new KeyValuePair<int, int>(index, value))
            .Aggregate(new KeyValuePair<int, int>(-1, -1), (min, cur) => 
                {
                    if (min.Key == -1 || cur.Value > min.Value)
                        return cur;
                    return min;
                }).Key;

        var beginning = list.Take(indexOfMax);
        var end = list.Skip(indexOfMax + 1);

- dbc

---

与其使用 int 并使用 -1 作为伪空值，您可以使用 int? 并实际使用 null 表示某些整数没有值。KeyValuePair 也是专门用于表示从一个值到另一个值的映射的对象。对于一般没有键/值关系的对，通常应该使用 Tuple。 - Servy

还要注意的是，虽然这比创建一个通用的MaxBy方法使用更少的代码，就像我在答案中所做的那样，但我发现该方法足够有用，其应用也足够常见，值得将该逻辑重构为自己的方法，而不是每次遇到问题时都重复实现该逻辑。你的解决方案可以在一个答案中减少代码量，但很容易导致更多的代码和不易维护的代码，在更大的代码库的过程中。 - Servy

@Servy - 我使用KeyValuePair有两个原因。首先，对于非常小的元组，出于性能原因，我更喜欢使用结构体而不是类。其次，在这种情况下，KeyValuePair确实代表了一种映射，因为键是列表索引。-1作为无效或未初始化索引的标志符是相当常规的。至于创建自己的MaxBy()方法，如果您要重用代码，请务必这样做；代码重用总是好的。 - dbc

@Servy - 另外，通过为一个空列表返回-1，Take和Skip表达式会导致空的可枚举对象而不是异常。 - dbc

Answer 4

首先，您需要确保您的 IEnumerable<T> 对象按照特定顺序包含项目。这可以通过选择有序的 IOrderedEnumerable<T> 而不是普通的无序 IEnumerable<T>，或者选择可以通过索引引用元素的 IList<T> 来完成。

当您弄清楚了这一点后，拆分就变得非常简单：通过索引或顺序迭代元素，并将它们添加到 IList<T> above 直到找到您的元素。跳过该元素，然后继续迭代元素并将它们添加到 IList<T> below。

- Dmitri Trofimov