3. Länge eines stringstreams, wie?

Länge eines stringstreams, wie?

  • T

    Was spricht gegen diese Lösung?

    unskilled schrieb:

    std::string get_int_as_string(int value)
{
  std::stringstream ss;
  ss << value;
  return ss.str();
}
    0
  • M

    Tachyon schrieb:

    Was spricht gegen diese Lösung?

    unskilled schrieb:

    std::string get_int_as_string(int value)
{
  std::stringstream ss;
  ss << value;
  return ss.str();
}

    Zu lahm.

    0
  • P

    Michael E. schrieb:

    Zu lahm.

    Wieviel lahmer? Zeitmessungen gemacht?

    0
  • M
     

    #include <iostream>
#include <string>
#include <sstream>
#include <boost/random/linear_congruential.hpp>
using namespace std;

typedef unsigned __int64 u64; 

#pragma warning(push) 
#pragma warning(disable:4035) 
u64 rdtsc() 
{ 
	__asm rdtsc; 
} 
#pragma warning(pop)

int getLength1(int arg)
{
	stringstream ss;
	ss << arg;
	return ss.str().length();
}

int getLength2(int arg)
{
	int ret = (arg < 0);

	do
		++ret;
	while(arg /= 10);

	return ret;
}

int main()
{
	const int n = 100000;
	int result[n];
	int (*func[2])(int) = { getLength1, getLength2};
	boost::rand48 generator;

	for(int i = 0; i < 10; ++i)
	{
		for(int j = 0; j < 2; ++j)
		{
			generator.seed(42);
			for(int k = 0; k < n; ++k)
				result[k] = generator();

			u64 start = rdtsc();

			for(int k = 0; k < n; ++k)
				result[k] = func[j](result[k]);

			u64 end = rdtsc();

			if(j)
				cout << end - start << "\n";
			else
				cout << end - start << " <-> ";
		}
	}
}

    Intel Core i3-330M, Windows 7 Home Premium 64 Bit, Visual Studio 2008 SP1, Optimierung auf "Geschwindigkeit maximieren":

    /O2 /Oi /GL /I "d:\boost/boost_1_42" /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /Gy /Fo"Release\\" /Fd"Release\vc90.pdb" /W3 /nologo /c /Zi /TP /errorReport:prompt

    Ausgabe:

    605812167 <-> 9224968
573697862 <-> 9301400
572169548 <-> 9157740
578836805 <-> 9419872
569198168 <-> 9235780
562688192 <-> 9165412
572129856 <-> 9244632
573213868 <-> 9171600
569073352 <-> 9297776
568769208 <-> 9402188

    Macht also einen Faktor von etwa 60.

    0
  • T

    Michael E. schrieb:

    [...]Zu lahm.

    Zu lahm wofür? Es geht nicht um das Ermitteln der Ziffernzahl. Es geht um das Erstellen eines Images des gegebenen Integers...

    0
  • P

    Michael E. schrieb:

    Macht also einen Faktor von etwa 60.

    Wenn die Funktion mit allen Aufrufen nur einen winzigen Bruchteil des Gesamtprogramms ausmacht macht ein Faktor 60 den Kohl auch nicht fett und reduziert die Auswahl zwischen den beiden Möglichkeiten zur Geschmackssache.

    0
  • U

    edit: oh - mein fehler : D

    0
  • F

    Da die Zahlen endlich sind, ist eine Lookup-Table doch schneller. 😃

    0
  • M

    Eins vorneweg: Ich hab nicht gesehen, dass der OP schon mit Stringstreams herumwurschelt, sondern bin davon ausgegangen, dass es wirklich nur darum geht, die Anzahl der Ziffern herauszufinden. Denn Tachyon hat recht mit seiner Aussage.

    pumuckl schrieb:

    Wenn die Funktion mit allen Aufrufen nur einen winzigen Bruchteil des Gesamtprogramms ausmacht macht ein Faktor 60 den Kohl auch nicht fett und reduziert die Auswahl zwischen den beiden Möglichkeiten zur Geschmackssache.

    Versteh mich nicht falsch. Ich bin auch kein Freund vom frühzeitigen Optimieren und wähle sehr oft andere Wege als den schnellsten, aber hier ist es egal, für welche Version man sich entscheidet, auf den Rest des Codes hat das keine Auswirkungen. Auch sind beide Varianten in etwa "gleich schön", sodass man sich hier durchaus nach der Geschwindigkeit richten kann, auch wenns nachher bei der Programmausführung nicht auffällt.

    unskilled schrieb:

    for(int k = 0; k < n; ++k)
  result[k] = func[j](result[k]);

    klar, wenn vll eine "lange" zahl und dann nur noch ziffern untersucht werden, dass die schleife wahnsinnig schnell ist - ich nehme mal an, dass sich das ein wenig relativiert, wenn du längere zahlen nimmst...

    Das sind alles Zahlen mit fünf bis zehn Ziiffern. Wie willst du noch längere Zahlen in int speichern?

    0
  • U

    Michael E. schrieb:

    Das sind alles Zahlen mit fünf bis zehn Ziiffern. Wie willst du noch längere Zahlen in int speichern?

    mein fehler - hatte mich verguckt -.-
    habs mal wegeditiert...^^

    0
  • Administrator

    Fellhuhn schrieb:

    Da die Zahlen endlich sind, ist eine Lookup-Table doch schneller. 😃

    Sowas vielleicht?

    #include <limits>

template<typename T, std::size_t BIT>
struct max_value_helper
{
  static T const result = ((T)1 << BIT) + max_value_helper<T, BIT - 1>::result;
};

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

template<typename T>
struct max_value // ich vermisse constexpr von C++0x
{
private:
  typedef std::numeric_limits<T> limits;

  static std::size_t const bits = std::numeric_limits<T>::digits;
  static std::size_t const sub = std::numeric_limits<T>::is_signed ? 1 : 0;

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

template<typename T, T VALUE, std::size_t COUNTER = 0, bool CHECK = true>
struct max_decimal_places_helper
{
private:
  typedef max_decimal_places_helper<T, VALUE / 10, COUNTER + 1, (VALUE > 0)> next;

public:
  static std::size_t const result = 1 + next::result;
};

template<typename T, T VALUE, std::size_t COUNTER>
struct max_decimal_places_helper<T, VALUE, COUNTER, false>
{
  static std::size_t const result = 0;
};

template<typename T>
struct max_decimal_places
{
private:
  typedef max_decimal_places_helper<T, max_value<T>::result / 10> helper;

public:
  static std::size_t const result = helper::result;
};

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, std::size_t DECIMAL_PLACES>
struct decimal_place_counter
{
  static T const check = e10<T, DECIMAL_PLACES>::result;

  static std::size_t count(T val)
  {
    if((val < 0 && val > -check) || (val >= 0 && val < check))
    {
      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;
  }
};

template<typename T>
std::size_t decimal_place_count(T val)
{
  typedef max_decimal_places<T> places;
  typedef decimal_place_counter<T, places::result - 1> counter;

  return counter::count(val);
}

    Grüssli 🤡 😃

    0
  • L

    Dravere schrieb:

    Sowas vielleicht?

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

    0
  • V

    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
}
    0
  • L

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

    0
  • U

    life schrieb:

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

    wieso?

    0
  • V

    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.

    0
  • Administrator

    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

    0
  • ?

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

    0
  • V

    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.

    0
  • Mod

    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.

    0
Anmelden zum Antworten