Feedback

C# - Alle Indizes in einem Array finden

Veröffentlicht von Fuzzi59 am 10/22/2014

(0 Bewertungen)

Findet alle Stellen in einem Array, an dem der gesuchte Wert vorhanden ist und speichert diese in einem int-Array.

Im Beispiel steht davor noch ArrayFunctions,
dies ist eine von mir erstellte Klasse und sollte dann gelöscht werden wenn man es kopiert hat.(Um Fehler zu vermeiden)

 public static int[] FindAllIndex<R>(R[] T, Predicate<R> value)
        {
            int[] values = new int[T.Count<R>(new Func<R,bool>(value))];
            int startIndex = 0;
            for (int i = 0; i != values.Length; i++)
            {
                values[i] = Array.FindIndex(T, startIndex, value);
                startIndex = values[i] + 1;
            }
            return values;
        }
        ////Beispiel////
        static void Main(string[] args)
        {
            int[] eins = new int[12] { 3, 3, 2, 2, 3, 3, 3, 2, 1, 2, 3, 1 };
            int[] dreien;
            dreien = ArrayFunctions.FindAllIndex<int>(eins, (x => x == 3));
            foreach (int el in dreien)
            { Console.WriteLine(el); }
            Console.ReadLine();
        }
        //Output 0 , 1 , 4, 5 , 6 , 10

Abgelegt unter Array, Index.

11 Kommentare zum Snippet

Koopakiller schrieb am 10/23/2014:

Warum nimmst du 2 Delegaten entgegen? Das macht die Funktion unnötig Fehleranfällig. Beispiel: FindAllIndex<int>(eins, (x => x == 4), (p => p == 3));

Allgemein hätte ich es anders gelöst:

public static IEnumerable<int> FindAllIndexes<T>(IEnumerable<T> source, Predicate<T> predicate)
{
    int i = 0;
    foreach (var item in source)
        if (predicate(item))
            yield return i++;
        else
            i++;
}

Das hat den Vorteil, das es auf jede Art von Liste anwendbar ist und erst ausgewertet wird, wenn das Ergebnis wirklich benötigt wird. Das normale Prozedere von IEnumerable<T> eben.
Weiterhin hat es einen klaren Geschwindigkeitsvorteil, da du die Liste nicht zweimal* durchlaufen musst. (Bei dir wäre es einmal Count und dann nochmal die Schleife.)
Auch das Jonglieren mit den Indizes fällt weg.
Und dann noch 2 Halb-Triviale Dinge: 1. Die Typparemeter fangen nach Konvention immer mit einem großen T an und 2. sollte die Methode entsprechend auch die Mehrzahl von Index als Namen bekommen. (lt. Bing Indexes auf Englisch.)

*Mit .ToArray() kannst du ein IEnumerable wieder in ein Array umwandeln, das durchläuft die Liste auch noch mal. Wenn du jedoch, wie im Beispiel gezeigt, das Ergebnis nur in einer foreach-Schleife durchlaufen willst, kannst du dir einen Durchgang sparen.

Fuzzi59 schrieb am 10/23/2014:

Das mit zwei Delegaten ist unschön und wollte es auch erst nur mit einem versuchen. Da dies nicht funktioniert hat, habe ich es szs. doppelt gemacht. Das IEnumerable würde das Problem lösen, aber um an mein int-Array mit den Indizes zu kommen müsste ich trotzdem zweimal das Array durchlaufen. Es würde sich also nur die Fehleranfälligkeit ändern.

Und das mit Indexe habe ich auch geändert.

Sukram Ab Anvil schrieb am 10/23/2014:

Und warum nicht das Predicate im Count aufrufen und somit die zwei Delegates umgehen?


  public static int[ ] FindAllIndex<T>(this T[ ] @this, Predicate<T> filter )
    {
     var values = new int[@this.Count( el => filter( el ) )];
      int startIndex = 0;
      for( int i = 0; i != values.Length; i++ )
      {
        values[ i ] = Array.FindIndex( @this, startIndex, filter );
        startIndex = values[ i ] + 1;
      }
      
      return values;
    }

