Adatszerkezeti megközelítések

Kategória: Python.
Alkategória: Python adatszerkezetek.

Áttekintés

Ezen az oldalon programozástechnikai megközelítésekről van szó. Ugyanazt a feladatot többféleképpen is meg fogjuk oldani:

  • hagyományos módszerrel (segédváltozók, feltételkezelés, ciklus);
  • folyam (stream) módszerrel,
  • adat keret (data frame) módszerrel.

A legtöbb fejlesztő számára a hagyományos módszer a legkézenfekvőbb: ezt tanultuk először, ebben van gyakorlatunk. Ám a big data és az adattudomány területei újabb megközelítéseket kívánnak.

A programokat többnyire Python segítségével valósítjuk meg, bár maga az elv nyelvfüggetlen.

Első feladat

A feladat

Adott egy egész számokból álló tömb. A páros számok felét adjuk össze.

A feladat kissé mesterkélt, ugyanakkor jól érthető. A feladathoz hozzá tartozik, hogy a felezést az összeadás előtt végezzük el. A feladatban tehát 3 műveletet kell végrehajtani:

  • szűrni kell bizonyos feltétel alapján,
  • átalakítást kell végrehajtani a kiszűrt értékeken,
  • végre kell hajtani egy műveletet, melynek az eredménye egy skalár.

Példaként tekintsük az alábbi inputot:

numbers = [4, 3, 6, 8, 5, 7]

Ebben a példában a 4-nek, a 6-nak és a 8-nak a felét, azaz a 2-t, 3-at és 4-et kell összeadni, az elvárt eredmény tehát 9.

Megoldás hagyományos módszerekkel

Első gondolatunk a következő:

  • létrehozunk egy segédváltozót, amibe a végeredmény került,
  • egy ciklusban végiglépkedünk az elemeken,
  • a ciklusmagban megvizsgáljuk, hogy az adott elem páros-e,
  • ha igen, megfelezzük, és hozzáadjuk a segédváltozóhoz,
  • végül visszatérünk a segédváltozó értékével.

A program:

def cyclish(numbers):
    result = 0
    for number in numbers:
        if number % 2 == 0:
            half_number = number // 2
            result += half_number
    return result

Programozástechnikai érdekesség: Pythonban a // művelet az egész osztás. Nyilván lehetne ezen még optimalizálni, de a ciklust tartalmazó hagyományos megoldásnak ebben a formában is megteszi.

A függvényt pl. így tudjuk meghívni:

print(cyclish(numbers))

Nagy mennyiségű adatok esetén ezzel a megoldással több probléma is felmerülhet:

  • A teljes adatmennyiségnek egyszerre kell, hogy a memóriában legyen.
  • A változók növelik a komplexitást és a hibázási lehetőséget, valamint a fordítónak is az optimalizálási lehetőségeit is csökkentik.

Megoldás folyammal

A folyamokkal történő programozás egész más gondolkodásmódot kíván, mint a hagyományos eszközökkel történő. A lehetőségek itt szűkebbek, bonyolultabb feladatok megoldása sokkal nehezebb lehet, mint hagyományos eszközökkel. Azok a programozási nyelvek jöhetnek itt szóba, amelyek támogatják a folyamokat. Elsősorban a funkcionális nyelvek tartoznak ide, de a legtöbb modern programozási nyelv is ma már tartalmaz ilyen kiegészítést.

A folyam műveletek legfontosabb építőkockái:

  • Szűrés (filter): egy adott szűrőfeltétel dönti el, hogy az inputként kapott struktúra mely elemei maradnak benne a további feldolgozásban, és melyek nem.
  • Átalakítás (map): a struktúra mindegyik elemén végrehajtunk egy átalakítást. Az eredmény típusa eltérhet az eredetitől.
  • Redukálás (reduce): azt jelenti, hogy veszünk két értéket a struktúrából, azokon végrehajtunk egy műveletet, melynek típusa megegyezik az eredeti adatok típusával, majd az eredménnyel tovább hajtjuk végre a műveletet mindeddig, amíg el nem fogy. Ha a végrehajtott művelet kommutatív és asszociatív (mint pl. az összeadás), akkor a futtató rendszernek van elvi esélye arra is, hogy párhuzamosan futtassa.

