Week 7

Polia - úvod, indexovanie prvkov, deklarácia a inicializácia poľa, prechod poľom, cyklus for, Off-by-One Error, Segmentation fault, lineárne vyhľadávanie, operátor sizeof(), pole ako parameter, binárne vyhľadávanie, bublinkové triedenie, quick sort

Video (8.11.2018, Paralelka B)

Prezentácia

Zdrojový kód

Poznámky k prednáške

Úvod do polí

  • Aktuálne vie converter.c previesť práve jednu hodnotu. Avšak čo ak by sme chceli merať teplotu 4x? Musíme pridať potrebné premenné navyše: celsius2, celsius3 a celsius4 a adekvátne kelvin2, kelvin3, kelvin4, fahrnheit2, fahrnheit3 a fahrnheit4.
  • Modifikácia kódu bude teda nasledovná (converter-array-bad.c):
#include <stdio.h>

int main(){
    printf("Enter the temperature in Celsius: ");
    float celsius, celsius2, celsius3, celsius4;
    scanf( "%f %f %f %f", &celsius, &celsius2, &celsius3, &celsius4 );

    float fahrnheit = 9.0/5.0 * celsius + 32;
    float kelvin = celsius + 273.15;

    float fahrnheit2 = 9.0/5.0 * celsius2 + 32;
    float kelvin2 = celsius2 + 273.15;

    float fahrnheit3 = 9.0/5.0 * celsius3 + 32;
    float kelvin3 = celsius3 + 273.15;

    float fahrnheit4 = 9.0/5.0 * celsius4 + 32;
    float kelvin4 = celsius4 + 273.15;

    printf("%.2f in Celsius is %.2f in Fahrnheit and %.2f in Kelvin\n",
        celsius, fahrnheit, kelvin );
    printf("%.2f in Celsius is %.2f in Fahrnheit and %.2f in Kelvin\n",
        celsius2, fahrnheit2, kelvin2 );
    printf("%.2f in Celsius is %.2f in Fahrnheit and %.2f in Kelvin\n",
        celsius3, fahrnheit3, kelvin3 );
    printf("%.2f in Celsius is %.2f in Fahrnheit and %.2f in Kelvin\n",
        celsius4, fahrnheit4, kelvin4 );

    return 0;
}
  • Čo ale v prípade, ak by sme chceli merať teplotu počas dňa každú hodinu? Čo ak by sme chceli merať každú polhodinu? Každú minútu? Budeme zasa copy'n'paste-ovať?
  • Najčastejší problém: Neviem dopredu povedať, aké bude N.
  • Pole je štruktúra, ktorá:
    • Obsahuje prvky rovnakého typu
    • Má konečnú veľkosť, ktorá musí byť známa už v čase vytvárania poľa

Aktualizácia converter.c o pole

  • Upravíme náš príklad pre konverziu teploty tak, aby používal pole.
  • Deklarácia poľa: Načítanie čísla N, a deklarácia poľa, ktoré bude uchovávať hodnoty typu float.
  • Postupné načítanie všetkých teplôt a ich umiestnenie v poli.
  • Vypísanie výsledku na obrazovku.
  • Výsledný kód (converter-array.c):
#include <stdio.h>

int main(){
    // ask for the number of elements in array
    printf("Enter the nr of measurements: ");
    int count;
    scanf( "%d", &count );

    // declare an array
    float data[count];

    int index = 0;

    while( index != count ){
        printf("Enter the %d. temperature in Celsius: ", index + 1);
        float celsius;
        scanf( "%f", &celsius );
        data[index] = celsius;
        index++;
    }

    index = 0;
    while( index != count ){
        float fahrnheit = 9.0/5.0 * data[index] + 32;
        float kelvin = data[index] + 273.15;

        printf("%d: %.2f in Celsius is %.2f in Fahrnheit and %.2f in Kelvin\n",
            index+1, data[index], fahrnheit, kelvin );
        index++;
    }

    return 0;
}

