Tablice w Arduino – #7 – praktyczny przykład

[Gieneq]

W tej i następnej części kursu przećwiczymy zdobytą wiedzę na praktycznym przykładzie przetwarzania danych zebranych przez czujnik. Dane te mogą być być obarczone błędem, aby dowiedzieć się jaka jest prawidłowa wartość można wyznaczyć parametry sygnału takie jak wartość średnia, odchylenie standardowe czy mediana. Zrealizujemy to przy użyciu tablic!

Spis treści

• #1 – wstęp i praktyka
• #2 – organizacja pamięci
• #3 – tablice w pamięci
• #4 – tablica jest wskaźnikiem
• #5 – znaki, cstring
• #6 – argumenty funkcji
• #7 – przykład (czytasz ten artykuł)
• #8 – przykład cd.
• #9 – tablice wielowymiarowe
• #10 – tablice dynamiczne
• #11 – zakończenie

Wstęp

Dobrze napisany kod programu powinien być elastyczny tak by modyfikacje nie były zbyt trudne. Funkcje, które piszemy powinny nadawać się do użytku w podobnych zadaniach – postaramy się trzymać tych dobrych wytycznych.

W zadaniu dane wejściowe będą pochodziły z czujnika (prawdziwego lub udawanego), a naszym zadaniem będzie przygotowanie funkcji, które umożliwią wyznaczenie m.in. średniej i mediany.

Dlaczego tablice?

Pierwsza myśl to dlaczego w tym zadaniu przydadzą się tablice? Odpowiedź jest prosta – musimy pamiętać dane z przeszłości, aby móc na ich podstawie zauważyć pewne trendy sygnału. Gdybyśmy tylko przez chwilę patrzyli na zegar prędkości w aucie,  ciężko byłoby stwierdzić czy przyspieszamy czy zwalniamy – potrzeba obserwować zegar przez pewien czas lub zerkać na niego co chwilę (tak będzie bezpieczniej).

Te 2 sposoby obserwacji dobrze odzwierciedlają metody w jaki przeprowadza się pomiary:

• pierwsza z nich ma charakter ciągły - proces startuje i kończy się,
• druga ma charakter dyskretny (nieciągły) - proces jest wyzwalany niczym przycisk w aparacie, stan na daną chwilę jest uwieczniony i proces momentalnie się kończy.

Dyskretność może być myląca. Zazwyczaj kojarzymy to ze słowami: niejawny, poufny. W elektronice ma jednak inne znaczenie – element dyskretny to np. rezystor. W algebrze, gdy funkcja ma wartości dyskretne, to jej wykres składa się z kropek – jest nieciągła. W przetwarzaniu sygnałów (w tym co robimy) pomiar dyskretny, to podobnie co w algebrze wyrywkowy stan mierzonego obiektu.

Momenty statystyczne – trochę matematyki

Wartość średnia pozwala jedną liczbą opisać cały zbiór danych określając wokół jakiej liczby skupione są pomiary. Jak wiemy wartości pomiarów rzeczywistych czujników wahają się w pewnych granicach, co wynika chociażby z niedoskonałości przetworników, wpływu temperatury czy nieidealnego zasilania. Chcąc zminimalizować wpływ tych błędów, możemy dokonać uśrednienia kilku pomiarów (tzw. próbek).

Możemy przyjrzeć się symulacji czujnika, który na swoim wyjściu podaje bardzo zaszumiony sygnał:

Widzimy, że wartości pomiarów zawarte są w przedziale od około 1,38 do 3,46 V. Co można powiedzieć o tym sygnale? Na początek wyznaczmy wartość średnią – dodajemy wartości próbek (pomiarów) i dzielimy tę wartość przez liczbę próbek zgodnie ze wzorem:

Tak uzyskane "spłaszczenie" określa wokół jakiej wartości skupione są pomiary. W przypadku z ilustracji wartość średnia wynosi 2,51 V i zaznaczono to poziomą linią:

Wartość średnia to jednak nie wszystko, bo można tak dobrać dane, że średnia będzie taka sama. Stąd, trzeba wprowadzić kolejny parametr sygnału jakim jest odchylenie standardowe.

Pomiary można utożsamić z sygnałem.

