Jak to się nazywa, gdy zmienia się czas wykonania funkcji Big O funkcji [zamknięte]

Powiedzmy, że mam funkcję sortującą bazę danych w O(n^2)czasie. Chcę zająć się refaktoryzacją, aby O(n log(n))działała na czas, a robiąc to, zmienię podstawowy sposób działania operacji, zachowując równoważne wartości zwracane i dane wejściowe.

Jak nazywam to działanie refaktoryzacyjne?

„Przyspieszanie-ifying” nie wydaje się całkiem właściwe, ponieważ możesz przyspieszyć działanie algorytmu bez zmiany dużej prędkości O, przy której się wykonuje.

„Upraszczanie” również nie wydaje się właściwe.

Jak nazywam tę aktywność?

Aktualizacja

Najlepsza odpowiedź, jaką mogłem znaleźć, to zmniejszenie złożoności czasu asympotycznego.

Zazwyczaj nazywa się to „optymalizacją wydajności” , ale nie nazwałbym tego „refaktoryzacją”, ponieważ termin ten zwykle odnosi się do zmian w kodzie, które nie zmieniają jego widocznego zachowania . A zmiana w Big-O jest zdecydowanie czymś, co nazwałbym widoczną zmianą.

robiąc to, zmienię podstawowy sposób działania operacji

W takim przypadku optymalizacja polega na przepisaniu tej funkcji. Nie każda optymalizacja, nawet jeśli zmienia „Big-O”, jest koniecznie przeróbką, czasem tylko niewielkie zmiany są konieczne do osiągnięcia takiej poprawy, ale nawet wtedy niechętnie używam do tego terminu „refaktoryzacja”, ponieważ ma tendencję do dawania złego wrażenia na temat charakteru zmiany.

EDYCJA: Sprawdziłem listę refaktoryzacji Fowlera , a wśród tych ~ 100 nazwanych refaktoryzacji, ostatnia nazywa się „Algorytmem zastępczym” . Jeśli więc weźmiemy to jako odniesienie kanoniczne, istnieje mały, szary obszar, w którym optymalizację opisanej formy można nazwać specjalnym rodzajem refaktoryzacji (ale IMHO nie jest typowym). Zauważ też, że celem Fowlera we wszystkich refaktoryzacjach była zawsze poprawa projektu, z naciskiem na łatwość konserwacji i ewolucję istniejącego kodu bez przepisywania go, i oczywiście nie optymalizację wydajności.

Nie wydaje mi się, aby istniał standardowy termin, ale powszechnie używany jest optymalizacja, ale poprawa , lub przyspieszenie byłoby również poprawne, wyjaśniając, że mówisz o zmianach kodu, a nie o zmianach sprzętowych.

Jak powiedzieli inni, „optymalizacja” to ogólny termin na poprawę wydajności algorytmu. Jednak optymalizacja często oznacza poprawę stałych czynników. Gdybym chciał zwięźle, ale wyraźnie stwierdzić, że zmniejszyłem złożoność asymptotyczną (czasową), powiedziałbym, że „poprawiłem wydajność asymptotyczną”. Czasami ludzie opisują to jako „poprawę skalowania”, ale jest to obecnie szczególnie dwuznaczne.

Ostrzeżenie : Zmniejszenie asymptotycznej złożoności czasu niekoniecznie jest tym samym, co optymalizacja w kontekście praktycznym . Często używane są asymptotycznie nieoptymalne algorytmy, ponieważ w zakresie danych wejściowych program faktycznie jest narażony na mniej optymalne algorytmy działające lepiej.

Będzie zależał od kontekstu.

„Naprawianie kwadratowego błędu wydajności środowiska uruchomieniowego” jest zwykle tym, co widzę. Jednak to, czy należy to naprawić (zmiana kodu), zależy od kontekstu.

Należy pamiętać, że bazy danych zapewniają wiele narzędzi zwiększających złożoność czasu. Na przykład, aby uzyskać najlepsze wyniki N z bazy danych, po prostu to powiedz. Podczas przekształcania niewydajnego kludge we wbudowane zoptymalizowane wywołanie wyjaśnienie wydaje się zbędne.

Powód, dla którego uważam algorytm z kwadratowym środowiskiem wykonawczym, aby zasługiwał na przegląd kodu (dyskusja), jest nie tyle dlatego, że jest wolny (powolny jest względny; kwadratowy jest szybki w porównaniu do wykładniczego), ale dlatego, że ludzka intuicja (np. Twoi klienci lub inni programiści) są wewnętrznie niewygodni dzięki funkcji oprogramowania, która odbiega zbyt daleko od liniowego czasu działania, ze względu na mieszanie oczekiwań z życia codziennego.

Wiele skarg klientów dotyczących wydajności oprogramowania można podzielić na dwie kategorie:

• Cały system (oprogramowanie i sprzęt) został określony na podstawie szacowanego zużycia. W zeszłym tygodniu wszystko działa dobrze, pewna funkcjonalność zajęła mniej niż 5 sekund. W tym tygodniu po zainstalowaniu aktualizacji ta sama funkcja trwa dłużej niż 1 minutę.

  • Jest to porównanie z poprzednio testowaną wydajnością. Klient utrzymuje przyszłe wyniki w absolutnej mierze ludzkiej skali czasowej (od sekund do minuty).

• Przesłałem do systemu 100 zleceń. Dlaczego przetwarzanie zajmuje 400 razy więcej czasu niż jedno zadanie?

  • Klient oczekuje, że czas przetwarzania będzie liniowy. W rzeczywistości klient nie może zrozumieć ani zaakceptować faktu, że istnieją zadania wolniejsze niż liniowe.

Z tego powodu klient uzna czas wykonania za błąd, jeśli oba są prawdziwe:

• Wolniej niż liniowo
• Zauważalne (tzn. Mieszczą się w ludzkim przedziale czasu (dłuższym niż sekundy lub minuty) przy typowych rozmiarach zadań)

Uzasadnione argumenty wyjaśniające, że kwadratowy algorytm uruchomieniowy nie stanowi problemu (tzn. Nie zasługuje na zmianę kodu):

• Rozmiar zadania zwykle obsługiwanego przez tę kwadratową funkcję środowiska wykonawczego jest nieco ograniczony
• Biorąc pod uwagę typowy zakres wielkości, rzeczywisty (bezwzględny) czas wykonania jest wciąż wystarczająco krótki, aby można go było odrzucić
• Jeśli użytkownik faktycznie próbuje wysłać zadanie, które jest wystarczająco duże, aby było zauważalne, użytkownik otrzyma komunikat ostrzegający o długim czasie działania
• Użytkownicy systemu są ekspertami, dlatego wiedzą, co robią. Na przykład użytkownicy interfejsu API powinni przeczytać drobny druk w dokumentacji interfejsu API.

Wiele algorytmów przydatnych w typowym tworzeniu aplikacji jest w rzeczywistości wolniejszych niż liniowe (głównie O (N log N), jak w sortowaniu), dlatego duże oprogramowanie faktycznie spróbuje obejść to, sortując tylko odpowiednią część danych lub użyj technik filtrowania histogramu (statystycznego), które osiągają podobny efekt.

Dotyczy to klientów oprogramowania, ale jeśli uważasz, że użytkownicy biblioteki oprogramowania lub funkcji API również są „klientami”, odpowiedź nadal będzie obowiązywać.

Jeśli oryginalny algorytm został poprawnie zaimplementowany (lub jakiekolwiek błędy, które nie są istotne), wówczas „zmiana algorytmu” lub „podstawienie algorytmu” , ponieważ takie zmiany oznaczają, że robisz to dokładnie; podstawienie algorytmu o różnej złożoności czasowej na poprzednio używany.

Jeśli złożoność poprzedniego czasu była spowodowana błędem w implementacji (np. Powiedzmy, że przypadkowo zresetowałeś punkt początkowy wewnętrznej pętli w sekwencji, aby to, co powinno być O (n), stało się O (n ² )), to „naprawiam” kwadratowy błąd kosztów ” lub podobny.

Nakładają się na siebie, w takim przypadku wpływ na kod jest taki sam, jeśli od początku wiadomo, że praca może być wykonana w czasie O (n), a czas O (n ² ) był błędem, lub jeśli najpierw celowo zaimplementowałeś go w czasie O (n ² ), a następnie zdałeś sobie sprawę, że nadal będzie działał poprawnie bez resetowania punktu początkowego, i w ten sposób zastąpiłeś algorytm O (n) dla O (n ² ).

Optymalizacja prędkości według rzędu / rzędów wielkości. Chociaż jest to matematycznie niepoprawny język, najlepiej oddaje ideę zmiany Zakonu.

Poprawiona skalowalność. słyszałem także.