Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
18.06.2008, 12:07 Uhr
PaRu

ich habe ein programm, bei dem es sehr auf die geschwindigkeit ankommt. daher meine frage, welche implementierung schneller ist.

mein problem:
ich muss immer wieder eine fft ausführen, bei der sich nur ein eingabewert verändert. es kommt ein neuer wert hinzu und der letzte wert wird gelöscht.

1. lösungsansatz:
ich benutze eine ring-array in dem ich den zeiger mit der modulo operation wandern lasse.
+ der array für die eingabewerte muss nicht umkopiert werden
- die fft muss auch mittels modulo auf den array zugreifen und jede modulo operation kostet rechenzeit.

2. lösungsanstz:
ich kopiere den array für die eingabewerte um.
+ keine rechenintensiven modulo operationen
- umkopieren kostet rechenzeit

kann die modulo operation evtl. schneller durchgeführt werden, da der array für die eingabewerte eine länge von 2^n hat? evtl. gibt es da eine möglichkeit etwas mit shifts zu zaubern so dass es doch nicht so rechenintensiv ist?
--
Gruß Patrick

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
18.06.2008, 14:56 Uhr
0xdeadbeef
Gott
(Operator)

Je nachdem, wie groß das Array ist, und wie oft es sich ändert, könntest du u.U. das Array zweimal direkt hintereinander im Speicher aufbewahren. Dann kannst du beim Funktionsaufruf den Anfang per Modulo bestimmen, während die Funktion sich nicht darum kümmern muss.

Welcher Ansatz im Endeffekt am schnellsten ist, lässt sich ohne genaue Kenntnis der betreffenden Funktionen nicht sagen, das müsstest du ggf. durch einen Profiler jagen. Das wäre sowieso sinnvoll, um herauszufinden, ob hier überhaupt ein Flaschenhals vorliegt.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
18.06.2008, 16:07 Uhr
PaRu

der array hat ca. 512 werte (plus minus eine 2er potenz). die fft wird permanent aufgerufen für verschiedene arrays, bei denen immer nur ein element ersetzt wird. die fft wird nur auf neue befüllte arrays angewendet und nie ein zweitesmal für ein array im selben zustand.

was ist ein profiler?
--
Gruß Patrick

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
18.06.2008, 16:14 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

Ein profiler ist ein programm der dir sagt was an deinem Code die meiste Rechenzeit, oder andere Parameter (Speicher, usw) verbraucht, da kannste eben dann die stellen, die dir zeit kosten, herausfinden.
--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
18.06.2008, 16:35 Uhr
PaRu

gbit es da eine gute opensource solution, die auch benutzbar ist? ich benutze mingw.

ich bin aber dennoch für weitere meinungen zu meinem problem offen.
--
Gruß Patrick

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
18.06.2008, 19:45 Uhr
0xdeadbeef
Gott
(Operator)

Bei mingw sollte gprof schon dabei sein. Damit gprof die Executable profilen kann, musst du beim Kompilieren -pg in den Compileroptionen mit angeben.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
18.06.2008, 21:52 Uhr
ao

(Operator)

Zitat von PaRu:

kann die modulo operation evtl. schneller durchgeführt werden, da der array für die eingabewerte eine länge von 2^n hat? evtl. gibt es da eine möglichkeit etwas mit shifts zu zaubern so dass es doch nicht so rechenintensiv ist?

Wenn ich mich nicht irre, ist "x modulo 2^n" dasselbe wie "x & (2^n - 1)", das gilt aber nur für Division durch eine Zweierpotenz.

Ansonsten würde ich deadbeefs Vorschlag unterstützen, vorausgesetzt, das Profiling ergibt, dass die Zeit tatsächlich an dieser Stelle verlorengeht:

Zitat:

könntest du u.U. das Array zweimal direkt hintereinander im Speicher aufbewahren.

Dieser Post wurde am 18.06.2008 um 21:52 Uhr von ao editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: