Используя Linq, чтобы получить последние N элементов коллекции?

284

Для данной коллекции есть ли способ получить последние N элементов этой коллекции? Если в структуре нет метода, как лучше написать метод расширения для этого?

Мэтью Гровс
источник

Ответы:

422
collection.Skip(Math.Max(0, collection.Count() - N));

Этот подход сохраняет порядок элементов без зависимости от какой-либо сортировки и обладает широкой совместимостью между несколькими поставщиками LINQ.

Важно соблюдать осторожность, чтобы не звонить Skipс отрицательным номером. Некоторые провайдеры, такие как Entity Framework, будут генерировать ArgumentException, когда представлены с отрицательным аргументом. Призыв Math.Maxизбегать этого аккуратно.

В приведенном ниже классе есть все необходимое для методов расширения: статический класс, статический метод и использование thisключевого слова.

public static class MiscExtensions
{
    // Ex: collection.TakeLast(5);
    public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> source, int N)
    {
        return source.Skip(Math.Max(0, source.Count() - N));
    }
}

Краткая заметка о производительности:

Поскольку обращение к Count()может вызвать перечисление определенных структур данных, такой подход может вызвать два прохода по данным. На самом деле это не проблема для большинства перечислимых; фактически уже существуют оптимизации для списков, массивов и даже запросов EF для оценки Count()операции за O (1) времени.

Однако, если вы должны использовать перечислимое только для пересылки и хотели бы избежать двухпроходного прохождения, рассмотрите однопроходный алгоритм, как описывают Лассе В. Карлсен или Марк Байерс . Оба этих подхода используют временный буфер для хранения элементов при перечислении, которые выдаются после того, как будет найден конец коллекции.

kbrimington
источник
2
+1, так как это работает в Linq to Entities / SQL. Я предполагаю, что он также более эффективен в Linq to Objects, чем стратегия Джеймса Керрана.
StriplingWarrior
11
Зависит от характера коллекции. Count () может быть O (N).
Джеймс Керран
3
@James: Абсолютно верно. Если иметь дело строго с коллекциями IEnumerable, это может быть двухпроходный запрос. Мне было бы очень интересно увидеть гарантированный алгоритм 1 прохода. Это может быть полезно.
Кбримингтон
4
Сделал несколько тестов. Оказывается, LINQ to Objects выполняет некоторые оптимизации в зависимости от типа коллекции, которую вы используете. Используя массивы Lists и LinkedLists, решение Джеймса имеет тенденцию быть быстрее, хотя и не на порядок. Если рассчитывается IEnumerable (например, через Enumerable.Range), решение Джеймса занимает больше времени. Я не могу придумать способа гарантировать один проход, не зная ничего о реализации или не копируя значения в другую структуру данных.
StriplingWarrior
1
@RedFilter - Достаточно справедливо. Я предполагаю, что мои привычки подкачки просочились сюда. Спасибо за ваш острый глаз.
Кбримингтон
59
coll.Reverse().Take(N).Reverse().ToList();


public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> coll, int N)
{
    return coll.Reverse().Take(N).Reverse();
}

ОБНОВЛЕНИЕ: Для решения проблемы clintp: a) Использование метода TakeLast (), который я определил выше, решает проблему, но если вы действительно хотите сделать это без дополнительного метода, то вам просто нужно признать, что Enumerable.Reverse () может быть Если вы используете метод расширения, вы не обязаны использовать его таким образом:

