Miesiąc: marzec 2021

Drugim najważniejszym wąskim gardłem, które ludzie znajdują, jest natura języka R, który jest językiem interpretowanym i dynamicznie wpisywanym na maszynie. Oznacza to, że w dowolnym wierszu programu obiekt może być liczbą całkowitą, w następnym wierszu może to być ramka danych, następnie łańcuch znaków i może to być lista ramek danych dwa wiersze później. Jest to naturą braku ustalonych typów obiektów, a ponieważ interpreter nie może z góry wiedzieć, jak obsługiwać takie obiekty, ponieważ za każdym razem mogą one być zupełnie inne, musi sprawdzać typ obiektu za każdym razem, gdy chce zastosować jakieś rodzaj operacji na nim. Jest to trochę przesadzone, ale chodzi o to, że skoro istnieje możliwość zmiany typu obiektu, należy go stale sprawdzać. Zobaczymy, jak uniknąć niektórych z tych kontroli, aby zwiększyć wydajność, ale aby poradzić sobie z interpretowaną i dynamicznie wpisywaną naturą, będziemy musieli skorzystać z innych języków programowania, takich jak Fortran lub C ++, co pokażemy w dalszej części rozdziału . Te języki naprawiają typ obiektu podczas jego tworzenia i jeśli spróbujesz go zmienić w pewnym momencie, program zgłosi błąd. Może to być postrzegane jako niepotrzebne ograniczenie, ale w rzeczywistości może być bardzo potężne, gdy komunikuje zamiar jakiegoś kodu, a także pozwala kompilatorom na zapewnienie potężnych optymalizacji obsługi takich obiektów

Poprawa szybkości implementacji języka R niekoniecznie wiąże się z zaawansowanymi technikami optymalizacji, takimi jak zrównoleglenie. Rzeczywiście, istnieje wiele prostych poprawek, które choć nie zawsze są oczywiste, mogą sprawić, że R będzie działał znacznie szybciej. Największym wąskim gardłem, jakie ludzie napotykają w przypadku R, jest brak zrozumienia właściwości niezmienności obiektu oraz kosztów ogólnych poniesionych podczas wykonywania kopii takich obiektów. Samo zajęcie się tym może przynieść radykalną poprawę wydajności i nie jest to zbyt trudne, gdy zrozumiesz, jak to zrobić. To dobry kandydat do rozpoczęcia poszukiwań optymalizacji. Jako przykład niektórych problemów, które mogą się pojawić, załóżmy, że masz nazwaną tablicę liczb. Teraz załóżmy, że chcesz zaktualizować pierwszy element programu to be, jak pokazano w poniższym fragmencie kodu:

a[1] <- 10

To zadanie jest o wiele bardziej złożone, niż się wydaje. W rzeczywistości jest realizowany za pośrednictwem funkcji zastępczej `”[<-„1` poprzez to wywołanie i przypisanie:

a <- `”[<-„` (a, 1, value = 10)

Na początku może się wydawać, że jest to bardzo dziwna składnia, ale pamiętaj, że jak widzieliśmy, że możemy mieć ciągi znaków, które reprezentują obiekty, w tym funkcje, tak jak w tym przypadku. Części linii `”[<-„` to w rzeczywistości nazwa funkcji wywoływanej z parametrami, a,1 i value = 10. Jeśli wykonasz poprzednie dwie linie, powinieneś otrzymać ten sam wynik; to jest pierwszy element w a bycia równym 10. To, co faktycznie się dzieje, to tworzenie wewnętrznej kopii; pierwszy element takiego obiektu zostanie zmieniony na 10 , a wynikowy obiekt zostanie ponownie przypisany do a. Mimo że po prostu zmieniamy tylko jeden element tablicy, w rzeczywistości cały wektor jest ponownie obliczany. Im większy wektor, tym gorszy problem, a to może znacznie spowolnić implementację. Jest jeszcze gorzej, gdy używasz ciężkich struktur danych, takich jak ramki danych. Języki, które pozwalają na mutabilność, takie jak Fortran lub C ++, po prostu zmienią określoną wartość w tablicy zamiast tworzyć nową kopię pełnej tablicy. Dlatego często zdarza się, że kod, który byłby w porządku w innych językach, generuje bardzo duże i często niepotrzebne narzuty, gdy jest programowany w podobny sposób w R.