Odchylenie standardowe informuje jak bardzo rozrzucone są wartości w sygnale, przy czym warto podkreślić, że nie jest to amplituda sygnału. Sygnał losowy, czyli taki jak szum na linii z czujnika ma rozkład normalny opisany krzywą Gaussa (tzw. krzywą kapeluszową). Wartość średnia oznacza położenie wierzchołka kapelusza (odczyty, które występują najczęściej). Odchylenie standardowe oznacza jak "szeroki jest kapelusz" krzywej Gaussa i można zauważyć, że w obszarze wykreślonym przez +-odchylenie standardowe zawarta jest większość wartości.

Dla naszych 100 pomiarów narysowanie histogramu, czyli wykresu opisującego ile jest próbek o danym przedziale wartości w sygnale nie ma sensu, ale gdy pomiarów jest więcej, np. 10 tyś, widać wyraźnie rozkład normalny:

Bez zbytniego zagłębiania się w ten temat przejdźmy do wyznaczenia odchylenia standardowego. Na początek wzór:

Bez obaw, nie jest to takie straszne  'O' z ogonkiem to mała grecka litera o nazwie sigma. Po prawej znowu mamy jakąś sumę (która też jest sigmą... wielką), ale w tym przypadku wyznaczamy różnicę próbki sygnału i wartości średniej, następnie podnosimy to do kwadratu i dodajemy. Tak uzyskaną sumę dzielimy przez liczbę próbek i na koniec wyciągamy pierwiastek.

Gdyby pominąć pierwiastek i pozostawić sigmę w kwadracie to uzyskalibyśmy tzw. wariancję.

Dla naszego sygnału z wykresu odchylenie standardowe wynosi około 0.45 V:

Gdyby przeanalizować sygnał o mniejszym odchyleniu standardowym, to zauważymy, że dla tej samej wartości średniej rozrzut pomiarów jest mniejszy:

 

Na koniec została nam jeszcze mediana, którą najprościej opisać słownie jako: wartość środkowa w posortowanym sygnale. Już z samej definicji widzimy, że musimy dysponować jakimś wycinkiem pomiarów składających się z przynajmniej kilku próbek.

Dla przykładu z wykresu mediana jest bardzo podobna do wartości średniej i wynosi około 2.51 V, nie ma co jednak przyzwyczajać się do takich podobieństw.

Filtracja

Wartość średnia i mediana nie służą tylko do analizy sygnału, można je wykorzystać w roli tzw. cyfrowych filtrów dolnoprzepustowych. Co to znaczy? 

Wróćmy do tego, że wartość średnia określa wokół jakiej wartości skupia się sygnał, a mediana informuje jaki jest środkowy element (coś podobnego do wartości średniej). Czyli, jeżeli w sygnale nagle pojawi się zakłócenie trwające tylko kilka pomiarów (próbek), to czy będzie mieć znaczny wpływ? Dla wartości średniej może być nieodczuwalne, a mediana może nawet pominąć ten fakt. Dlatego nazywamy te operacje filtrami dolnoprzepustowymi ponieważ uznają one tylko sygnały o niskich częstotliwościach zmian.

Dolnoprzepustowość odnoście się do wykresu częstotliwości zmian w sygnale, w którym niskie częstotliwości są po lewej stronie blisko zero, czyli "na dole" wykresu.

Przykład: co by się stało gdybyśmy w wychłodzonym pomieszczeniu odkręcili grzejnik na maxa, ale tylko na kilka sekund? Efekt byłby nieodczuwalny dlatego, że system (w tym przypadku pomieszczenie) jest za wolny - ma za dużą inercję. Podobnie dla operacji uśredniania, chwilowa zmiana (nawet o dużej wartości) niewiele wpływa na całokształt.

Implementacja

Dobrze dosyć teorii i przykładów – napiszmy kod programu! Zacznijmy od przygotowania zarysu projektu. Potrzebujemy pobrać dane oraz mieć gdzie je zapisywać. Od razu warto pisać funkcje, które będą realizowały jedną funkcjonalność:

constexpr int BUFFER_LENGTH = 10;

int samples_buffer[BUFFER_LENGTH];

int read_sensor() {
  return random(20);
}

void setup() {
  Serial.begin(9600);
  randomSeed(12345UL);
}

void loop() {
}

