String zu Long, manuell

Christoph

reano schrieb:

Oder sogar ganz ohne Multiplikationen:

for( int i = 0; i < Eingabe.size(); ++i )
{
	Zahl = ( Zahl << 3 ) + ( Zahl << 1 ) + Eingabe[i] - '0';
}

Das ist allerdings ziemlich unsinnig, weil es deutlich langsamer sein kann. Auf einem AVR atmega16 zum Beispiel kostet eine Multiplikation genau 2 Takte. Ein Shift um 3 Positionen nach links kostet 3 Takte, ein Shift um eine Position nach links 1 Takt und die zusätzliche Addition nochmal 1 Takt. Insgesamt hat man hier also 5 Takte für deine Lösung gegenüber 2 Takte, wenn man einfach direkt mit 10 multipliziert.

Solche Optimierungen überlässt man besser dem Compiler.

Natürlich ist das systemabhängig.

int main()
{
	const char* nr = "1336543215";

	const int maxNum = 100000000;

	{
		StopWatch w; // nutzt den PerformanceCounter
		w.Start();
		for(int i=0;i<maxNum;++i)
		{
			int k = atoiReano(nr);
			if(k!=1336543215)
				cout << "unmoeglich\n";
		}
		w.Stop();
		cout << w.GetTime() << "ms\n";
	}
	{
		StopWatch w;
		w.Start();
		for(int i=0;i<maxNum;++i)
		{
			int k = atoi(nr);
			if(k!=1336543215)
				cout << "unmoeglich\n";
		}
		w.Stop();
		cout << w.GetTime() << "ms\n";
	}
}

Ausgabe:

1.01927ms
5.02301ms

Für mein System ist das eindeutig, von Unsinn kann da keine Rede sein.

Ah, jetzt habe ich doch glatt Pi vergessen: 1.0830ms.

Stellenangebot:

Putzfrau gesucht
10 € / Stunde

unskilled

debugmode?

for(int i=0;i<maxNum;++i) 
        { 
            int k = atoiReano(nr); 
            if(k!=1336543215) 
                cout << "unmoeglich\n"; 
        }

das das rausoptimiert werden kann, erkennt auch der unfähigste compiler Oo

pyhax

Aber warum dann nicht bei atoiPi oder atoi standart?

Reano: 20ms
Pi: 40ms
Standart: 90ms

Christoph

Thorgrim schrieb:

Ausgabe:
1.01927ms
5.02301ms
Für mein System ist das eindeutig, von Unsinn kann da keine Rede sein.

Hast du im generierten Assembler-Code geprüft, dass deine Schleife nicht einfach komplett rausoptimiert wurde?

pyhax

http://tinodidriksen.com/2010/02/16/cpp-convert-string-to-int-speed/

unskilled schrieb:

das das rausoptimiert werden kann, erkennt auch der unfähigste compiler Oo

phyax hat ja schon einen Link gepostet, während ich mir noch den asm-Output angeschaut habe. 20% der Zeit von atoi passt ja auch. Compiler war VC 9, win64 und x64-Code natürlich im Releasemodus, Schleifen nicht rausoptimiert (VC tut sich diesbezüglich immer schwer damit).

Update:

0.770659s  Reano
5.03864s   atoi
1.17046s   Pi
123.285s   stringstream

Mit dem alten g++ 4.4

1.0659s
5.07371s
1.09504s
105.263s

Ich hatte erwähnt, Zeichenfolgen zufällig zusammenzustellen, aber auch bei statischen Zeichenketten optimieren die Compiler nichts weg.

314159265358979

Nimm mal den Range-Check raus, dann dürfte meine genau gleich schnell sein, wenn nicht sogar schneller.

camper

constexpr unsigned long pow10(unsigned long e) {
    return e == 0 ? 0 : pow10( e - 1 ) <= std::numeric_limits<unsigned long>::max() / 10 ? 10 * pow10( e - 1 ) : 0;
}

template <typename T> struct identity {
    using type = T;
};

template <std::size_t... i> struct index_list
    : identity<index_list<i...>> {};

template <typename T> struct append_index_list
    : append_index_list<typename T::type> {};
template <std::size_t... i> struct append_index_list<index_list<i...>>
    : index_list<0, (i+1)...> {};

template <std::size_t N> struct make_index_list
    : append_index_list<make_index_list<N-1>> {};
template <> struct make_index_list<0>
    : index_list<> {};

template <typename Dim> struct table_pow10
    : table_pow10<typename Dim::type> {};
template <std::size_t... i> struct table_pow10<index_list<i...>> {
    static const unsigned long data[sizeof...(i)];
};
template <std::size_t... i>
const unsigned long table_pow10<index_list<i...>>::data[] = { ( ( i % 10u ) * pow10( i / 10u ) )... };

unsigned long atoul(const std::string& s)
{
    unsigned long result = 0;
    const unsigned long* p = table_pow10<make_index_list<10 * ( std::numeric_limits<unsigned long>::digits10 + 1 )>>::data;
    for ( auto i = s.size(); i != 0; p += 10)
        result += p[ s[--i] - '0' ];
    return result;
}