A folyam megoldások jellemzői:

  • A folyam műveletek bemenetei és kimenetei is folyamok, így az utasítások tipikusan egymás után vannak láncolva.
  • Nincsenek segédváltozók.
  • A folyam műveletek paraméterei függvények. Ezeket tipikusan lambda függvényként valósítjuk meg.
  • A folyam megoldásoknak gyakori előnye még az, hogy tipikusan egyetlen utasításként valósítjuk meg. Így alkalmazható olyan helyzetekben is, ahol csak egy utasítást adhatunk ki.

Az egy utasításból álló folyam művelet tipikus formája az alábbi:

  • egy return,
  • utána szükség esetén egy folyammá alakító művelet,
  • majd az egyes folyam műveletek, egymás után láncolva,
  • végül egy végművelet, pl. redukálás.

Scala

A sort illik egy funkcionális programozási nyelvvel kezdeni. A Scala százas nagyságrendű folyam műveletet definiál, amiről pl. a https://www.scala-lang.org/api/3.0.2/scala/collection/immutable/List.html oldalon tájékozódhatunk.

A fenti példa megvalósítása Scala-ban:

def streamish(numbers: List[Int]): Int = {
  return numbers
    .filter(_ % 2 == 0)
    .map(_ / 2)
    .reduce(_ + _)
}

Meghívása:

println(streamish(List(4, 3, 6, 8, 5, 7)))

A Scala ezt a megközelítést preferálja a hagyományos módszerrel szemben, persze úgy is meg lehet valósítani. A kód meglehetősen tömör, és aki még nem látott Scala kódot, annak idegenként hathat, így bizonyos részek magyarázatra szorulnak.

A filter() egy ún. predikátumot vár, azaz egy olyan függvényt, melynek egy paramétere van, kimenete pedig logikai. Ennek megértéséhez egy kicsit távolabbról indítunk. Képzeljük el, hogy van egy ilyen függvényünk:

def isEven(x: Int): Boolean = {
  return x % 2 == 0
}

Ekkor a fenti streamish függvényt írhatnánk így is:

def streamish(numbers: List[Int]): Int = {
  return numbers
    .filter(isEven)
    .map(_ / 2)
    .reduce(_ + _)
}

Az isEven függvény elhagyható, készíthetünk belőle név nélküli lambdát. Ugyanezt a lépést a map és a reduce esetén is végrehajtva ezt kapjuk:

def streamish(numbers: List[Int]): Int = {
  return numbers
    .filter(x => x % 2 == 0)
    .map(x => x / 2)
    .reduce((x, y) => x + y)
}

A Scala szereti a tömör kódot (emiatt van egyébként az, hogy ott a behúzási konvenció a 2 szóköz a máshol megszokott 4 helyett), és itt is egyszerűsít. Ha megnézzük az első lambdát (x => x % 2 == 0), akkor azt látjuk, hogy a paraméter egyszer fordul elő a végeredmény meghatározásában. Ez esetben valójában nevet sem kell neki adni, és a => is megspórolható, ha ezt írjuk _ % 2 == 0. Hasonlóan ebből: x => x / 2 ez lesz: _ / 2. Ez a módszer több paraméterrel is működik, ha mindegyik paraméter egyszer fordul elő a számításban, az eredeti sorrendben. Így rövidíthetjük ezt: (x, y) => x + y erre: _ + _.