Mamy przygotowany bufor danych samples_buffer, do którego będzie wkładać kolejne wartości. 10 elementów to mało, ale w celach edukacyjnych pozwoli nam patrząc na dane od razu coś wywnioskować.

W funkcji read_sensor() na razie zwracamy wartość losową o stałym zarodku, aby móc otrzymać powtarzalne "pomiary". Używając w tym miejscu funkcję, zyskamy możliwość implementacji różnych czujników zmieniając tylko tę funkcję, dlatego choć jest bardzo prosta, to nie ma potrzeby jej redukować (przełożyć ciała funkcji w miejsce wywołania). Lepiej rozważyć użycie specyfikatora inline, który przy kompilacji przekopiuje ciało funkcji oszczędzając miejsce na stosie.

Zapis pomiarów

To nie jest takie oczywiste... pomyśl przez chwilę, jak można do takiej tablicy zapisywać pomiary? Może przyjść Ci do głowy pomysł, że potrzeba do każdego kolejnego elementu wpisywać kolejny pomiar – super pomysł! Na pewno przyda się tu dodatkowa zmienna informująca o aktualnym indeksie do którego można coś zapisać:

int current_buffer_index;

void feed_buffer(int *buff, int capacity, int *current_index, int sample) {
  if (*current_index < capacity) {
    buff[*current_index] = sample;
    ++(*current_index);
  }
}

Tworzymy funkcję do dodawania próbek (ang. sample) do naszej tablicy. Do funkcji przekazuję wskaźnik na tablicę buff, rozmiar tej tablicy capacity oraz wskaźnik na wybrany indeks, tak by można go było modyfikować z wnętrza funkcji. Funkcję można jeszcze uprościć i nie powinna stracić na czytelności (pamiętamy tylko o postinkrementacji):

void feed_buffer(int *buff, int capacity, int *current_index, int sample) {
  if (*current_index < capacity)
    buff[(*current_index)++] = sample;
}

Użyjmy teraz tę funkcję do zapisania 10 elementów:

void setup() {
  Serial.begin(9600);
  delay(1000);
  
  for (int i = 0; i < 10; i++)
    feed_buffer(samples_buffer, BUFFER_LENGTH, &current_buffer_index, read_sensor());
}

Do wypisania wartości tablicy możemy skorzystać z funkcji printer() z poprzedniej części kursu. Bogatsi o widzę o kolejnych dobrych zwyczajach możemy dodać specyfikator const w argumencie:

void printer(const int *tab, int len) {
  for(int i = 0; i < len; ++i) {
    Serial.print(i); Serial.print(F(": " )); Serial.println(*(tab + i)); 
  }
}

Tu wyraźnie widać jak przydatne jest pisanie dość ogólnikowych funkcji, bez problemu przełożyliśmy jej kod do nowego projektu! Ewentualnie możemy zunifikować (ujednolicić) argumenty funkcji zmieniając nazwy na buff i capacity. Dodajemy na końcu wywołanie funkcji wypisującej:

void setup() {
  Serial.begin(9600);
  
  for (int i = 0; i < 10; i++)
    feed_buffer(samples_buffer, BUFFER_LENGTH, &current_buffer_index, read_sensor());
  
  printer(samples_buffer, BUFFER_LENGTH);
}

Uruchamiamy i mamy kilka przykładowych "pomiarów":

0: 7
1: 9
2: 13
3: 18
4: 10
5: 12
6: 4 
7: 18
8: 3
9: 9

Dobrze, to już coś... tylko co dalej? Jakbyśmy teraz chcieli dodać nowy pomiar, to gdzie go zapisać?

Kolejkowanie

Gdyby zależało nam na zapisaniu wszystkich próbek to byśmy zrobili możliwie dużą tablicę i tam zapisywali pomiary. Nam jednak zależy na obserwacji pewnego okna czasowego – ostatnich 10 pomiarów. W takiej sytuacji najstarszy pomiar musi zostać odrzucony, aby zrobić miejsce dla nowszego.

Nawiązując nieco do czasu pandemii – to tak jakbyśmy stali w kolejce przed sklepem, do którego może wejść 10 klientów. Klient, który jest przy kasie (stał najdłużej bo był pierwszy) opuszcza sklep, wszyscy się przesuwają i może wejść kolejny (nowy) klient.