Zrozumienie, dlaczego język programowania może być powolny, jest podstawową umiejętnością potrzebną do zwiększenia szybkości jego implementacji. Na każdą implementację w dowolnym języku programowania ma podobny wpływ czas algorytmu i złożoność pamięci, ponieważ są one algorytmami, a nie właściwościami implementacji. Jednak sposób, w jaki języki obsługują określone implementacje, może się znacznie różnić i na tym się teraz skupimy. W przypadku R ludzie często znajdują cztery główne wąskie gardła:

* Niezmienność obiektu

* Zinterpretowane dynamiczne typy

* Procesy związane z pamięcią

* Procesy jednowątkowe

W żadnym wypadku ta lista nie jest kompletna ani nie występuje w każdej implementacji. To tylko najczęstsze wąskie gardła, jakie widziałem, a które po naprawieniu spowodowały największą liczbę ulepszeń szybkości. Często są to dobre punkty wyjścia, ale każda implementacja jest inna, więc bardzo trudno jest zasugerować ogólne zasady optymalizacji wydajności i należy o tym pamiętać.

Jak wspomniano wcześniej, przez pozostałą część rozdziału będziemy pracować z implementacjami SMA. Aby je rozróżnić, będziemy zmieniać nazwę funkcji dla każdej kolejnej implementacji, zaczynając od sma_slow_1(). Wszystkie implementacje SMA otrzymają następujące parametry:

period : Aby określić, ile obserwacji ma być używanych dla SMA.

symbol: Aby oznaczyć składnik aktywów, dla którego chcemy wykonać obliczenia. W tym przykładzie opcje będą for lub for. Jednak gdy samodzielnie uruchomisz system, będziesz mógł go rozszerzyć o dowolny symbol kryptowaluty, który sobie zażyczysz.

data : Rzeczywiste dane zawierające szeregi czasowe cen dla każdego zasobu.

Zrobimy dwa założenia, że ​​kolumna data – timestamp jest w porządku rosnącym i nie mamy luk w szeregach czasowych, co oznacza, że ​​mamy dane cenowe z każdej minuty. To pozwala nam pominąć wszelkie procedury zamawiania i sprawdzić, czy SMA powinno zawierać wewnętrznie NA, gdy nie są dostępne żadne dane. Zauważ, że oba te założenia są spełnione przez naszą symulację danych. Teraz wyjaśnimy, jak sma_slow_1() działa. Zauważ, że jest to bardzo nieefektywna implementacja i zdecydowanie powinieneś unikać programowania w ten sposób. Są to jednak typowe błędy popełniane przez ludzi i będziemy je usuwać jeden po drugim, mierząc ich wpływ na szybkość kodu. Zobaczmy, jak to się robi, wykonując następujące kroki:

1. Najpierw tworzymy pustą ramkę danych nazwaną result, który zawiera pojedynczą kolumnę o nazwie sma.
2. Następnie wykonujemy pętlę po wszystkich wierszach danych; oznacza koniec lub prawy koniec rozważanego interwału SMA.
3. Tworzymy liczbę całkowitą position, która jest taka sama jak end za każdym razem, gdy zaczynamy pętlę, a także obiekt sma, który będzie zawierał rzeczywiste obliczenia SMA dla pozycji końcowej, liczbę całkowitą n_accumulated, która śledzi liczbę zgromadzonych obserwacji oraz ramkę danych period_prices, która zawiera jedną kolumnę do przechowywania cen dla bieżącej kalkulacji SMA.
4. Następnie sprawdzamy, czy obserwacja przy bieżącym end odpowiada temu symbol, co nas interesuje. Jeśli tak nie jest, po prostu ignorujemy tę iterację, ale jeśli tak, będziemy kumulować perdiod_prices zaczynając od pozycji end (pamiętaj, że position równa się end i temu punktowi) i cofając się do liczby skumulowanych cen jest równa period interesującej nas lub aktualnej position mniejszej niż 1 (co oznacza, że ​​jesteśmy na początku szeregu czasowego). Aby to zrobić, używamy pętli while, która sprawdza warunek wspomniany wcześniej, zwiększa n_acumulated, gdy zostanie znaleziona obserwacja z tym samym symbol , a jej dane są dołączane do ramki danych period_prices, i zwiększa position niezależnie od tego, czy obserwacja była przydatna, abyśmy nie utknęli.
5. Po zakończeniu pętli while wiemy, że albo zgromadziliśmy liczbę cen równą period, która nas interesuje, albo napotkaliśmy początek szeregu czasowego. W pierwszym przypadku obliczamy średnią takich cen poprzez iterację po ramce danych period_prices i przypisujemy ją jako wartość sma dla aktualnej pozycji end. W drugim przypadku po prostu rejestrujemy wartość NA, ponieważ nie byliśmy w stanie obliczyć pełnego SMA. Spójrz na następujący fragment kodu:

Jeśli implementacja wydaje się skomplikowana, to dlatego, że tak jest. Gdy zaczniemy ulepszać nasz kod, zostanie on oczywiście uproszczony, co ułatwi jego zrozumienie.

6. Teraz chcemy faktycznie zobaczyć, że to działa. Aby to zrobić, wprowadzamy plik sma-slow.R do pamięci (która zawiera wszystkie powolne implementacje), a także dane, jak pokazano w poniższym fragmencie kodu:

source(„./sma-slow.R”)

data_original  <- read.csv(„.data.csv”)

Zwróć uwagę, że bierzemy tylko pierwsze 100 obserwacji, które odpowiadają 50 minutom akcji cenowej Bitcoin (pamiętaj, że te 100 obserwacji zawiera tylko 50 dla Bitcoin; pozostałe 50 dotyczą Litecoina). Widzimy, że SMA (5) dla Bitcoin ma sens, w tym pierwsze cztery NA (możesz sprawdzić liczby ręcznie, ale pamiętaj, aby wykorzystać dane i wyniki do własnej symulacji danych):

data <- data_original[1:100, ]

symbol <- „BTC”

period <- 5

sma-1 <= sma_slow_1(period, symbol, data)

sma_1

#> sma

#> 1 NA

#> 2 NA

#> 3 NA

#> 4 NA

#> 5 7999,639

#> 6 7997.138

#> 7 8000.098

#> 8 8001.677

#> 9 8000.633

#> 10 8000.182

(Obcięte wyjście)

Zanim zrozumiemy, jak naprawić ten kod, musimy zrozumieć, dlaczego R może być powolne, a także jak zmierzyć wpływ, jaki wywieramy, gdy go ulepszamy.