Azt gondolom, hogy a lenti ugyan kicsit szószátyárabb, de talán jobban olvasható; a fenti azért némi gyakorlatot kíván. Összefoglalva:

  • Első lépésben a filter() hívással megszűrjük a folyamot, és az eredményben csak a páros számok maradnak benne.
  • Második lépésben egyesével átalakítjuk a folyam elemeit, megfelezve azokat. Figyeljük meg: ezt önmagában el tudjuk végezni mindegyik elemen, nem kell hozzá más információ. Nagyon fontos a folyam műveleteknél az, hogy ennyire atomi részekre bontsuk.
  • A harmadik lépés a redukálás, melynek során vesszük az első két elemet, végrehajtunk rajtuk egy műveletet (jelen esetben az összeadást), majd az eredményen és a harmadik elemen hajtjuk végre ugyanezt, és így tovább, amíg el nem fogy.

A végeredmény az lesz, ami az elvárt.

Java

A 8-as verziótól kezdve a Java-ban is megjelentek a funkcionális elemek, többek között a folyamok is. Ebben egyébként tetten érhető a Scala visszahatása. A példa Java-ban az alábbi:

package mystream;
 
import java.util.Arrays;
import java.util.List;
 
public class MyStream {
    public static void main(String[] args) {
        System.out.println(streamish(Arrays.asList(4, 3, 6, 8, 5, 7)));
    }
 
    public static int streamish(List<Integer> numbers) {
        return numbers.stream()
                .filter(x -> x % 2 == 0)
                .map(x -> x / 2)
                .reduce((x, y) -> x + y)
                .get();
    }
}

Itt már a teljes kódot láthatjuk, mivel a Java-ban nem lehet kódrészleteket külön végrehajtani. Importálni kell dolgokat, a stream() hívással folyammá kell alakítani a listát, a végén pedig egy veszélyes get() művelettel zárunk, ugyanis a reduce() eredménye valójában opcionális, és pl. üres folyam esetén üres lesz a végeredmény is; most ilyen hibakezeléssel nem foglalkozunk.

Ez a megközelítés kissé bőbeszédűbb, mint a Scala megfelelője, de azt gondolom, hogy még befogadható mennyiségű és jól olvasható.

Python

Meglepő módon a Pythonban meglehetősen szűkösek e tekintetben a lehetőségek, de azért a legfontosabb folyam műveleteket itt is végre tudjuk hajtani:

  • Szűrés: Pythonban technikailag ezt a filter() függvény végzi, melynek első paramétere a szűrő függvény (ami lehet egy olyan függvény neve, melynek egy paramétere van, a visszatérési típusa pedig logikai, vagy egy megfelelő lambda kifejezés), a második pedig az a struktúra, melynek elemein a szűrést végre tudjuk hajtani. Ez sajnos eltér a többi programozási nyelvben megszokott megközelítéstől, melyben magán a folyamon egymás után láncolva hajtjuk végre a műveleteket, és a paraméterben csak a szűrőfeltételt kell megadnunk.
  • Átalakítás: Pythonban technikailag hasonlít a szűréshez: a map() függvény hajtja végre, melynek első paramétere az átalakító függvény, a második pedig a struktúra. Hasonló módon ez is eltér a más programozási nyelvekben megszokottaktól.
  • Redukálás: Pythonban sajnos ilyen művelet alapból nincs, ehhez be kell tölteni a functools csomagból a reduce függvényt.

Más folyam műveletről nem tudok Pythonban, így ott sajnos túl bonyolult feladatokat valószínűleg nem tudunk folyam módszerrel megvalósítani. A feladat megoldása Pythonban folyam módszerrel az alábbi:

from functools import reduce
 
