Porównanie metod iteracji: liczba iteracji vs. czas procesora

Porównuję dwie iteracyjne metody odwracania losowych macierzy kwadratowych. Ponieważ macierze są losowe, każdy przypadek testowy wymaga zarówno różnych ilości iteracji, jak i różnych czasów, które upłynęły. Moje pytanie, oprócz średniego czasu procesora, to średnia wartość iteracji pobranych przez obie metody, przydatne informacje do porównania metod.

performance benchmarking

— srijan
źródło

Przeredagowałem twoje pytanie, aby, mam nadzieję, wyjaśnić. Upewnij się, że nie zmieniłem twojego znaczenia w żaden sposób.

— Godric Seer,

@GodricSeer Twoja edycja poprawiła moje pytanie. Dzięki

— srijan,

Odpowiedzi:

Ogólnie rzecz biorąc, obie metody porównań wydajności mają swoje miejsce.

Porównywanie czasu procesora jest w pewnym sensie najciekawszą miarą, ponieważ pod koniec dnia naprawdę interesuje Cię, która z metod jest szybsza. (Ale upewnij się, że kryteria zakończenia są porównywalne; np. Obie metody dają przybliżenie z tą samą dokładnością). Wadą jest to, że mówi tylko, która metoda (a co ważniejsze, która implementacja ) jest szybsza na komputerze, na którym przeprowadziłeś testy. Nie ma gwarancji, że inna maszyna z inną architekturą lub oprogramowaniem wybierze tego samego zwycięzcę.
Z drugiej strony porównywanie liczb iteracyjnych jest niezależne od maszyny, ale może wprowadzać w błąd, jeśli obie metody mają bardzo różne iteracje - w tym przypadku metoda o mniejszej, ale droższej iteracji może nie być preferowana (np. Metody optymalizacji Newtona i gradientu jeśli potrzebujesz tylko bardzo niskiej dokładności).

Tak więc, sensowne jest podanie obu liczb [1], i często widziałem to w publikacjach. Istnieje również trzecia opcja:

Porównywanie liczby podstawowych operacji . Jeśli obie iteracje składają się z tego samego rodzaju odpowiednio drogiej operacji, ale wymagają innej liczby (być może nawet nie tej samej liczby w każdej iteracji), warto policzyć całkowitą liczbę tych operacji. W twoim przypadku prawdopodobnym kandydatem byłoby mnożenie macierzy-wektor lub macierz-macierz.

[1] Zdecydowanie przedstawi statystyki w wielu przebiegach; jeśli wykażesz środki, nie zapomnij również o standardowych odchyleniach.

— Christian Clason
źródło

Nie bierz środków! Jeśli masz wystarczającą liczbę punktów testowych z przypadkowymi danymi wejściowymi, wykreśl rozkład.

— Bill Barth

@BillBarth - dobra uwaga, chociaż nie zawsze jest to możliwe; ale podawanie odchyleń standardowych wraz ze średnią powinno zawsze być możliwe. W rzeczywistości, które statystyki przedstawione w celu przedstawienia wyników wydają się doskonałym pytaniem uzupełniającym.

— Christian Clason,

@BillBarth Zrobiłeś dobry punkt. Ale używam kilku matryc testowych w kolejności rosnącej. W takich przypadkach nie jest możliwe wykreślenie rozkładu, ponieważ muszę wykreślić rozkłady dla wszystkich innych matryc testowych. Dlatego chciałem je podsumować. Dziękuję za komentarze.

— srijan

@srijan: Będziesz miał dane, powinieneś narysować dla siebie histogramy, gdziekolwiek możesz. Nie musicie publikować ich wszystkich, ale obiecuję wam, że wykres rozkładu pokaże więcej niż morze liczb lub tylko średnie kiedykolwiek.

— Bill Barth

Podałbym czas wykonania na iterację. Ponieważ każda matryca jest inna, możesz mieć inną liczbę iteracji z różnymi czasami wykonania. Wraz z tym, co powiedział @Cristian, przydatny byłby czas wykonania na iterację.

— jbcolmenares

Uważam, że liczba iteracji jest wprowadzającą w błąd metryką, ponieważ sugeruje „szybkość”, gdy tak nie jest. Prosty przykład porównania kilku różnych warunków wstępnych wykazujących tę różnicę można znaleźć tutaj: http://www.dealii.org/developer/doxygen/deal.II/step_6.html#Possabilitiesforextensions

— Wolfgang Bangerth
źródło

Dziękuję za odpowiedź. Nie jestem w stanie zrozumieć tej liczby wierszy „liczby iteracji jako wprowadzającej w błąd metryki, ponieważ sugeruje ona„ szybkość ”, gdy nie jest”. Przykład, który zasugerowałeś, jest dla mnie nieco trudny do zrozumienia.

— srijan

Mówię o tym, że często przedstawiamy „liczbę iteracji” jako równoważne z „zużytym czasem procesora”, co oznacza, że metoda wymagająca mniejszej liczby iteracji jest również szybsza. Ale to nieprawda, jak pokazują liczby, z którymi się łączyłem.

— Wolfgang Bangerth

Teraz w pełni zrozumiałem twój punkt widzenia. To samo zaobserwowałem przy metodzie Newtona do aproksymacji odwrotności macierzy kwadratowej. Ponieważ kolejność metody wzrasta, początkowo czas procesora, jak również liczba iteracji, zmniejszają się, ale wraz ze wzrostem kolejności, czas rozpoczęcia procesora rośnie, chociaż liczba iteracji maleje. Bardzo dziękuję za odpowiedź.

— srijan

W przypadku, gdy w innych odpowiedziach nie jest jasne, dla jakiej liczby iteracji korzystna jest duża argumentacja.

Nie jest to dobre dla prędkości bezwzględnej, ponieważ zależy to od średniego czasu na iterację, który może różnić się między metodami w dużej mierze.

Na przykład istnieje tendencja do ignorowania kosztu obliczania indeksów tablic, co może również stanowić dużą część czasu procesora.

DODANO: Ponadto, jak wskazałem gdzie indziej, za każde wywołanie tej metody zazwyczaj wiąże się koszt instalacji. Następnie, jeśli matryce zwykle nie są bardzo duże, ten koszt instalacji może sam stanowić znaczną część czasu procesora (tak, że usunięcie go spowodowałoby dużą różnicę w szybkości).

— Mike Dunlavey
źródło