Länge eines stringstreams, wie?

[life]

Dravere schrieb:

Sowas vielleicht?

Ca. 40% schneller als die while-schleife bei mir .

[volkard]

Würde ich Speed suchen, würde ich wohl drei Sachen anbieten und dem Benutzer überlassen, was er als schnellstes ausmißt.

- mit if von klein nach groß

- mit if/else binär suchen

- bsf benutzen:

unsigned int get_length(unsigned int x)
{
	//STATIC_ASSERT(sizeof(x)==4);
	switch(floorLog2(x))//asm bsr
	{
		case 0://0-1
		case 1://2-3
		case 2://4-7
			return 1;
		case 3://8-15
			return 1+(x>=10);
		case 4://16-31
		case 5://32-64
			return 2;
		case 6://64-128
			return 2+(x>=100);
		case 7://128-255
		case 8://256-511
			return 3;
		case 9://512-1023
			return 3+(x>=1000);

		//Hier noch ein paar Fälle einfügen. 
		//alternativ:
		//ach, keine Lust mehr
		//default: return 3+get_length(x/1000);

		//oder	
		//default: __assume(false);//bringt Speed auf MSVC
		//aber dann die Fälle alle machen
	}
	return 0;//only to make the compiler happy
}

[life]

Jetzt das ganze am besten noch ohne das "STATIC_ASSERT(sizeof(x)==4)". Vielleicht mit Boost Preprocessor?

[unskilled]

life schrieb:

Jetzt das ganze am besten noch ohne das "STATIC_ASSERT(sizeof(x)==4)". Vielleicht mit Boost Preprocessor?

wieso?

[volkard]

unskilled schrieb:

life schrieb:

Jetzt das ganze am besten noch ohne das "STATIC_ASSERT(sizeof(x)==4)". Vielleicht mit Boost Preprocessor?

wieso?

Das war ironisch gemeint. Nachdem ich ein Metamonster getötet hatte, wollte er mir zum Spaß nochmal die Schlinge von hinten ins Auge schießen.

[Dravere]

volkard schrieb:

Nachdem ich ein Metamonster getötet hatte, ...

Du brutaler Metamonster töter! Die Metamonster haben auch Gefühle!
Wirklich ernst war der Vorschlag schon nicht gemeint, ich hätte schliesslich wirklich nur ein if-else machen können bis zu 19 Stellen für long long . Oder eine for-Schleife über ein Array, welches statisch gebaut wird. Der Kompiler könnte es dann immer noch optimieren.
Aber war noch spannend sowas mit der Template-Metaprogrammierung zu machen, auch wenn es völlig übertrieben und überhaupt nicht praxisnah ist

Grüssli

[falafel]

Ihr solltet es noch parallelisieren, bis der Arzt :hoppschwiiz: kommt.

[volkard]

Da mußte ich noch ein wenig frickeln.

#include <iostream>
using namespace std;

typedef unsigned int UInt32;

inline UInt32 floorLog2(UInt32 x) {
//assert(x!=0);
	UInt32 result;
	asm(
		"bsrl %[x],%[result];"
		:[result] "=r"(result)
		:[x] "mr"(x)
	);
	return result;
}

UInt32 get_length(UInt32 x) {
	static UInt32 const pow10[]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,};
	if (x==0) return 1;
	UInt32 result=floorLog2(x)*9/32;// 9/32 ist ungefähr ln(2)/ln(10)
	if (x>=pow10[result])
		++result;
	return result+1;
}

int main() {
	UInt32 x=0;
	UInt32 y=1;
	cout<<y<<": "<<x<<'-';
	do {
		if (get_length(x)!=y) {
			cout<<x-1<<'\n';
			y=get_length(x);
			cout<<y<<": "<<x<<'-';
		}
		++x;
	} while (x);
	cout<<x-1<<'\n';
}

Zum Testen