def streamish(numbers):
    return reduce(lambda x, y: x + y, map(lambda x: x // 2, filter(lambda x: x % 2 == 0, numbers)))

A fentiekben leírtak miatt a szokásostól eltérően jobbról balra kell olvasni:

  • a bemenet a numbers,
  • első művelet a lambda x: x % 2 == 0 szűrés,
  • második művelet a lambda x: x // 2 átalakítás,
  • a redukáló művelet pedig az összeadás: lambda x, y: x + y.

Megoldás Numpy segítéségével

A Numpy egy Python könyvtár, amelynek segítségével tömb műveleteket tudunk végrehajtani. Logikája sokban hasonlít az adatkeretekhez. Az első megoldásban volt ciklus, a másodikban explicit ciklus ugyan nem volt, de "bújtatott" igen (a filter() és a map() a tömb minden elemén végrehajtja a műveletet, ami végső soron ciklus művelet), itt viszont ciklus nélkül valósítjuk meg.

A Numpy nem része az alap disztribúciónak, azt külön fel kell telepíteni:

pip install numpy

Szokásos konvenció szerint a Numpy-ra np-ként hivatkozunk. Tekintsük az alábbi kódot:

import numpy as np
 
def numpyish(numbers):
    np_numbers = np.array(numbers)
    np_evens = np_numbers[np_numbers % 2 == 0]
    np_halves = np_evens // 2
    np_sum = np.sum(np_halves)
    return np_sum

Magyarázat:

  • np_numbers = np.array(numbers): ezzel hozzuk létre a Python tömbből a Numpy tömböt.
  • np_evens = np_numbers[np_numbers % 2 == 0]: így szűrünk. Érdemes megfigyelni azt, hogy a np_numbers % 2 azt jelenti, hogy a np_numbers tömb minden elemén külön-külön hajtsa végre a 2-vel történő maradékos osztást; ugyanígy a np_numbers % 2 == 0 eredménye a np_numbers hosszával megegyező logikai tömb lesz, ami szűrőfeltételként alkalmazható az eredeti tömbön. Nagyon fontos megértenünk ezt a példát, mert az adatkeretes gondolkodásban ez alapvető fontosságú.
  • np_halves = np_evens // 2: ugyancsak elemenként hajtja végre a műveletet, tehát nem az np_evens tömböt osztja kettővel, hanem a tömb elemeit, és az eredmény is tömb lesz.
  • np_sum = np.sum(np_halves): a Numpy-ban vannak redukáló függvények, amelyek egy adott műveletet hajtanak végre a tömb elempárjain. A sum() értelemszerűen összeadja az elemeket.

Szokni kell ezt a módszert.

Második feladat

A feladat

Tegyük fel, hogy az adatunk "táblázatszerű": két oszlopa van, az egyik gyümölcsnevekkel, a másik pedig egész értékekkel, az adott gyümölcs darabszámával. A feladat kiszűrni a negatív darabszámokat, majd összegezni az adott gyümölcsök darabszámát. Tegyük fel, hogy az input a következő:

fruit_pieces = [
    ('apple', 3),
    ('banana', 2),
    ('apple', -2),
    ('orange', 4),
    ('banana', -3),
    ('apple', 2),
    ('banana', 5),
]

Ebben az esetben a -2-t és a -3-at nem vesszük figyelembe, így az elvárt eredmény a következő szótár:

{'banana': 7, 'orange': 4, 'apple': 5}

Megoldás hagyományos módszerekkel

A hagyományos programozástechnikai eszközökkel a megoldás a következő:

  • hozzunk létre egy üres szótárt;
  • lépkedjünk végig a struktúra elemein;
  • egy feltétellel vizsgáljuk meg, hogy ha a második értéke pozitív-e;
  • ha igen, akkor vizsgáljuk meg, hogy van-e már első érték kulcsú elem;
  • ha nincs, helyezzük be az aktuális (második) értékkel, egyébként adjuk hozzá;
  • térjünk vissza az eredménnyel.

A kód valahogy így néz ki:

def cyclish(fruit_pieces):
    result = {}
    for one_fruit_piece in fruit_pieces:
        fruit, pieces = one_fruit_piece
        if pieces > 0:
            if fruit in result:
                result[fruit] = result[fruit] + pieces
            else:
                result[fruit] = pieces
    return result

Megoldás folyammal

A folyamban itt sem használunk segédváltozót, és itt is egy utasításként adjuk ki:

from functools import reduce
from collections import Counter
 
def streamish(fruit_pieces):
    return dict(reduce(lambda x, y: x + y, map(lambda fp: Counter({fp[0]: fp[1]}), filter(lambda fp: fp[1] > 0, fruit_pieces))))

Magyarázat:

  • Először szűrünk a filter segítségével.
  • Utána átalakítjuk az elem kettest egy egyelemű szótárrá, ahol a kulcs az első (azaz 0 sorszámú) elem, az érték pedig a második (az 1 sorszámú). Egészen pontosan nem a beépített dict-et használjuk, hanem a Counter-t, ami egyébként a dict-ből származik, és számos kényelmi funkciója van. Többek között az, hogy úgy tudunk összevonni szótárakat, hogy az azonos kulcsú elemekkel műveletet tudunk végrehajtani (hagyományosan az egyik felülírja a másikat).
  • A redukálás során "összeadjuk" a két Counter-t.
  • A végeredményt dict-té alakítjuk, hogy nem Counter legyen, hanem az alap szótár.

Az eredmény ugyanaz, mint a ciklusos esetben.

Megoldás SQL lekérdezéssel

A ciklusmentes megoldások felé haladva érdemes megemlítenünk az SQL-t. Az adat keret lényegében az SQL tábláknak a tovább gondolása.

A fenti adatstruktúrát hozzuk létre egy adatbázisban! PostgreSQL szintaxissal:

CREATE TABLE fruits (
    id SERIAL,
    fruit TEXT,
    pieces INT
);
INSERT INTO fruits(fruit, pieces) VALUES('apple', 3);
INSERT INTO fruits(fruit, pieces) VALUES('banana', 2);
INSERT INTO fruits(fruit, pieces) VALUES('apple', -2);
INSERT INTO fruits(fruit, pieces) VALUES('orange', 4);
INSERT INTO fruits(fruit, pieces) VALUES('banana', -3);
INSERT INTO fruits(fruit, pieces) VALUES('apple', 2);
INSERT INTO fruits(fruit, pieces) VALUES('banana', 5);

Az alábbi lekérdezés eredménye az, amit szeretnénk:

SELECT fruit, SUM(pieces) FROM fruits WHERE pieces > 0 GROUP BY fruit;

Érdemes megfigyelni a párhuzamot:

  • a WHERE feltétel a szűrés;
  • a GROUP BY az ami mentén csoportosítunk;
  • a SUM() az a művelet, amit csoporton belül végrehajtunk.

Végrehajtás Pythonból: először fel kell telepíteni az adatbázis specifikus könyvárat; PostgreSQL esetén a félelmetes nevű psycopg2-t:

pip install psycopg2

Majd a kód (melyben a kapcsolódási adatokat megfelelően át kell állítani):

import psycopg2
 
fruit_db = psycopg2.connect(
    host='localhost',
    user='csaba',
    password='farago',
    database='fruitdb'
)
 
fruit_cursor = fruit_db.cursor()
fruit_cursor.execute('SELECT fruit, SUM(pieces) FROM fruits WHERE pieces > 0 GROUP BY fruit')
fruit_records = fruit_cursor.fetchall()
print(dict(fruit_records))

Az eredmény egy ugyanolyan szótr, mint a korábbi megoldásokban.

Megoldás Python adat kerettel

A Pandas a legelterjedtebb Python adatkeret könyvtár. Ezt fel kell telepíteni:

pip install pandas

Használati konvenció: pd-ként hivatkozunk a pandas-ra. A kód:

import pandas as pd
 
def dataframish(fruit_pieces):
    fruit_pieces_df = pd.DataFrame(fruit_pieces, columns=['fruit', 'pieces'])
    fruit_pieces_filtered = fruit_pieces_df[fruit_pieces_df['pieces'] > 0]
    fruit_pieces_grouped = fruit_pieces_filtered.groupby(['fruit'], as_index=False).sum()
    return fruit_pieces_grouped.set_index('fruit').to_dict()['pieces']

Magyarázat:

  • fruit_pieces_df = pd.DataFrame(fruit_pieces, columns=['fruit', 'pieces']): ennek segítségével hozzuk létre a Pandas adatkeretet a szabványos Python adatstruktúrákból kiindulva.
  • fruit_pieces_filtered = fruit_pieces_df[fruit_pieces_df['pieces'] > 0]: ezzel szűrünk. Érdemes megfigyelni a logikai hasonlóságot a Numpy megoldás és eközött.
  • fruit_pieces_grouped = fruit_pieces_filtered.groupby(['fruit'], as_index=False).sum(): ez a csoportosítás és a művelet végrehajtása. (Itt most nem nézünk meg minden apró részletet.)
  • return fruit_pieces_grouped.set_index('fruit').to_dict()['pieces']: hagyományos Python szótárrá alakítjuk az eredményt.

Megoldás Sparkban

Az Apache Spark egy big data keretrendszer, ami lehetővé teszi a műveletek párhuzamos futtatását. Számos módon használhatjuk, és Pythonon belül is több lehetőségünk van. A Spark adat keret létrehozása Pythonban:

fruits_df = spark.createDataFrame([
    ('apple', 3),
    ('banana', 2),
    ('apple', -2),
    ('orange', 4),
    ('banana', -3),
    ('apple', 2),
    ('banana', 5)
]).toDF('fruit', 'pieces')

A végrehajtandó műveletek:

from pyspark.sql.functions import sum, col, asc
 
fruits_df\
  .select('fruit', 'pieces')\
  .where(col('pieces') > 0)\
  .groupBy('fruit')\
  .agg(sum('pieces').alias('pieces'))\
  .show()

Az eredmény:

+------+------+
| fruit|pieces|
+------+------+
| apple|     5|
|banana|     7|
|orange|     4|
+------+------+

Érdemes megfigyelni a hasonlóságokat e között és az SQL között: meglehetősen közel állnak egymáshoz, és a Pandas szintaxistól jelentősen eltér. Viszont a műveletek jól megfeleltethetőek egymásnak. Ciklus itt sincs. Ha Sparkban mindenképp a Pandas szintaxist szeretnénk használni, akkor a Koalas csomagot használhatjuk.

Kitérő: megoldás R adat kerettel

Érdemes egy kis kitérő erejéig megnézni, hogy ugyanez hogyan néz ki R-ben:

fruits <- data.frame(
  fruit = c('apple', 'banana', 'apple', 'orange', 'banana', 'apple', 'banana'),
  pieces = c(3, 2, -2, 4, -3, 2, 5)
)

fruits_filtered = fruits[fruits$pieces > 0,]
fruits_aggregated = aggregate(pieces ~ fruit, fruits_filtered, sum)
print(fruits_aggregated)

Az aggregate() függvény egészen elegáns módon oldja meg a műveletet. Persze itt is számos egyéb módja van a fenti művelet végrehajtásának.

Adatkeret műveletek

Láthattunk eltéréseket a szintaxisban és hasonlóságokat a filozófiai megközelítésekben. Általános receptet tehát nagyon nehéz adni, viszont érdemes tisztában lenni a fő adatkeret műveletekkel. A fontosabbak közül néhány:

  • oszlopok kiválasztása;
  • sorok szűrése valamilyen oszlop érték (vagy értékek) alapján;
  • csoportosítás, műveletek végrehajtása csoporton belül;
  • sorba rendezés;
  • oszlopok hozzáadása, beleértve a külső adatforrást és más oszlopokkal történő átalakítást;
  • adatkeretek összekapcsolása, a hagyományos, 4 féle összekapcsoló művelettel (inner, left, right, outer),
  • adatok mozgatása egyik sorból a másikba,
  • és még nagyon sok egyéb.

Ahhoz, hogy komfortosan érezzük magunkat az adattudomány világában, nagyon sok gyakorlásra van szükségünk. Legvégső soron mindegyik rendszer biztosítja azt, hogy egy for ciklusban végiglépkedjünk a sorokon, de ehhez tényleg csak a legvégső esetben folyamodjunk; igyekezzünk minden esetben enélkül megoldani.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License