Presmerovanie štandardného vstupu

  • Aby sme sa nezdržiavali opätovným načítavaním hodnôt znova a znova, môžeme si vstupné údaje pripraviť do samostného súboru a pomocou presmerovania štandardného vstupu zabezpečiť ich načítanie v programe.
  • Súbor so vstupnými údajmi bude obsahovať všetky údaje, ktoré by sme ináč načítavali ručne. Pre našu implementáciu teda môže vyzerať nasledovne (data):
5
17.5 17.9 18.4 18.2 18.1
  • Presmerovanie následne zabezpečíme spustením preloženého programu v tvare:
./converter < data

Inicializácia prvkov poľa

  • Namiesto postupného plnenia prvkov poľa alebo presmerovania zo vstupu môžeme pole pri deklarácii rovno inicializovať:
#include <stdio.h>

int main(){
    // number of elements in array
    int count = 10;

    // declare and initialize an array
    float data[] = {38.7, 39, 40.5, 41, 41.5, 41.5, 40, 39.5, 38, 37};

    int index = 0;
    while( index != count ){
        float fahrnheit = 9.0/5.0 * data[index] + 32;
        float kelvin = data[index] + 273.15;

        printf("%d: %.2f in Celsius is %.2f in Fahrnheit and %.2f in Kelvin\n",
            index+1, data[index], fahrnheit, kelvin );
        index++;
    }

    return 0;
}
  • Túto inicializáciu je však možné vykonať len raz a aj to len pri deklarácii poľa!

Cyklus for

  • Pri práci s poľom je možné s výhodou použiť aj cyklus for:
#include <stdio.h>

int main(){
    // number of elements in array
    int count = 10;

    // declare and initialize an array
    float data[] = {38.7, 39, 40.5, 41, 41.5, 41.5, 40, 39.5, 38, 37};

    for( int index = 0; index < count; index++ ){
        float fahrnheit = 9.0/5.0 * data[index] + 32;
        float kelvin = data[index] + 273.15;

        printf("%d: %.2f in Celsius is %.2f in Fahrnheit and %.2f in Kelvin\n",
            index+1, data[index], fahrnheit, kelvin );
    }

    return 0;
}

Hranice poľa

Off-by-one Error

  • Off-by-one Error
  • Častá chyba pri indexovaní poľa, pomýlenie sa o 1 na začiatku alebo konci. Obyčajne spôsobená nesprávnou podmienkou.
  • Podobný typ tohto problému sa volá Fencepost problem: Predstavte si, že máte plot dlhý 30m a každé 3m potrebujete umiestniť tyčku. Koľko tyčiek do tohto plota umiestnite? Odpoveď 10 je zlá, pretože ich je 11.

Segmentation fault

  • Ľahko sa však môžeme dopustiť aj opačného problému - značné presiahnutie veľkosti poľa. Prekladač totiž hranice poľa nekontroluje, čo môže viesť ku pádu vašej aplikácie so správou Segmentation fault. Túto situáciu ilustruje nasledujúci príklad (segfault.c):
#include <stdio.h>

int main(){
    // declare and initialize an array
    float data[] = {38.7, 39, 40.5, 41, 41.5, 41.5, 40, 39.5, 38, 37};

    for(int index = 0; index < 10000; index++){
        float fahrnheit = 9.0/5.0 * data[index] + 32;
        float kelvin = data[index] + 273.15;

        printf("%d: %.2f in Celsius is %.2f in Fahrnheit and %.2f in Kelvin\n",
            index+1, data[index], fahrnheit, kelvin );
    }

    return 0;
}
  • Odhaliť tento typ problému je možné pomocou iných nástrojov ako prekladača, napr. pomocou niektorého lint-u pre jazyk C (zoznam lint-erov pre jazyk C na Wikipedii). Napríklad pomocou nástroja cppcheck v tvare:
cppcheck --enable=all segfault.c

Vyhľadávanie prvkov v poli

  • Operácia vyhľadávania patrí k najčastejším operáciám, ktoré budete nad údajmi v poli robiť. Napr. aj najdôležitejšia operácia pri práci s SQL databázami je práve operácia selekcie (vyhľadávania).
  • V čom spočíva problém - máme pole, ktoré obsahuje obrovské množstvo údajov a našou úlohou je nájsť požadovaný údaj čo najrýchlejšie (a teda - čo najefektívnejšie).

Linear Search

  • Dobrovoľník z davu: Tvojou úlohou je čo najrýchlejšie nájsť pod týmito kartami číslo 7. O prvkoch v poli vieš len toľko, že nie sú nijak usporiadané. Po dokončení sa treba opýtať: Ako si postupoval?. Výsledkom by malo byť, že začal karty obracať zľava doprava (pokiaľ ich náhodou nezačne obracať náhodne :-))
  • Presne takto funguje lineárne vyhľadávanie - hľadáme od prvého prvku poľa až po posledný, pričom vyhľadávanie skončíme, keď prvok nájdeme (linear.c):
#include <stdio.h>

int main(){
    int data[] = {5,4,2,6,8,1,9,3,7,6};
    int find;
    printf("Which number to find: ");
    scanf("%d", &find);

    int location = -1;
    for(int idx=0; idx < 10; idx++){
        if(data[idx] == find){
            location = idx;
            break;
        }
    }

    if(location != -1){
        printf("Location of %d is at %d\n", find, location);
    }
    else{
        printf("Not found\n");
    }

    return 0;
}
  • Je však praktickejšie takéto riešenie osamostatniť do samostatnej funkcie, ktorej iba posunieme pole a prvok, ktorý chceme nájsť (linear2.c):
#include <stdio.h>

int search(const int data[], const int find);

int main(){
    int data[] = {5,4,2,6,8,1,9,3,7,6};
    int find;
    printf("Which number to find: ");
    scanf("%d", &find);

    int location = search(data, find);
    if(location != -1){
        printf("Location of %d is at %d\n", find, location);
    }
    else{
        printf("Not found\n");
    }

    return 0;
}

int search(const int data[], const int find){
    int location = -1;
    for(int idx=0; idx < 10; idx++){
        if(data[idx] == find){
            location = idx;
            break;
        }
    }

    return location;
}

Zistenie veľkosti poľa

  • Parametrom funkcie search() ale nie vždy bude pole len o veľkosti 10 prvkov. Ako sme hovorili, veľkosť môže byť ľubovoľná - teda N. Ako teda toto N zistiť?
  • Na zistenie veľkosti poľa, je možné v niektorých prípadoch použiť operátor sizeof(). V prípade, ak jeho parametrom bude pole, vráti počet bytov, ktoré toto pole zaberá v pamäti:
#include <stdio.h>

int main(){
    int data[] = {1,2,3,4,5};

    printf("sizeof(data): %ld\n", sizeof(data));

    return 0;
}
  • Ak chceme vedieť počet prvkov v poli, výsledok treba ešte predeliť počtom bytov, ktoré v pamäti zaberá aj typ prvkov v ňom uložených:
#include <stdio.h>

int main(){
    int data[] = {1,2,3,4,5};

    printf("sizeof(data): %ld\n", sizeof(data)/sizeof(int));

    return 0;
}
  • Po aktualizovaní funkcie search() o túto možnosť dostaneme nasledujúci kód:
int search(const int data[], const int find){
    int size = sizeof(data)/sizeof(int);
    int location = -1;
    for(int idx=0; idx < size; idx++){
        if(data[idx] == find){ 
            location = idx;
            break;
        }
    }

    return location;
}
  • Ten však nebude pracovať správne, nakoľko pole je funkcii predávané adresou a nie hodnotou. Preto, ak pole odovzdávate nejakej funkcii ako parameter, odovzdajte nutne aj ďalší, ktorý hovorí o veľkosti tohto poľa:
int search(const int data[], const int size, const int find){
    int location = -1;
    for(int idx=0; idx < size; idx++){
        if(data[idx] == find){ 
            location = idx;
            break;
        }
    }

    return location;
}

Binary Search

  • Teraz to skús ešte raz, ale o tejto sade platí, že je usporiadaná. Pokús sa číslo nájsť na čo najmenší počet pokusov (resp: máš na to max. 3 pokusy). (paródia na: Uhádni číslo, ktoré si myslím, ale máš na to _N pokusov_). Po nájdení sa treba opýtať, akú stratégiu zvolil, pričom by mal zvoliť metódu delenia intervalu ;)
  • Presne takto funguje binárne vyhľadávanie - ak vieme, že sú údaje v poli utriedené, môžeme túto znalosť využiť v náš prospech pri vyhľadávaní - pri akomkoľvek výbere prvku v poli budeme vždy vedieť na základe podmienky utriedenia, v ktorej časti poľa sa náš prvok bude nachádzať.
  • Takýmto spôsobom fungujú napr. indexy v databázach - utriedený jeden stĺpec informácií pre urýchlenie operácie vyhľadávania, ktorý odkazuje na úplné záznamy do pôvodnej tabuľky (binary-search.c):
#include <stdio.h>

int search(const int[], const int, const int);

int main(){
    int data[] = {1,2,3,4,5,6,7,8,9,10};
    int find;
    printf("Which number to find: ");
    scanf("%d", &find);

    int location = search(data, sizeof(data)/sizeof(int), find);
    if(location != -1){
        printf("Location of %d is at %d\n", find, location);
    }
    else{
        printf("Not found\n");
    }

    return 0;
}

int search(const int array[], const int length, const int element){
    int middle, start, end;

    start = 0;
    end = length - 1;

    while(start <= end){
        middle = start + (end - start + 1) / 2;

        if (array[middle] == element){
            return middle;
        }
        else if (array[middle] > element){
            end = middle - 1;
        }
        else{ //(array[middle] < element)
            start = middle + 1;
        }
    }

    return -1;
}

Zložitosť problémov

  • Ktorý z týchto vyhľadávacích algoritmov bol lepší (efektívnejší)?
  • Sumarizujme výsledky
Algoritmus Najlepší prípad Najhorší prípad
Lineárne vyhľadávanie (Linear Search) O(1) O(n)
Binárne vyhľadávanie (Binary Search) O(1) O(log(n))

Triedenie prvkov v poli

  • Ukázali sme si, že operáciu vyhľadávania vieme urýchliť tak, že zoznam prvkov v poli budeme udržiavať utriedený. Ako však utriediť prvky v poli?
  • Sedem dobrovoľníkov, ktorí sa postavia do konfigurácie uvedenej na slajde a necháme ich usporiadať samých seba od najmenšieho čísla po najväčšie. Následne sa ich treba opýtať, ako postupovali - úvod do bublinkového triedenia.
  • Priebeh bublinkového triedenia:
4 1 5 9 8 2 3
1 4 5 8 2 3 9
1 4 5 2 3 8 9
1 4 2 3 5 8 9
1 2 3 4 5 8 9
  • Priebeh selection sortu:
4 1 5 9 8 2 3
1 4 5 9 8 2 3
1 2 5 9 8 4 3
1 2 3 9 8 4 5
1 2 3 4 8 9 5
1 2 3 4 5 9 8
1 2 3 4 5 8 9
  • Ktorý z týchto triediacich algoritmov bol lepší (efektívnejší)?
  • Sumarizujme výsledky
Algoritmus Najlepší prípad Najhorší prípad
Bublinkové triedenie (Bubble Sort) O(n) O(n^2)
Triedenie výberom (Selection Sort) O(n^2) O(n^2)