Idąc tym tokiem rozumowania możemy dojść do rozwiązania, które będzie ok:

void feed_buffer(int *buff, int capacity, int *current_index, int sample) {
  if (*current_index < capacity)
    buff[(*current_index)++] = sample;
  else {
    for (int i = 0; i < capacity - 1; ++i)
      buff[i] = buff[i + 1];
    buff[capacity - 1] = sample;
  }
}

Czyli jeżeli zapełniliśmy wolne miejsca w buforze to pozostałe przesuwamy (wypychając najstarszego klienta) i na ostatniej pozycji dodajemy nową wartość (nowego klienta). Podejście to powoduje jednak spory problem – dla długich tablic wykonanie tylu operacji staje się kosztowne.

Zapętlanie bufora

Powyższe rozwiązanie da się poprawić, trzeba tylko zmienić sposób myślenia. Czy to, że wstawimy najnowszą wartość w indeksie 9 czy 0 ma większe znaczenie? Nie ma, zwłaszcza że interesują nas pewne wyznaczniki dotyczące całych danych. Możemy więc zmieniać wartość tylko najstarszego elementu, a pozostałe zostawić w spokoju – tak jak odbywa się to na wizualizacji radaru widocznej na grafice – promień wodzący odświeża najstarsze dane, a pozostałe są nieruszone.

Zabierzmy się za kod:

void feed_buffer(int *buff, int capacity, int *current_index, int sample) {
  if (*current_index < capacity)
    buff[(*current_index)++] = sample;
  else
    *current_index = 0;
    buff[*current_index] = sample;
}

Można to nawet uprościć dzięki operacji dzielenia modulo, która zawęzi zmienną do przedziału: <0; capacity), czyli:

void feed_buffer(int *buff, int capacity, int *current_index, int sample) {
  buff[(*current_index)++] = sample;
  *current_index %= capacity;
}

Spróbujmy wypełnić tablicę 12 wartościami (na 10), w wyniku 2 pierwsze elementy zyskały nowe wartości:

0: 0 
1: 5 
2: 13
3: 18
4: 10
5: 12
6: 4 
7: 18
8: 3
9: 9

Wygląda dobrze. Na razie zamknijmy temat tej funkcji, ale niedługo okaże się, że te uproszczenia wprowadziły pewien problem.

Wyznaczanie średniej

Funkcja zwracająca średnią może wyglądać następująco:

float eval_mean(const int *buff, int capacity) {
  float result = 0;
  for (int i = 0; i < capacity; ++i)
    result += buff[i];
  return result / capacity;
}

Nazwa funkcji oznacza oszacowanie/wyznaczenie (ang. evalueate) średniej (ang. mean). W argumentach podajemy wskaźnik do tablicy oraz długość tablicy. Wewnątrz logika jest identyczna jak opisana w teorii. Dla 10 wyników z poprzedniego przykładu (12 pomiarów) średnia wyszła 9,2.

Sprawdźmy jednak jak średnia wygląda dla 2 elementów. Ustawmy 2 iteracje w "pomiarach", jak pamiętamy wyniki to 7 i 9 wiec średnia powinna wyjść 8. Tymczasem średnia wyszła: 1,6.

Dzieje się dlatego, że nie mamy informacji o tym czy zdążyliśmy zapełnić całą tablicę – dla 2 elementów pomiary "dopiero się rozpędzają", a wiarygodne wyniki otrzymamy dopiero od 10 elementów. Tablica jest obiektem globalnym więc nieużyte elementy mają wartość 0, która w tym przypadku może być interpretowana jako poprawne pomiary.

Tak, można zmienić wartość capacity, zrobimy to za chwilę.

Warunki początkowe

Aby poradzić sobie z tym problemem można obrać 2 drogi. Albo poczekać aż "algorytm się rozgrzeje" albo sprawdzić w jakim miejscu jest aktualnie wybrany indeks. Specjalnie zaznaczyłem, że algorytm wypełniania tablicy ma pewną bolączkę – przez uproszczenia nie ma już stałej liczby wskazującej na koniec napełniania bufora (current_index = 2 może oznaczać, że albo są 2 elementy, albo zapełniliśmy bufor i jest 10 elementów w tym 2 nadpisane).