int main() {
	UInt32 x=0;
	UInt32 s=0;
	do {
			s+=get_length(x/*%65536*/);
		++x;
	} while (x);
	cout<<s<<'\n';

Zum Messen

Process returned 0 (0x0)   execution time : 40.203 s //gleichverteilt 0-2^32
37.781 //gleichverteilt 0-2^16

Da die Zeit mitunter sehr stark von der Verteilung abhängt, messe ich immer diese beiden.
Man sieht, daß bsr auf meinem Rechner (AMD Athlon 3000+ oder so) nicht lecker schnell ist.

UInt32 get_length(UInt32 x) {
	if (x==0) return 1;
	switch(floorLog2(x)){
		case 0: return 1;
		case 1: return 1;
		case 2: return 1;
		case 3: return 1+(x>=10);
		case 4: return 2;
		case 5: return 2;
		case 6: return 2+(x>=100);
		case 7: return 3;
		case 8: return 3;
		case 9: return 3+(x>=1000);
		case 10: return 4;
		case 11: return 4;
		case 12: return 4;
		case 13: return 4+(x>=10000);
		case 14: return 5;
		case 15: return 5;
		case 16: return 5+(x>=100000);
		case 17: return 6;
		case 18: return 6;
		case 19: return 6+(x>=1000000);
		case 20: return 7;
		case 21: return 7;
		case 22: return 7;
		case 23: return 7+(x>=10000000);
		case 24: return 8;
		case 25: return 8;
		case 26: return 8+(x>=100000000);
		case 27: return 9;
		case 28: return 9;
		case 29: return 9+(x>=1000000000);
		case 30: return 10;
		case 31: return 10;
		default: return 0;
	}
}

Process returned 0 (0x0)   execution time : 38.812 s
40.156

Das switch läßt sich nicht so einfach ausmessen, bsr dominiert.

UInt32 get_length(UInt32 x){
	if(x>=1000000000) return 10;
	if(x>=100000000) return 9;
	if(x>=10000000) return 8;
	if(x>=1000000) return 7;
	if(x>=100000) return 6;
	if(x>=10000) return 5;
	if(x>=1000) return 4;
	if(x>=100) return 3;
	if(x>=10) return 2;
	return 1;
}

Process returned 0 (0x0)   execution time : 10.656 s
13.359

Praktisch, dreieckig, gut!

//Das Metamonster

Process returned 0 (0x0)   execution time : 10.609 s
13.357

Nur anders eingetippt.

UInt32 get_length(UInt32 x) {
	if(x==0) return 1;
	return log10(x)+1;
}

ewig. 
ewig.

Naja, war auch klar.

UInt32 get_length(UInt32 x) {
	static UInt32 const pow10[]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
	if (x>1000000000) return 10;
	if (x==0) return 1;
	UInt32 result=floorLog2(x)*9/32;// 9/32 ist ungefähr ln(2)/ln(10)
	if (x>=pow10[result])
		++result;
	return result+1;
}

Process returned 0 (0x0)   execution time : 20.953 s
37.540

Für gleichverteilung bsr abfedern. Zwecklos.

UInt32 get_length(UInt32 x){
	if(x<=9) return 1;
	if(x<=99) return 2;
	if(x<=999) return 3;
	if(x<=9999) return 4;
	if(x<=99999) return 5;
	if(x<=999999) return 6;
	if(x<=9999999) return 7;
	if(x<=99999999) return 8;
	if(x<=999999999) return 9;
	return 10;
}

Process returned 0 (0x0)   execution time : 27.291
17.562

UInt32 get_length(UInt32 x){
	if(x>=100000)//6
		if(x>=100000000)//9
			if(x>=1000000000)//10
				return 10;
			else
				return 9;
		else
			if(x>=10000000)//8
				return 8;
			else
				if(x>=10000000)//7
					return 7;
				else
					return 6;
	else
		if(x>=1000)//4
			if(x>=10000)//5
				return 5;
			else
				return 4;
		else
			if(x>=100)//3
				return 3;
			else
				if(x>=10)//2
					return 2;
				else
					return 1;
}

Process returned 0 (0x0)   execution time : 10.296
8.765

Seltsam.

Falls das mal jemand auf einem modernen Prozessor mit voller Optimierung, z.B. -march=native -O3 nachmessen möchte, das wäre lieb.

[SeppJ]

volkard schrieb:

Falls das mal jemand auf einem modernen Prozessor mit voller Optimierung, z.B. -march=native -O3 nachmessen möchte, das wäre lieb.

Gerade mal ein bisschen in der Mittagspause meine Compileroptimierungsfertigkeiten testen. Intel Compiler, O3, auf einem i7, SSE4.2 Befehlssatz ist aktiviert.

UInt32 get_length(UInt32 x) {
    static UInt32 const pow10[]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,};
    if (x==0) return 1;
    UInt32 result=floorLog2(x)*9/32;// 9/32 ist ungefähr ln(2)/ln(10)
    if (x>=pow10[result])
        ++result;
    return result+1;
}

