anfängerprobleme mit sprintf

Ethon schrieb:

Hacker schrieb:

Tja, Ethon, du bist ein Genius.

Lässt sich doch fixen. Bei 2x Speedup sollte das danach immer noch deutlich schneller sein. Mal ausprobieren.

Denkst du, dass, wenn du's an ISO/IEC schickst, sie es dann in den nächsten aufnehmen?

Ethon

template<typename CharT, unsigned Base>
    std::basic_string<CharT> to_string(unsigned value)
    {
        static_assert(Base <= 16, "Unsupported Base");

        CharT const lookup[] =
        {
            CharT('0'), CharT('1'), CharT('2'), CharT('3'),
            CharT('4'), CharT('5'), CharT('6'), CharT('7'),
            CharT('8'), CharT('9'), CharT('A'), CharT('B'),
            CharT('C'), CharT('D'), CharT('E'), CharT('F')
        };

        std::array<CharT, std::numeric_limits<unsigned>::digits> buffer;
        auto iter = buffer.rbegin();
        while(value > Base)
        {
            *iter = lookup[value % Base];
            ++iter;
            value /= Base;
        }

        *iter = lookup[value];
        return std::basic_string<CharT>(&(*iter), buffer.end());
    }

Gefixt und noch schneller geworden.

Zum Konvertieren von 10.000.000 rand Werten braucht meine Funktion

real 0m11.909s
user 0m11.905s
sys 0m0.000s

und std::to_string

real 0m26.853s
user 0m26.838s
sys 0m0.004s

Also, was ist der Unterschied?

Ethon!! Welchen Compiler benutzt du? Alter, mein GCC 4.7 meckert, dass to_string nicht deklariert ist (obwohl ich string implementiere). Was soll ich nur tun :schluchz:

Ethon

Gcc 4.6.1

Kompiliert mit:

g++ -o test -O3 -march=native -std=c++0x test.cpp

Für std::to_string brauchst du <string> und den C++11 Switch.

Ethon schrieb:

Gcc 4.6.1

Kompiliert mit:

g++ -o test -O3 -march=native -std=c++0x test.cpp

Für std::to_string brauchst du <string> und den C++11 Switch.

Funktioniert immer noch nicht.

Swordfish

Ethon schrieb:

return std::basic_string<CharT>(&(*iter), buffer.end());

Bist Du sicher, daß basic_string diesen c-tor haben muss?

Ethon

[quote="Swordfish"]

Ethon schrieb:

return std::basic_string<CharT>(&(*iter), buffer.end());
Bist Du sicher, daß basic_string diesen c-tor haben muss?

Jeder Container lässt sich garantiert mit einem Inputiteratorenpaar konstruieren, bin mir zu 100% sicher dass es auch für std::basic_string vorgeschrieben ist, man findet ihn auch in jeder C++ Referenz.

Incocnito

Ich hab auch noch eine Idee:

#include <algorithm>

std::string to_hex_string(unsigned value)
{
    static std::string hex;
    hex.clear();
    do
    {
        if(value%16 >= 0 && value%16 < 10)
            hex += value%16 + '0';
        else if(value%16 > 9 && value%16 < 17)
            hex += value%16 + 55;
    } while(value /= 16);
    std::reverse(hex.begin(), hex.end());
    return hex;
}

Swordfish: 414.683
Hacker: 1317.21
Meine: 284.66

Außerdem braucht bei mir

std::string to_hex_string(unsigned value)
{
    char buffer[sizeof(value) * 2 + 1];
    sprintf(buffer,"%x", value);
    return std::string(buffer);
}

sogar mit 2370.08 deutlich länger (mit -O3)...

Swordfish

Aaaaahh! Jetz' seh' ich's erst, iter ist auto ... da kann ich mein msvc stecken lassen ... *umschreibengeh'*

Incocnito schrieb:

Außerdem braucht bei mir [sprintf] sogar mit 2370.08 deutlich länger (mit -O3)...

Grenzt an unmöglichkeit. Maschine?

// edit:

Swordfish: 594.549
Hacker:    1022.05
Ethon:     176.339
Ethon 2:   34.5288
Ethon 3:   49.962
Incocnito: 71.5127

// edit: Ethon 3 mit return std::basic_string<CharT, std::char_traits< CharT > >( iter.base( ), buffer.end( ) );

camper

Swordfish schrieb:

Ethon schrieb:
return std::basic_string<CharT>(&(*iter), buffer.end());
Bist Du sicher, daß basic_string diesen c-tor haben muss?

Er meint sicher

return std::basic_string<CharT>(iter.base(), buffer.end());

Incocnito

Ich hab Code::Blocks mit dem GCC 4.6.2 auf Windows 7 64 bit, duo 2.3ghz.
Das hier kompiliert
Und bekomm als Ausgabe
Ethon: ~2300
Ist irgendwie komisch.

Michael E.

[quote="Ethon"]

Swordfish schrieb:

