Jak uzyskać indeks elementu w IEnumerable?

144

Ja to napisałem:

public static class EnumerableExtensions
{
    public static int IndexOf<T>(this IEnumerable<T> obj, T value)
    {
        return obj
            .Select((a, i) => (a.Equals(value)) ? i : -1)
            .Max();
    }

    public static int IndexOf<T>(this IEnumerable<T> obj, T value
           , IEqualityComparer<T> comparer)
    {
        return obj
            .Select((a, i) => (comparer.Equals(a, value)) ? i : -1)
            .Max();
    }
}

Ale nie wiem, czy już istnieje, prawda?

Jader Dias
źródło
4
Problem z Maxpodejściem polega na tym, że a: szuka dalej, a b: zwraca ostatni indeks, gdy są duplikaty (ludzie zwykle oczekują pierwszego indeksu)
Marc Gravell
1
geekswithblogs.net porównuje 4 rozwiązania i ich wydajność. Do ToList()/FindIndex()wykonuje trik najlepiej
nixda

Odpowiedzi:

51

Cały sens wyrzucania rzeczy jako IEnumerable polega na tym, abyś mógł leniwie iterować zawartość. W związku z tym tak naprawdę nie ma pojęcia indeksu. To, co robisz, naprawdę nie ma większego sensu dla IEnumerable. Jeśli potrzebujesz czegoś, co obsługuje dostęp przez indeks, umieść to na rzeczywistej liście lub kolekcji.

Scott Dorman
źródło
8
Obecnie trafiłem na ten wątek, ponieważ implementuję ogólne opakowanie IList <> dla typu IEnumerable <> w celu użycia moich obiektów IEnumerable <> ze składnikami innych firm, które obsługują tylko źródła danych typu IList. Zgadzam się, że próba uzyskania indeksu elementu w obiekcie IEnumerable jest prawdopodobnie w większości przypadków oznaką czegoś złego Zdarza się, że znalezienie takiego indeksu jest lepsze od odtworzenia dużej kolekcji w pamięci tylko w celu znalezienia indeksu pojedynczego elementu, gdy masz już IEnumerable.
jpierson
215
-1 przyczyna: istnieją uzasadnione powody, dla których chcesz pobrać indeks z pliku IEnumerable<>. Nie kupuję całego dogmatu „powinieneś to robić”.
John Alexiou,
78
Zgadzam się z @ ja72; gdybyś nie miał do czynienia z indeksami, IEnumerableto Enumerable.ElementAtby nie istniał. IndexOfjest po prostu odwrotnością - każdy argument przeciwko temu musi mieć równe zastosowanie ElementAt.
Kirk Woll,
7
Jasne, C # pomija koncepcję IIndexableEnumerable. byłby to po prostu odpowiednik koncepcji „losowo dostępnej” w terminologii języka C ++ STL.
v.oddou,
14
rozszerzenia z przeciążeniami, takie jak Select ((x, i) => ...), wydają się sugerować, że te indeksy powinny istnieć
Michael
126

Zakwestionowałbym mądrość, ale może:

source.TakeWhile(x => x != value).Count();

(używając EqualityComparer<T>.Defaultdo emulacji w !=razie potrzeby) - ale musisz oglądać, aby zwrócić -1, jeśli nie zostanie znaleziony ... więc może po prostu zrób to długo

public static int IndexOf<T>(this IEnumerable<T> source, T value)
{
    int index = 0;
    var comparer = EqualityComparer<T>.Default; // or pass in as a parameter
    foreach (T item in source)
    {
        if (comparer.Equals(item, value)) return index;
        index++;
    }
    return -1;
}
Marc Gravell
źródło
8
+1 za „kwestionowanie mądrości”. 9 razy na 10 to prawdopodobnie zły pomysł.
Joel Coehoorn
Rozwiązanie jawnej pętli działa również 2x szybciej (w najgorszym przypadku) niż rozwiązanie Select (). Max ().
Steve Guidi
1
Możesz po prostu liczyć elementy przez lambdę bez TakeWhile - zapisuje jedną pętlę: source.Count (x => x! = Wartość);
Kamarey
10
@Kamarey - nie, to robi coś innego. TakeWhile zatrzymuje się, gdy wystąpi awaria; Count (predykat) zwraca te, które pasują. tzn. jeśli pierwsza była chybieniem, a wszystko inne było prawdą, TakeWhile (pred) .Count () zgłosi 0; Count (pred) zgłosi n-1.
Marc Gravell
1
TakeWhilejest sprytny! Pamiętaj jednak, że zwraca to, Countjeśli element nie istnieje, co jest odchyleniem od standardowego zachowania.
nawfal
27

Wdrożyłbym to w ten sposób:

public static class EnumerableExtensions
{
    public static int IndexOf<T>(this IEnumerable<T> obj, T value)
    {
        return obj.IndexOf(value, null);
    }

    public static int IndexOf<T>(this IEnumerable<T> obj, T value, IEqualityComparer<T> comparer)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
        var found = obj
            .Select((a, i) => new { a, i })
            .FirstOrDefault(x => comparer.Equals(x.a, value));
        return found == null ? -1 : found.i;
    }
}
dahlbyk
źródło
1
To naprawdę bardzo urocze, +1! Obejmuje dodatkowe obiekty, ale powinny one być stosunkowo tanie (GEN0), więc nie jest to duży problem. ==Może wymagać pracy?
Marc Gravell
1
Dodano przeciążenie IEqualityComparer w prawdziwym stylu LINQ. ;)
dahlbyk
1
Myślę, że chcesz powiedzieć ... porównaj. Równa się (xa, wartość) =)
Marc
Ponieważ wyrażenie Select zwraca połączony wynik, który jest następnie przetwarzany, wyobrażam sobie, że jawne użycie typu wartości KeyValuePair pozwoliłoby uniknąć wszelkiego rodzaju alokacji sterty, o ile .NET implikuje typy wartości na stosie i każda maszyna stanu, którą może wygenerować LINQ, używa pola dla wyniku Select'd, które nie jest zadeklarowane jako czysty obiekt (w ten sposób powodując, że wynik KVP zostanie zapakowany). Oczywiście musiałbyś przerobić znaleziony warunek == null (ponieważ znaleziony byłby teraz wartością KVP). Może przy użyciu DefaultIfEmpty () lub KVP<T, int?>(nullable index)
kornman00
1
Niezła implementacja, chociaż jedną rzeczą, którą proponuję dodać, jest sprawdzenie, czy obj implementuje, IList<T>a jeśli tak, odrocz do jego metody IndexOf, na wypadek gdyby miała optymalizację specyficzną dla typu.
Josh
16

Sposób, w jaki obecnie to robię, jest nieco krótszy niż te już sugerowane i, o ile wiem, daje pożądany efekt:

 var index = haystack.ToList().IndexOf(needle);

Jest trochę niezgrabny, ale spełnia swoje zadanie i jest dość zwięzły.

Mark Watts
źródło
6
Chociaż działałoby to w przypadku małych kolekcji, przypuśćmy, że masz milion pozycji w „stogu siana”. Wykonanie ToList () na tym spowoduje iterację wszystkich miliona elementów i dodanie ich do listy. Następnie przeszuka listę, aby znaleźć indeks pasującego elementu. Byłoby to wyjątkowo nieefektywne, podobnie jak możliwość rzucenia wyjątku, jeśli lista stanie się zbyt duża.
esteuart
3
@esteuart Zdecydowanie - musisz wybrać podejście, które pasuje do Twojego przypadku użycia. Wątpię, czy istnieje rozwiązanie uniwersalne, dlatego prawdopodobnie nie ma implementacji w podstawowych bibliotekach.
Mark Watts
8

Najlepszym sposobem na złapanie pozycji jest FindIndexta funkcja jest dostępna tylko dlaList<>

Przykład

int id = listMyObject.FindIndex(x => x.Id == 15); 

Jeśli masz moduł wyliczający lub tablicę, użyj tego sposobu

int id = myEnumerator.ToList().FindIndex(x => x.Id == 15); 

lub

 int id = myArray.ToList().FindIndex(x => x.Id == 15); 
daniele3004
źródło
7

Myślę, że najlepszą opcją jest wdrożenie w ten sposób:

public static int IndexOf<T>(this IEnumerable<T> enumerable, T element, IEqualityComparer<T> comparer = null)
{
    int i = 0;
    comparer = comparer ?? EqualityComparer<T>.Default;
    foreach (var currentElement in enumerable)
    {
        if (comparer.Equals(currentElement, element))
        {
            return i;
        }

        i++;
    }

    return -1;
}

Nie utworzy również anonimowego obiektu

Axente Adrian
źródło
5

Wiem, że trochę późno w grze ... ale to właśnie ostatnio zrobiłem. Jest nieco inny niż twój, ale pozwala programiście dyktować, jaka ma być operacja równości (predykat). Co uważam za bardzo przydatne w przypadku różnych typów, ponieważ mam wtedy ogólny sposób robienia tego niezależnie od typu obiektu i <T>wbudowanego operatora równości.

