Usando o Linq para obter os últimos N elementos de uma coleção?

284

Dada uma coleção, existe uma maneira de obter os últimos N elementos dessa coleção? Se não houver um método na estrutura, qual seria a melhor maneira de escrever um método de extensão para fazer isso?

Matthew Groves
fonte

Respostas:

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

Essa abordagem preserva a ordem dos itens sem depender de nenhuma classificação e possui ampla compatibilidade entre vários provedores LINQ.

É importante tomar cuidado para não ligar Skipcom um número negativo. Alguns provedores, como o Entity Framework, produzirão uma ArgumentException quando apresentados com um argumento negativo. A chamada para Math.Maxevita isso ordenadamente.

A classe abaixo possui todos os elementos essenciais para os métodos de extensão, que são: uma classe estática, um método estático e o uso da thispalavra - chave.

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

Uma breve nota sobre o desempenho:

Como a chamada para Count()pode causar a enumeração de determinadas estruturas de dados, essa abordagem corre o risco de causar duas passagens nos dados. Isso não é realmente um problema com a maioria dos enumeráveis; de fato, já existem otimizações para listas, matrizes e até consultas EF para avaliar a Count()operação no tempo O (1).

Se, no entanto, você deve usar um enumerável de encaminhamento somente e gostaria de evitar duas passagens, considere um algoritmo de uma passagem como Lasse V. Karlsen ou Mark Byers descrevem. Ambas as abordagens usam um buffer temporário para armazenar itens enquanto enumera, que são gerados quando o final da coleção é encontrado.

Kbrimington
fonte
2
+1, pois isso funciona no Linq to Entities / SQL. Acho que também é mais eficiente no Linq to Objects do que a estratégia de James Curran.
precisa
11
Depende da natureza da coleção. Count () pode ser O (N).
James Curran
3
@ James: Absolutamente correto. Se estiver lidando estritamente com coleções IEnumerable, pode ser uma consulta de duas passagens. Eu ficaria muito interessado em ver um algoritmo de 1 passagem garantido. Pode ser útil.
precisa saber é o seguinte
4
Fiz alguns benchmarks. Acontece que o LINQ to Objects realiza algumas otimizações com base no tipo de coleção que você está usando. Usando matrizes, se Listes, LinkedLista solução de James tende a ser mais rápida, embora não por uma ordem de magnitude. Se o IEnumerable for calculado (via Enumerable.Range, por exemplo), a solução de James levará mais tempo. Não consigo pensar em nenhuma maneira de garantir uma única passagem sem saber algo sobre a implementação ou copiar valores para uma estrutura de dados diferente.
StriplingWarrior
1
@RedFilter - Justo. Suponho que meus hábitos de paginação vazaram aqui. Obrigado pelo seu olhar atento.
kbrimington
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();
}

UPDATE: Para resolver o problema de clintp: a) O uso do método TakeLast () que eu defini acima resolve o problema, mas se você realmente deseja fazê-lo sem o método extra, basta reconhecer que, enquanto Enumerable.Reverse () pode ser usado como um método de extensão, não é necessário usá-lo dessa maneira:

List<string> mystring = new List<string>() { "one", "two", "three" }; 
mystring = Enumerable.Reverse(mystring).Take(2).Reverse().ToList();
James Curran
fonte
O problema que tenho com isso é se eu disser: List<string> mystring = new List<string>() { "one", "two", "three" }; mystring = mystring.Reverse().Take(2).Reverse(); Eu recebo um erro do compilador porque .Reverse () retorna nulo e o compilador escolhe esse método em vez do Linq que retorna um IEnumerable. Sugestões?
Clinton Pierce
1
Você pode resolver este problema, lançando explicitamente mystring para IEnumerable <String>: ((IEnumerable <String>) mystring) .reverse () Tomar (2) .reverse ().
Jan Hettich
Fácil e simples o suficiente, mas requer a reversão completa do pedido duas vezes. Esta pode ser a melhor maneira
Shashwat
Eu gosto disso, além da resposta aceita pelo kbrimington. Se você não se importa com o pedido após ter os últimos Nregistros, pode pular o segundo Reverse.
ZoolWay #
@shashwat Não inverte a ordem duas vezes "completamente". A segunda reversão se aplica apenas à coleção de N itens. Além disso, dependendo de como Reverse () for implementada, a primeira chamada a ele poderá reverter N itens. (A implementação .NET 4.0 irá copiar a coleção para uma matriz, e índice de trás fora dela)
James Curran
47