List<string> mystring = new List<string>() { "one", "two", "three" }; 
mystring = Enumerable.Reverse(mystring).Take(2).Reverse().ToList();
Джеймс Керран
источник
Проблема, с которой я столкнулся, заключается в следующем: List<string> mystring = new List<string>() { "one", "two", "three" }; mystring = mystring.Reverse().Take(2).Reverse(); я получаю ошибку компилятора, потому что .Reverse () возвращает void, и компилятор выбирает этот метод вместо метода Linq, который возвращает IEnumerable. Предложения?
Клинтон Пирс
1
Вы можете решить эту проблему, явно приведя mystring к IEnumerable <String>: ((IEnumerable <String>) mystring) .Reverse (). Take (2) .Reverse ()
Ян Хеттих,
Легко и просто, но требует полностью изменить порядок в два раза. Это может быть лучшим способом
shashwat
Мне нравится это в дополнение к принятому ответу от kbrimington. Если вы не заботитесь о заказе после того, как у вас есть последние Nзаписи, вы можете пропустить вторую Reverse.
ZoolWay,
@shashwat Он не меняет порядок дважды "полностью". Второе обращение относится только к коллекции N предметов. Кроме того, в зависимости от того, как реализована функция Reverse (), первый вызов может изменить только N элементов. (Реализация .NET 4.0 будет копировать коллекцию в массив и индексировать ее обратно)
Джеймс Керран
47

Примечание : я пропустил заголовок вашего вопроса, который гласил « Использование Linq» , поэтому в моем ответе фактически не используется Linq.

Если вы хотите избежать кэширования неленивой копии всей коллекции, вы можете написать простой метод, который делает это, используя связанный список.

Следующий метод добавит каждое значение, которое он найдет в исходной коллекции, в связанный список и урежет связанный список до необходимого количества элементов. Поскольку связанный список обрезается до этого количества элементов все время путем перебора всей коллекции, он будет хранить только копию не более N элементов из исходной коллекции.

Он не требует, чтобы вы знали количество элементов в исходной коллекции и не повторяли ее более одного раза.

Использование:

IEnumerable<int> sequence = Enumerable.Range(1, 10000);
IEnumerable<int> last10 = sequence.TakeLast(10);
...

Метод расширения:

public static class Extensions
{
    public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> collection,
        int n)
    {
        if (collection == null)
            throw new ArgumentNullException(nameof(collection));
        if (n < 0)
            throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)} must be 0 or greater");

        LinkedList<T> temp = new LinkedList<T>();

        foreach (var value in collection)
        {
            temp.AddLast(value);
            if (temp.Count > n)
                temp.RemoveFirst();
        }

        return temp;
    }
}
Лассе В. Карлсен
источник
Я все еще думаю, что у вас есть хороший, верный ответ, даже если он технически не использует Linq, поэтому я все еще даю вам +1 :)
Мэтью Гроувс
чистый, аккуратный и расширяемый +1!
Ясир Шейх
1
Я думаю, что это единственное решение, которое не заставляет исходный перечислитель проходить дважды (или более), и не вызывает материализацию перечисления, поэтому в большинстве приложений я бы сказал, что это будет гораздо более эффективно с точки зрения памяти и скорости.
Спротти
30

Вот метод, который работает с любым перечислимым, но использует только O (N) временное хранилище:

public static class TakeLastExtension
{
    public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> source, int takeCount)
    {
        if (source == null) { throw new ArgumentNullException("source"); }
        if (takeCount < 0) { throw new ArgumentOutOfRangeException("takeCount", "must not be negative"); }
        if (takeCount == 0) { yield break; }

        T[] result = new T[takeCount];
        int i = 0;

        int sourceCount = 0;
        foreach (T element in source)
        {
            result[i] = element;
            i = (i + 1) % takeCount;
            sourceCount++;
        }

        if (sourceCount < takeCount)
        {
            takeCount = sourceCount;
            i = 0;
        }

        for (int j = 0; j < takeCount; ++j)
        {
            yield return result[(i + j) % takeCount];
        }
    }
}

Использование:

List<int> l = new List<int> {4, 6, 3, 6, 2, 5, 7};
List<int> lastElements = l.TakeLast(3).ToList();

Он работает с использованием кольцевого буфера размера N для хранения элементов так, как он их видит, перезаписывая старые элементы новыми. Когда достигнут конец перечислимого, кольцевой буфер содержит последние N элементов.

