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.
complexity
big-o
Zaklinacz kodów
źródło
źródło
O(log(n))
czasie również działa wO(n^2)
czasie. ZnaczenieO(n^2)
„nie rośnie szybciej niż kwadratowe”. Prawdopodobnie miałeś na myśli Theta (log (n)), co oznacza „rośnie tak szybko jaklog(n)
”. en.wikipedia.org/wiki/…Odpowiedzi:
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ą.
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.
źródło
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.
źródło
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.
źródło
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ę.
Przesłałem do systemu 100 zleceń. Dlaczego przetwarzanie zajmuje 400 razy więcej czasu niż jedno zadanie?
Z tego powodu klient uzna czas wykonania za błąd, jeśli oba są prawdziwe:
Uzasadnione argumenty wyjaśniające, że kwadratowy algorytm uruchomieniowy nie stanowi problemu (tzn. Nie zasługuje na zmianę kodu):
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ć.
źródło
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 2 )), 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 2 ) był błędem, lub jeśli najpierw celowo zaimplementowałeś go w czasie O (n 2 ), 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 2 ).
źródło
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.
źródło