Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

C++ Code Beschleunigung

  • 1
  • 2

Werbeanzeige

Planck

Frischling

  • »Planck« ist der Autor dieses Themas

Beiträge: 6

  • Private Nachricht senden

1

13.08.2012, 01:37

C++ Code Beschleunigung

Hallo,
ich bin neu hier und komme auch schon mit einem kleinen problem.
ich haber ein programm geschrieben und das ausführen dauert ewig, beim profilen hab ich festgestellt das die folgende funktion einen großteil der rechenzeit in anspruch nimmt (die if abfrage)

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void arraysort(int spalte)
{
    int i,j,kleinst; double buffer;
    
    for(i=0;i<gesamtzahl;i++)
    {
        kleinst=i;
        for(j=i;j<gesamtzahl;j++)
        {
            if(input[j][spalte]<input[kleinst][spalte])
                            kleinst=j;
        }
        
        for(j=0;j<=3;j++)
        {
            buffer=input[i][j];
            input[i][j]=input[kleinst][j];
            input[kleinst][j]=buffer;
        }
    }
}


wie könnte ich den code den beschleunigen oder iwie verbessern? wäre für hilfen und tipps sehr dankbar

viele grüße
planck

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Planck« (14.08.2012, 09:52)

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

2

13.08.2012, 01:57

1. Hast du auch wirklich die Release Version mit einem Profiler analysiert?
2. Willst du nicht eine etwas effizientere Sortiermethode benutzen anstatt Bubblesort bevor du dich an Low-Level Aufgaben machst?
3. Was man hier effektiv machen könnte wäre den generierten Code anschauen und schauen was genau so lange geht. Offensichtlich könnte man hier einen Array Zugriff mit einfachen inkrement auf Zeiger realisieren. Aber ich bezweifle, dass das hier wirklich nötig ist. Was hast du sonst für eine Anwendung, wo so etwas wirklich eine Rolle spielt?
http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

3

13.08.2012, 08:14

Es gibt fertige Sortieralgorithmen für STL Container, die sehr viel schneller sind. Deiner hat quadratische Laufzeit (die erste innere Schleife wird für jedes Element für jedes Element ausgeführt, also gesamtzahl*gesamtzahl) und das ist bei genügend großem gesamtzahl immer schlecht.
Infos über effiziente Sortieralgorithmen gibt es im Netz genug, der Klassiker ist wohl QuickSort.
Lieber dumm fragen, als dumm bleiben!

Planck

Frischling

  • »Planck« ist der Autor dieses Themas

Beiträge: 6

  • Private Nachricht senden

4

13.08.2012, 08:58

Oh wow das ging ja schnell danke! und sogar ohne "google ist dein freund" attitüde. Danke

zu:

1. Hast du auch wirklich die Release Version mit einem Profiler analysiert?
ja hab nen ide internen profiler verwendet der sampled alle 40µs und gibt aus in welcher prozedur er sich befindet und da kam eben heraus das 35% der zeit in dieser einen routine verschwendet wird.

2. Willst du nicht eine etwas effizientere Sortiermethode benutzen anstatt Bubblesort bevor du dich an Low-Level Aufgaben machst?
ja welche methoden gibt es den da und welche wären zu empfehlen (sry bin neu in sachen speed optimierung hatte bisher nie was damit zu tun)

3. Was man hier effektiv machen könnte wäre den generierten Code anschauen und schauen was genau so lange geht. Offensichtlich könnte man hier einen Array Zugriff mit einfachen inkrement auf Zeiger realisieren. Aber ich bezweifle, dass das hier wirklich nötig ist. Was hast du sonst für eine Anwendung, wo so etwas wirklich eine Rolle spielt?

das programm generiert mir daten aus nem riesen datensatz die ganze prozedur dauert über 6 stunden und wie vorhin schon erwähnt werden 35% bei dem sortieren verschwendet daher war das mein erster ansatzpunkt.

Zu jonathan:
Eine kurze google suche hat mir gesagt das das quicksort eine nicht stabiler sortieralgorythmus ist.. ist das oft der fall? es wäre ärgerlich nach 6 stunden rechenzeit festzustellen das das ergebnis nicht konvergiert.. hast du noch weitere tips für sortieralgorythmen?