Fuzzi59 schrieb am 10/23/2014:

Gute Idee Sukram Ab Anvil. Ich habe sie gleich umgesetzt und es funktioniert genauso wie vorher.

Koopakiller schrieb am 10/23/2014:

@Fuzzi59
In deinem Beispiel oben brauchst du nicht zwingend ein Array - dort würde es das Ganze effektiver machen.
Da fällt mir auch noch ein 2. Geschwindigkeitsnachteil auf, value (irreführende Bezeichnung) wird für jedes Element zweimal aufgerufen. Lass es mal eine aufwendige Prüfung sein...

Fuzzi59 schrieb am 10/23/2014:

@Koopakiller
Ich weiß nicht, ob du mich ganz verstehst:
Das ist eine Funktion für ein Array. Sie soll herausfinden, wo eine 3 ist.
eins[0] == 3
eins[1] == 3, usw.
Die Länge des zurückgegebenen Arrays ist die Anzahl der 3-en.
eins[dreien[0]] == 3 (Für die erste drei in eins)

Koopakiller schrieb am 10/23/2014:

@Fuzzie59
Ich habe dich schon verstanden. Und mir ist auch bewusst das es für die im Beispiel gezeigten Datenmengen noch irrelevant ist.

Es geht mir aber daraum, dass wenn du das Ergebnis in einer foreach Schleife durchläufst, auch ein IEnumerable<T> reicht.
Wende die Funktion mal auf ein paar Tausend Datensätze mit relativ komplizierter Abfrage an und du wirst den Unterschied sehen:

var table = new DataTable("Table1");
table.Columns.Add("ID", typeof(int));
table.Columns.Add("Name", typeof(string));
table.Columns.Add("LastName", typeof(string));
table.Columns.Add("Address", typeof(string));
DataRow[] rows = new DataRow[1000000];
for (int i = 0; i < rows.Length; ++i)
{
    rows[i] = table.Rows.Add(i, "Vorname " + i, "Nachname " + i, "Adresse " + i);
}

//Die Abfrage für die Datensätze:
Predicate< DataRow> predicate = row => row.Field< string>("Address").Length > 9 && (row.Field< string>("Name") + " " + row.Field< string>("LastName")).Length < 23 && row.Field< int>("ID") < 50000;

var sw = new Stopwatch();

Console.WriteLine("Als Ergebnis wird ein Array angefordert:");
sw.Start();
var res1 = FindAllIndex(rows, predicate);
sw.Stop();
Console.WriteLine("Array - Version:          " + sw.ElapsedMilliseconds + "ms");
sw.Reset();

sw.Start();
var res2 = FindAllIndexes(rows, predicate).ToArray();
sw.Stop();
Console.WriteLine("IEnumerable<T> - Version: " + sw.ElapsedMilliseconds + "ms");

Console.WriteLine("\nDas Ergebnis wird in einer Schleife durchlaufen:");
sw.Start();
foreach (var item in FindAllIndex(rows, predicate)) { }
sw.Stop();
Console.WriteLine("Array - Version:          " + sw.ElapsedMilliseconds + "ms");
sw.Reset();

sw.Start();
foreach (var item in FindAllIndexes(rows, predicate)) { }
sw.Stop();
Console.WriteLine("IEnumerable<T> - Version: " + sw.ElapsedMilliseconds + "ms");

Console.ReadKey();

Wenn man ein Array haben will, ist meine Funktion geringfügig schneller als deine (~10ms). Beim durchlaufen in einer Schleife jedoch fast 2mal so schnell.
Auch der Arbeitsspeicher würde bei deiner Version mehr Ansteigen, da du Kopien aller Datensätze erstellst, was IEnumerable<T> verhindert.

