Dlaczego przetwarzanie posortowanej tablicy trwa krócej niż nieposortowanej?
![Dlaczego przetwarzanie posortowanej tablicy trwa krócej niż nieposortowanej?](https://wykop.pl/cdn/c3397993/link_gHBXSKA4T5aSLiXwitqkzNfjcNxcdiK6,w300h194.jpg)
Prosty kod napisany w C++ (jak i Javie) wykonuje się znacznie szybciej w sytuacji gdy tablica danych zostanie wcześniej posortowana. Dlaczego? Świetny przykład jak działa i jak istotne jest przewidywanie rozgałęzień w procesorach, polecam przeczytać :)
- #
- #
- #
- #
- #
- 115
Komentarze (115)
najlepsze
Jeżeli zgadnie, przechodzi do kolejnej instrukcji. A przy posortowanych danych jest wysokie prawdopodobieństwo, że zgadnie.
Niżej autor wyjaśnienia prezentuje też sposób który działa równie szybko na posortowanych i nieposortowanych danych. Który w przypadku c++ działa równie szybko co przy posortowanych danych, a więc oszczędzamy czas, bo
@anonim1133: W zasadzie to jest temat na dłuższy wykład ;)
Można powiedzieć, że największym "wrogiem" dla procesorów są skoki warunkowe - bo zmuszają procesor do
@anonim1133: Ale skąd wie że się pomylił bądź nie? Bo jeśli wie jaki jest poprawny to po co ma zgadywać? ;) Domyślam się że zastosowałeś jakiś skrót myślowy, możesz to rozwinąć?
http://www.numberworld.org/misc_runs/pi-10t/details.html
if (data[c] >= 128)
sum += data[c];
zamieniło się w to
Zastanów się co robi
int t = (data[c] - 128) >> 31
. Jeśli data[c] jest większe lub równe 128 to wyjdzie tam liczba nieujemna (a więc bit znaku
Mingw 4.7.2 (win7 natywnie)
Sorted: 7.44
Unsorted:
Różnica jest ogromna. Myślałem, że w środowiskach dostosowanych pod GCC z automatu środowisko daje -g.
Co do czasów to nie wiem jakie powinny być, ale po prostu bez -g rzeczy się inaczej wykonują. Na bank to odczujesz w MSVC i pojemnikach z STLa, kompilując z GCC powinno być podobnie.