Optimierung?

ness

Ich glaube nicht. 1. dürfte die Möglichkeit, von hinten zu durchsuchen, ganz ordentlich sein. 2. leidet die Leesbarkeit nicht so (OK, bis auf den Kommentar ist Volkards verständlich, aber ein find_last(str.begin(),str.end(),'.') ist wohl deutlicher). Nun gibt es nur ein Problem: Wenn man einen string zurückgibt, wird dieser kopiert, das dauert. So wie ich die Funktion interptretiere, sollte das so sein, aber in der Originalfn wird auch nicht kopiert. Eigentlich wird ein Zeiger auf den letzten Punkt zurückgegeben, der sich dann als string benutzen lässt, aber kein eigenständiger ist. Wenn man also gleich einen iterator zurückgibt, der vmtl. sowieso ein poiner ist, spart man die Kopierkosten. Geht man noch davon aus, dass die stlklassen vmtl. hoch optimiert sind, dürfte es wohl schneller gehen...

eventuell ist das schneller, aber nicht viel

// gibt 0 zurück wenn kein punkt gefunden wurde
char* GetFilenameExtension(char* pcFilename) 
{ 
    char *lastdot = 0;

    while(*pcFilename) 
        if(*pcFilename++ == '.')
            lastdot = pcFilename;

    return lastdot; 
}

volkard

Abkürzer schrieb:

eventuell ist das schneller, aber nicht viel

// gibt 0 zurück wenn kein punkt gefunden wurde
char* GetFilenameExtension(char* pcFilename) 
{ 
    char *lastdot = 0;

    while(*pcFilename) 
        if(*pcFilename++ == '.')
            lastdot = pcFilename;

    return lastdot; 
}

vergleich die funktion doch mal mit meiner von 21 Mai 2005 23:45.

volkard

Meep Meep schrieb:

folgende variante, falls kein std::string oder aehnliches vorhanden ist, sollte um einiges schneller sein:
...

ich kann sie leider nicht nachvollziehen.

const char* GetExtension(const char *t_filename)
   {
      const char *p1 = t_filename - 1;
      const char *p2 = 0;
      unsigned int d = 0;
      unsigned int temp = 0;
      unsigned int t1 = 0;
      unsigned int t2 = 0;

      do
      {
         ++p1;
         //nur, wenn der string well-aligned ist
         if((((unsigned int) p1) & (sizeof(int) - 1)) == 0)
         {
            do
            {
               //dann hüpfe in viererschritten durch
               d = *((unsigned int*) p1);
               //zieh bei von jedem byte '.' ab
               //und kümmere dich um keine überträge! warum?
               temp = *((unsigned int*) p1) - 0x2E2E2E2E;
               //schaut, on ein byte drin gleich 0x00 war.
               t1 = ((d - 0x01010101) & ~d & 0x80808080);
               //dito
               t2 = ((temp - 0x01010101) & ~temp & 0x80808080);
               //merkt sich, wo '.' war oder bis zu 3 davor
               if(t2)
                  p2 = p1;
               p1 += sizeof(int);
            }  while(!t1);
            p1 -= sizeof(int);
         }
      }  while(*p1 != 0);
      //wenn sich nix gemerkt wurde, also kein '.' vorkam, bitten 
      //wir zum absturz durch string-ende-überschreitung?
      if(p2)
      {
         while(*p2 != '.') *(++p2);
      }
      //ansonsten geben wir die korrekte position zurück oder bis zu 3 davor
      return (!p2 && p2 < p1) ? p2 : 0;
   }

nee, ich kann deinem code nicht folgen, aber befürchte, er hat grippe.

volkard

ness schrieb:

Ich glaube nicht. 1. dürfte die Möglichkeit, von hinten zu durchsuchen, ganz ordentlich sein.

jo. insbesondere bei den modernen namen wie

C:\Dokumente und Einstellungen\All Users\Anwendungsdaten\Microsoft\User Account Pictures\Default Pictures\Schmetterling.bmp

oder

/usr/portage/sys-kernel/openmosix-sources/files/openmosix-sources.CAN-2004-0841-fix_ldisc_switch.patch

Wenn man also gleich einen iterator zurückgibt, der vmtl. sowieso ein poiner ist, spart man die Kopierkosten. Geht man noch davon aus, dass die stlklassen vmtl. hoch optimiert sind

die sind zwar hoch optimiert, aber gar nicht so performant, wie man meinen mag. sie sind sehr allgemein gehalten, was der performance entgegenwirkt.

, dürfte es wohl schneller gehen...

dürfte was schneller sein? rückwärts suchen? klar. nen string kopieren? klar nicht.

Konfusius

um einen string von hinten zu durchsuchen, muß man erst einmal an das stringende kommen. und dazu muß man den string auch vollständig durchlaufen. ich denke, schneller als der ursprüngliche code gehts nicht.

die volkard-methode klappt leider nicht auf allen platformen. bei manchen rechnern muß ein langwort an einer graden addresse beginnen. außerdem glaube ich nicht, daß diese methode bei modernen prozessoren mit caching etc wirklich schneller ist. ich denke, der aufwand steht da in keinem verhältnis zum nutzen.

mit c++-strings würde ich es so machen:

string
GetFileNameExtension (const string &fname)
{
  int pos=fname.find_last_of('.');

  return (pos<fname.lenght() ? fname.substr(pos+1) : "");
}

ist allerdings kein wunder an effizienz...

Meep Meep

re

grippe ? nein
schnupfen ? ja

uebertraege vergessen, ja stimmt.

wieso "bitten wir zum absturz durch string-ende-überschreitung?"
find da den fehler nicht. kaffee ausgegangen

Meep Meep

finix

Konfusius schrieb:

um einen string von hinten zu durchsuchen, muß man erst einmal an das stringende kommen. und dazu muß man den string auch vollständig durchlaufen. ich denke, schneller als der ursprüngliche code gehts nicht.

Ja, aber du prüfst nicht bei jedem Zeichen ob es ein Punkt ist, oder merkst dir (potentiell überflüssigerweise) wo der Punkt nun gewesen ist.

Da der Punkt dann meistens schon wieder das 3. oder 4. Zeichen ist, dürfte es (schätzungsweise) doch ein wenig schneller sein, im Durchschnitt.
Aber wen juckt's, bei dieser Funktion?

Konfusius schrieb:

mit c++-strings würde ich es so machen:
string
GetFileNameExtension (const string &fname)
{
  int pos=fname.find_last_of('.');

  return (pos<fname.lenght() ? fname.substr(pos+1) : "");
}
ist allerdings kein wunder an effizienz...

Wieso nutzt du nicht std::string::npos? Wäre deutlicher und potentiell schneller...

volkard

Meep Meep schrieb:

re

grippe ? nein
schnupfen ? ja

uebertraege vergessen, ja stimmt.

wieso "bitten wir zum absturz durch string-ende-überschreitung?"
find da den fehler nicht. kaffee ausgegangen

Meep Meep

if(p2) 
      { 
         while(*p2 != '.') *(++p2); 
      }

ok, kein absturz. das if(p2) schützt ja.

aber ein priblemchen bei
"foo-1.2.a"
weil im zweiten int "1.2." vorkommen und die schleife bem ersten '.' abbricht.

camper

Meep Meep schrieb:

uebertraege vergessen, ja stimmt.

ist ja kein problem mit

temp = *((unsigned int*) p1) ^ 0x2E2E2E2E;