c#: schneller vergleichalgorythmus gesucht

[Gero (Gast)]

Hallo,
vlt. kann mir der eine oder andere von Euch auf die Sprünge helfen, ich 
finde hier keine optimale Lösung.

In meinem Programm möchte ich (viele) Werte in einem array nach einem 
vergleichen von einer Vorlage indizieren/markieren.

Das Array ist eine Struktur aus zwei Variablen. im ersten Wert ist der 
Vergleichswert, im zweiten Wert kommt ein Index von 1...16656 rein 
(abhängig vom Vergleichswert).

struct MeinWert []
{
     int Vergleichswert;
     int index;
}

Nun habe ich ein weiteres Array mit ähnlichem Aufbau das Wertebereiche 
für den Vergleichswert festlegt:

struct Gruppen []
{
     int MinWert;
     int MaxWert;
     int Index;
}

und da ahnt man dann auch schon was ich vor habe: fällt der obere 
Vergleichswert zwischen Min- und Maxwert des zweiten array, so übernehme 
ich den Index des unteren array in den Index des oberen array. Somit 
habe ich die Werte im oberen array klassifiziert.



Mein code sieht derzeit so aus

for (int i = 0; i < MeinWert.Length; i++)
{
   for (int n = 0; n < Gruppen.Length; n++)
   {
     if ((MeinWert[i].Vergleichswert >= Gruppen[n].MinWert) || (MeinWert[i].Vergleichswert <= Gruppen[n].MaxWert))
     {
        MeinWert.index = Gruppen.index;
        return;
     }
   }
}

so, das ganze funktioniert, aber wirklich erträglich ist das nicht. 
Solange man eine Hand voll Werte hat mag das OK sein, aber MeinWert[] 
und Gruppen[] sind bei mir beides sehr groß, das dauert mehrere Minuten 
bis das Programm den Vergleich durch hat :-(



Sieht jemand eine Lösung das ganze zu beschleunigen? die Werte müssen 
eben irgendwie auf Min-Max geprüft werden und es wäre schön wenn das 
etwas schneller gehen würde. Vlt. gibt es ja auch schon "etwas fertiges" 
in irgendeiner Klassenbibliothek!?

Ich bin um jeden Tipp dankbar, auch wenn ich mir einfach nur bestätigt 
dass es eben doch nicht schneller geht :-(

Danke und Gruß

[Peter II (Gast)]

1. for ist langsamer als foreach
2. warum oder?
   if ((MeinWert[i].Vergleichswert >= Gruppen[n].MinWert) ||
   (MeinWert[i].Vergleichswert <= Gruppen[n].MaxWert))
3. sortierte die werte in Gruppen, damit du rechtzeitg abbrechen kannst
4. schreibe eine funktion um es besser lesbar zu machen

foreach( w in MeinWert ) {
   w.index = GetIndex( w.Vergleichswert  );
}

(foreach braucht eventuell ein class und kein struct)

[Quips (Gast)]

Ohne jetzt zu lange nachzudenken:
Dein Aufwand liegt im Moment bei O(n^2)  (mit n = max(MeinWert.Length, 
Gruppen.Length).

Den könntest du recht einfach auf O(n log n) drücken, indem du die Werte 
zuerst sortierst, dann über die Gruppen iterierst und hier per binärer 
suche die passenden Werte suchst.

Ob's noch schneller geht? ka ;-)

[Informatiker (Gast)]

Hast du mal probiert das mit LINQ zu realisieren?

Vom Gefühl her könnte bei einer großen Menge an Werten durch ein 
Vorsortieren von den Arrays dafür sorgen, dass die Laufzeit gedrückt 
wird

[Gero (Gast)]

Hi,
vielen dank für Eure Hilfe!

Das mit dem "oder" ist ein Fehler meinerseits, es muss natürlich && 
heißen!

ich sortiere jetzt mal die Daten um und versuche mal das mit der binären 
Suche.

Min LINQ kenne ich mich überhaupt nicht aus, ich weiß zwar dass es das 
gibt, habe da aber nicht etwas damit gemacht, "man" müsste sich eben 
einarbeiten...


Danke!

[Karl H. (kbuchegg)]

Gero schrieb:
> Hi,
> vielen dank für Eure Hilfe!
>
> Das mit dem "oder" ist ein Fehler meinerseits, es muss natürlich &&
> heißen!
>
> ich sortiere jetzt mal die Daten um und versuche mal das mit der binären
> Suche.

Wenn man es genau nimmt brauchst du gar nicht binär suchen.

Denn wenn du den korrekten Bereich für den Vergleichswert 5 hast, dann 
ist klar, dass der Bereich für den Vergleichswert 7 nur dahinter oder 
der gleiche sein kann. Auf jeden Fall aber kann der korrekte Bereich für 
7 in der Gruppenliste nicht vor dem Bereich für 5 sein.


D.h. durch die Sortierung, brauchst du hier

int n = 0;

for (int i = 0; i < MeinWert.Length; i++)
{
   for ( ; n < Gruppen.Length; n++)

n nicht jedesmal wieder bei 0 anfangen lassen, sondern kannst mit dem 
für das letzte i gefundene n weitermachen.

   {
     if ((MeinWert[i].Vergleichswert >= Gruppen[n].MinWert) || (MeinWert[i].Vergleichswert <= Gruppen[n].MaxWert))
     {
        MeinWert.index = Gruppen.index;
        return;

(wieso return? :-)
hier breakst du dich aus der inneren for Schleife raus. Und da deine 
Vergleichswerte sortiert sind wird die korrekte Gruppe für das nächste 
MeinWert[i].Vergleichswert in unmittelbarer Nähe hinter dem zuletzt 
gefundenen n sein.


damit hast du eine O(n+m) + 2*(die O deines Sortierverfahrens).

Sortieren ist eben oft eine extrem gute Idee :-)

Aufpassen: wenn sich deine Gruppen 'überlappen' können, in dem Sinne, 
dass es zu ein und demselben Minimum mehrere Maxima gibt, dann musst du 
in der Sortierbedingung das berücksichtigen, dass du ein primäres 
Sortierkriterium und ein Sekundäres hast.

[D. I. (Gast)]

Quips schrieb:
> Ob's noch schneller geht? ka ;-)

Wenns der Speicher hergibt, hashen. Dann haste lineare Laufzeit

[Schorsch (Gast)]

D. I. schrieb:
> Wenns der Speicher hergibt, hashen.

Er soll auf den Dachboden gehen und kiffen?