Ma również bardzo, bardzo małe zużycie pamięci i jest bardzo, bardzo szybki / wydajny ... jeśli o to ci chodzi.

Co gorsza, po prostu dodasz to do listy rozszerzeń.

W każdym razie ... oto jest.

 public static int IndexOf<T>(this IEnumerable<T> source, Func<T, bool> predicate)
 {
     int retval = -1;
     var enumerator = source.GetEnumerator();

     while (enumerator.MoveNext())
     {
         retval += 1;
         if (predicate(enumerator.Current))
         {
             IDisposable disposable = enumerator as System.IDisposable;
             if (disposable != null) disposable.Dispose();
             return retval;
         }
     }
     IDisposable disposable = enumerator as System.IDisposable;
     if (disposable != null) disposable.Dispose();
     return -1;
 }

Mam nadzieję, że to komuś pomoże.

MaxOvrdrv
źródło
1
Może ja czegoś brakuje, ale dlaczego GetEnumeratori MoveNextzamiast po prostu foreach?
Josh Gallagher
1
Krótka odpowiedź? Wydajność. Długa odpowiedź: msdn.microsoft.com/en-us/library/9yb8xew9.aspx
MaxOvrdrv
2
Patrząc na IL, wydaje się, że różnica w wydajności polega na tym, że foreachwywołanie Disposemodułu wyliczającego, jeśli implementuje IDisposable. (Zobacz stackoverflow.com/questions/4982396/ ) Ponieważ kod w tej odpowiedzi nie wie, czy wynik wywołania GetEnumeratorjest jednorazowy, czy nie, powinien zrobić to samo. W tym momencie wciąż nie jestem pewien, czy istnieje korzyść perfekcyjna, chociaż było trochę dodatkowego IL, którego cel nie rzucił się na mnie!
Josh Gallagher
@JoshGallagher Zrobiłem trochę badań jakiś czas temu na temat korzyści płynących z perf między foreach i for (i), a główną zaletą używania for (i) było to, że ReRefsuje obiekt w miejscu, a nie tworzy go ponownie / przekazuje z powrotem ByVal. Zakładam, że to samo dotyczy MoveNext w porównaniu z foreach, ale nie jestem tego pewien. Może oboje używają ByVal ...
MaxOvrdrv
2
Czytając tego bloga ( blogs.msdn.com/b/ericlippert/archive/2010/09/30/… ) może się zdarzyć, że „pętla iteracyjna”, do której się odwołuje, jest foreachpętlą, w którym to przypadku dla konkretnego przypadku Tbędąc typem wartości, może to oznaczać zapisanie operacji box / unbox przy użyciu pętli while. Jednak nie jest to potwierdzone przez IL, który otrzymałem z wersji Twojej odpowiedzi z foreach. Nadal uważam jednak, że warunkowe usunięcie iteratora jest ważne. Czy możesz zmodyfikować odpowiedź, aby to uwzględnić?
Josh Gallagher
5

Kilka lat później, ale to używa Linq, zwraca -1, jeśli nie zostanie znaleziony, nie tworzy dodatkowych obiektów i powinno spowodować zwarcie, gdy zostanie znalezione [w przeciwieństwie do iteracji po całym IEnumerable]:

public static int IndexOf<T>(this IEnumerable<T> list, T item)
{
    return list.Select((x, index) => EqualityComparer<T>.Default.Equals(item, x)
                                     ? index
                                     : -1)
               .FirstOr(x => x != -1, -1);
}

Gdzie „FirstOr” to:

public static T FirstOr<T>(this IEnumerable<T> source, T alternate)
{
    return source.DefaultIfEmpty(alternate)
                 .First();
}

public static T FirstOr<T>(this IEnumerable<T> source, Func<T, bool> predicate, T alternate)
{
    return source.Where(predicate)
                 .FirstOr(alternate);
}
Greg
źródło
Innym sposobem na zrobienie tego może być: public static int IndexOf <T> (ta lista IEnumerable <T>, pozycja T) {int e = list.Select ((x, index) => EqualityComparer <T> .Default.Equals ( pozycja, x)? x + 1: -1) .FirstOrDefault (x => x> 0); return (e == 0)? -1: e - 1); }
Anu Thomas Chandy
„nie tworzy dodatkowych obiektów”. Linq faktycznie będzie tworzył obiekty w tle, więc nie jest to do końca poprawne. Obie source.Wherei source.DefaultIfEmptyna przykład utworzą IEnumerableeach.
Martin Odhelius
1

Natknąłem się na to dzisiaj w poszukiwaniu odpowiedzi i pomyślałem, że dodam swoją wersję do listy (gra słów nie zamierzona). Wykorzystuje zerowy operator warunkowy języka C # 6,0

