1  Typy i struktury danych

1.1 Typy danych

Typ danych to zbiór wartości, które mogą być przechowywane w zmiennej lub strukturze danych.

Typy danych:

• Skalarne
• Wektorowe
• Macierzowe
• Tensorowe
• Listy/krotki
• Stosy
• Kolejki
• Słowniki (mapy)
• Zbiory
• Własne klasy: typy danych zdefiniowane przez użytkownika
• Inne

1.1.1 Dane skalarne

Dane skalarne to pojedyncze wartości, które nie są podzielone na mniejsze części. Przykłady danych skalarne to liczby, tekst, wartości logiczne, itp.

W R i Pythonie dane skalarne są zazwyczaj reprezentowane przez zmienne, które przechowują pojedynczą wartość.

R

int = 1L
num = 1.0
char = "jeden"
logical = TRUE

Python

int = 1
num = 1.0
char = "jeden"
logical = True

W niektórych językach programowania istnieją specjalne typy danych dla danych skalarnych.

1.1.2 Dane wektorowe

Dane wektorowe to zbiór wartości tego samego typu, które są przechowywane w jednej zmiennej. W R są one reprezentowane przez klasę vector, a w Pythonie przez listę lub tablicę.

R

vec = c(1, 2, 3)
vec

[1] 1 2 3

Python

vec = [1, 2, 3]
vec

[1, 2, 3]

1.1.3 Dane macierzowe

Dane macierzowe to zbiór wartości tego samego typu, które są przechowywane w postaci dwuwymiarowej (wiersze i kolumny). Klasa reprezentująca macierze jest wbudowana w niektóre języki programowania (np. R), a w innych jest dostępna jako część zewnętrznej biblioteki (np. NumPy w Pythonie).

R

mat = matrix(c(1, 2, 3, 4, 5, 6), nrow = 2, ncol = 3)
mat

     [,1] [,2] [,3]
[1,]    1    3    5
[2,]    2    4    6

Python

import numpy as np
mat = np.array([[1, 2, 3], [4, 5, 6]])
mat

array([[1, 2, 3],
       [4, 5, 6]])

1.1.4 Dane tensorowe

Dane tensorowe to zbiór wartości tego samego typu, które są przechowywane w postaci wielowymiarowej (np. trójwymiarowej, czterowymiarowej, itp.).

R

tensor = array(1:12, dim = c(2, 3, 2))
tensor

, , 1

     [,1] [,2] [,3]
[1,]    1    3    5
[2,]    2    4    6

, , 2

     [,1] [,2] [,3]
[1,]    7    9   11
[2,]    8   10   12

Python

import numpy as np
tensor = np.array([[[1, 2, 3], [4, 5, 6]], [[7, 8, 9], [10, 11, 12]]])
tensor

array([[[ 1,  2,  3],
        [ 4,  5,  6]],

       [[ 7,  8,  9],
        [10, 11, 12]]])

1.1.5 Listy/krotki

Listy i krotki to zbiory wartości różnych typów, które są przechowywane w jednej zmiennej.

R

lista = list(1L, 1, "jeden", TRUE)
lista

[[1]]
[1] 1

[[2]]
[1] 1

[[3]]
[1] "jeden"

[[4]]
[1] TRUE

Python

lista = [1, 1.0, "jeden", True]
lista

[1, 1.0, 'jeden', True]

1.1.6 Stosy

Stosy (ang. stacks) to struktury danych, które przechowują wartości w sposób LIFO (ang. last in, first out). Oznacza to, że ostatni element dodany do stosu jest pierwszy, który zostanie pobrany.

R

library(collections)
s = stack()
s$push("element1")
s$push("element2")
s$as_list()

[[1]]
[1] "element2"

[[2]]
[1] "element1"

popped_element = s$pop()
popped_element

[1] "element2"

s$as_list()

[[1]]
[1] "element1"

Python

s = []
s.append('element1')
s.append('element2')
s

['element1', 'element2']

popped_element = s.pop()
popped_element

'element2'

# from queue import LifoQueue
# stack = LifoQueue()
# stack.put('element1')
# stack.put('element2')
# popped_element = stack.get()

1.1.7 Kolejki

Kolejki (ang. queue) to struktury danych, które przechowują wartości w kolejności, w jakiej zostały dodane. Elementy są pobierane z kolejki w takiej samej kolejności, w jakiej zostały dodane. Takie struktury są często określane jako FIFO (ang. first in, first out).

R

library(collections)
kolejka = queue()
kolejka$push("element1")
kolejka$push("element2")
kolejka$as_list()

[[1]]
[1] "element1"

[[2]]
[1] "element2"

usuniety_element = kolejka$pop()
usuniety_element

[1] "element1"

kolejka$as_list()

[[1]]
[1] "element2"

# kolejka = list()
# kolejka = append(kolejka, "element1")
# kolejka = append(kolejka, "element2")
# kolejka
# usuniety_element = kolejka[[1]]
# usuniety_element
# kolejka = tail(kolejka, -1)
# kolejka

Python

from queue import Queue
kolejka = Queue()
kolejka.put("element1")
kolejka.put("element2")
kolejka.queue

deque(['element1', 'element2'])

popped_element = kolejka.get()
popped_element

'element1'

kolejka.queue

deque(['element2'])

1.1.8 Słowniki i mapy

Słowniki i mapy to struktury danych, które przechowują pary klucz-wartość. Klucz jest unikalnym identyfikatorem, który służy do odnalezienia wartości w strukturze tego typu. Słowniki, w przeciwieństwie do map są mutowalne, co oznacza, że można zmieniać ich zawartość.

R

slownik = list()
slownik[["klucz1"]] = "wartosc1"
slownik[["klucz2"]] = "wartosc2"
slownik

$klucz1
[1] "wartosc1"

$klucz2
[1] "wartosc2"

Python

slownik = dict()
slownik["klucz1"] = "wartosc1"
slownik["klucz2"] = "wartosc2"
slownik

{'klucz1': 'wartosc1', 'klucz2': 'wartosc2'}

1.1.9 Zbiory

Zbiory (ang. sets) to struktury danych, które przechowują unikalne wartości. Oznacza to, że każda wartość w zbiorze występuje tylko raz.

R

zbior = c(1, 2, 3, 1, 2)
zbior = unique(zbior)
zbior

[1] 1 2 3

Python

zbior = {1, 2, 3, 1, 2}
zbior

{1, 2, 3}

1.1.10 Własne klasy

Własne klasy to typy danych zdefiniowane przez użytkownika.

R

stworz_punkt = function(x, y) {
    punkt = list(x = x, y = y)
    structure(punkt, class = "punkt")
}
odleglosc_to_startu = function(punkt){
    UseMethod("odleglosc_to_startu")
}
odleglosc_to_startu.punkt = function(punkt) {
    sqrt(punkt$x^2 + punkt$y^2)
}
p = stworz_punkt(3, 4)
odleglosc_to_startu(p)

[1] 5

Python

class Punkt:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def odleglosc_to_startu(self):
        return(self.x ** 2 + self.y ** 2) ** 0.5

p = Punkt(3, 4)
p.odleglosc_to_startu()

5.0

1.1.11 Inne

Istnieje wiele innych typów danych, które są używane w różnych językach programowania, w tym łączone listy (ang. linked lists), drzewa (ang. trees), grafy (ang. graphs), itp.

1.2 Struktury danych

Struktury danych są organizacją i przechowywaniem danych w sposób umożliwiający zarządzanie nimi oraz wykonywanie różnych operacji.

1.2.1 Uporządkowane struktury danych

Uporządkowane struktury danych to te, które przechowują dane w określonym porządku. Oznacza to, że elementy są poukładane w określonej kolejności, co ułatwia dostęp do nich i manipulację. Zazwyczaj uporządkowane struktury danych są zgodne z formatem tabelarycznym z relacjami między różnymi wierszami i kolumnami. Przykładami uporządkowanych struktur danych są tabele, arkusze kalkulacyjne, bazy danych, itp.

Takie struktury danych są zorganizowane w taki sposób, aby były czytelne i zrozumiałe dla człowieka lub programu komputerowego.

Uporządkowane struktury danych mają szereg zalet. Oprócz łatwości zrozumienia i użycia danych, uporządkowane struktury danych są łatwe do przeszukiwania, sortowania i filtrowania. Ich struktura jest spójna, co ułatwia ich analizę i wizualizację. Ponadto, dane w uporządkowanych strukturach można wydajnie przechowywać oraz pozyskiwać z nich informacje.

Z drugiej strony takie struktury danych mają też wady. Najważniejszą z nich jest możliwość przechowywania danych o ograniczonym stopniu złożoności.

1.2.1.1 Koncepcja uporządkowanych danych

Uporządkowane dane (ang. tidy data) to te, które spełniają następujące kryteria (Wickham 2014)¹:

1. Każda zmienna jest kolumną; każda kolumna jest zmienną.
2. Każda obserwacja to wiersz; każdy wiersz to obserwacja.
3. Każda wartość jest komórką; każda komórka jest pojedynczą wartością.

