Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Ile razy wystąpiła dana liczba w tekście?

Ostatnio zmodyfikowano 2016-03-11 16:41
Autor Wiadomość
Kaikso
» 2016-03-08 23:15:16
Wszystko ale bez przesady. To należy umiejętnie stosować, a im częściej się do tego stosujesz tym lepszy kod piszesz.

Sprawdziłem dokładnie różnice w twoim i moim kodzie. Najpierw sprawdziłem czas działania programu (części właściwej kodu) wynik twój kod jest 2 razy wolniejszy. Potem skompilowałem oba programy do kodu w asemblerze za pomocą gcc i clang: mój miał około 250 instrukcji, a twój około 2000 instrukcji.

Ta różnica w większym projekcie może mieć naprawdę duże znaczenie.

I naprawdę warto się do tego stosować. ;)

Równie dobrze wszystko można pisać w mainie żeby unikać skoków, przesuwania ramki stosu itp. rzeczy ale czy to ma sens ?
Oczywiście że to nie ma sensu. Należy stosować różne techniki w zależności od sytuacji tak aby osiągnąć najkorzystniejsze wskaźniki dla: ilości kodu, czasu działania, użycia pamięci, rozmiaru programu, czytelności i łatwości pisania kodu. Przecież dlatego programy piszemy programy w C++, a nie asm-ie.
P-145772
Elaine
» 2016-03-09 00:22:10
W ten sposób kompilator podczas kompilacji main.cpp nie ma dostępu do wywoływanej funkcji więc nie może wykonać odpowiedniej optymalizacji bo funkcja test mogła by równie dobrze modyfikować zasoby zewnętrzne więc jest to owa „materializacja” się programu. Teraz dla prostej operacji dodawania, która mogła by być przetłumaczona na pojedynczą instrukcje procesora, zostanie wykonany szereg operacji najpierw przepisania argumentów do rejestrów, potem wywołania funkcji (zapisanie adresu powrotu i skoku), zapisanie ramki stosu na którą składa się kilka operacji, wykonania instrukcji warunkowych, wykonania działania, przywrócenie ramki stosu, powrotu z procedury (odczytanie adresu powrotu ze stosu i skok do niego).
Dziwne, bo u mnie main wygląda tak:
0000000000400790 <main>:
  400790:       48 83 ec 18             sub    $0x18,%rsp
  400794:       bf a0 12 60 00          mov    $0x6012a0,%edi
  400799:       48 8d 74 24 0c          lea    0xc(%rsp),%rsi
  40079e:       e8 8d ff ff ff          callq  400730 <std::istream::operator>>(int&)@plt>
  4007a3:       48 8d 74 24 08          lea    0x8(%rsp),%rsi
  4007a8:       bf a0 12 60 00          mov    $0x6012a0,%edi
  4007ad:       e8 7e ff ff ff          callq  400730 <std::istream::operator>>(int&)@plt>
  4007b2:       8b 74 24 0c             mov    0xc(%rsp),%esi
  4007b6:       03 74 24 08             add    0x8(%rsp),%esi
  4007ba:       bf c0 13 60 00          mov    $0x6013c0,%edi
  4007bf:       e8 1c ff ff ff          callq  4006e0 <std::ostream::operator<<(int)@plt>
  4007c4:       48 89 c7                mov    %rax,%rdi
  4007c7:       e8 74 ff ff ff          callq  400740 <std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)@plt>
  4007cc:       8b 74 24 0c             mov    0xc(%rsp),%esi
  4007d0:       2b 74 24 08             sub    0x8(%rsp),%esi
  4007d4:       bf c0 13 60 00          mov    $0x6013c0,%edi
  4007d9:       e8 02 ff ff ff          callq  4006e0 <std::ostream::operator<<(int)@plt>
  4007de:       48 89 c7                mov    %rax,%rdi
  4007e1:       e8 5a ff ff ff          callq  400740 <std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)@plt>
  4007e6:       8b 74 24 08             mov    0x8(%rsp),%esi
  4007ea:       bf c0 13 60 00          mov    $0x6013c0,%edi
  4007ef:       0f af 74 24 0c          imul   0xc(%rsp),%esi
  4007f4:       e8 e7 fe ff ff          callq  4006e0 <std::ostream::operator<<(int)@plt>
  4007f9:       48 89 c7                mov    %rax,%rdi
  4007fc:       e8 3f ff ff ff          callq  400740 <std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)@plt>
  400801:       8b 44 24 0c             mov    0xc(%rsp),%eax
  400805:       bf c0 13 60 00          mov    $0x6013c0,%edi
  40080a:       99                      cltd  
  40080b:       f7 7c 24 08             idivl  0x8(%rsp)
  40080f:       89 c6                   mov    %eax,%esi
  400811:       e8 ca fe ff ff          callq  4006e0 <std::ostream::operator<<(int)@plt>
  400816:       48 89 c7                mov    %rax,%rdi
  400819:       e8 22 ff ff ff          callq  400740 <std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)@plt>
  40081e:       8b 44 24 0c             mov    0xc(%rsp),%eax
  400822:       bf c0 13 60 00          mov    $0x6013c0,%edi
  400827:       99                      cltd  
  400828:       f7 7c 24 08             idivl  0x8(%rsp)
  40082c:       89 d6                   mov    %edx,%esi
  40082e:       e8 ad fe ff ff          callq  4006e0 <std::ostream::operator<<(int)@plt>
  400833:       48 89 c7                mov    %rax,%rdi
  400836:       e8 05 ff ff ff          callq  400740 <std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)@plt>
  40083b:       31 c0                   xor    %eax,%eax
  40083d:       48 83 c4 18             add    $0x18,%rsp
  400841:       c3                      retq
Kod nie jest idealny, bo dzielenie wystarczyłoby zrobić raz, ale przyczyną tego jest upośledzony interfejs standardowych strumieni, który uniemożliwia kompilatorowi zauważenie, że zmienne a i b nie są zmieniane przez operacje na std::cout. Niemniej, jest to identyczny kod wynikowy, jak ten, który powstaje z kodu używającego operacji arytmetycznych bezpośrednio.

Kompilatory obecnie potrafią odłożyć generowanie kodu na czas linkowania, bo wtedy widzą cały program lub bibliotekę, nie tylko pojedynczą jednostkę translacji. Wystarczy z tego skorzystać.
P-145775
michal11
» 2016-03-09 00:52:17
OK, potestowałem, mój program jest kilka razy wolniejszy od twojego, głównie przez istringstream (nawiasem mówiąc vector tam jest nie potrzebny ale może się przydać jeżeli ktoś chciałby coś jeszcze z tymi liczbami później robić, można dać ifa w getline i jakiś licznik i tez będzie dobrze), próbowałem go trochę przyśpieszyć ale zatrzymałem się na pisaniu własnej funkcji konwertującej string na int doszedłem do wniosku, że to nie ma sensu.
Mam tylko pytanie, co jeżeli przyjdzie klient i powie ci, że specyfikacja się zmieniła i teraz chce znaleźć wszystkie liczby z przedziału <250;300> albo 2 przedziały (np. <10;60> i <100;150>) jak dużo zmian w kodzie ty byś musiał zrobić a jak dużo ja ? A co jeżeli klient chce z tego zrobić, sparametryzowaną funkcję ?
P-145776
Kaikso
» 2016-03-10 20:57:52
Trochę spóźniona odpowiedź ale jest. Niestety nie miałem wcześniej możliwości.

@Alueril mógłbym wiedzieć jakim to magicznym sposobem skompilowałeś mój przykład bo u mnie main wygląda tak:

0000000000400936 <main>:
  400936: 55                   push   rbp
  400937: 48 89 e5             mov    rbp,rsp
  40093a: 48 83 ec 10          sub    rsp,0x10
  40093e: 64 48 8b 04 25 28 00 mov    rax,QWORD PTR fs:0x28
  400945: 00 00
  400947: 48 89 45 f8          mov    QWORD PTR [rbp-0x8],rax
  40094b: 31 c0                xor    eax,eax
  40094d: 48 8d 45 f0          lea    rax,[rbp-0x10]
  400951: 48 89 c6             mov    rsi,rax
  400954: bf 80 10 60 00       mov    edi,0x601080
  400959: e8 b2 fe ff ff       call   400810 <_ZNSirsERi@plt>
  40095e: 48 8d 45 f4          lea    rax,[rbp-0xc]
  400962: 48 89 c6             mov    rsi,rax
  400965: bf 80 10 60 00       mov    edi,0x601080
  40096a: e8 a1 fe ff ff       call   400810 <_ZNSirsERi@plt>
  40096f: 8b 4d f4             mov    ecx,DWORD PTR [rbp-0xc]
  400972: 8b 45 f0             mov    eax,DWORD PTR [rbp-0x10]
  400975: ba 00 00 00 00       mov    edx,0x0
  40097a: 89 ce                mov    esi,ecx
  40097c: 89 c7                mov    edi,eax
  40097e: e8 3a 01 00 00       call   400abd <_Z4testii6oper_e>
  400983: 89 c6                mov    esi,eax
  400985: bf a0 11 60 00       mov    edi,0x6011a0
  40098a: e8 11 fe ff ff       call   4007a0 <_ZNSolsEi@plt>
  40098f: be 30 08 40 00       mov    esi,0x400830
  400994: 48 89 c7             mov    rdi,rax
  400997: e8 84 fe ff ff       call   400820 <_ZNSolsEPFRSoS_E@plt>
  40099c: 8b 4d f4             mov    ecx,DWORD PTR [rbp-0xc]
  40099f: 8b 45 f0             mov    eax,DWORD PTR [rbp-0x10]
  4009a2: ba 01 00 00 00       mov    edx,0x1
  4009a7: 89 ce                mov    esi,ecx
  4009a9: 89 c7                mov    edi,eax
  4009ab: e8 0d 01 00 00       call   400abd <_Z4testii6oper_e>
  4009b0: 89 c6                mov    esi,eax
  4009b2: bf a0 11 60 00       mov    edi,0x6011a0
  4009b7: e8 e4 fd ff ff       call   4007a0 <_ZNSolsEi@plt>
  4009bc: be 30 08 40 00       mov    esi,0x400830
  4009c1: 48 89 c7             mov    rdi,rax
  4009c4: e8 57 fe ff ff       call   400820 <_ZNSolsEPFRSoS_E@plt>
  4009c9: 8b 4d f4             mov    ecx,DWORD PTR [rbp-0xc]
  4009cc: 8b 45 f0             mov    eax,DWORD PTR [rbp-0x10]
  4009cf: ba 02 00 00 00       mov    edx,0x2
  4009d4: 89 ce                mov    esi,ecx
  4009d6: 89 c7                mov    edi,eax
  4009d8: e8 e0 00 00 00       call   400abd <_Z4testii6oper_e>
  4009dd: 89 c6                mov    esi,eax
  4009df: bf a0 11 60 00       mov    edi,0x6011a0
  4009e4: e8 b7 fd ff ff       call   4007a0 <_ZNSolsEi@plt>
  4009e9: be 30 08 40 00       mov    esi,0x400830
  4009ee: 48 89 c7             mov    rdi,rax
  4009f1: e8 2a fe ff ff       call   400820 <_ZNSolsEPFRSoS_E@plt>
  4009f6: 8b 4d f4             mov    ecx,DWORD PTR [rbp-0xc]
  4009f9: 8b 45 f0             mov    eax,DWORD PTR [rbp-0x10]
  4009fc: ba 03 00 00 00       mov    edx,0x3
  400a01: 89 ce                mov    esi,ecx
  400a03: 89 c7                mov    edi,eax
  400a05: e8 b3 00 00 00       call   400abd <_Z4testii6oper_e>
  400a0a: 89 c6                mov    esi,eax
  400a0c: bf a0 11 60 00       mov    edi,0x6011a0
  400a11: e8 8a fd ff ff       call   4007a0 <_ZNSolsEi@plt>
  400a16: be 30 08 40 00       mov    esi,0x400830
  400a1b: 48 89 c7             mov    rdi,rax
  400a1e: e8 fd fd ff ff       call   400820 <_ZNSolsEPFRSoS_E@plt>
  400a23: 8b 4d f4             mov    ecx,DWORD PTR [rbp-0xc]
  400a26: 8b 45 f0             mov    eax,DWORD PTR [rbp-0x10]
  400a29: ba 04 00 00 00       mov    edx,0x4
  400a2e: 89 ce                mov    esi,ecx
  400a30: 89 c7                mov    edi,eax
  400a32: e8 86 00 00 00       call   400abd <_Z4testii6oper_e>
  400a37: 89 c6                mov    esi,eax
  400a39: bf a0 11 60 00       mov    edi,0x6011a0
  400a3e: e8 5d fd ff ff       call   4007a0 <_ZNSolsEi@plt>
  400a43: be 30 08 40 00       mov    esi,0x400830
  400a48: 48 89 c7             mov    rdi,rax
  400a4b: e8 d0 fd ff ff       call   400820 <_ZNSolsEPFRSoS_E@plt>
  400a50: b8 00 00 00 00       mov    eax,0x0
  400a55: 48 8b 55 f8          mov    rdx,QWORD PTR [rbp-0x8]
  400a59: 64 48 33 14 25 28 00 xor    rdx,QWORD PTR fs:0x28
  400a60: 00 00
  400a62: 74 05                je     400a69 <main+0x133>
  400a64: e8 97 fd ff ff       call   400800 <__stack_chk_fail@plt>
  400a69: c9                   leave 
  400a6a: c3                   ret

Kompilatory obecnie potrafią odłożyć generowanie kodu na czas linkowania, bo wtedy widzą cały program lub bibliotekę, nie tylko pojedynczą jednostkę translacji. Wystarczy z tego skorzystać.
Mówisz o kompilatorze czy linkerze?

Hymm, po twoim poście postanowiłem zmienić mój nawyk, bo i tak on nie miał sensu skoro we wszystkim wyręczy mnie kompilator!
P-145879
Elaine
» 2016-03-10 21:58:44
mógłbym wiedzieć jakim to magicznym sposobem skompilowałeś mój przykład
Przecież napisałem: poprosiłem kompilator o generowanie kodu na etapie linkowania.

Kompilatory obecnie potrafią odłożyć generowanie kodu na czas linkowania, bo wtedy widzą cały program lub bibliotekę, nie tylko pojedynczą jednostkę translacji. Wystarczy z tego skorzystać.
Mówisz o kompilatorze czy linkerze?
O kompilatorze. Ponieważ gołego linkera rzadko kiedy się używa, przekazując pliki obiektowe zamiast tego do kompilatora, kompilator może sprawdzić, czy w tych plikach są dane, których potrzebuje do generowania kodu na etapie linkowania i z nich skorzystać. W GCC na przykład odpowiedzialne za to jest collect2.

Linker może, ale nie musi, brać w tym udziału; najczęściej stosowanym w praktyce rozwiązaniem jest użycie przez kompilator pluginu do linkera, a jeśli tak się nie da, to działa to tak, jak wyżej.
P-145883
Kaikso
» 2016-03-10 22:10:56
Okey teraz rozumiem.
Ale w różnych projektach dość często widzę zwykłe ld w plikach makefile.
P-145884
mokrowski
» 2016-03-10 23:39:45
E tam.. szybsze.. Wąskim gardłem będzie i tak plik a w docelowym programie "stado plików". Z premedytacją rozwiązanie bez dotykania "myślenia w C". Nie mierzyłem wydajności bo chciałem pomęczyć szablony i algorytmy. Jedyny cel: reużywalność kodu. Jest na poziomie ~90% :-)
Kompilować zgodnie ze standardem C++14:
C/C++
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

class LineString
    : public string
{
public:
    friend auto & operator >>( istream & is, LineString & lin )
    {
        return getline( is, lin );
    }
};

template < char TSeparator >
class SeparatorValString
    : public string
{
public:
    friend auto & operator >>( istream & is, SeparatorValString & com )
    {
        return getline( is, com, TSeparator );
    }
};

template < typename T >
auto count_values_in_file( ifstream & file, T min_inclusive, T max_inclusive )
{
    using istrLine = istream_iterator < LineString >;
    using istrComma = istream_iterator < SeparatorValString < ',' >>;
   
    auto counter = T();
   
    for_each( istrLine( file ), istrLine(),
    [ & counter, & min_inclusive, & max_inclusive ]( const auto & line ) {
        istringstream linestream( line );
        counter += count_if( istrComma( linestream ), istrComma(),
        [ & min_inclusive, & max_inclusive ]( const auto & strval ) {
            // TODO: Tu najlepiej użyć lexical_cast z Boost, ale zostawię do potencjalnej
            // optymalizacji jak ktoś będzie chciał robić wybór konwersji w zal. od typu.
            auto value = stol( strval );
            return( min_inclusive <= value ) &&( max_inclusive <= value );
        }
        );
    }
    );
    return counter;
}

int main()
{
    long counter;
    {
        ifstream file( "data.txt" );
        if( file.fail() )
        {
            cerr << "Błąd otwarcia pliku" << endl;
            return 1;
        }
        counter = count_values_in_file( file, 10L, 20L );
    }
    cout << "W pliku jest " << counter
    << " wartości z zakresu [10, 20]." << endl;
}
P-145886
Kaikso
» 2016-03-10 23:48:34
No to ja dla porównania dam kompleksowy program (po za takimi rzeczami jak np. sprawdzanie czy liczba nie wychodzi po za zakres).

C/C++
#include <iostream>
#include <fstream>
#include <string>
#include <locale>
#include <map>

class SetOfNumber final
{
private:
    struct range
    {
        long double vmin, vmax;
        range * next;
    } first;
   
public:
    SetOfNumber() = delete;
    SetOfNumber( const long double & vmin, const long double & vmax );
    ~SetOfNumber();
   
    bool fill( const long double & val ) const;
    void add_range( const long double & vmin, const long double & vmax );
   
private:
    const range * get_range( const long double & val ) const;
};

bool request_range( long double & vmin, long double & vmax );

int main()
{
    std::string fname;
    std::cout << "Proszę podać nazwę pliku do analizy: ";
    std::cin >> fname;
   
    std::ifstream input( fname );
    if( input.fail() )
    {
        std::cerr << "Wystąpił błąd podczas próby otwarcia pliku." << std::endl;
        return - 1;
    }
   
    long double vmin, vmax;
    bool complet = request_range( vmin, vmax );
    SetOfNumber test( vmin, vmax );
   
    while( !complet )
    {
        complet = request_range( vmin, vmax );
        test.add_range( vmin, vmax );
    }
   
    std::map < long double, size_t > count;
    while( !input.eof() )
    {
        std::string line;
        std::getline( input, line );
       
        for( size_t i = 0; line[ i ] != '\0'; i++ ) if(( line[ i ] >= '0' && line[ i ] <= '9' ) || line[ i ] == '-' )
        {
            long double val = 0;
           
            bool sign = false;
            if( line[ i ] == '-' ) sign = true, i++;
           
            while( line[ i ] >= '0' && line[ i ] <= '9' )
                 val = val * 10 + line[ i++ ] - '0';
           
            if( line[ i ] != '.' && std::tolower( line[ i ] ) != 'e' )
            {
                val = sign ? - val: val;
                if( test.fill( val ) ) count[ val ] ++;
               
                continue;
            }
           
            if( line[ i ] == '.' ) for( long double r = 0.1; line[ ++i ] >= '0' && line[ i ] <= '9'; r /= 10 )
                 val +=( line[ i ] - '0' ) * r;
           
            if( std::tolower( line[ i ] ) != 'e' )
            {
                val = sign ? - val: val;
                if( test.fill( val ) ) count[ val ] ++;
               
                continue;
            }
           
            bool esign = false;
            if( line[ ++i ] == '-' ) esign = true, i++;
           
            size_t e = 0;
            while( line[ i ] >= '0' && line[ i ] <= '9' )
                 e = e * 10 + line[ i++ ] - '0';
           
            if( esign ) while( e-- ) val /= 10;
            else while( e-- ) val *= 10;
           
            if( test.fill( val ) ) count[ val ] ++;
           
        }
    }
   
    for( auto & current: count )
         std::cout << "Liczba " << current.first << " występuje " << current.second << " razy." << std::endl;
   
    return 0;
}

bool request_range( long double & vmin, long double & vmax )
{
    std::cout << "Proszę podać minimalną wartość zakresu do przeszukiwania: "; std::cin >> vmin;
    std::cout << "Proszę podać maksymalną wartość zakresu do przeszukiwania: "; std::cin >> vmax;
   
    do
    {
        std::string response;
        std::cout << "[Tak/Nie] Czy dodać kolejny zakres? "; std::cin >> response;
        for( char & c: response ) c = std::tolower( c );
       
        if( response == "t" || response == "tak" ) return false;
       
        if( response == "n" || response == "nie" ) return true;
       
    } while( true );
   
}

SetOfNumber::SetOfNumber( const long double & vmin, const long double & vmax )
    : first
{ vmin, vmax, nullptr }
{ }

SetOfNumber::~SetOfNumber()
{
    while( first.next != nullptr )
    {
        range * tmp = first.next;
        first.next = tmp->next;
        delete tmp;
    }
}

const SetOfNumber::range * SetOfNumber::get_range( const long double & val ) const
{
    const range * current = & first;
   
    do
    {
        if( val >= current->vmin && val <= current->vmax )
             return current;
       
        current = current->next;
    } while( current != nullptr );
   
    return nullptr;
}

bool SetOfNumber::fill( const long double & val ) const
{
    return get_range( val ) == nullptr ? false
        : true;
}

void SetOfNumber::add_range( const long double & vmin, const long double & vmax )
{
    range * left = const_cast < range * >( get_range( vmin ) );
    range * right = const_cast < range * >( get_range( vmax ) );
   
    if( left != nullptr )
    {
        if( left == right ) return;
       
        if( right != nullptr )
        {
            if( right != & first )
            {
                left->vmax = right->vmax;
                delete right;
            }
            else
            {
                right->vmax = left->vmax;
                delete left;
            }
        }
        else left->vmax = vmax;
       
    }
    else if( right != nullptr ) right->vmin = vmin;
    else first.next = new range { vmin, vmax, first.next };
}

Widać znaczny wzrost ilości kodu, ale za to jest skalowalny i w miarę zoptymalizowany ;)
P-145887
1 2 « 3 » 4
Poprzednia strona Strona 3 z 4 Następna strona