Liczenie inwersji jeszcze szybciej
Ostatnio zmodyfikowano 2020-05-02 00:36
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: #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; }
|
|
nanoant20 |
» 2020-05-01 08:08:04 |
|
pekfos |
» 2020-05-01 17:19:25 nanoant20: on nie używa <iostream> at() nie jest równoznaczne z []. Przeprowadza dodatkowo sprawdzanie zakresu, które w tym wypadku jest całkowicie zbędne. 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. |
|
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ę ;) |
|
« 1 » |