Nota : Perdi o título da sua pergunta que dizia Usando o Linq , então minha resposta não usa o Linq.

Se você deseja evitar o armazenamento em cache de uma cópia não preguiçosa de toda a coleção, escreva um método simples que faça isso usando uma lista vinculada.

O método a seguir adiciona cada valor encontrado na coleção original a uma lista vinculada e reduz a lista vinculada ao número de itens necessários. Como mantém a lista vinculada aparada para esse número de itens o tempo todo durante a iteração na coleção, ela manterá apenas uma cópia de no máximo N itens da coleção original.

Não requer que você saiba o número de itens na coleção original, nem repita mais de uma vez.

Uso:

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

Método de extensão:

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;
    }
}
Lasse V. Karlsen
fonte
Eu ainda acho que você tem uma boa, a resposta válida mesmo se não for tecnicamente usando Linq, então eu ainda dar-lhe um +1 :)
Matthew Groves
+1 limpo, arrumado e extensível!
Yasser Shaikh
1
Eu acho que é a única solução que não faz com que o enumerador de origem seja executado duas vezes (ou mais) e não força a materialização da enumeração; portanto, na maioria dos aplicativos, eu diria que seria muito mais eficiente em termos de memória e velocidade.
Sprotty
30

Aqui está um método que funciona em qualquer enumerável, mas usa apenas armazenamento temporário 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];
        }
    }
}

Uso:

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

Ele funciona usando um buffer de anel do tamanho N para armazenar os elementos como os vê, substituindo elementos antigos por novos. Quando o final do enumerável é alcançado, o buffer do anel contém os últimos N elementos.

Mark Byers
fonte
2
+1: isso deve ter um desempenho melhor que o meu, mas você deve garantir que ele faça a coisa certa quando a coleção contiver menos elementos que n.
Lasse V. Karlsen
Bem, na maioria das vezes, suponho que as pessoas cuidem da cópia do código do SO para uso em produção para adicionar essas coisas, talvez não seja um problema. Se você for adicioná-lo, considere também verificar se a variável de coleção é nula. Caso contrário, excelente solução :) Eu estava pensando em usar um buffer de anel, porque uma lista vinculada adicionaria pressão de GC, mas já faz um tempo desde que eu fiz um e não queria incomodar o código de teste para descobrir se eu fiz direito. Devo dizer que estou me apaixonando pelo LINQPad :) linqpad.net
Lasse V. Karlsen
2
Uma possível otimização seria verificar se o enumerável IList implementado e usar a solução trivial, se isso acontecer. A abordagem de armazenamento temporário, então, só pode ser necessário para verdadeiramente 'streaming' IEnumerables
piers7
1
trivial nit-escolher: seus argumentos para ArgumentOutOfRangeException estão na ordem errada (R # diz)
piers7
28

O .NET Core 2.0+ fornece o método LINQ TakeLast():

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

exemplo :

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

// outputs:
// 8
// 9
// 10
Raio
fonte
Estou usando: NET Standard 2.0 e não o tenho disponível. O que há de errado? :(
SuperJMN
@SuperJMN Embora você possa fazer referência às bibliotecas .net padrão 2.0, talvez não esteja direcionando a versão correta do dotnet core em seu projeto. Este método não está disponível para v1.x ( netcoreapp1.x), mas apenas para as v2.0 e v2.1 de dotnetcore ( netcoreapp2.x). É possível que você esteja direcionando a estrutura completa (por exemplo net472), que também não é suportada. (as bibliotecas padrão .net podem ser usadas por qualquer uma das opções acima, mas podem apenas expor determinadas APIs específicas a uma estrutura de destino. consulte docs.microsoft.com/en-us/dotnet/standard/frameworks )
Ray
1
Isso precisa ser mais alto agora. Não há necessidade de re-inventar a roda
James Woodley
11

Estou surpreso que ninguém tenha mencionado, mas SkipWhile tem um método que usa o índice do elemento .

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)

O único benefício perceptível que esta solução apresenta sobre outras é que você pode ter a opção de adicionar um predicado para fazer uma consulta LINQ mais poderosa e eficiente, em vez de ter duas operações separadas que percorrem o IEnumerable duas vezes.

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));
}
Nick Babcock
fonte
9

Use EnumerableEx.TakeLast no assembly System.Interactive do RX. É uma implementação O (N) como a de @ Mark, mas usa uma fila em vez de uma construção de buffer de anel (e remove da fila os itens quando atinge a capacidade do buffer).