Марк Байерс
источник
2
+1: у него должна быть лучшая производительность, чем у меня, но вы должны убедиться, что он работает правильно, когда коллекция содержит меньше элементов, чем n.
Лассе В. Карлсен
Что ж, большую часть времени я предполагаю, что люди будут осторожны, когда копируют код из SO для производственного использования, чтобы добавлять такие вещи сами, это может не быть проблемой. Если вы собираетесь добавить его, попробуйте также проверить переменную коллекции на нулевое значение. В противном случае, отличное решение :) Я сам подумывал об использовании кольцевого буфера, потому что связанный список добавит GC-давление, но прошло много времени с тех пор, как я его создал, и я не хотел возиться с тестовым кодом, чтобы выяснить если я сделал это правильно. Я должен сказать, что влюбляюсь в LINQPad,
Лассе В. Карлсен
2
Возможной оптимизацией было бы проверить, реализован ли перечисляемый реализованный IList, и использовать тривиальное решение, если это так. Подход с временным хранилищем тогда будет необходим только для действительно потокового IEnumerables
piers7
1
тривиальный пример: ваши аргументы ArgumentOutOfRangeException находятся в неправильном порядке (R # говорит)
piers7
28

.NET Core 2.0+ предоставляет метод LINQ TakeLast():

https://docs.microsoft.com/en-us/dotnet/api/system.linq.enumerable.takelast

пример :

Enumerable
    .Range(1, 10)
    .TakeLast(3) // <--- takes last 3 items
    .ToList()
    .ForEach(i => System.Console.WriteLine(i))

// outputs:
// 8
// 9
// 10
луч
источник
Я использую: NET Standard 2.0, и у меня нет его в наличии. В чем дело? :(
SuperJMN
@SuperJMN Хотя вы можете ссылаться на библиотеки стандарта .net 2.0, вы, возможно, не нацелены на правильную версию ядра dotnet в своем проекте. Этот метод недоступен для v1.x ( netcoreapp1.x), но только для v2.0 и v2.1 функции dotnetcore ( netcoreapp2.x). Возможно, вы нацелены на полную структуру (например net472), которая также не поддерживается. (Стандартные библиотеки .net могут использоваться любым из вышеперечисленных, но могут предоставлять только определенные API-интерфейсы, специфичные для целевой платформы. См. docs.microsoft.com/en-us/dotnet/standard/frameworks )
Ray
1
Это должно быть выше сейчас. Не нужно заново изобретать колесо
Джеймс Вудли,
11

Я удивлен, что никто не упомянул об этом, но у SkipWhile есть метод, который использует индекс элемента .

public static IEnumerable<T> TakeLastN<T>(this IEnumerable<T> source, int n)
{
    if (source == null)
        throw new ArgumentNullException("Source cannot be null");

    int goldenIndex = source.Count() - n;
    return source.SkipWhile((val, index) => index < goldenIndex);
}

//Or if you like them one-liners (in the spirit of the current accepted answer);
//However, this is most likely impractical due to the repeated calculations
collection.SkipWhile((val, index) => index < collection.Count() - N)

Единственное ощутимое преимущество, которое дает это решение перед другими, состоит в том, что вы можете иметь возможность добавить предикат для создания более мощного и эффективного запроса LINQ вместо двух отдельных операций, которые дважды пересекают IEnumerable.

public static IEnumerable<T> FilterLastN<T>(this IEnumerable<T> source, int n, Predicate<T> pred)
{
    int goldenIndex = source.Count() - n;
    return source.SkipWhile((val, index) => index < goldenIndex && pred(val));
}
Ник Бэбкок
источник
9

Используйте EnumerableEx.TakeLast в сборке System.Interactive RX. Это реализация O (N), как у @ Mark, но она использует очередь, а не конструкцию кольцевого буфера (и удаляет элементы, когда она достигает емкости буфера).

(Примечание: это версия IEnumerable, а не версия IObservable, хотя реализация этих двух программ практически идентична)

piers7
источник
Это лучший ответ. Не катайте свою собственную, если есть подходящая библиотека, которая делает работу, и команда RX высокого качества.
Bradgonesurfing
Если вы собираетесь с этим, установите его с Nuget - nuget.org/packages/Ix-Async
nikib3ro
Разве C # не Queue<T>реализован с использованием циклического буфера ?
tigrou
@tigrou. нет, оно не круглое
ситикид
6

Если вы имеете дело с коллекцией с ключом (например, записи из базы данных), быстрое (т.е. быстрее, чем выбранный ответ) решение будет

collection.OrderByDescending(c => c.Key).Take(3).OrderBy(c => c.Key);
dav_i
источник
+1 работает для меня, и его легко прочитать, у меня есть небольшое количество объектов в моем списке
fubo
5

Если вы не против погрузиться в Rx как часть монады, вы можете использовать TakeLast:

IEnumerable<int> source = Enumerable.Range(1, 10000);

IEnumerable<int> lastThree = source.AsObservable().TakeLast(3).AsEnumerable();
Ричард Сзалай
источник
2
Вам не нужен AsObservable (), если вы ссылаетесь на System.Interactive RX вместо System.Reactive (см. Мой ответ)
piers7
2

Если использование сторонней библиотеки является опцией, MoreLinq определяет, TakeLast()что именно это и делает.

см
источник
2

Я попытался объединить эффективность и простоту и в конечном итоге с этим:

public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> source, int count)
{
    if (source == null) { throw new ArgumentNullException("source"); }

    Queue<T> lastElements = new Queue<T>();
    foreach (T element in source)
    {
        lastElements.Enqueue(element);
        if (lastElements.Count > count)
        {
            lastElements.Dequeue();
        }
    }

    return lastElements;
}

О производительности: в C # Queue<T>реализован с использованием циклического буфера, поэтому в каждом цикле не выполняется создание объектов (только когда очередь растет). Я не установил емкость очереди (используя выделенный конструктор), потому что кто-то может вызвать это расширение с помощью count = int.MaxValue. Для дополнительной производительности вы можете проверить, реализует ли источник, IList<T>и если да, напрямую извлечь последние значения, используя индексы массива.

tigrou
источник
1

Немного неэффективно брать последние N из коллекции, используя LINQ, поскольку все вышеупомянутые решения требуют итерации по всей коллекции. TakeLast(int n)В System.Interactiveтоже есть эта проблема.

Если у вас есть список, более эффективный способ - нарезать его, используя следующий метод

/// Select from start to end exclusive of end using the same semantics
/// as python slice.
/// <param name="list"> the list to slice</param>
/// <param name="start">The starting index</param>
/// <param name="end">The ending index. The result does not include this index</param>
public static List<T> Slice<T>
(this IReadOnlyList<T> list, int start, int? end = null)
{
    if (end == null)
    {
        end = list.Count();
    }
     if (start < 0)
    {
        start = list.Count + start;
    }
     if (start >= 0 && end.Value > 0 && end.Value > start)
    {
        return list.GetRange(start, end.Value - start);
    }
     if (end < 0)
    {
        return list.GetRange(start, (list.Count() + end.Value) - start);
    }
     if (end == start)
    {
        return new List<T>();
    }
     throw new IndexOutOfRangeException(
        "count = " + list.Count() + 
        " start = " + start +
        " end = " + end);
}

с участием

public static List<T> GetRange<T>( this IReadOnlyList<T> list, int index, int count )
{
    List<T> r = new List<T>(count);
    for ( int i = 0; i < count; i++ )
    {
        int j=i + index;
        if ( j >= list.Count )
        {
            break;
        }
        r.Add(list[j]);
    }
    return r;
}

и некоторые тесты

[Fact]
public void GetRange()
{
    IReadOnlyList<int> l = new List<int>() { 0, 10, 20, 30, 40, 50, 60 };
     l
        .GetRange(2, 3)
        .ShouldAllBeEquivalentTo(new[] { 20, 30, 40 });
     l
        .GetRange(5, 10)
        .ShouldAllBeEquivalentTo(new[] { 50, 60 });

}
 [Fact]
void SliceMethodShouldWork()
{
    var list = new List<int>() { 1, 3, 5, 7, 9, 11 };
    list.Slice(1, 4).ShouldBeEquivalentTo(new[] { 3, 5, 7 });
    list.Slice(1, -2).ShouldBeEquivalentTo(new[] { 3, 5, 7 });
    list.Slice(1, null).ShouldBeEquivalentTo(new[] { 3, 5, 7, 9, 11 });
    list.Slice(-2)
        .Should()
        .BeEquivalentTo(new[] {9, 11});
     list.Slice(-2,-1 )
        .Should()
        .BeEquivalentTo(new[] {9});
}
bradgonesurfing
источник
1

Я знаю, что уже поздно отвечать на этот вопрос. Но если вы работаете с коллекцией типа IList <> и вам не важен порядок возвращаемой коллекции, тогда этот метод работает быстрее. Я использовал ответ Марка Байерса и внес небольшие изменения. Так что теперь метод TakeLast:

public static IEnumerable<T> TakeLast<T>(IList<T> source, int takeCount)
{
    if (source == null) { throw new ArgumentNullException("source"); }
    if (takeCount < 0) { throw new ArgumentOutOfRangeException("takeCount", "must not be negative"); }
    if (takeCount == 0) { yield break; }

    if (source.Count > takeCount)
    {
        for (int z = source.Count - 1; takeCount > 0; z--)
        {
            takeCount--;
            yield return source[z];
        }
    }
    else
    {
        for(int i = 0; i < source.Count; i++)
        {
            yield return source[i];
        }
    }
}

Для теста я использовал метод Марка Байерса и ответ Кбримингтона . Это тест:

IList<int> test = new List<int>();
for(int i = 0; i<1000000; i++)
{
    test.Add(i);
}

Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();

IList<int> result = TakeLast(test, 10).ToList();

stopwatch.Stop();

Stopwatch stopwatch1 = new Stopwatch();
stopwatch1.Start();

IList<int> result1 = TakeLast2(test, 10).ToList();

stopwatch1.Stop();

Stopwatch stopwatch2 = new Stopwatch();
stopwatch2.Start();

IList<int> result2 = test.Skip(Math.Max(0, test.Count - 10)).Take(10).ToList();

stopwatch2.Stop();

И вот результаты для взятия 10 элементов:

введите описание изображения здесь

и для взятия 1000001 элементов получаются следующие результаты: введите описание изображения здесь

Саша
источник
1

Вот мое решение:

public static class EnumerationExtensions
{
    public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> input, int count)
    {
        if (count <= 0)
            yield break;

        var inputList = input as IList<T>;

        if (inputList != null)
        {
            int last = inputList.Count;
            int first = last - count;

            if (first < 0)
                first = 0;

            for (int i = first; i < last; i++)
                yield return inputList[i];
        }
        else
        {
            // Use a ring buffer. We have to enumerate the input, and we don't know in advance how many elements it will contain.
            T[] buffer = new T[count];

            int index = 0;

            count = 0;

            foreach (T item in input)
            {
                buffer[index] = item;

                index = (index + 1) % buffer.Length;
                count++;
            }

            // The index variable now points at the next buffer entry that would be filled. If the buffer isn't completely
            // full, then there are 'count' elements preceding index. If the buffer *is* full, then index is pointing at
            // the oldest entry, which is the first one to return.
            //
            // If the buffer isn't full, which means that the enumeration has fewer than 'count' elements, we'll fix up
            // 'index' to point at the first entry to return. That's easy to do; if the buffer isn't full, then the oldest
            // entry is the first one. :-)
            //
            // We'll also set 'count' to the number of elements to be returned. It only needs adjustment if we've wrapped
            // past the end of the buffer and have enumerated more than the original count value.

            if (count < buffer.Length)
                index = 0;
            else
                count = buffer.Length;

            // Return the values in the correct order.
            while (count > 0)
            {
                yield return buffer[index];

                index = (index + 1) % buffer.Length;
                count--;
            }
        }
    }

    public static IEnumerable<T> SkipLast<T>(this IEnumerable<T> input, int count)
    {
        if (count <= 0)
            return input;
        else
            return input.SkipLastIter(count);
    }

    private static IEnumerable<T> SkipLastIter<T>(this IEnumerable<T> input, int count)
    {
        var inputList = input as IList<T>;

        if (inputList != null)
        {
            int first = 0;
            int last = inputList.Count - count;

            if (last < 0)
                last = 0;

            for (int i = first; i < last; i++)
                yield return inputList[i];
        }
        else
        {
            // Aim to leave 'count' items in the queue. If the input has fewer than 'count'
            // items, then the queue won't ever fill and we return nothing.

            Queue<T> elements = new Queue<T>();

            foreach (T item in input)
            {
                elements.Enqueue(item);

                if (elements.Count > count)
                    yield return elements.Dequeue();
            }
        }
    }
}

