Entwickler-Ecke

Basistechnologien - Int-Arrays vergleichen / sortieren


StudentWI - Fr 12.12.08 22:54
Titel: Int-Arrays vergleichen / sortieren
Hallo,

ich habe folgende Problemstellung: (bin WI-Student im ersten Semester, habe daher kaum Erfahrung)

Ich soll eine Funktion schreiben, die als Parameter zwei int-Arrays erhält, diese vergleicht und die Werte, die in beiden vorkommen innerhalb eines weiteren int arrays zurück gibt.
Beide Arrays sind unsortiert und enthalten 10 Millionen Elemente.

Ziel bei der Aufgabe ist es so schnell wie möglich zu sein.

Ich habe es so realisiert, dass ich die Arrays zunächst einmal mit Array.Sort sortiere und danach vergleiche.

Der Array.Sort macht die Funktion nun aber sehr langsam:

Array.Sort dauerte 2016 ms
Rest dauerte 123 ms

Rechner: P4 2,8 GHZ

Wäre top, wenn mir hier jemand sagen kann wie das schneller geht.

Ich habe bereits ausgiebig gegoogelt und bin auf intersect und distinct aufmerksam geworden, allerdings klappt das mit dem Einbinden von System.Linq nicht. Anscheinend soll das erst ab 3.0 gehen, stimmt das oder habe ich da etwas falsch vertanden?


Moderiert von user profile iconChristian S.: Topic aus C# - Die Sprache verschoben am Fr 12.12.2008 um 21:58


Horst_H - Fr 12.12.08 23:23

Hallo,

sortiert C# wirklich so langam? Das sind doch keine Strings.
alzaimar würde sicher eine hash-Tabelle nutzen
http://www.aspheute.com/artikel/20000823.htm
und auf doppelte Treffer testen.
Gruß Horst
P.S.: Kein C#-nutzer


Christian S. - Fr 12.12.08 23:42

Hast Du mal versucht, selber einen Quicksort zu implementieren. Oder per Google zu schauen, ob es den im Netz für C# gibt. Würde ich fast mal wetten ;-)


jaenicke - Sa 13.12.08 01:30

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
sortiert C# wirklich so langam? Das sind doch keine Strings.
Das nicht, aber C# sortiert in diesem Fall AFAIK mit Hilfe des IComparable Interfaces, d.h. es wird jedesmal die entsprechende Methode zum Vergleich aufgerufen. Das wird der Grund für die etwas langsame Sortierung sein.

Aus dem Grund wird es sich lohnen dem Vorschlag von user profile iconChristian S. zu folgen, denn du kennst den Typ ja und musst nicht über ein allgemeines Interface gehen.


StudentWI - Sa 13.12.08 12:28
Titel: Qicksort hat wenig Erfolg
user profile iconjaenicke hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
sortiert C# wirklich so langam? Das sind doch keine Strings.
Das nicht, aber C# sortiert in diesem Fall AFAIK mit Hilfe des IComparable Interfaces, d.h. es wird jedesmal die entsprechende Methode zum Vergleich aufgerufen. Das wird der Grund für die etwas langsame Sortierung sein.

Aus dem Grund wird es sich lohnen dem Vorschlag von user profile iconChristian S. zu folgen, denn du kennst den Typ ja und musst nicht über ein allgemeines Interface gehen.


Ich habe nun nach Qicksort gegoogelt und ein paar gefunden:

http://www.osix.net/modules/article/print.php?id=695
http://www.publicjoe.f9.co.uk/csharp/sort05.html

Beide sind allerdings deutlich langsamer als der Array.Sort.

Was ist den mit dem Intersect und Distinct? Ich habe damit schon rumprobiert allerdings kann ich System.Linq nicht einbinden. In einem anderen Forum meinten ein paar das würde bei Framework 2.0 noch nicht gehen? Stimmt das?


JüTho - Sa 13.12.08 12:45
Titel: Re: Qicksort hat wenig Erfolg
user profile iconStudentWI hat folgendes geschrieben Zum zitierten Posting springen:
Was ist den mit dem Intersect und Distinct? Ich habe damit schon rumprobiert allerdings kann ich System.Linq nicht einbinden. In einem anderen Forum meinten ein paar das würde bei Framework 2.0 noch nicht gehen? Stimmt das?

So ist es.

Vielleicht ist List<T> insgesamt schneller, weil es moderner als Array ist. Dann kannst Du so vorgehen:
  1. Erzeuge eine List<int> mit dem Array als Argument des Konstruktors.
  2. List.Sort().
  3. Übernimm mit List.ToArray das Ergebnis.