Wybierzmy ten drugi sposób, stwórzmy zmienną informującą o liczbie zapełnionych elementów usage_count przekazywanej przez wskaźnik:

int usage_count;

void feed_buffer(int *buff, int capacity, int *current_index, int *usage_count, int sample) {
  buff[(*current_index)++] = sample;
  *usage_count = max(*usage_count, *current_index);
  *current_index %= capacity;
}

Sposobów na realizację może być kilka, ja wybrałem użycie funkcji max(). Operację należy wstawić po inkrementacj, a przed sprawdzeniem danych tak by możliwe było zapisanie wartości równiej liczbie elementów (capacity).

Jak widać liczba argumentów zrobiła się dość duża. Tego wszystkiego dałoby się uniknąć, gdybyśmy odwołali się do zmiennych globalnych, albo przełożyli kod do osobnego pliku lub klasy, co zrobimy w kolejnej części kursu.

Jak teraz użyć zmienną usage_count? Wystarczy że będziemy stosować ją w roli liczby elementów tablicy:

void setup() {
  Serial.begin(9600);

  for (int i = 0; i < 2; i++)
    feed_buffer(samples_buffer, BUFFER_LENGTH, &current_buffer_index, &usage_count, read_sensor());
  
  printer(samples_buffer, usage_count);
  Serial.print("Mean: "); Serial.println(eval_mean(samples_buffer, usage_count)); 
}

W wyniku otrzymamy: 

0: 7
1: 9
Mean: 8.00

Jak widać wyniki są poprawne i co ciekawe, ani nie zmieniliśmy funkcji wyznaczającej średnią, ani funkcji wypisującej elementy tablicy – jedynie zmieniliśmy funkcję zasilającą bufor danymi.

Wyznaczanie mediany

Mediana jest nieco trudniejsza do wyznaczenia, bo potrzebne jest posortowanie tablicy, które wymaga funkcji do zamiany elementów tablicy. Nie możemy jednak posortować oryginalnej tablicy, bo zakłuci to przepływ pomiarów więc musimy utworzyć kopię roboczą bufora. Dopiero później możemy wyznaczyć wartość środkową, ale i w tym pojawi się problem co zrobić dla tablicy o parzystej liczbie elementów (gdzie nie ma elementu środkowego).

Można wyczuć, że czeka nas wiele kroków pośrednich, dobrze jednak określić co się robi i w jakiej kolejności oraz wydzielić pomniejsze zadania prowadzące do realizacji większego celu – metoda dziel i zwyciężaj zawsze się opłaca   Kopiowania tablicy nie unikniemy, można się co najwyżej zastanowić: czy częściej będę wpisywał pomiary z czujników, czy częściej wyznaczał medianę? Sensowne jest, że częściej zapisujemy pomiary.

Sortowanie

Sortowanie polega na ułożeniu elementów w kolejności od najmniejszego do największego (lub odwrotnie). Jest to tak popularna operacja, że doczekała się całego mnóstwa algorytmów o złożoności (liczbie kroków potrzebnych do osiągnięcia celu) od O(n²) (czyli rosnącej kwadratowo wraz ze wzrostem danych), przez wiele algorytmów O(nlog_n), a skończywszy na wydajnych o złożoności liniowej O(n) ale tylko w specyficznych sytuacjach (tzw. niedetrministyczne).

Zapis O(n²) oznacza złożoność algorytmu – w tym przypadku złożoność n² (kwadratowa), tj. trzeba wykonać n² kroków, aby przetworzyć n danych.

Warto pamiętać o właściwościach danych posortowanych:

• jeżeli z posortowanych danych usuniemy dowolny element to dane pozostaną posortowane,
• dodanie elementu do posortowanych danych tak by poprzedzający element był mniejszy, a kolejny większy lub równy sprawi, że dane pozostaną posortowane.

Widać zatem, że zapytanie o częstość dokonywania pomiarów i wyznaczania mediany jest bardzo istotne!

Załóżmy, że bierzemy algorytm sortowania bąbelkowego o tragicznej złożoności O(n²). Oznacza to że dla naszych 10 elementów tablicy wykonamy teoretycznie aż 100 operacji! W praktyce trochę mniej.

Pomyślmy co się bardziej opłaca:

