Arrays

Video (22.10.2024)

Prezentácia

• prezentácia v HTML

Zdrojový kód

• converter-array-bad.c
• converter-array.c
• data
• segfault.c
• linear.c
• linear2.c
• binary-search.c
• bubble-sort.c
• bubble-sort2.c
• qsort.c

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, fahrenheit2, fahrenheit3 a fahrenheit4.
• 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 fahrenheit = 9.0/5.0 * celsius + 32;
    float kelvin = celsius + 273.15;

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

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

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

    printf("%.2f in Celsius is %.2f in Fahrenheit and %.2f in Kelvin\n",
        celsius, fahrenheit, kelvin );
    printf("%.2f in Celsius is %.2f in Fahrenheit and %.2f in Kelvin\n",
        celsius2, fahrenheit2, kelvin2 );
    printf("%.2f in Celsius is %.2f in Fahrenheit and %.2f in Kelvin\n",
        celsius3, fahrenheit3, kelvin3 );
    printf("%.2f in Celsius is %.2f in Fahrenheit and %.2f in Kelvin\n",
        celsius4, fahrenheit4, 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 fahrenheit = 9.0/5.0 * data[index] + 32;
        float kelvin = data[index] + 273.15;

        printf("%d: %.2f in Celsius is %.2f in Fahrenheit and %.2f in Kelvin\n",
            index+1, data[index], fahrenheit, 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 fahrenheit = 9.0/5.0 * data[index] + 32;
        float kelvin = data[index] + 273.15;

        printf("%d: %.2f in Celsius is %.2f in Fahrenheit and %.2f in Kelvin\n",
            index+1, data[index], fahrenheit, 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 fahrenheit = 9.0/5.0 * data[index] + 32;
        float kelvin = data[index] + 273.15;

        printf("%d: %.2f in Celsius is %.2f in Fahrenheit and %.2f in Kelvin\n",
            index+1, data[index], fahrenheit, 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 fahrenheit = 9.0/5.0 * data[index] + 32;
        float kelvin = data[index] + 273.15;

        printf("%d: %.2f in Celsius is %.2f in Fahrenheit and %.2f in Kelvin\n",
            index+1, data[index], fahrenheit, 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

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

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;
}

Video