Wie gesat, für das von dir gezeigte Beispiel ist es irrelavent, nur für meine 1 Mio Datensätze ist es 1/4 Sekunde unterschied.

PS: Mir fällt in meinem 1. Kommentar gerade auf das alle generischen Parameter entfernt wurden - sehen warscheinlich zu sehr wie HTML Tags aus...

Fuzzi59 schrieb am 10/23/2014:

Mag sich vielleicht blöd anhören, aber ich habe zweimal 50Mio durchsuchen lassen. Gleiches Array mit gleichen Werten.
Aber bei mir ist meine Version immer knapp 200ms schneller gewesen, als deins!?

Koopakiller schrieb am 10/23/2014:

Hast du auch im Release-Modus getestet?
Poste bitte mal deinen Testcode, damit ich mal gucken kann, woran das liegt.

Fuzzi59 schrieb am 10/23/2014:

        static void Main(string[] args)
        {
            Stopwatch my = new Stopwatch();
            Random zufall = new Random();
            int[] eins = new int[50000000];
            long Koopa = 0;
            long ich = 0;
            int anzahlIch = 0;
            int anzahlKoopa = 0;
            int anzahlGleich = 0;
            for (int i = 0; i != eins.Length / 2; i++)
            { eins[i] = 4; }
            for (int i = eins.Length / 2; i != eins.Length; i++)
            {
                eins[i] = 3;
            }
            for (int h = 0; h != 10; h++)
            {
                Console.WriteLine(h);
                my.Reset();
                int[] dreien;
                my.Start();
                dreien = ArrayFunctions.FindAllIndex(eins, (x => x == 3));//Meine Funktion
                my.Stop();
                ich = my.ElapsedMilliseconds;
                Array.Clear(dreien, 0, dreien.Length - 1);
                my.Reset();
                my.Start();
                dreien = FindAllIndexes(eins, (x => x == 3)).ToArray<int>();//Funktion von Koopa
                my.Stop();
                Koopa = my.ElapsedMilliseconds;
                if (Koopa < ich)
                {
                    Console.WriteLine("Koopa " + Convert.ToString(ich - Koopa));
                    anzahlKoopa++;
                }
                else if (ich < Koopa)
                {
                    Console.WriteLine("Ich " + Convert.ToString(-ich + Koopa));
                    anzahlIch++;
                }
                else
                {
                    Console.WriteLine("gleich");
                    anzahlGleich++;
                }

            }
            Console.WriteLine("Ich " + anzahlIch);
            Console.WriteLine("Koopa " + anzahlKoopa);
            Console.WriteLine("Gleich " + anzahlGleich);
            Console.ReadLine();
        }

Das ist jetzt mein Code, aber da tut sich nicht viel von der Zeit.
Mal ist meine Funktion schneller, mal deine.
(liegt zwischen 0ms und 250ms, teilweise 600ms)

Koopakiller schrieb am 10/23/2014:

Dein Code hat hier in 2 Richtungen einen Vorteil:
1.) Du verwendest nur 3 und 4 - dein Code wird bei mir um das 3fache langsamer wenn ich Zufallszahlen verwende - .NET cached hier wahrscheinlich Ergebnisse.
2.) Die bei mir übrigen 10-20ms langsamere Ausführung kommt durch die mehr Delegaten, die in meinem Code eine Rolle spielen.

Jedoch dreht sich das Schnell um wenn du komplexere Abfragen verwendest oder aber das Ergebnis auch auswertest. (Schleifendurchlauf ohne ToArray())

Dein Code ist also manchmal der schnellere, nur wird das in der Praxis selten der Fall sein. Das beginnt schon damit das du selten Arrays bekommst, sondern häufig andere Listen verarbeiten musst. So hätte ich in meinem Beispiel auch direk die Row-Eigenschaft des DataTable verwenden können.

Logge dich ein, um hier zu kommentieren!

Ähnliche Snippets