Wie gesagt: ich weiß nichts über die Geschwindigkeit, aber es wäre ein Dreizeiler und deshalb einen Versuch wert.

Gruß Jürgen


Kha - Sa 13.12.08 13:00
Titel: Re: Int-Arrays vergleichen / sortieren
2 Sekunden finde ich für 10 Mio Einträge nicht soo langsam :gruebel: . Vielleicht kann ja jemand mal einen Delphi-Vergleich beisteuern, wobei TList.Sort natürlich den gleichen minimalen Overhead wie Array.Sort besitzt.
user profile iconStudentWI hat folgendes geschrieben Zum zitierten Posting springen:
Anscheinend soll das erst ab 3.0 gehen, stimmt das oder habe ich da etwas falsch vertanden?
3.5 ist nötig.

user profile iconJüTho hat folgendes geschrieben Zum zitierten Posting springen:
Vielleicht ist List<T> insgesamt schneller, weil es moderner als Array ist.
Benutzt intern Array.Sort ;) .


StudentWI - Sa 13.12.08 14:28
Titel: Re: Int-Arrays vergleichen / sortieren
user profile iconKha hat folgendes geschrieben Zum zitierten Posting springen:
2 Sekunden finde ich für 10 Mio Einträge nicht soo langsam :gruebel: .


Ja, das stimmt.

Bei uns an der FH kann man sich durch Hausaufgaben Zusatzpunkte für die Klausur erarbeiten. Die oben beschriebene Funktion stellt dabei so eine Hausaufgabe dar.
Der Professor stellt seine Lösung der Funktion als externe DLL bereit, sodass man mit der Geschwindigkeitsvergleiche fahren aber nicht den Code einsehen kann.
Wenn man genauso schnell wie er oder gar schneller ist gibt es mehr Punkte.
Er liegt mit seiner Lösung bei ca. 900 ms und meinte es ginge nochmal doppelt so schnell. Daher bin ich mit den 2 Sekunden nicht glücklich.

Gibt es eventuell eine Lösungsmöglichkeit, in der man die Arrays for dem Vergleich überhaupt nicht sortieren muss? Weil das nimmt 90% des Zeitbedarfs der Funktion in Anspruch. Falls nicht werde ich mich wohl geschlagen geben müssen ;-)


