3. Länge eines stringstreams, wie?

Länge eines stringstreams, wie?

  • V

    Michael E. schrieb:

    theliquidwave schrieb:

    Dein Code "failt" bei 0 (Länge = 0) und Minuszahlen (Endlosschleife).
    Hier mal ein Fix 😉

    int get_length(int value)
{
	if (value == 0)
		return 1;
	
	int ret_val = 0;
	
	if (value < 0)
	{
		value *= -1;
		++ret_val;
	}
	
	for(; value != 0; ++ret_val)
		value /= 10;
	
	return ret_val;
}

    get_length(-2147483648);

    :p

    Das gibt aber auch kein falsches Ergebnis.
    Falls value*=-1 gar nicht benötigt wird, was zur Zeit vermutet wird.

    0
  • S

    unskilled schrieb:

    ich glaube kaum, dass es sich bei einer 32bit zahl überhaupt lohnen wird...

    alleine schon die ständigen umwandlungen wären für mich schon grund genug, es nicht zu verwenden...

    int g0(int const& X)
{
    return log10( abs(X) ) +1 + (X<0);
}

    Jo, hab das std:: vergessen, hinzukommt das ich X=0 nicht abfrage,
    lustigerweise funktionierte es bei mir trozdem (gcc), da ich es mit unsigned als Rückgabewert getestet habe und scheinbar -inf +1 zu null gecasted wird?!
    Ist das Compiler abhängig?
    Kann das jemand erklären?

    #include <iostream>
#include <cmath>

int main()
{
    std::cout << std::log10(0) <<"\n"; //-inf0
    std::cout << (int)std::log10(0)<<"\n"; // -2147483648
    std::cout << (unsigned int)std::log10(0); // 0
    return 0;
}
    0
  • 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
Anmelden zum Antworten