(Nota: esta é a versão IEnumerable - não a versão IObservable, embora a implementação das duas seja praticamente idêntica)

piers7
fonte
Esta é a melhor resposta. Não faça o seu próprio se houver uma biblioteca adequada que faça o trabalho e a equipe do RX for de alta qualidade.
Bradgonesurfing
Se você está indo com isso, instale-o Nuget - nuget.org/packages/Ix-Async
nikib3ro
O C # não é Queue<T>implementado usando um buffer circular ?
usar o seguinte
@tigrou. não, não é circular
citykid
6

Se você estiver lidando com uma coleção com uma chave (por exemplo, entradas de um banco de dados), uma solução rápida (ou seja, mais rápida que a resposta selecionada) seria

collection.OrderByDescending(c => c.Key).Take(3).OrderBy(c => c.Key);
dav_i
fonte
+1 funciona para mim e é fácil de ler, eu tenho um pequeno número de objetos na minha lista
Fubo
5

Se você não se importa de mergulhar no Rx como parte da mônada, pode usar TakeLast:

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

IEnumerable<int> lastThree = source.AsObservable().TakeLast(3).AsEnumerable();
Richard Szalay
fonte
2
Você não precisa de AsObservable () se fizer referência ao System.Interactive do RX em vez de System.Reactive (veja minha resposta)
piers7
2

Se o uso de uma biblioteca de terceiros for uma opção, o MoreLinq define o TakeLast()que faz exatamente isso.

sm
fonte
2

Tentei combinar eficiência e simplicidade e acabei com isso:

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

Sobre desempenho: Em C #, Queue<T>é implementado usando um buffer circular para que não haja instanciação de objeto feita a cada loop (somente quando a fila está crescendo). Não configurei a capacidade da fila (usando o construtor dedicado) porque alguém pode chamar esse ramal com count = int.MaxValue. Para um desempenho extra, você pode verificar se o código-fonte implementa IList<T>e, se sim, extrair diretamente os últimos valores usando índices de matriz.

tigrou
fonte
1

É um pouco ineficiente obter o último N de uma coleção usando o LINQ, pois todas as soluções acima exigem iteração na coleção. TakeLast(int n)noSystem.Interactive também tem este problema.

Se você tem uma lista, uma coisa mais eficiente a fazer é cortá-la usando o seguinte método

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

com

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

e alguns casos de teste

[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
fonte
1

Eu sei que é tarde demais para responder a essa pergunta. Mas se você estiver trabalhando com uma coleção do tipo IList <> e não se importar com uma ordem da coleção retornada, esse método estará funcionando mais rapidamente. Eu usei a resposta de Mark Byers e fiz algumas alterações. Então agora o método 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];
        }
    }
}

Para o teste, usei o método Mark Byers e a resposta de kbrimington . Este é o teste:

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

E aqui estão os resultados para obter 10 elementos:

insira a descrição da imagem aqui

e para obter 1000001 elementos, os resultados são: insira a descrição da imagem aqui

Sasha
fonte
1

Aqui está a minha solução:

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

O código é um pouco robusto, mas como um componente reutilizável, ele deve ter o melhor desempenho possível na maioria dos cenários e manterá o código que o está usando agradável e conciso. :-)

Meu TakeLastpara nãoIList`1 é baseado no mesmo algoritmo de buffer de anel que o encontrado nas respostas de @Mark Byers e @MackieChan. É interessante como eles são semelhantes - escrevi o meu de forma totalmente independente. Acho que há realmente apenas uma maneira de fazer um buffer de anel corretamente. :-)

Olhando para a resposta de @ kbrimington, uma verificação adicional pode ser adicionada a isso para IQuerable<T>retornar à abordagem que funciona bem com o Entity Framework - assumindo que o que tenho neste momento não funciona.

Jonathan Gilbert
fonte
0

Abaixo do exemplo real, como obter os três últimos elementos de uma coleção (matriz):

// 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();
Aleksey Timkov
fonte
0

Usando este método para obter todo o intervalo sem erro

 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 ;
        }
Ali asghar Fendereski
fonte
0

Implementação pouco diferente com o uso de buffer circular. Os benchmarks mostram que o método é cerca de duas vezes mais rápido que os que usam o Queue (implementação do TakeLast no System.Linq ), mas não sem um custo - ele precisa de um buffer que cresça junto com o número solicitado de elementos, mesmo se você tiver um pequena coleção, você pode obter uma enorme alocação de memória.

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
fonte