Vielen dank leute!

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

5

13.08.2012, 09:06

Es ist klar, dass die Zeit im "if" verbracht wird, weil dort der Speicherzugriff stattfindet.

"Nicht stabil" bedeutet nicht, dass das Ergebnis falsch sein könnte.
Es bedeutet nur, dass die Reihenfolge von Elementen mit gleichem Wert nicht unbedingt erhalten bleibt. Bei Zahlen ist das aber völlig egal, weil eine Zahl keine andere Information hat als ihren Wert ;)

Heapsort oder Mergesort sind gut.
David Scherfgens Website | Konzentrationstest Polizei

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

6

13.08.2012, 09:08

Du weißt, was "stabiler Sortieralgorithmus" bedeutet? Es heißt *nicht* dass die Sortierung nicht fertig wird. Bei 6 Stunden Rechenzeit wirst Du mit QuickSort vermutlich mehrere Stunden Rechenzeit einsparen, sofern Du nicht nur 100 Datensätze immer wieder sortierst, sondern große Datenmengen.

Edit: Ninja David war schneller.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

7

13.08.2012, 09:11

PS: Wenn der Datensatz so riesig ist, könnte sich auch paralleles Sortieren lohnen!
David Scherfgens Website | Konzentrationstest Polizei

Planck

Frischling

  • »Planck« ist der Autor dieses Themas

Beiträge: 6

  • Private Nachricht senden

8

13.08.2012, 09:23

Ah ok das hört sich schonmal gut an ich werd gleich mal nach den schlagwörtern suchen.
thx soweit :)

bezüglich paralellisieren hab ich mich mal etwas eingelesen aber irgendwie hab ich da noch zu große berührungsängste :D
edit: es sind bis bis zu 50k datensätze

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Planck« (13.08.2012, 09:38)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

9

13.08.2012, 10:02

50.000 ist ein Klecks.
Du kannst dein ganzes Problem mit einem einzigen Aufruf von std::sort() lösen, und es sollte deutlich unter 1 Sekunde dauern.
(wahrscheinlich wird es so schnell gehen, dass du den Aufruf gar nicht merkst)
David Scherfgens Website | Konzentrationstest Polizei

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

10

13.08.2012, 15:09

Zitat von »David Scherfgen«

50.000 ist ein Klecks.
Du kannst dein ganzes Problem mit einem einzigen Aufruf von std::sort() lösen, und es sollte deutlich unter 1 Sekunde dauern.
(wahrscheinlich wird es so schnell gehen, dass du den Aufruf gar nicht merkst)

Kommt wohl auf das Sortierkriterium an, aber ja, üblicherweise ist das keine Menge, die Probleme macht.

@Planck
Irgendwie wie habe ich das Gefühl, dass du etwas mehr oder weniger seriöses umsetzen musst, aber anscheinend fehlen dir einige Grundlagen.
Wenn es dir wirklich nur darum geht zu lernen, dann solltest du dich ein wenig in die Materie einarbeiten (sortieren ist etwas, was man so ziemlich als erstes lernt in Algorithmen Vorlesungen). Weitere Stichwörter bzgl. dem Thema sind: Mergesort (für paralleles sortieren z.B.), Heapsort, Laufzeit (O-Notation) derer, Introsort, Selectionsort, Insertionsort etc. Wenn du dich nach dem Zeugs erkundigst solltest du, wenn du weitere Keywords auch weitersuchst relativ viel über die Materie in Erfahrung bringen können.

Wenn es nicht nur für den Lerneffekt ist, dann empfehle ich dir auch einfach std::sort zu benutzen. Das ist schnell, getestet und einfach zu benutzen. Wenn das immer noch zu langsam wäre, dann könntest du dich mal um eine eigene Implementierung bemühen (oder eine Library suchen, die das kann; gibt ganz bestimmt eine, die deinen Wünschen entspricht).
http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Werbeanzeige

  • 1
  • 2

Ähnliche Themen