• przy każdej medianie: kopiujemy tablicę, sortujemy – O(n + n²) ,
• przy każdym pomiarze: usuwamy najstarszy element, wkładamy element do już posortowanej tablicy – O(n+n).

Wyraźnie widać, że lepiej jest dodawać elementy przy pomiarze, jednak na korzyść tej pierwszej metody przemawia inny aspekt – łatwiej zachować uniwersalność kodu.

Dodanie kolejnej tablicy do już i tak pęczniejącej funkcji spowoduje nadmierne rozbudowanie jej funkcjonalności. Dobrze jest móc w prosty sposób powiedzieć co robi funkcja, a funkcja co zwraca 2 typy tablic i jeszcze modyfikuje jakąś zmienną pod wskaźnikiem zaczyna być zbyt skomplikowana.

Tego wszystkiego dałoby się uniknąć tworząc osobną bibliotekę.

Zatem sortowanie będzie w funkcji wyznaczającej medianę. Zacznijmy zatem pisać kod:

void sort_buffer(int *buff, int capacity) {
  for (int i = 0; i < capacity - 1; ++i)   {
    for (int j = 0; j < capacity - i - 1; ++j) {
      if (buff[j] > buff[j + 1])
        swap(buff[j], buff[j + 1]);
    }
  }
}

Funkcję swap() możemy zaczerpnąć z poprzedniej części kursu. Weźmy wariant z referencjami, ale dodajmy specyfikator inline, bo będzie ona często używana i może zostać zoptymalizowana:

inline void swap(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}

Na czym polega ten algorytm sortowania? Sprawdza "wszystkie ze wszystkimi" elementy czy potrzebują być posortowane. Iteracje zmienną j są ograniczone do zmiennej i dlatego, że jeżeli sprawdzimy jeden z elementów ze wszystkimi i ustalimy jego miejsce jako najmniejszy (w porównaniu z pozostałymi) to już nie trzeba go sprawdzać. Zatem złożoność tego algorytmu jest mniejsza od O(n²), wynosi raczej O(n²/2) co i tak jest dużo.

Zagnieżdżenie jednej pętli w drugiej wskazuje na złożoność kwadratową.

Dodajmy teraz pomocniczą tablicę i funkcję do kopiowania wartości tablic:

int sorting_buffer[BUFFER_LENGTH];

void copy_buffers(const int *src, int *dst, int len){
  for(int i = 0; i < len; ++i)
    dst[i] = src[i];
}

Zakładamy, że rozmiar tablic jest identyczny. Dla pewności dodałem specyfikator const, bo tu o pomyłkę bardzo łatwo, a może w ten sposób uda się rozwiązać ewentualne problemy.

Teraz pozostało dodać funkcję wyznaczającą medianę. Kopiujemy funkcję wyznaczającą średnią, zmieniamy nazwę i piszemy ciało funkcji. Tylko jedna kwestia... jeżeli dane nie posiadają wyrazu środkowego (są parzyste) to co robimy?

Jak jesteśmy leniwi to nie przejmujemy się – bierzemy wyraz środkowy dzieląc liczbę elementów na 2 całkowicie i wtedy wpadnie element tablicy "bardzie po lewej". Jeżeli jednak jesteśmy skrupulatni to dla parzystej liczby danych wyznaczamy średnią z 2 elementów środkowych. My jesteśmy skrupulatni  

float eval_median(int *buff, int capacity) {
  if (capacity % 2 == 0)
    return eval_mean(buff + capacity / 2 - 1, 2); // zastąpienie dzielenia: capacity >> 1
  return buff[capacity / 2];
}

Kod wygląda na trudny ale są tu użyte tylko 2 sztuczki:

• dzielenie całkowitoliczbowe: jeżeli capacity = 5, to capacity / 2 nie da 2,5 tylko 2 (0,5 jest ucięte),
• użyliśmy funkcji eval_mean na fragmencie tablicy bez jawnego wydzielania jej do osobnej zmiennej.

Dzielenie zmiennoprzecinkowe w 8 bit AVR jest realizowane programowo, stąd warto go unikać. Gdy dzielnikiem jest potęga 2 to można zastąpić to przesunięciem bitowym w prawo o log₂(dzielnik) miejsc (co może za nas zrobić kompilator na etapie optymalizacji).

