Autor Beitrag
StudentWI
Hält's aus hier
Beiträge: 4



BeitragVerfasst: Fr 12.12.08 22:54 
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


Zuletzt bearbeitet von StudentWI am Fr 12.12.08 23:03, insgesamt 1-mal bearbeitet
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
www.aspheute.com/artikel/20000823.htm
und auf doppelte Treffer testen.
Gruß Horst
P.S.: Kein C#-nutzer
Christian S.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: 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 ;-)

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19339
Erhaltene Danke: 1752

W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: 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 Threadstarter
Hält's aus hier
Beiträge: 4



BeitragVerfasst: 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:

www.osix.net/modules...cle/print.php?id=695
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2021
Erhaltene Danke: 6

Win XP Prof
C# 2.0 (#D für NET 2.0, dazu Firebird); früher Delphi 5 und Delphi 2005 Pro
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 13.12.08 13:00 
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 Threadstarter
Hält's aus hier
Beiträge: 4



BeitragVerfasst: Sa 13.12.08 14:28 
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 ;-)


Zuletzt bearbeitet von StudentWI am Sa 13.12.08 14:36, insgesamt 1-mal bearbeitet
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19339
Erhaltene Danke: 1752

W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Sa 13.12.08 14:32 
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: 4100 ms
C++, Internetquelle: 3700 ms
Delphi, Internetquelle: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 13.12.08 17:11 
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 Threadstarter
Hält's aus hier
Beiträge: 4



BeitragVerfasst: Sa 13.12.08 19:05 
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.

ausblenden volle Höhe 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19339
Erhaltene Danke: 1752

W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 44

Win XP
C# Java C PHP
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19339
Erhaltene Danke: 1752

W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2021
Erhaltene Danke: 6

Win XP Prof
C# 2.0 (#D für NET 2.0, dazu Firebird); früher Delphi 5 und Delphi 2005 Pro
BeitragVerfasst: 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. Jürgen

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