Ethon schrieb:
return std::basic_string<CharT>(&(*iter), buffer.end());
Bist Du sicher, daß basic_string diesen c-tor haben muss?
Jeder Container lässt sich garantiert mit einem Inputiteratorenpaar konstruieren, bin mir zu 100% sicher dass es auch für std::basic_string vorgeschrieben ist, man findet ihn auch in jeder C++ Referenz.

Nur ist das da kein Inputiteratorenpaar.

Ethon

[quote="Michael E."]

Ethon schrieb:

Swordfish schrieb:
Ethon schrieb:
return std::basic_string<CharT>(&(*iter), buffer.end());
Bist Du sicher, daß basic_string diesen c-tor haben muss?
Jeder Container lässt sich garantiert mit einem Inputiteratorenpaar konstruieren, bin mir zu 100% sicher dass es auch für std::basic_string vorgeschrieben ist, man findet ihn auch in jeder C++ Referenz.
Nur ist das da kein Inputiteratorenpaar.

Ein Zeiger unterstützt alle Operationen, die ein Inputiterator können muss, ist von daher also kompatibel.

Swordfish: 594.549
Hacker:    1022.05
Ethon:     176.339
Ethon 2:   34.5288
Ethon 3:   49.962
Incocnito: 71.5127

Interessant dass bei dir die dritte Version langsamer ist, beim GCC war sie schneller.

Er meint sicher

return std::basic_string<CharT>(iter.base(), buffer.end());

Was es nicht alles gibt, danke.

Michael E.

Ethon schrieb:

Ein Zeiger unterstützt alle Operationen, die ein Inputiterator können muss, ist von daher also kompatibel.

template<class InputIterator>
basic_string(InputIterator begin, InputIterator end,
const Allocator& a = Allocator());

Also müssen die beiden Parameter denselben Typ haben. Da Paragraph 21.4.5 sagt, dass string::iterator implementation defined ist mit Bezug auf Paragraph 23.2, darfst du dann die Stelle suchen, an der steht, dass string::iterator einen nicht expliziten einstelligen Konstruktor mit einem Pointer als Parameter hat (keine Ahnung, obs die Garantie gibt, bin aber zu faul zum Suchen).

Incocnito

Lustig. Wenn ich diesen Code hier kompiliere, erhalte ich folgende Ergebnisse unterm GCC (-O3):

Swordfish: 418.613
Hacker: 1298.35
Ethon: 2315.44
Inco: 287.326

Und wenn ich das ganze mit VS-2010 Express mache, hing mein Computer erstmal ne ganze Weile komplett, und dann hatte ich diese Ausgabe:

Swordfish: 18503.3
Hacker: 36503.5
Ethon: 5813.38
Inco: 12065.5

Kann mir das jemand erklären

Ethon

Also müssen die beiden Parameter denselben Typ haben.

Haben sie ja, 2x char*.

Da Paragraph 21.4.5 sagt, dass string::iterator implementation defined ist mit Bezug auf Paragraph 23.2, darfst du dann die Stelle suchen, an der steht, dass string::iterator einen nicht expliziten einstelligen Konstruktor mit einem Pointer als Parameter hat (keine Ahnung, obs die Garantie gibt, bin aber zu faul zum Suchen).

Wieso string::iterator? Der Konstruktor ist nicht umsonst templated, damit man jeden anderen Iterator übergeben kann, der dereferenziert einen passenden Char-Typ zurückgibt. Ein String-Iterator wird hier nie konstruiert.
Dank iterator_traits etc sind du unterschiede zwischen "richtigen" Iteratoren und Pointern nicht existent.

Swordfish

Incocnito schrieb:

Und wenn ich das ganze mit VS-2010 Express mache, hing mein Computer erstmal ne ganze Weile komplett, und dann hatte ich diese Ausgabe: [...]

Release kompilieren, von hand starten.

Michael E.

Sorry, buffer ist ja ein std::array und kein std::string. Die Argumentation bleibt aber dieselbe: buffer.end() ist ein array::iterator, &(*iter) ein Pointer, beide müssen denselben Typ haben.

Ethon

Michael E. schrieb:

Sorry, buffer ist ja ein std::array und kein std::string. Die Argumentation bleibt aber dieselbe: buffer.end() ist ein array::iterator, &(*iter) ein Pointer, beide müssen denselben Typ haben.

boost::array implementiert den Iterator als Pointer, da dachte ich mal die std Implementierung macht das genauso. Was sagt der Standard dazu? Implementation defined?

Im Zweifelsfall muss man es halt korrekt machen, mit der Lösung von Camper, also Base() auf den Reverse Iterator aufrufen.

camper

Habe zum Spaß auch eine Version geschrieben

#include <iostream>
#include <algorithm>
#include <array>
#include <limits>
#include <sstream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <ctime>

std::string to_hex_string_swordfish( unsigned value ) {
    static std::ostringstream ss;
    ss.clear( );
    ss.str( "" );
    ss << std::hex << value;
    return ss.str( );
}

std::string to_hex_string_hacker( unsigned value)
{
    std::ostringstream stream;
    stream << std::hex << value;
    return stream.str();
}