19.280 // 0-2^32
9.250  // 0-2^16

Woah, fetter Unterschied.

UInt32 get_length(UInt32 x) {
    if (x==0) return 1;
    switch(floorLog2(x)){
        case 0: return 1;
        case 1: return 1;
        case 2: return 1;
        case 3: return 1+(x>=10);
        case 4: return 2;
        case 5: return 2;
        case 6: return 2+(x>=100);
        case 7: return 3;
        case 8: return 3;
        case 9: return 3+(x>=1000);
        case 10: return 4;
        case 11: return 4;
        case 12: return 4;
        case 13: return 4+(x>=10000);
        case 14: return 5;
        case 15: return 5;
        case 16: return 5+(x>=100000);
        case 17: return 6;
        case 18: return 6;
        case 19: return 6+(x>=1000000);
        case 20: return 7;
        case 21: return 7;
        case 22: return 7;
        case 23: return 7+(x>=10000000);
        case 24: return 8;
        case 25: return 8;
        case 26: return 8+(x>=100000000);
        case 27: return 9;
        case 28: return 9;
        case 29: return 9+(x>=1000000000);
        case 30: return 10;
        case 31: return 10;
        default: return 0;
    }
}

7.060 // 2^32
8.370 // 2^16

Was geht hier ab?

UInt32 get_length(UInt32 x){
    if(x>=1000000000) return 10;
    if(x>=100000000) return 9;
    if(x>=10000000) return 8;
    if(x>=1000000) return 7;
    if(x>=100000) return 6;
    if(x>=10000) return 5;
    if(x>=1000) return 4;
    if(x>=100) return 3;
    if(x>=10) return 2;
    return 1;
}

4.970
4.850

Wie erwartet das bisher schnellste.

// Das Metamonster

Das schmeißt bei mir übrigens Warnungen ohne Ende über unsinnigen Code, aber ich mag das jetzt nicht Debuggen. Das Ergebnis stimmt jedenfalls. Zeit:

5.020
6.220

Gar nicht mal so übel.

UInt32 get_length(UInt32 x) {
    if(x==0) return 1;
    return log10(x)+1;
}

ewig.
ewig.

UInt32 get_length(UInt32 x) {
    static UInt32 const pow10[]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
    if (x>1000000000) return 10;
    if (x==0) return 1;
    UInt32 result=floorLog2(x)*9/32;// 9/32 ist ungefähr ln(2)/ln(10)
    if (x>=pow10[result])
        ++result;
    return result+1;
}

8.290
9.590

UInt32 get_length(UInt32 x){
    if(x<=9) return 1;
    if(x<=99) return 2;
    if(x<=999) return 3;
    if(x<=9999) return 4;
    if(x<=99999) return 5;
    if(x<=999999) return 6;
    if(x<=9999999) return 7;
    if(x<=99999999) return 8;
    if(x<=999999999) return 9;
    return 10;
}

16.420
9.150

Und der letzte:

UInt32 get_length(UInt32 x){
    if(x<=9) return 1;
    if(x<=99) return 2;
    if(x<=999) return 3;
    if(x<=9999) return 4;
    if(x<=99999) return 5;
    if(x<=999999) return 6;
    if(x<=9999999) return 7;
    if(x<=99999999) return 8;
    if(x<=999999999) return 9;
    return 10;
}

7.660
6.560

Alle Tests jeweils nur einmal gelaufen, aber der Rechner hatte nichts zu tun und mehrmalige Testläufe hatten keine große Varianz.

[Dravere]