Код немного коренастый, но как вставляемый повторно используемый компонент, он должен работать так же хорошо, как и в большинстве сценариев, и он будет сохранять код, который его использует, красивым и лаконичным. :-)

Мой TakeLastдля неIList`1 основан на том же алгоритме кольцевого буфера, что и в ответах по @Mark Байерс и @MackieChan дальше. Интересно, насколько они похожи - я написал абсолютно самостоятельно. Думаю, на самом деле есть только один способ правильно создать кольцевой буфер. :-)

Глядя на ответ @ kbrimington, можно добавить дополнительную проверку, IQuerable<T>чтобы вернуться к подходу, который хорошо работает с Entity Framework - при условии, что то, что у меня есть на данный момент, не так.

Джонатан Гилберт
источник
0

Ниже приведен реальный пример того, как взять последние 3 элемента из коллекции (массива):

// split address by spaces into array
string[] adrParts = adr.Split(new string[] { " " },StringSplitOptions.RemoveEmptyEntries);
// take only 3 last items in array
adrParts = adrParts.SkipWhile((value, index) => { return adrParts.Length - index > 3; }).ToArray();
Алексей Тимков
источник
0

Используя этот метод, чтобы получить весь диапазон без ошибок

 public List<T> GetTsRate( List<T> AllT,int Index,int Count)
        {
            List<T> Ts = null;
            try
            {
                Ts = AllT.ToList().GetRange(Index, Count);
            }
            catch (Exception ex)
            {
                Ts = AllT.Skip(Index).ToList();
            }
            return Ts ;
        }
Али Асгар Фендерески
источник
0

Немного отличается реализация с использованием кольцевого буфера. Тесты показывают, что метод примерно в два раза быстрее, чем те, которые используют Queue (реализация TakeLast в System.Linq ), однако не без затрат - ему нужен буфер, который увеличивается вместе с запрошенным количеством элементов, даже если у вас есть Небольшая коллекция, вы можете получить огромное выделение памяти.

public IEnumerable<T> TakeLast<T>(IEnumerable<T> source, int count)
{
    int i = 0;

    if (count < 1)
        yield break;

    if (source is IList<T> listSource)
    {
        if (listSource.Count < 1)
            yield break;

        for (i = listSource.Count < count ? 0 : listSource.Count - count; i < listSource.Count; i++)
            yield return listSource[i];

    }
    else
    {
        bool move = true;
        bool filled = false;
        T[] result = new T[count];

        using (var enumerator = source.GetEnumerator())
            while (move)
            {
                for (i = 0; (move = enumerator.MoveNext()) && i < count; i++)
                    result[i] = enumerator.Current;

                filled |= move;
            }

        if (filled)
            for (int j = i; j < count; j++)
                yield return result[j];

        for (int j = 0; j < i; j++)
            yield return result[j];

    }
}
Romasz
источник