std::string to_hex_string_ethon(unsigned value)
{
    char buffer[sizeof(value) * 2 + 1];
    sprintf(buffer,"%x", value);
    return std::string(buffer);
}

std::string to_hex_string_ethon2(unsigned value)
{
    typedef std::string string_type;
    typedef char CharT;
    string_type result(sizeof(value) * 2, 0);
    typename string_type::reverse_iterator iter = result.rbegin();
    while(value > 16)
    {
        unsigned cur = value % 16;
        *iter = cur < 10 ? CharT('0') + cur : CharT('A') + cur - 10;
        ++iter;
        value /= 16;
    }

    *iter = value < 10 ? CharT('0') + value : CharT('A') + value - 10;
    return result;
}

std::string to_hex_string_ethon3(unsigned value)
{
    typedef char CharT;
    const unsigned Base = 16;
    CharT const lookup[] =
        {   CharT('0'), CharT('1'), CharT('2'), CharT('3'), CharT('4'),
            CharT('5'), CharT('6'), CharT('7'), CharT('8'), CharT('9'),
            CharT('A'), CharT('B'), CharT('C'), CharT('D'), CharT('E'),
            CharT('F') };

    typedef std::basic_string<CharT> string_type;
    string_type result(sizeof(value) * 2, 0);
    typename string_type::reverse_iterator iter = result.rbegin();
    while(value > Base)
    {
        *iter = lookup[value % Base];
        ++iter;
        value /= Base;
    }

    *iter = lookup[value];
    return result;
}
std::string to_hex_string_ethon4(unsigned value)
{
    typedef char CharT;
    const unsigned Base = 16;

    CharT const lookup[] =
    {
        CharT('0'), CharT('1'), CharT('2'), CharT('3'),
        CharT('4'), CharT('5'), CharT('6'), CharT('7'),
        CharT('8'), CharT('9'), CharT('A'), CharT('B'),
        CharT('C'), CharT('D'), CharT('E'), CharT('F')
    };

    std::array<CharT, std::numeric_limits<unsigned>::digits> buffer;
    auto iter = buffer.rbegin();
    while(value > Base)
    {
        *iter = lookup[value % Base];
        ++iter;
        value /= Base;
    }

    *iter = lookup[value];
    return std::basic_string<CharT>(iter.base(), buffer.end());
}
std::string to_hex_string_incognito(unsigned value)
{
    static std::string hex;
    hex.clear();
    do
    {
        if( value%16 < 10)
            hex += value%16 + '0';
        else if(value%16 > 9 && value%16 < 17)
            hex += value%16 + 55;
    } while(value /= 16);
    std::reverse(hex.begin(), hex.end());
    return hex;
}
template <typename T>
struct identity
{

    typedef T type;
};
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...>>
    : identity<index_list<(i+1)..., 0>> {};

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

template <typename T, std::size_t... i>
std::string to_hex_string_camper_(T value, index_list<i...>)
{
    const char lut[] = "0123456789abcdef";
    return std::string{ lut[(value>>(4*i))%16]... };
}
std::string to_hex_string_camper(unsigned value)
{
    return to_hex_string_camper_(value,make_index_list<(std::numeric_limits<unsigned>::digits+3)/4>::type());
}

#define MEASSURE( name )                                            \
    {                                                               \
        std::clock_t start = std::clock();                          \
        for( size_t i = 0; i < 2000000; ++i )                       \
            result = to_hex_string_##name( rand() );             \
        std::clock_t end = std::clock();                            \
        double elapsed = ( end - start ) / frequency;                      \
        std::cout << #name << '\t' << to_hex_string_##name(0x12345678) << '\t' << elapsed << std::endl; \
    }
int main()
{
    std::cout << RAND_MAX << std::endl;
    std::srand( static_cast< unsigned >( std::time( 0 ) ) );
    std::string result;
    double frequency = CLOCKS_PER_SEC;
    MEASSURE( swordfish );
    MEASSURE( hacker );
    MEASSURE( ethon );
    MEASSURE( ethon2 );
    MEASSURE( ethon3 );
    MEASSURE( ethon4 );
    MEASSURE( incognito );
    MEASSURE( camper );
}

Mit -march=native (atom,64bit) und -O3 erhalte ich

swordfish	12345678	2.14
hacker	12345678	9.96
ethon	12345678	1.95
ethon2	12345678	0.98
ethon3	12345678	0.97
ethon4	2345678	0.81
incognito	12345678	1.45
camper	12345678	0.8

mit gcc-4.7, mit gcc-4.6.2 dagegen

swordfish	12345678	2.81
hacker	12345678	13.38
ethon	12345678	2.29
ethon2	12345678	1.28
ethon3	12345678	1.27
ethon4	2345678	1.01
incognito	12345678	1.73
camper	12345678	1.13

Der große Unterschied ist doch etwas überraschend.
gcc-4.5.3

swordfish	12345678	2.74
hacker	12345678	12.91
ethon	12345678	2.2
ethon2	12345678	1.24
ethon3	12345678	1.2
ethon4	2345678	1.02
incognito	12345678	1.68
camper	12345678	1.1