Divide IEnumerable in three parts: "above", "element", "below" with efficiency

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; 

I want to find an element in IEnumerable and split IEnumerable into IEnumerable , which no longer contains the element I found. The above code shows the result that I want to achieve, however I had to convert IEnumerable to a list.

I feel that there must be a way to do this using only LinQ and IEnumerable. How can I do that?

Answer 1

So we have a few sub-questions. The first problem is returning the item to the collection with the highest value of some projection of that item. Max compares only the element or, if a projection is specified, returns the result of this projection.

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

This allows us to get the index of the element with the largest value much more efficiently:

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

Then, to split the collection, you can simply use skip / take:

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

There are a number of different problems with the code that you have here.

You calculate the Max value for each individual item in the query to get an item , rather than calculate it once and use that calculated value.

Then you go for each item in the list and copy all the items into the new list twice, look at this list to try to find the position of the max element, and then try to find the position of the current element. Then you do it just two times. This means that you copy the entire array to the list four times for each element, look for the position of the maximum element four times per element in the collection, and search the list linearly to find the index of the current element (you could calculate something in about one time by simply counting) twice for each element. It will scale ... badly as the number of elements increases.

Here, the code finds the index of the max element in one pass of the collection, and then creates sequences that represent each half, each of which has virtually no overhead, except for a simple repetition of these elements.

Answer 2

Try using extension methods in which you can use the index. See the example below with comments.

 // 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); 

Answer 3

First, you need to find the (first) index of the maximum element. As a Servy answer option, this can be done with Select and Aggregate . Then list the elements before and after this index:

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

Answer 4

First, you need to ensure that your IEnumerable<T> contains the elements in a specific order. This can be done either using IOrderedEnumerable<T> instead of the usual unordered IEnumerable<T> , or using IList<T> , which can refer to elements by index.

When you get this shape, the splitting becomes pretty trivial: repeat the elements in index or in order and add them to IList<T> above until you find your element. Skip this element, and then continue to iterate through the elements, adding them to the IList<T> below .