Bublinkové triedenie

  • Jedna z najjednoduchších reprezentácií triediacich algoritmov
  • Kód môže vyzerať nasledovne (bubble-sort.c):
#include <stdio.h>

int main(){
    int numbers[] = { 8, 3, 5, 2, 1, 6, 7 };
    int size = 7;

    // before
    for(int i = 0; i < size; i++){
        printf("%d ", numbers[i]);
    }
    printf("\n");

    // sort
    for(int j = 0; j < size -1; j++){
        for(int i = 0; i < size - 1; i++){
            if(numbers[i+1] < numbers[i]){
                // swap
                int tmp = numbers[i+1];
                numbers[i+1] = numbers[i];
                numbers[i] = tmp;
            }
        }
    }

    // after
    for(int i = 0; i < size; i++){
        printf("%d ", numbers[i]);
    }
    printf("\n");

    return 0;
}
  • Keď sa pozrieme na rozsahy cyklov for, vidíme, že algoritmus triedenia je možné zrealizovať aj na menej krokov:
    for(int j = size-1; j > 0; j--){
        for(int i = 0; i < j; i++){
            if(numbers[i+1] < numbers[i]){
                // swap
                int tmp = numbers[i+1];
                numbers[i+1] = numbers[i];
                numbers[i] = tmp;
            }
        }
    }
  • Samozrejme, pre zvýšenie znovupoužiteľnosti je dobré vytvoriť realizáciu bublinkového triedenia ako samostatnú funkciu (bubble-sort2.c):
#include <stdio.h>

void bsort(int[], const int);

int main(){
    int numbers[] = { 8, 3, 5, 2, 1, 6, 7 };
    int size = 7;

    // before
    for(int i = 0; i < size; i++){
        printf("%d ", numbers[i]);
    }
    printf("\n");

    bsort(numbers, size);

    // after
    for(int i = 0; i < size; i++){
        printf("%d ", numbers[i]);
    }
    printf("\n");

    return 0;
}

void bsort(int numbers[], const int size){
    // sort
    for(int j = size-1; j > 0; j--){
        for(int i = 0; i < j; i++){
            if(numbers[i+1] < numbers[i]){
                // swap
                int tmp = numbers[i+1];
                numbers[i+1] = numbers[i];
                numbers[i] = tmp;
            }
        }
    }
}

qsort() & stdlib.h

  • V praxi nebudete potrebovať vytvárať vlastnú implementáciu niektorého (najlepšieho) z triediacich algoritmov - implementácie sú už hotové a stačí ich len použiť
  • Jazyk C poskytuje v rámci štandardnej knižnice stdlib.h pripravenú implementáciu Quick sort algoritmu ( qsort.c):
#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b){
    const int *arg1 = a;
    const int *arg2 = b;

    return *arg1 - *arg2;
}

int main(){
    int numbers[] = { 8, 3, 5, 2, 1, 6, 7 };
    int size = 7;

    // before
    for(int i = 0; i < size; i++){
        printf("%d ", numbers[i]);
    }
    printf("\n");

    // sort
    qsort(numbers, size, sizeof(int), compare);

    // after
    for(int i = 0; i < size; i++){
        printf("%d ", numbers[i]);
    }
    printf("\n");

    return 0;
}

Doplňujúce zdroje

  1. Proč počítačům dělají problémy desetinná čísla
  2. What Every Computer Scientist Should Know About Floating-Point Arithmetic
  3. W. Wulf, M. Shaw: Global variable considered harmful, 1973
  4. Big-O cheat sheet
  5. Sorting algorithm animations
  6. Data atructure animations using processing.js
  7. AlgoRythmics - kanál na YouTube, ktorý tanečne prezentuje rozličné typy triediacich algoritmov.
  8. Operátor sizeof(): c-reference - Queries size of the object or type. Used when actual size of the object must be known.
  9. Cyklus for: c-reference - Executes a loop. Used as a shorter equivalent of while loop.

Video