jaenicke - Sa 13.12.08 14:32
Titel: Re: Int-Arrays vergleichen / sortieren
user profile iconKha hat folgendes geschrieben Zum zitierten Posting springen:
2 Sekunden finde ich für 10 Mio Einträge nicht soo langsam :gruebel: .
Deshalb habe ich ja auch geschrieben "etwas langsamere Sortierung". Aber ich habe das mal ausprobiert, und die Ergebnisse verwirren mich. Ergebnis auf einem etwas älteren PC:
C#, Array.Sort: 3400 ms
C#, Link 2 [http://www.publicjoe.f9.co.uk/csharp/sort05.html]: 4100 ms
C++, Internetquelle [http://www.stefan-baur.de/cs.algo.quicksort.html]: 3700 ms
Delphi, Internetquelle [http://delphi.about.com/od/objectpascalide/a/quicksort.htm]: 1816 ms

Dass Delphi schneller ist als C# hätte ich vermutet, aber C++? Vielleicht habe ich da auch einen Fehler bei der Implementierung gemacht. Ich werde später das noch einmal richtig sauber schreiben.

Nach dem Ergebnis glaube ich nicht, dass man das Sortieren so sehr beschleunigen kann. Ich vermute eher, dass der Vergleichsalgorithmus einfach besser ist.
Wie du gerade geschrieben hast wie ich im Threadupdate sehe vermutlich ohne Sortierung.

Vielleicht wie oben user profile iconHorst_H meinte per Hash. Mal schauen, irgendwann nachher werd ich mal überlegen, ob sowas schneller sein könnte.


Kha - Sa 13.12.08 17:11
Titel: Re: Int-Arrays vergleichen / sortieren
user profile iconStudentWI hat folgendes geschrieben Zum zitierten Posting springen:
Gibt es eventuell eine Lösungsmöglichkeit, in der man die Arrays for dem Vergleich überhaupt nicht sortieren muss?
Intersect benutzt ein Hash-Set, damit komme ich aber mit Zufallszahlen aus dem gesamten Int32-Bereich auch nur auf 3 Sekunden.
Wichtig wären Informationen über den Input. In welchem Intervall liegen die Zahlen? Wie sind sie verteilt?


StudentWI - Sa 13.12.08 19:05
Titel: Re: Int-Arrays vergleichen / sortieren
user profile iconKha hat folgendes geschrieben Zum zitierten Posting springen:
Wichtig wären Informationen über den Input. In welchem Intervall liegen die Zahlen? Wie sind sie verteilt?


Anbei die vom Professor vorgegebene Methode Main zur Erzeugung und der Arrays. Durch Main wird die Methode Test(hier nicht aufgeführt), in der der Vergleich aufgerufen und die Zeitmessung erfolgen soll, mehrmals mit unterschiedlich Arraygrößen aufgerufen. Es beginnt zuerst mit zwei Arrays der Größe 100, dann 1000, 10000 .... bis 10 Mio. Der Professor möchte hier wohl zeigen, dass mit zunehmender Arraygröße einen gut programmierten vergleich immer wichtiger wird.


C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
    public static void Main(string[] args) {
        
        // Anzahl der Versuche ist über 
        // die Kommandozeile einstellbar
        //int Grenze = 1000000;
        int Grenze = 10000000;
        if (args.Length > 0)
        {
            
            try  {
                int nn = Convert.ToInt32(args[0]);
                Grenze = nn;
            }
            catch(Exception){
                Console.WriteLine("Falscher Parameter {0}",args[0]);
            }
        }
        ++Grenze;
        
        Log = new StreamWriter("Log.txt");
        Log.WriteLine("Testlauf max. Anzahl: "+Grenze);
        
        for(int anz = 100; anz < Grenze; anz *= 10)
        {
            Console.WriteLine("Aktuelle Elementzahl {0}",anz);

            // Feld aufbauen
            int[] ll1 = new int[anz];
            int[] ll2 = new int[anz];

            // Alle verschieden
            for(int no=0; no < anz;++no)
                ll1[no]=0;
            
            for(int no=0; no < anz;++no)
                ll2[no]=1;

            // ein paar Duplikate einbauen
            ll2[1] = ll2[anz-2] = 3;
            ll1[1] = ll1[anz-2] = 3;
            ll2[anz-3] = 4;
            ll1[2] = ll1[anz-4] = 4;
        
            int anzMal0Punkt1 = anz/10;
            for(int no=0; no < anzMal0Punkt1 -3;++no)
            {
                int wert = no/100+123;
                ll2[5*no+2] = ll1[3*no+2] = wert;
                ll2[2*no+2] = ll1[4*no+2] = wert;
            }


            // Testen
            test(ll1,ll2);
        }
        Log.Close();
    }


Moderiert von user profile iconChristian S.: Quote- durch C#-Tags ersetzt


jaenicke - Sa 13.12.08 19:29

Was auffällt ist, dass einerseits extrem viele Nullen bzw. Einsen vorkommen und dass andererseits der Zahlenbereich extrem klein im Vergleich zu der Anzahl der Zahlen ist.
Eine eigentümliche Art der Erzeugung der Zahlen, einen Sinn sehe ich nicht dahinter. :nixweiss:

Hier könnte man ein Array aus int nehmen und einfach die Anzahlen der einzelnen Zahlen speichern, das bei beiden machen und danach einfach das Minimum der beiden Arrays für jede Zahl als gemeinsame Anzahl nehmen.
Grund: Die höchste Zahl ist kleiner als 1000, das Array wäre also extrem klein im Vergleich.

Ich glaube ich sollte mehr als die Idee nicht weiter ausführen, schließlich ist es deine Aufgabe ;-). Ich vermute aber, dass das bei solchen komischen Zahlen deutlich schneller ist als sortieren oder Hashes.


ffprogramming - Do 08.01.09 19:58
Titel: quick sort
ich denke quick sort wäre wohl gut
aber bei mir is c# auf dem pc beim sortieren schneller


jaenicke - Do 08.01.09 20:26
Titel: Re: quick sort
user profile iconffprogramming hat folgendes geschrieben Zum zitierten Posting springen:
ich denke quick sort wäre wohl gut
Grundsätzlich ja, bei dieser Zahlenverteilung geht es anders wie gesagt schneller.

user profile iconffprogramming hat folgendes geschrieben Zum zitierten Posting springen:
aber bei mir is c# auf dem pc beim sortieren schneller
Im Vergleich zu? ;-)

// EDIT:
Und ist das dein Hobby alte und schon beantwortete Threads wieder auszubuddeln? :gruebel:


JüTho - Do 08.01.09 20:30

Nicht wundern, Sebastian: Ich glaube, er wollte nur seinen Beitragszähler hochsetzen. Siehe Prüfen, ob die TextBox leer ist [http://www.c-sharp-forum.de/viewtopic.php?p=543499#543499]. Jürgen

/Edit: Ah ja, Du hast es inzwischen auch schon festgestellt.