Oczywiście zbierasz dane z rynków kryptowalut, odkąd zaimplementowałeś własną wersję systemu obiektowego, który opracowaliśmy w poprzednim rozdziale, prawda? Tylko żartuję. Jeśli tak, to prawdopodobnie nie są wystarczające dane do tego, co zrobimy w tym rozdziale, więc oto mały fragment kodu, który będzie symulował dwie serie czasowe dla ceny Bitcoin i Litecoin w dolarach amerykańskich. Struktura danych jest podobna do tej zastosowanej w poprzedniej części, dzięki czemu kod, który tu opracowujemy, jest przydatny również w tym systemie. Nie będziemy zagłębiać się zbytnio w działanie tej funkcji, ponieważ w tym momencie powinno być dla Ciebie jasne, z wyjątkiem wskazania, że ​​używamy funkcji time_to_timesamp(. TomeStamp(), którą opracowaliśmy poprzednio , i że funkcja simulate_prices()wykorzystuje model kwadratowy górę symulacji ARIMA. Spójrzmy na następujący kod:

source(„../chapter-08/cryptourrencies/utilities/time-stamp.R”_

library(lubridate)

N <- 60 * 24 * 365

simulate_market <- funtion(name, symbol. now, n , base, sd, x ) {

dates <- seq(now- minutes(n-1), nowm by = „min”)

ts <- unlist(lapply(lapply (

dates, times_to_timestamp.TimeStamp), unclass))

price_usd <- simulate_prices(n, base, sd, x)

data <- data.frame(timestamp – ts, prie_usd = price_usd)

data$name <- name

data$symbol <- symbol

return(data)

simulate_prices <- funtion(n, base, sd, x) {

ts <- arima.sim(list(15, 15,15(, n = n , sd = sd)

quadratic_model <- base + (x-1) * base / (n^2) * (1:n)^2

return(as.numeri(ts+quadrati_model))

now <- Sys.time()

btc <- simulate_market(„Bitcoin, „BTC”, now, N , 8000, 8 ,2)

bltc <- simulate_market(„Litecoin, „LTC”, now, N , 80, 8 ,2)

data <- rbind(bt, ltc)

data <- data[order(data$timestamp) , ]

write.sv(data, „./data.csv”, row.names = FALSE)

Zauważ, że parametry użyte do wywołania funkcji  simulate_market() starają się przypominać co widać obecnie w cenach Bitcoin i Litecoin, ale pamiętaj, że jest to bardzo prosty model, więc nie oczekuj, że będzie on zachowywał się jak rzeczywiste szeregi czasowe cen tych aktywów. Na koniec symulujemy 525 600 obserwacji dla każdego zasobu, co w przybliżeniu odpowiada liczbie minut w roku (N <- 60 * 248 365, która obejmuje sekundy na godzinę, godziny dziennie i dni w roku). Oznacza to, że symulujemy dane minuta po minucie. Aby zwizualizować ceny Bitcoinów, które symulowaliśmy, możesz użyć następującego kodu. Po prostu tworzy jeden wykres, który wykorzystuje próbkę 1000 elementów przez cały rok (więcej niż to jest niepotrzebne, ponieważ nie będziesz w stanie dostrzec więcej punktów, a to spowolni obliczenia); tworzony jest również inny wykres, który pokazuje efekt powiększenia danych do pierwszej godziny:

s <- sample(1:nrow(btc), 1000)

plot(btc[s[order(s)], „price_usd”], xlab = „Minutes”, ylab=”Price” , xaxt = ‘n’)

title(main=”Bitcoin price simulation for 1 year”)

lines(btc[s[order(s)], „proce_usd”)

plot(btc[1:60, „price_usd”], xlab = „Minutes”, ylab=”Price” , xaxt = ‘n’)

title(main=” Bitcoin price simulation for 1 hour”)

lines(btc[1:60, „price_usd”[)

Jak widać, obserwując całoroczną symulację, obserwuje się silny trend wzrostowy, ale jeśli powiększysz do mniejszego przedziału czasowego, zobaczysz sporą różnicę cen, która pozwala na użyteczne implementacje SMA

Algorytm, z którym będziemy pracować w dalszej części , nazywa się prostą średnią ruchomą (SMA). Jest to bardzo dobrze znane narzędzie do przeprowadzania analizy technicznej szeregów czasowych, szczególnie dla rynków finansowych i handlu. Ideą SMA jest to, że obliczysz średnią na każdy punkt w czasie, patrząc wstecz na określoną liczbę okresów. Na przykład, powiedzmy, że patrzysz na szeregi czasowe minuta po minucie i obliczysz SMA (30). Oznacza to, że przy każdej obserwacji w swoim szeregu czasowym weźmiesz obserwacje odpowiadające poprzednim 30 minutom od rozpoczęcia określonej obserwacji (30 obserwacji wstecz) i zapiszesz średnią z tych 30 obserwacji jako SMA (30 ) wartość dla tego punktu w czasie.

Na późniejszym diagramie możesz zwizualizować ideę SMA. Diagram przedstawia monotoniczne szeregi czasowe, które wzrastają o jedną jednostkę wartości dla każdej jednostki czasu, z których obie zaczynają się od jednej (to znaczy, że jej wartość wynosi 1 w czasie 1, 2 w czasie 2 itd.), Wzdłuż z pewnymi liczbami otaczającymi grupę obserwacji, zostaną podjęte obliczenia SMA. Jak widać, w przypadku SMA (3) ostatnie trzy elementy otrzymujemy w każdym punkcie szeregu czasowego; podobnie dla SMA (4) otrzymujemy cztery ostatnie elementy. Kiedy obliczasz średnią dla podzbioru elementów na rysunku, otrzymasz liczby w lewym górnym rogu, które odpowiadają określonym obliczonym szeregom czasowym SMA. W szczególności dla takich szeregów czasowych, dla przypadku SMA (3), wynikiem jest NA, NA, 2, 3, 4, 5, 6, 7 i 8, a dla przypadku SMA (4) wynik to NA, NA, NA, 2,5, 3,5, 4,5, 5,5, 6,5 i 7,5. Istnieje kilka następujących właściwości, na które powinniśmy zwrócić uwagę na temat SMA:

• Po pierwsze, należy zauważyć, że zarówno SMA(3), jak i SMA(4) są szeregami zawierającymi taką samą liczbę obserwacji jak oryginalne szeregi czasowe, w tym przypadku 9.
• Po drugie, zauważ, że oba zaczynają się liczbą NA równą liczbie parametru SMA minus jeden. Dzieje się tak, ponieważ w przypadku SMA (3) w czasie 2 nie mamy trzech obserwacji wstecz, mamy tylko dwie. Dlatego NA jest używany do wskazania, że ​​w tym momencie nie można było obliczyć SMA (3). To samo wyjaśnienie dotyczy wszystkich innych wartości NA.
• Po trzecie i wreszcie, zauważ, że za każdym razem, gdy przesuwamy się o jedną jednostkę czasu, dodajemy jedną obserwację i usuwamy kolejną obserwację (ogon) z bieżącego podzbioru.

Załóżmy, że wybrałeś dobry algorytm i zaimplementowałeś go bez zbytniego dbania o optymalizację, jak to zwykle bywa przy pierwszych próbach. Czy warto poświęcić czas na jego optymalizację? Optymalizacja wydajności może być bardzo kosztowną czynnością. Nie możesz próbować optymalizować swojego kodu, chyba że musisz. Twój czas jest cenny i prawdopodobnie lepiej spędzić go na robieniu czegoś innego. Powiedzmy, że z jakiegoś powodu musisz przyspieszyć implementację. Pierwszą rzeczą, o której musisz zdecydować, jest to, jak szybko jest wystarczająco szybko. Czy twój algorytm musi po prostu zakończyć się w ciągu kilku godzin zamiast kilku dni, czy też musisz zejść do poziomów mikrosekund? Czy jest to bezwzględny wymóg, czy po prostu powinieneś wykonać najlepszą pracę, jaką możesz w określonym czasie? Są to ważne pytania, które należy rozważyć przed optymalizacją kodu, a czasami rozwiązaniem nie jest nawet optymalizacja. Nierzadko zdarza się, że klienci wolą wydawać więcej pieniędzy na używanie pewnego rodzaju zasobów w chmurze w celu rozwiązania problemu z wydajnością, zamiast spędzać cenny czas na optymalizowaniu wydajności algorytmu, zwłaszcza jeśli mogą zapewnić większą wartość biznesową, robiąc coś innego. Oprócz wspomnianego wcześniej kompromisu między czasem maszynowym a czasem ludzkim, przy podejmowaniu decyzji o optymalizacji implementacji algorytmu należy wziąć pod uwagę inne kwestie. Chcesz, aby Twój kod był czytelny? Czy chcesz, aby Twój kod był dostępny? Często zdarza się, że bardziej wydajny kod jest również trudniejszy do zrozumienia. Co więcej, jeśli tworzysz kod, który jest wykonywany równolegle, nałoży to szereg ograniczeń na typ systemów, które mogą go wykonać, i musisz o tym pamiętać. Proponuję ograniczyć do minimum liczbę optymalizacji; dzięki temu osiągniesz swój cel dotyczący tego, jak szybko musi działać implementacja, i nie rób więcej. Proces będzie prosty: znajdź najważniejsze wąskie gardło, usuń je (lub przynajmniej zmniejsz jego wpływ), sprawdź, czy Twoja implementacja jest wystarczająco szybka, a jeśli nie, powtórz. W tym rozdziale przejdziemy przez ten cykl kilka razy i chociaż z perspektywy czasu wydaje się to łatwe, w rzeczywistości może być dość trudne, szczególnie w przypadku złożonych algorytmów.

Obliczanie liczb Fibonacciego jest tradycyjnym przykładem przy nauczaniu rekurencji. Tutaj użyjemy go do porównania wydajności dwóch algorytmów, jednego rekurencyjnego i jednego sekwencyjnego. Jeśli ich nie znasz, liczby Fibonacciego są definiowane rekurencyjnie w sekwencji, w której następna jest sumą dwóch poprzednich, a dwie pierwsze liczby to jedynki (nasze przypadki bazowe). Rzeczywista sekwencja to 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 i tak dalej. Nazywa się to ciągiem Fibonacciego i wykazuje interesujące właściwości, takie jak związek ze złotym podziałem, na który zdecydowanie powinieneś sprawdzić, jeśli nie wiesz, co to jest. Nasza funkcja  fivbonaci_recursive() przyjmuje pozycję liczby Fibonacciego, którą chcemy obliczyć jako n, ograniczoną do liczb całkowitych większych lub równych jeden. Jeśli jest to przypadek podstawowy, to znaczy, jeśli jest poniżej 1, po prostu go zwrócimy (nie, że jeśli obliczamy liczbę Fibonacciego na drugiej pozycji, nasza operacja n-2 wyniesie zero, co nie jest prawidłową pozycją, dlatego musimy użyć <=  zamiast ==). W przeciwnym razie zwrócimy sumę wywołań rekurencyjnych do dwóch poprzednich za pomocą fibonacci_recursive(n-1)  i fibonacci_recursive(n-2), jak pokazano w poniższym fragmencie kodu:

fibonacci_recursive <- function(n) {

if(n <= 1) {return(n) }

return(fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

Jak widać na poniższym fragmencie kodu, nasza funkcja działa zgodnie z oczekiwaniami. Co się jednak dzieje, gdy chcemy pobrać 35 lub 40 liczbę Fibonacciego? Jak możesz doświadczyć podczas uruchamiania tego kodu, im dalej liczba Fibonacciego jest od przypadków podstawowych, tym więcej czasu zajmie, a gdzieś w okolicach 30. pozycji zaczyna być zauważalnie wolniejsza. Jeśli spróbujesz obliczyć setną liczbę Fibonacciego, będziesz czekać długo, zanim otrzymasz wynik:

fibonacci_recursive(1)

#> [1] 1

fibonacci_recursive(2)

#> [1] 1

fibonacci_recursive(3)

#> [1] 2

fibonacci_recursive(4)

#> [1] 3

fibonacci_recursive(5)

#> [1] 5

fibonacci_recursive(35)

#> [1] 9227465

Dlaczego to się dzieje? Odpowiedź brzmi, że ten algorytm wykonuje dużo niepotrzebnej pracy, co czyni go złym algorytmem. Aby zrozumieć, dlaczego, przejdźmy mentalnie przez wykonanie algorytmu dla trzeciej i czwartej liczby Fibonacciego i utwórzmy odpowiednie drzewa wykonania, jak pokazano na poniższym diagramie:

Na poprzednim diagramie f(n) jest skrótem od fibonacci_recursive(n) , dzięki czemu możemy zmieścić wszystkie obiekty w nim, a kolory są używane do pokazania, które wywołania funkcji są powtarzane. Jak widać, podczas wykonywania fibonacci_recursive(3) , fibonacci_recursive(1) wywołanie jest wykonywane dwukrotnie. Podczas wykonywania fibonacci_recursive(4)  to samo wywołanie jest wykonywane trzy razy. Ile razy będzie to wykonywane za fibonacci_recursive(5) i fibonacci_recursive(6)?  To ćwiczenie dla ciebie, czytelniku, a jak się przekonasz, liczba ta rośnie wykładniczo. Aby być technicznie precyzyjnym, złożoność czasowa algorytmu wynosi O(2ⁿ), co jest tak złe, jak tylko można. Ponadto większość obliczeń jest całkowicie niepotrzebna, ponieważ są one powtarzane. Algorytm jest poprawny, ale jego wydajność jest jedną z gorszych. Jak wspomnieliśmy wcześniej, nawet jeśli zapewnisz najbardziej wydajną implementację tego algorytmu, będzie to znacznie wolniejsze niż bardzo nieefektywna implementacja bardziej wydajnego. Jeśli zaprojektujemy poprawny algorytm, który pozwoli uniknąć wykonywania wszystkich niepotrzebnych obliczeń, możemy to zrobić mają znacznie szybszy program i właśnie to robi następujący algorytm. Zamiast tworzyć drzewo rekurencyjnych wywołań, po prostu obliczymy liczby Fibonacciego w kolejności aż do tej, o którą jesteśmy proszeni. Po prostu dodamy poprzednie dwie liczby i zapiszemy wynik w tablicy, która będzie zawierała liczby całkowite. Określamy dwa przypadki podstawowe i kontynuujemy obliczenia, jak pokazano w poniższym fragmencie kodu:

fibanacci_sequential <- funtion(n) {

if (n <= 2) { return(1)

f <- integer(n)

f[1] <- 1

f[2] <- 1

for (i in 3:n) {

f[i] <- f[i-2] + f[i-1]

}

return(f[n])

 Jak widać, każda liczba jest obliczana tylko raz, co jest najbardziej wydajnym algorytmem, jaki możemy zaprojektować dla tego problemu. Pozwala to uniknąć całego narzutu związanego z algorytmem rekurencyjnym i pozostawia nam liniową złożoność czasową O (n). Nawet jeśli kodujemy ten algorytm bez dbania o optymalizację wydajności, jego czas wykonania będzie szybszy o wiele rzędów wielkości. Za pomocą tego algorytmu możemy w rzeczywistości obliczyć 1476 liczbę Fibonacciego, która jest największą, na jaką pozwala architektura wewnętrzna R. Jeśli spróbujemy obliczyć 1477. liczbę Fibonacciego, otrzymamy nieskończoność (Inf) jako odpowiedź ze względu na mechanizmy używane przez R do przechowywania liczb całkowitych, co jest tematem, którym nie będziemy się zajmować. Co więcej, obliczenia dla 1476 liczby Fibonacciego są prawie natychmiastowe, co pokazuje, jak ważne jest wybranie dobrego algorytmu, zanim zacznie się go optymalizować:

fibonacci_sequemtial(1476)

# [1] 1.306989e + 308

fibonacci_sequemtial(1477)

#[1] Inf

Na koniec zauważ, że osiągnęliśmy wzrost szybkości kosztem wykorzystania większej ilości pamięci. Algorytm rekurencyjny odrzucał każdą liczbę Fibonacciego po jej obliczeniu, podczas gdy algorytm sekwencyjny przechowuje każdą w pamięci. W przypadku tego konkretnego problemu wydaje się to być dobrym kompromisem. Kompromis między czasem i przestrzenią jest powszechny w optymalizacji wydajności. Teraz, gdy zobaczyliśmy, jak ważny może być wybór algorytmu, w dalszej części rozdziału będziemy pracować z jednym algorytmem i skupimy się na optymalizacji jego implementacji. Pozostaje jednak kwestia, że ​​wybór wydajnego algorytmu jest ważniejszy niż efektywne jego wdrożenie.

Aby móc jasno przekazać idee zawarte w tutaj, najpierw muszę podać kilka prostych definicji. Mówiąc o algorytmie, mam na myśli abstrakcyjną specyfikację procesu. Kiedy mówię o implementacji, mam na myśli sposób, w jaki algorytm jest faktycznie programowany. Wreszcie, kiedy mówię o programie lub aplikacji, mam na myśli zbiór takich implementacji algorytmów współpracujących ze sobą. To powiedziawszy, łatwo jest zobaczyć, jak algorytm można zaimplementować na wiele różnych sposobów (na przykład jedna implementacja może korzystać z listy, a inna może używać tablicy). Każda z tych implementacji będzie miała inną wydajność i są one powiązane, ale nie równoważne, ze złożonością czasową algorytmu. Dla osób niezaznajomionych z ostatnim terminem każdy algorytm ma następujące dwie podstawowe właściwości

* Złożoność czasowa: Ta właściwość odnosi się do liczby obliczeń, które algorytm musi wykonać, w odniesieniu do wielkości otrzymywanych danych wejściowych. Istnieją różne narzędzia matematyczne do pomiaru tej złożoności, z których najpowszechniejszym jest notacja Big-O, która mierzy najgorszy scenariusz dla algorytmu.

* Złożoność przestrzeni: ta właściwość odnosi się do ilości pamięci wymaganej do wykonania algorytmu, ponownie w odniesieniu do rozmiaru danych wejściowych, które otrzymuje, i można ją również zmierzyć za pomocą tych samych narzędzi matematycznych. Powszechnie wiadomo, że nieefektywny algorytm zaimplementowany bardzo wydajnie może być o rząd wielkości wolniejszy niż wydajny algorytm zaimplementowany nieefektywnie. Oznacza to, że w większości przypadków wybór algorytmu jest znacznie ważniejszy niż optymalizacja implementacji.

Podczas oceny algorytmu należy wziąć pod uwagę wiele innych kwestii niż wspomniane wcześniej złożoności, takie jak wykorzystanie zasobów wydajności (na przykład przepustowość Internetu), a także inne właściwości, takie jak bezpieczeństwo lub trudność implementacji. Nie będziemy zagłębiać się w te tematy w tej książce. Jeśli jednak chcesz, aby Twój kod działał dobrze, musisz formalnie przestudiować struktury danych i algorytmy

W ciągu ostatnich kilku dziesięcioleci zapotrzebowanie na moc obliczeniową stale rosło, wraz ze wzrostem ilości danych i bardziej złożonymi modelami. Oczywiste jest, że zminimalizowanie czasu potrzebnego na te obliczenia stało się ważnym zadaniem i że istnieją oczywiste problemy z wydajnością, które należy rozwiązać. Te problemy z wydajnością wynikają z niedopasowania ilości danych do istniejących metod analitycznych. Ostatecznie konieczna będzie fundamentalna zmiana w technikach analizy danych, ale na razie musimy zadowolić się poprawą wydajności naszych wdrożeń. R został zaprojektowany jako język interpretowany o wysokim poziomie ekspresji i to jest jeden z powodów, dla których brakuje mu dużej części precyzyjnej kontroli i podstawowych konstrukcji do obsługi kodu o wysokiej wydajności. Jak Arora wbija to w książkę, zredagowała Conquering Big Data with High Performance Computing, Springer, 2016: „Chociaż R jest wyraźnie językiem o wysokiej produktywności, niekoniecznie był to język o wysokiej wydajności”. Nierzadko zdarza się, że czas wykonania programu R jest mierzony w godzinach lub nawet w dniach. Wraz ze wzrostem ilości analizowanych danych czas wykonywania może stać się zbyt długi i często zdarza się, że naukowcy zajmujący się danymi i statystycy utknęli w tych wąskich gardłach. Kiedy tak się stanie i jeśli nie wiedzą zbyt wiele na temat optymalizacji wydajności, prawdopodobnie po prostu zadowolą się zmniejszoną ilością danych, co może utrudnić ich analizę. Jednak nie bój się; Programy w języku R mogą być powolne, ale dobrze napisane programy w języku R są zwykle wystarczająco szybkie, dlatego przyjrzymy się różnym technikom, których możesz użyć do zwiększenia wydajności kodu R. Ten rozdział nie ma na celu uczynienia z Ciebie eksperta w zakresie optymalizacji wydajności, ale raczej zawierają omówienie, które wprowadza Cię w ogromną liczbę technik, których można użyć podczas próby zwiększenia wydajności kodu. Przyjrzymy się wielu różnym technikom, z których każda może mieć rozdziały, a nawet książki poświęcone im, więc będziemy musieli spojrzeć na nie z bardzo wysokiego poziomu, ale jeśli będziesz ciągle ograniczany przez zasoby obliczeniowe, są one czymś będziesz chciał zajrzeć dalej. Niektóre z ważnych tematów omawianych w tym rozdziale są następujące:

* Decydowanie, jak szybka musi być implementacja

* Znaczenie korzystania z dobrych algorytmów

* Powody, dla których R może czasami działać wolno lub nieefektywnie

* Duży wpływ na wydajność, jakie mogą mieć małe zmiany

* Pomiar wydajności kodu w celu znalezienia wąskich gardeł

* Porównanie różnych implementacji między sobą

* Maksymalne wykorzystanie możliwości komputera dzięki pracy równoległej

* Poprawa wydajności dzięki współpracy z innymi językami

Wymagane pakiety

Pracowaliśmy już z niektórymi pakietami wymaganymi w tym rozdziale, takimi jak ggplot2 i lubridate. Pozostałe trzy pakiety zostały wprowadzone do testów porównawczych funkcji i porównania ich wydajności między sobą, a także do zaawansowanych technik optymalizacji, takich jak delegowanie i zrównoleglanie, które zostaną wyjaśnione w odpowiednich sekcjach. Aby móc odtworzyć wszystkie przykłady w tym rozdziale, potrzebujesz również działających kompilatorów dla kodu Fortran i C ++. Zobacz Wymagane pakiety, aby uzyskać instrukcje dotyczące ich instalacji w systemie operacyjnym. Spójrzmy na poniższą tabelę przedstawiającą zastosowania wymaganych pakietów:

Pakiety : Powód

ggplo2 : Wysokiej jakości wykresy

lubridate : Łatwo przenosi daty

microbenchmark : Wydajność funkcji wzorcowych