Zacznijmy od przypadku dla rozmiaru nieparzystego – nie ma tam warunku domyślnego else, dlatego że powyższy warunek if ma swoją instrukcję return, która determinuje przebieg funkcji. Wybieramy indeks środkowy ucinając końcówkę po przecinku, przykładowo 9 / 2 = 4,5 ≈ 4.

Lub 9 >> log₂(2) = 9 >> 1 = 4 – najmłodszy bit o wartości 1 zostaje utracony.

Dla rozmiaru parzystego jest trudniej. Po pierwsze jaki indeks nas interesuje? Dla rozmiaru 10, ma to być indeks 4 (licząc od 0), dla rozmiaru 4 ma to być indeks 1 itd. Dzielimy więc rozmiar danych na 2 i zmniejszamy o 1. Dalej korzystamy z "magii wskaźników" przesuwamy wskaźnik na obszar pamięci o wyznaczoną liczbę pozycji i mówimy funkcji, że "to jest nasza tablica", a funkcja niezabardzo rozróżniając tablice od wskaźników, bierze co tam dostała. Mówimy jej jeszcze, że ta nasza tablica ma 2 elementy. Funkcja wyznacza z tego co dostała średnią i zwraca wynik.

Widzimy zatem jaki potencjał kryją w sobie tablice. Pozornie niebezpieczna operacja przesuwania wskaźnika okazała się niebywale przydatna.

Przetestujmy działanie programu, tym razem umieszczam cały kod programu, bo w międzyczasie wiele się działo i kod zdążył urosnąć:

constexpr int BUFFER_LENGTH = 10;

int samples_buffer[BUFFER_LENGTH];
int sorting_buffer[BUFFER_LENGTH];

int current_buffer_index;
int usage_count;

int read_sensor() {
  return random(20);
}

inline void swap(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}

void copy_buffers(const int *src, int *dst, int len){
  for(int i = 0; i < len; ++i)
    dst[i] = src[i];
}

void sort_buffer(int *buff, int capacity) {
  for (int i = 0; i < capacity - 1; ++i)   {
    for (int j = 0; j < capacity - i - 1; ++j) {
      if (buff[j] > buff[j + 1])
        swap(buff[j], buff[j + 1]);
    }
  }
}

void printer(const int *buff, int capacity) {
  for(int i = 0; i < capacity; ++i) {
    Serial.print(i); Serial.print(F(": " )); Serial.println(*(buff + i)); 
  }
}

void feed_buffer(int *buff, int capacity, int *current_index, int *usage_count, int sample) {
  buff[(*current_index)++] = sample;
  *usage_count = max(*usage_count, *current_index);
  *current_index %= capacity;
}

float eval_mean(const int *buff, int capacity) {
  float result = 0;
  for (int i = 0; i < capacity; ++i)
    result += buff[i];
  return result / capacity;
}


float eval_median(int *buff, int capacity) {
  if (capacity % 2 == 0)
    return eval_mean(buff + capacity / 2 - 1, 2); // zastąpienie dzielenia: capacity >> 1
  return buff[capacity / 2];
}


void setup() {
  Serial.begin(9600);

  for (int i = 0; i < 10; i++)
    feed_buffer(samples_buffer, BUFFER_LENGTH, &current_buffer_index, &usage_count, read_sensor());
  
  printer(samples_buffer, usage_count);
  Serial.print("Mean: "); Serial.println(eval_mean(samples_buffer, usage_count)); 

  copy_buffers(samples_buffer, sorting_buffer, usage_count);
  sort_buffer(sorting_buffer, usage_count);
  printer(sorting_buffer, usage_count);
  Serial.print("Median: "); Serial.println(eval_median(sorting_buffer, usage_count)); 
}

void loop() {
}

Na samej górze kodu umieszczamy pogrupowane stałe i zmienne. W dalszej kolejności są nasze "narzędzia" czyli funkcje, które też staramy się pogrupować zależnie od przeznaczenia.

Na samej górze jest funkcja obsługi czujnika – jest ona niepowiązana z resztą kodu. Niżej są 4 funkcje ogólnego przeznaczenia – pierwsza dotyczy pojedynczych zmiennych, 3 kolejne dotyczą tablic. Kolejne 3 funkcje dotyczą istoty algorytmu i do działania wymagają wyżej wymienionych narzędzi.

