Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
19.11.2006, 23:55 Uhr
~DerMond
Gast

Hallo,
ich habe ein array mit prioritäten und will 2 dinge machen:
1) Ich will die höchste priorität extrahieren
2) Alle anderen elemente um 1 inkrementieren

ich habe folgendes am laufen und glaube es geht noch schneller zu realisieren:

C++:

int max = 0;

     for(int idx = 1; idx < m_dimension; idx++)
     {
         if(m_priority[idx] > m_priority[max])
         {
             m_priority[max] += 1;
             max = idx;
         }
         else
             m_priority[idx] += 1;
     }
     m_priority[max] = 0;

wären z.B Pointer schneller?
Danke euch für eure ratschläge...

Profil || Private Message || Suche

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

001
20.11.2006, 08:10 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

da dürfte nicht mehr viel zu holen sein. Ich glaube wenn man geschwindigkeit holen will müsste man eher an dem Algo selbst arbeiten. Was genau willst du denn machen... Eventuell lässt sich das ja "geschickter" abbilden...
--
...fleißig wie zwei Weißbrote

Profil || Private Message || Suche

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

002
20.11.2006, 10:47 Uhr
Th

@Der Mond: So ganz leuchtet mir dein Algo nicht ein, warum erhöhst du noch jeweils den Wert beim aktuell maximalen Index, d.h. m_priority[max] += 1;
Dadurch gehen dann doch die ganzen Prioritäten durcheinander?

Wenn du eine nach Prioritäten sortierte Liste (bzw. Array) haben willst, dann schau dir mal die Klasse std::priority_queue an (sofern du C++ programmierst).

Profil || Private Message || Suche

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

003
20.11.2006, 14:28 Uhr
~Robert
Gast

C++:

int array[size];

int max = 0;
int *max_pointer;
int *begin = array;
int *end   = array + size;

while(begin != end)
{
   if(*begin > max)
      max = *begin, max_pointer = begin;
   ++begin;
}

begin = array;
end = max_pointer;

while(begin != end)  --(*(begin++));

begin = max_pointer + 1;
end = array + size;

while(begin != end) --(*(begin++));

Wäre noch zu überlegen, ob der Maximalwert öffters vor kommen kann.

Robert

Profil || Private Message || Suche

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

004
20.11.2006, 21:03 Uhr
~derMond
Gast

aha....ja der maximalwert kann mehrfach vorkommen sogar sehr oft tritt dieser fall ein...

Profil || Private Message || Suche

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

005
20.11.2006, 22:23 Uhr
~Robert
Gast

Hallo

Dann halt folgend:

C++:

int max = GetMaxFromArray(array);

int *begin = array;
int *end   = array + size;

while(begin != end)
{
   if(*begin != max)
      *begin -= 1;
   ++begin;
}

Anders wirst es wahrscheinlich nicht machen können.
Außer du hast die Möglichkeit beim Einlesen oder so schon das Maximum heraus zu bekommen.

Robert

Profil || Private Message || Suche

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

006
21.11.2006, 07:41 Uhr
~Robert
Gast

Hallo

Könnte man noch ausprobieren, ob man mit loop-unrolling noch Zeit raus holen kann.
Müsste dann ungefähr so aussehen:

C++:

int max = GetMaxFromArray(array);

int *begin = array;
int *end   = array + (size & (~(0x3)));

while(begin != end)
{
   *begin -= *begin != max ? 1 : 0;
   *(begin + 1) -= *(begin + 1) != max ? 1 : 0;
   *(begin + 2) -= *(begin + 2) != max ? 1 : 0;
   *(begin + 3) -= *(begin + 3) != max ? 1 : 0;
   begin += 4;
}

begin = end;
end = begin + (size & 0x3);
while(begin != end)
{
   if(*begin != max)
      *begin -= 1;
}

Ist ungetestet. Ob es was bringt, k.A.
Am besten nachmessen.

Robert

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: