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

Liczenie inwersji jeszcze szybciej

Ostatnio zmodyfikowano 2020-05-02 00:36
Autor Wiadomość
Kinzoku99
Temat założony przez niniejszego użytkownika
Liczenie inwersji jeszcze szybciej
» 2020-05-01 00:03:20
Prosiłbym o sugestie jak przyspieszyć poniższy kod.
Kod jest poprawny, ma za zadanie liczyć inwersje w ciągu za pomocą MergeSort i wypisywać posortowaną tablicę, jednak działa za wolno o 0.06s w najgorszych przypadkach.
Jak widać zamieniłem cout i cin na printf i scanf ale nie podziałało.
Limit czasu to 3s

Dane:
n - długość ciągu, 1 <= n <= 300 000
a - ciąg
ai element, 1 <= ai <= 1 000 000
wszystkie elementy ciągu są różne

Kod:
C/C++
#include <cstdio>
#include <vector>
using namespace std;

void MergeSort( vector < int > & a, int p, int q, int & inw )
{
    if( p == q )
         return;
   
    int s =( p + q ) / 2;
    MergeSort( a, p, s, inw );
    MergeSort( a, s + 1, q, inw );
   
    vector < int > b( a.size(), 0 );
   
    int i = p;
    int j = s + 1;
    for( int k = p; k <= q; k++ )
    if( j > q ||( i <= s && a.at( i ) < a.at( j ) ) ) {
        b.at( k ) = a.at( i );
        i++; }
    else {
        b.at( k ) = a.at( j );
        if( i <= s )
             inw += s - i + 1;
       
        j++; }
   
    for( int k = p; k <= q; k++ )
         a.at( k ) = b.at( k );
   
}

int main()
{
    int n;
    int inw = 0;
    scanf( "%d", & n );
    vector < int > a( n, 0 );
    for( int i = 0; i < n; i++ )
         scanf( "%d", & a.at( i ) );
   
    MergeSort( a, 0, n - 1, inw );
    for( int i = 0; i < n; i++ )
         printf( "%d ", a.at( i ) );
   
    printf( "\n%d", inw );
    return 0;
}
P-176756
nanoant20
» 2020-05-01 08:08:04
sztuczki na wymuszanie wydajności, zawsze można się pokusić
std::endl
std::ios_base::sync_with_stdio
std::cin.tie

on nie używa <iostream>
@pekfos racja, moja wypowiedź jest off-topic, mea culpa, mea maxima culpa

P-176758
pekfos
» 2020-05-01 17:19:25
nanoant20: on nie używa <iostream>

C/C++
a.at( i )
at() nie jest równoznaczne z []. Przeprowadza dodatkowo sprawdzanie zakresu, które w tym wypadku jest całkowicie zbędne.

C/C++
MergeSort( a, p, s, inw );
MergeSort( a, s + 1, q, inw );

vector < int > b( a.size(), 0 );
Możesz tu zmniejszyć ilość alokacji pamięci o połowę, jeśli zaalokujesz bufor dla wywołań rekurencyjnych, zamiast zawsze alokować tylko na własny użytek.
P-176761
Kinzoku99
Temat założony przez niniejszego użytkownika
» 2020-05-02 00:36:07
pekfos dziękuje, o ile zamienienie at na [] zmieniło czas wykonywania nieznacznie to zmiana alokacji pamięci skróciła czas działania prawie 6-krotnie. dziękuję ;)
P-176773
« 1 »
  Strona 1 z 1