Gdzie:

• Zmienna to cecha, którą można zmierzyć
• Obserwacja to zestaw pomiarów wykonanych w podobnych warunkach dla danego obiektu. Obserwacja zawiera kilka wartości, z których każda jest powiązana z inną zmienną
• Wartość to stan konkretnej zmiennej. Wartość zmiennej może się zmieniać w zależności od obserwacji

Forma szeroka (ang. wide):

df1

# A tibble: 14,060 × 4
   Kraj        Rok Populacja PKB_na_osobe
   <chr>     <dbl>     <dbl>        <dbl>
 1 Australia  1950   8180000        16400
 2 Australia  1951   8420000        16500
 3 Australia  1952   8630000        16200
 4 Australia  1953   8820000        16500
 5 Australia  1954   9000000        17100
 6 Australia  1955   9210000        17600
 7 Australia  1956   9430000        17600
 8 Australia  1957   9640000        17500
 9 Australia  1958   9850000        18000
10 Australia  1959  10100000        18600
# ℹ 14,050 more rows

Forma długa (ang. long):

df2

# A tibble: 28,120 × 4
   Kraj        Rok Zmienna      Wartosc
   <chr>     <dbl> <chr>          <dbl>
 1 Australia  1950 Populacja    8180000
 2 Australia  1950 PKB_na_osobe   16400
 3 Australia  1951 Populacja    8420000
 4 Australia  1951 PKB_na_osobe   16500
 5 Australia  1952 Populacja    8630000
 6 Australia  1952 PKB_na_osobe   16200
 7 Australia  1953 Populacja    8820000
 8 Australia  1953 PKB_na_osobe   16500
 9 Australia  1954 Populacja    9000000
10 Australia  1954 PKB_na_osobe   17100
# ℹ 28,110 more rows

Dane nie spełniające kryteriów uporządkowanych danych:

df3

# A tibble: 14,060 × 3
   ID             Populacja PKB_na_osobe
   <chr>              <dbl>        <dbl>
 1 Australia_1950   8180000        16400
 2 Australia_1951   8420000        16500
 3 Australia_1952   8630000        16200
 4 Australia_1953   8820000        16500
 5 Australia_1954   9000000        17100
 6 Australia_1955   9210000        17600
 7 Australia_1956   9430000        17600
 8 Australia_1957   9640000        17500
 9 Australia_1958   9850000        18000
10 Australia_1959  10100000        18600
# ℹ 14,050 more rows

1.2.2 Częściowo uporządkowane struktury danych

Dane częściowo uporządkowane to forma uporządkowane danych, która nie jest zgodna z formalną strukturą modeli danych związanych z relacyjnymi bazami danych lub innymi formami tabel, ale mimo to zawiera znaczniki do oddzielania elementów i wymuszania hierarchii rekordów oraz pól w danych. Inaczej mówiąć, posiadają one częściowy model danych, który jest elastyczny i może być dostosowywany do zmian w danych. Przykładem częściowo uporządkowanych danych są pliki XML, JSON, YAML, HTML, itp.

Takie dane mają elastyczną strukturę, która może być łatwo zmieniana i dostosowywana do zmian w danych. Dzięki temu nadają się dobrze do integracji i przechowywania danych z różnych źródeł. Z drugiej strony, mogą być one bardziej złożone i trudniejsze do zrozumienia niż uporządkowane struktury danych.

Uporządkowane struktury danych można bezpośrednio przekształcić do częściowo uporządkowanych struktur danych, ale odwrotny proces nie zawsze jest możliwy.

1.2.3 Nieuporządkowane struktury danych

Nieuporządkowane struktury danych nie mają zdefiniowanego konkretnego porządku elementów (modelu danych). Oznacza to, że nie ma stałego miejsca, w którym przechowywane są dane, co utrudnia bezpośredni dostęp do konkretnego elementu.

Przykłady takich struktur to pliki zawierające tekst, strony internetowe, obrazki, dźwięki, filmy, bazy danych No-SQL, itp.

Właściwości nieuporządkowanych struktur danych powodują, że nie są one ograniczane przez żadne modele danych, a w efekcie mogą przyjmować bardzo różnorodne dane o różnym stopniu złożoności. Z drugiej strony, nieuporządkowane struktury danych są trudniejsze do analizy i przetwarzania niż uporządkowane struktury danych.

Wickham, Hadley. 2014. „Tidy data”. Journal of statistical software 59: 1–23.

---

1. Ta idea jest zainspirowana przez koncepcję postaci normalnej (ang. database normalization) z baz danych.