SeppJ schrieb:

Das schmeißt bei mir übrigens Warnungen ohne Ende über unsinnigen Code, aber ich mag das jetzt nicht Debuggen.

Kannst du die Warnungen hier reinstellen oder mir eine E-Mail mit diesen zuschicken? Ich habe extra alle Warnungen unter MSVC und GCC ausgemerzt

Übrigens: Wie wäre es noch mit diesem Test:

struct decimal_place_counter_02
{
  static UInt32 const max_digits = std::numeric_limits<int>::digits10;
  UInt32 pow10[max_digits];

  decimal_place_counter_02()
  {
    UInt32 power = 1;

    for(UInt32 i = 0; i < max_digits; ++i)
    {
      power *= 10;
      pow10[i] = power;
    }
  }

  UInt32 count(UInt32 x) const
  {
    for(UInt32 i = 0; i < max_digits; ++i)
    {
      if(x < pow10[i])
        return i + 1;
    }

    return max_digits + 1;
  }
};

UInt32 get_length(UInt32 x)
{
  static decimal_place_counter_02 const counter;
  return counter.count(x);
}

Geht mir vor allem dabei darum, diese manuelle Aufzählung zu vernichten. Wenn man an long long denkt und man dies für 19 Stellen tun müsste, sähe das schon irgendwie blöd aus, finde ich
Da die For-Schleife über eine konstante Grösse geht, könnte ich mir vorstellen, dass der Kompiler in der Lage ist, diese auszurollen. Wodurch nur einmalig ein kleiner Mehraufwand stattfindet und danach die Zeiten wahrscheinlich ähnlich zum Dreieck sein sollten.

Grüssli

[SeppJ]

Dravere schrieb:

Kannst du die Warnungen hier reinstellen oder mir eine E-Mail mit diesen zuschicken? Ich habe extra alle Warnungen unter MSVC und GCC ausgemerzt

Das meiste ist ziemlich harmlos, der Intel Compiler ist bloß traditionell sehr mitteilungsfreudig, besonders wenn man auch noch extra viele Bemerkungen anschaltet. Zeilennummern sind wie in deinem Beitrag+1, weil ich noch ein #include<cstddef> davorschreiben musste für std::size_t. Da die Warnungen bei jeder Instanzierung aufkommen, bringe ich jeweils nur die Warnung für die erste Instanzierung:

sstream.cc(98): remark #1418: external function definition with no prior declaration
  std::size_t decimal_place_count(T val)

Harmlos.

sstream.cc(8): warning #63: shift count is too large
    static T const result = ((T)1 << BIT) + max_value_helper<T, BIT - 1>::result;
                                     ^
          detected during:
            instantiation of class "max_value_helper<T, BIT> [with T=unsigned int, BIT=32UL]" at line 27
            instantiation of class "max_value<T> [with T=unsigned int]" at line 51
            instantiation of class "max_decimal_places<T> [with T=unsigned int]" at line 101
            instantiation of "size_t={unsigned long} decimal_place_count(T) [with T=unsigned int]" at line 118

Dies allerdings ist interessant.

sstream.cc(78): remark #981: operands are evaluated in unspecified order
      if((val < 0 && val > -check) || (val >= 0 && val < check))
                         ^
          detected during instantiation of "size_t={unsigned long} decimal_place_count(T) [with T=unsigned int]" at line 118

Harmlos. Gleiche Bemerkung für den zweiten Term val<check .

sstream.cc(78): warning #186: pointless comparison of unsigned integer with zero
      if((val < 0 && val > -check) || (val >= 0 && val < check))
              ^
          detected during:
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=9UL]" at line 103
            instantiation of "size_t={unsigned long} decimal_place_count(T) [with T=unsigned int]" at line 118

Dein Code ist zu flexibel. Wer rechnet schon mit signed Datentypen?
Gleiche Warnung für den zweiten Term val >= 0 .

Diese Warnung wiederholt sich mit jeder Instanzierung, mit immer länger werdender Aufrufliste, bis man dann irgendwann dieses schöne Monstrum bekommt:

sstream.cc(78): warning #186: pointless comparison of unsigned integer with zero
      if((val < 0 && val > -check) || (val >= 0 && val < check))
                                           ^
          detected during:
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=1UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=2UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=3UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=4UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=5UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=6UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=7UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=8UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=9UL]" at line 103
            instantiation of "size_t={unsigned long} decimal_place_count(T) [with T=unsigned int]" at line 118

Zuletzt noch ein "schwerwiegender" Schönheitsfehler:

sstream.cc(90): remark #869: parameter "val" was never referenced
    static std::size_t count(T val)
                               ^
          detected during:
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=1UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=2UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=3UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=4UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=5UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=6UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=7UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=8UL]" at line 80
            instantiation of "size_t={unsigned long} decimal_place_counter<T, DECIMAL_PLACES>::count(T) [with T=unsigned int, DECIMAL_PLACES=9UL]" at line 103
            instantiation of "size_t={unsigned long} decimal_place_count(T) [with T=unsigned int]" at line 118

Also einfach den unbenutzten Parameternamen entfernen.

[Dravere]

SeppJ schrieb:

sstream.cc(8): warning #63: shift count is too large
    static T const result = ((T)1 << BIT) + max_value_helper<T, BIT - 1>::result;
                                     ^
          detected during:
            instantiation of class "max_value_helper<T, BIT> [with T=unsigned int, BIT=32UL]" at line 27
            instantiation of class "max_value<T> [with T=unsigned int]" at line 51
            instantiation of class "max_decimal_places<T> [with T=unsigned int]" at line 101
            instantiation of "size_t={unsigned long} decimal_place_count(T) [with T=unsigned int]" at line 118

Dies allerdings ist interessant.

Nicht interessant sondern Kopf -> Tisch. Völlig logische Warnung und ganz einfach zu eliminieren:

template<typename T>
struct max_value
{
private:
  typedef std::numeric_limits<T> limits;

  static std::size_t const bits = std::numeric_limits<T>::digits - 1;

public:
  static T const result = max_value_helper<T, bits>::result;
};

std::numer_limits<T>::digits gibt die Anzahl der nicht Vorzeichenbits zurück. Daher muss ich immer -1 rechnen und nicht nur bei Typen mit Vorzeichenbits.

Der Rest ist ziemlich klar und einfach abzuschaffen. Einzig vielleicht die Sache mit dem unsigned / signed Problem. Allerdings könnte man da wahrscheinlich etwas mit enable_if oder dergleichen zaubern.

Danke für die Rückmeldung.

Grüssli

[Th69]

Und warum nicht einfach diese Schleife:

int n = 1;
while(x >= 10)
{
  x /= 10;
  ++n;
}
return n;

Dürfte auch nicht (im Schnitt, d.h. gleichverteilt über alle Zahlen) viel langsamer sein, als die if-Kaskade (und ist nicht abhängig von der Datentyp-Größe)...

[Fellhuhn]

JUDAS!

[SeppJ]

Th69 schrieb:

Und warum nicht einfach diese Schleife:

int n = 1;
while(x >= 10)
{
  x /= 10;
  ++n;
}
return n;

Dürfte auch nicht (im Schnitt, d.h. gleichverteilt über alle Zahlen) viel langsamer sein, als die if-Kaskade (und ist nicht abhängig von der Datentyp-Größe)...

Das ist viel langsamer als alles bisher dagewesene, abgesehen vom Logarithmus. Über 47 Sekunden bei mir für die 0-2^32 Variante und immer noch 21 Sekunden bis 2^16, vergleiche mit knapp 5 s für die if-Kaskade (für beide Varianten). Mal eben ein Faktor 5 bis 10.

[Dravere]

Ok, hier mal die korrigierte und gekürzte Fassung des Metamonsters

#include <limits>
#include <cstddef>

template<typename T, std::size_t COUNT>
struct e10
{
  static T const result = e10<T, COUNT - 1>::result * 10;
};

template<typename T>
struct e10<T, 0>
{
  static T const result = 1;
};

template<typename T, T CHECK, bool SIGNED = std::numeric_limits<T>::is_signed>
struct decimal_place_test
{
private:
  static T const check = CHECK;
  static T const negative_check = -CHECK;

public:
  static bool test(T val)
  {
    if(val < 0)
    {
      return val > negative_check;
    }

    return val < check;
  }
};