IEnumerable<Item> collection = GetTheCollection();

var index = collection
.Select((item,idx) => new { Item = item, Index = idx })
//or .FirstOrDefault(_ =>  _.Item.Prop == something)
.FirstOrDefault(_ => _.Item == itemToFind)?.Index ?? -1;

Zrobiłem kilka „wyścigów starych koni” (testy) i dla dużych kolekcji (~ 100 000), najgorszy scenariusz, że przedmiot, który chcesz, jest na końcu, jest to 2x szybsze niż robienie ToList().FindIndex(). Jeśli żądany przedmiot znajduje się pośrodku, jest ~ 4x szybszy.

W przypadku mniejszych kolekcji (~ 10 000) wydaje się, że jest tylko nieznacznie szybszy

Oto, jak to przetestowałem https://gist.github.com/insulind/16310945247fcf13ba186a45734f254e

Dave
źródło
1

Korzystając z odpowiedzi @Marc Gravell, znalazłem sposób na użycie następującej metody:

source.TakeWhile(x => x != value).Count();

aby otrzymać -1, gdy przedmiotu nie można znaleźć:

internal static class Utils
{

    public static int IndexOf<T>(this IEnumerable<T> enumerable, T item) => enumerable.IndexOf(item, EqualityComparer<T>.Default);

    public static int IndexOf<T>(this IEnumerable<T> enumerable, T item, EqualityComparer<T> comparer)
    {
        int index = enumerable.TakeWhile(x => comparer.Equals(x, item)).Count();
        return index == enumerable.Count() ? -1 : index;
    }
}

Myślę, że ten sposób może być zarówno najszybszy, jak i prostszy. Jednak nie testowałem jeszcze wydajności.

Davide Cannizzo
źródło
0

Alternatywą dla znalezienia indeksu po fakcie jest zawinięcie Enumerable, nieco podobne do użycia metody Linq GroupBy ().

public static class IndexedEnumerable
{
    public static IndexedEnumerable<T> ToIndexed<T>(this IEnumerable<T> items)
    {
        return IndexedEnumerable<T>.Create(items);
    }
}

public class IndexedEnumerable<T> : IEnumerable<IndexedEnumerable<T>.IndexedItem>
{
    private readonly IEnumerable<IndexedItem> _items;

    public IndexedEnumerable(IEnumerable<IndexedItem> items)
    {
        _items = items;
    }

    public class IndexedItem
    {
        public IndexedItem(int index, T value)
        {
            Index = index;
            Value = value;
        }

        public T Value { get; private set; }
        public int Index { get; private set; }
    }

    public static IndexedEnumerable<T> Create(IEnumerable<T> items)
    {
        return new IndexedEnumerable<T>(items.Select((item, index) => new IndexedItem(index, item)));
    }

    public IEnumerator<IndexedItem> GetEnumerator()
    {
        return _items.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Co daje przykład użycia:

var items = new[] {1, 2, 3};
var indexedItems = items.ToIndexed();
foreach (var item in indexedItems)
{
    Console.WriteLine("items[{0}] = {1}", item.Index, item.Value);
}
Joshka
źródło
świetny punkt odniesienia. Pomocne jest również dodanie członków IsEven, IsOdd, IsFirst i IsLast.
JJS
0

Może to być naprawdę fajne z rozszerzeniem (działającym jako proxy), na przykład:

collection.SelectWithIndex(); 
// vs. 
collection.Select((item, index) => item);

Który automagicznie przypisze indeksy do kolekcji dostępnej przez to Index właściwości.

Berło:

public interface IIndexable
{
    int Index { get; set; }
}

Rozszerzenie niestandardowe (prawdopodobnie najbardziej przydatne do pracy z EF i DbContext):

public static class EnumerableXtensions
{
    public static IEnumerable<TModel> SelectWithIndex<TModel>(
        this IEnumerable<TModel> collection) where TModel : class, IIndexable
    {
        return collection.Select((item, index) =>
        {
            item.Index = index;
            return item;
        });
    }
}

public class SomeModelDTO : IIndexable
{
    public Guid Id { get; set; }
    public string Name { get; set; }
    public decimal Price { get; set; }

    public int Index { get; set; }
}

// In a method
var items = from a in db.SomeTable
            where a.Id == someValue
            select new SomeModelDTO
            {
                Id = a.Id,
                Name = a.Name,
                Price = a.Price
            };

return items.SelectWithIndex()
            .OrderBy(m => m.Name)
            .Skip(pageStart)
            .Take(pageSize)
            .ToList();
Yom S.
źródło