Pamiętamy, aby funkcje wchodzące w skład innych funkcji były umieszczone wyżej w kodzie.

Na koniec wszystko zostaje użyte w funkcji setup() dla 10 elementów i uzyskamy wyniki: średnia 10,3, mediana: 9,5:

0: 7
1: 9
2: 13
3: 18
4: 10
5: 12
6: 4
7: 18
8: 3
9: 9
Mean: 10.30
0: 3
1: 4
2: 7
3: 9
4: 9
5: 10
6: 12
7: 13
8: 18
9: 18
Median: 9.50

Jak widać mediana została wyznaczona ze średniej 2 elementów: 9 i 10.

Patrząc na to co właśnie napisaliśmy można pomyśleć, że to całkiem spory program i jeżeli posiedzimy nad nim jeszcze trochę, to szybko urośnie do kilkuset linii kodu – tak może się zdarzyć, dlatego w kolejnej części kursu zamienimy ten kod w bibliotekę. To że kod rośnie jest normalne i przy większych programach nie ma co z tym walczyć jeżeli poprawia to czytelność kodu i sprawia, że kod jest bardziej uniwersalny. Z drugiej strony, jeżeli nadmierne rozdrobnienie powoduje problemy z wydajnością, to trzeba pójść na kompromis.

Wydajność vs łatwość programowania to nieodłączny dylemat programowania. Z tego powodu popularność zyskały języki wysokiego poziomu, interpretowane, które choć są mniej wydajne od kompilowanych to są prostsze, a z ich pomocą szybciej tworzy się skomplikowane aplikacje. 

Ciąg dalszy

Ta część kursu urosła trochę za mocno, dlatego w ramach pracy domowej spróbuj samemu napisać funkcję realizującą odchylenie standardowe, a w kolejnej części otrzymasz odpowiedź. Postaramy się też wyodrębnić nasze narzędzia do osobnego pliku tworząc bibliotekę, tak by użytkownik nie musiał oglądać zbędnych bebechów naszego kodu. Dotkniemy też klas, którego starałem się uniknąć, ale skoro już jesteśmy w temacie to szkoda z tego nie skorzystać.

Edytowano Grudzień 7, 2021 przez Gieneq

[Gieneq]

W końcu odłożyłem setki innych równie pasjonujących spraw na bok i zebrałem się żeby dokończyć tę część kursu. Wyszła ciut przydługa dlatego została podzielona na 2 artykuły. Mam po tej części pewną refleksję, czy założenie, że końcowy przykład, który w szkicu mam podzielony na 3 artykuły faktycznie tyle zajmie...  I hope so i postaram się nie lać wody  

[Vova]

Podziwiam ludzi, którzy rozumieją chociaż 5 % z tego wszystkiego  

[pmochocki]

@Gieneq z tym tytułem to na serio? Metodyka pomiarów, wstęp do statystyki czy metod numerycznych, statystyka w pomiarach...

Artykuł jest fajny, ale bardzo napakowany. Jeszcze złożoność obliczeniową dodałeś

Ja wiem, że to są podstawy, ale jednak część osób pewnie wymiękła przy wzorze na średnią... 

Sugeruje dzielenie wiedzy na mniejsze kawałki. 

EDIT: Mogę mieć zły punkt odniesienia, bo czasami czytam artykuły mojemu dziewięciolatkowi... 

Edytowano Grudzień 12, 2021 przez pmochocki

[wojtowa]

Wielkie dzięki za ten materiał i czekam na dalsze części. bardzo mi pomogło w obliczeniach średniej na tablicach wielowymiarowych, zaoszcędziło mi to wielu godzin na dochodzenie i testowanie

BTW - nigdy nie spotkałem się z określeniem krzywej Gaussa jako krzywej "kapeluszowej", popularna nazwa to dzwonowa 

[Gasnyca]

Pomocne 7 części, dziękuje. Szkoda że niedokończone bo myślałem ze dojdzie do tworzenia małej biblioteki tak jak było wspomniane w tej części. Co ciekawe pierwszego dnia nie do końca wszystko rozumiałem, ale już po przerobieniu w kompilatorze 7 części oraz ponownego przeczytania kilku części głowa zrozumiała co i jak (a przynajmniej tak mi sie wydaje )