template<typename T, T CHECK>
struct decimal_place_test<T, CHECK, false>
{
  static bool test(T val)
  {
    return val < CHECK;
  }
};

template<typename T, std::size_t PLACES = std::numeric_limits<T>::digits10>
struct decimal_place_counter
{
  static std::size_t const decimal_places = PLACES;
  static T const check = e10<T, decimal_places>::result;

  static std::size_t count(T val)
  {
    if(decimal_place_test<T, check>::test(val))
    {
      return decimal_place_counter<T, decimal_places - 1>::count(val);
    }

    return decimal_places + 1;
  }
};

template<typename T>
struct decimal_place_counter<T, 0>
{
  static std::size_t count(T /*val*/)
  {
    return 1;
  }
};

/*-------------------------------------------*/
/* Intel Kompiler Befriedigung               */

template<typename T>
std::size_t decimal_place_count(T val);

/*                                           */
/*-------------------------------------------*/

template<typename T>
std::size_t decimal_place_count(T val)
{
  return decimal_place_counter<T>::count(val);
}

@Th69,
Du vergisst, dass die mehrfache Division deutlich langsamer ist als ein paar Vergleiche und Sprünge.

Grüssli

[SeppJ]

Erzeugt jetzt nur noch die Bemerkung mit der externen Deklaration und Definition, aber das liegt nur daran, dass ich zu faul bin das Testprogramm in mehrere Dateien aufzuspalten (der guckt nämlich auch danach in welcher Datei die Deklarationen stehen). Zeit für die 0-2^32 Version ist weiterhin gut 5 s, also nur ein kleines bisschen langsamer als die if-Kaskade. 0-2^16 ist ein bisschen weniger effizient.

[Dravere]

SeppJ schrieb:

Erzeugt jetzt nur noch die Bemerkung mit der externen Deklaration und Definition, aber das liegt nur daran, dass ich zu faul bin das Testprogramm in mehrere Dateien aufzuspalten (der guckt nämlich auch danach in welcher Datei die Deklarationen stehen).

Ach blöder Intel Kompiler, kann man ihn nicht einmal austricksen

Grüssli

[life]

Also bei mir ist ja die binäre Suche mit Abstand am schnellsten:

UInt32 get_length(UInt32 x){
    if(x>=100000)//6
        if(x>=100000000)//9
            if(x>=1000000000)//10
                return 10;
            else
                return 9;
        else
            if(x>=10000000)//8
                return 8;
            else
                if(x>=10000000)//7
                    return 7;
                else
                    return 6;
    else
        if(x>=1000)//4
            if(x>=10000)//5
                return 5;
            else
                return 4;
        else
            if(x>=100)//3
                return 3;
            else
                if(x>=10)//2
                    return 2;
                else
                    return 1;
}

[volkard]

Dravere schrieb:

Übrigens: Wie wäre es noch mit diesem Test:

struct decimal_place_counter_02
{
  static UInt32 const max_digits = std::numeric_limits<int>::digits10;
  UInt32 pow10[max_digits];

  decimal_place_counter_02()
  {
    UInt32 power = 1;

    for(UInt32 i = 0; i < max_digits; ++i)
    {
      power *= 10;
      pow10[i] = power;
    }
  }

  UInt32 count(UInt32 x) const
  {
    for(UInt32 i = 0; i < max_digits; ++i)
    {
      if(x < pow10[i])
        return i + 1;
    }

    return max_digits + 1;
  }
};

UInt32 get_length(UInt32 x)
{
  static decimal_place_counter_02 const counter;
  return counter.count(x);
}

Geht mir vor allem dabei darum, diese manuelle Aufzählung zu vernichten.

Process returned 0 (0x0)   execution time : 43.406 s
27.359

Die schlichte if-Kaskade ist schon sauschnell.
10 Sekunden @ 2GHz / 2^32 = 4.6 Takte pro Hauptschleifendurchlauf und die Hauptschleife hat eine Abbruchbedingung und hat aufsummiert.