| Autor |
Beitrag |
StudentWI
Hält's aus hier
Beiträge: 4
|
Verfasst: 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 Christian 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
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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.
      
Beiträge: 20451
Erhaltene Danke: 2264
Win 10
C# (VS 2019)
|
Verfasst: 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
      
Beiträge: 19339
Erhaltene Danke: 1752
W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Sa 13.12.08 01:30
Horst_H hat folgendes geschrieben : | | 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 Christian S. zu folgen, denn du kennst den Typ ja und musst nicht über ein allgemeines Interface gehen.
|
|
StudentWI 
Hält's aus hier
Beiträge: 4
|
Verfasst: Sa 13.12.08 12:28
Titel: Qicksort hat wenig Erfolg
|
|
JüTho
      
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
|
Verfasst: Sa 13.12.08 12:45
Titel: Re: Qicksort hat wenig Erfolg
StudentWI hat folgendes geschrieben : | | 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:
- Erzeuge eine List<int> mit dem Array als Argument des Konstruktors.
- List.Sort().
- Ü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
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Sa 13.12.08 13:00
2 Sekunden finde ich für 10 Mio Einträge nicht soo langsam  . Vielleicht kann ja jemand mal einen Delphi-Vergleich beisteuern, wobei TList.Sort natürlich den gleichen minimalen Overhead wie Array.Sort besitzt.
StudentWI hat folgendes geschrieben : | | Anscheinend soll das erst ab 3.0 gehen, stimmt das oder habe ich da etwas falsch vertanden? |
3.5 ist nötig.
JüTho hat folgendes geschrieben : | | Vielleicht ist List<T> insgesamt schneller, weil es moderner als Array ist. |
Benutzt intern Array.Sort  .
_________________ >λ=
|
|
StudentWI 
Hält's aus hier
Beiträge: 4
|
Verfasst: Sa 13.12.08 14:28
Kha hat folgendes geschrieben : | 2 Sekunden finde ich für 10 Mio Einträge nicht soo langsam . |
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
      
Beiträge: 19339
Erhaltene Danke: 1752
W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Sa 13.12.08 14:32
Kha hat folgendes geschrieben : | 2 Sekunden finde ich für 10 Mio Einträge nicht soo langsam . |
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 Horst_H meinte per Hash. Mal schauen, irgendwann nachher werd ich mal überlegen, ob sowas schneller sein könnte.
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Sa 13.12.08 17:11
StudentWI hat folgendes geschrieben : | | 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 
Hält's aus hier
Beiträge: 4
|
Verfasst: Sa 13.12.08 19:05
|
|
jaenicke
      
Beiträge: 19339
Erhaltene Danke: 1752
W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: 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.
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
      
Beiträge: 44
Win XP
C# Java C PHP
|
Verfasst: 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
      
Beiträge: 19339
Erhaltene Danke: 1752
W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Do 08.01.09 20:26
Titel: Re: quick sort
ffprogramming hat folgendes geschrieben : | | ich denke quick sort wäre wohl gut |
Grundsätzlich ja, bei dieser Zahlenverteilung geht es anders wie gesagt schneller.
ffprogramming hat folgendes geschrieben : | | 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? 
|
|
JüTho
      
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
|
Verfasst: 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.
|
|