Költségmodell és algoritmusválasztás

Cél és előfeltétel

Egy lassúnak érzett függvény átírása előtt nevezd meg, pontosan mi kerül sokba. Ebben a leckében keresések és részösszegek segítségével készítesz egyszerű költségmodellt. Előfeltétel a Vec és slice gyakorlata, valamint az iterátoros adatfeldolgozás. A feladatokhoz elég a standard könyvtár; minden megoldást külön edition 2024 projektben futtass.

A költségmodell választott műveleteket számol, például az összehasonlításokat vagy a feldolgozott elemeket. Nem állítja, hogy két ilyen művelet azonos ideig tart. Egy rövid szöveg összehasonlítása más munka, mint egy hosszú közös előtagé; a memóriából olvasás sem minden helyzetben egyforma. A modell mégis hasznos, mert láthatóvá teszi, melyik bemenet növekedésére számítunk érzékenységgel.

Az előfeldolgozásnak is ára van

Az egyszeri keresés és az ugyanazon adatokon végzett ezer keresés eltérő feladat. Az utóbbinál megtérülhet egy rendezett másolat vagy index készítése, az előbbinél annak költsége lehet a döntő. Ezért a kérdés nem pusztán a függvény neve: az adatok létrehozásától az utolsó eredményig terjedő munkát kell megnevezned. Ha a bemenet közben változik, az index karbantartása is a számlára kerül.

Az aszimptotikus jelölés a növekedést írja le, nem konkrét milliszekundumot. Kis adatsoron egy egyszerű bejárás kedvezőbb is lehet a bonyolultabb struktúránál. A standard gyűjtemények dokumentációja külön kezeli a várható és amortizált költségeket. Egyetlen push vagy hashelés megfigyelt idejéből ezért nem érdemes általános ígéretet készíteni. A mai feladatok állításai kizárólag eredményt és megszámolt munkát ellenőriznek, időhatárt nem.

1. feladat: számold a tényleges összehasonlításokat

Írj lineáris keresést, amely az első találat indexe mellett az összehasonlítások számát is visszaadja. Üres bemenetnél nulla munka történjen. Próbáld ki a korai találatot és a hiányzó elemet, mert az átlagos esetet nem helyettesíti a legkényelmesebb teszt.

fn find(xs: &[u32], wanted: u32) -> (Option<usize>, usize) {
    let mut compared = 0;
    for (index, value) in xs.iter().enumerate() {
        compared += 1;
        if *value == wanted { return (Some(index), compared); }
    }
    (None, compared)
}
fn main() {
    assert_eq!(find(&[], 7), (None, 0));
    assert_eq!(find(&[7, 2, 7], 7), (Some(0), 1));
    assert_eq!(find(&[1, 2, 3], 9), (None, 3));
}

2. feladat: több részösszeg közös előkészítéssel

Készíts prefixösszegeket, amelyekkel több félig nyitott tartomány összegét kérdezheted le. Az üres tartomány összege nulla legyen, a hibás sorrend vagy túlnyúló határ hiányt jelezzen. Az előkészítés ne rejtsen el egész túlcsordulást. A segédstruktúra előállításához külön memóriát használunk.

fn prefix(xs: &[u64]) -> Option<Vec<u64>> {
    let mut out = vec![0_u64];
    for x in xs { out.push(out.last()?.checked_add(*x)?); }
    Some(out)
}
fn range_sum(p: &[u64], start: usize, end: usize) -> Option<u64> {
    if start > end { return None; }
    p.get(end)?.checked_sub(*p.get(start)?)
}
fn main() {
    let p = prefix(&[2, 5, 3]).unwrap();
    assert_eq!(range_sum(&p, 1, 3), Some(8));
    assert_eq!(range_sum(&p, 2, 2), Some(0));
    assert_eq!(range_sum(&p, 3, 1), None);
    assert_eq!(range_sum(&p, 0, 4), None);
    assert_eq!(prefix(&[u64::MAX, 1]), None);
}

3. feladat: tartsd meg az eredeti adatsorrendet

Készíts rendezett másolatot ismételt tagságvizsgálathoz. Az eredeti vektor maradjon változatlan, az ismétlődő elemeket pedig ne tekintsd külön találati követelménynek. Itt csak azt kérdezzük, jelen van-e egy érték; nem az összes előfordulás indexét keressük.

fn main() {
    let original = vec![8, 2, 8, 4];
    let mut sorted = original.clone();
    sorted.sort_unstable();
    assert!(sorted.binary_search(&8).is_ok());
    assert!(sorted.binary_search(&3).is_err());
    assert_eq!(original, vec![8, 2, 8, 4]);
    let empty: Vec<u32> = Vec::new();
    assert!(empty.binary_search(&1).is_err());
}

Helyességi szerződés az algoritmuscsere előtt

Egy gyorsabbnak gondolt változat csak akkor helyettesíti a régit, ha ugyanazt a feladatot oldja meg. A tagságvizsgálat, az első előfordulás keresése és az összes előfordulás visszaadása külön szerződés. A rendezett másolat az eredeti pozíciókat már nem őrzi meg. Ha a felület indexet ígér az eredeti bemenetbe, külön pozícióadatot kellene tárolnod; a mai harmadik feladat tudatosan csak jelenlétről dönt.

Készíts kis döntési táblát a saját felhasználásodra: változik-e az adat, szükséges-e az eredeti sorrend, hányszor kérdezel, és mennyi plusz memóriát tarthatsz meg? Ezek nélkül a választás könnyen egy kedvelt adatszerkezet indokolatlan használatává válik. Üres, ismétlődő és a tartomány szélén lévő értékekkel mindkét jelölt ugyanazt az eredményt adja, mielőtt időmérésbe kezdenél.

A műveletszámláló sem ingyenes megfigyelés: a ténylegesen időzített változatból el kell különíteni, ha magának a számlálásnak a költségét nem szeretnéd mérni. A mostani program tehát az algoritmus működését magyarázza, és nem egy kész összehasonlító benchmark. Ez a különbség segít elkerülni, hogy egy tanulóeszközből megalapozatlan termékígéret legyen.

Elfogadási feltételek

1. A lineáris keresés üres adaton nulla, hiányzó elemnél a hosszával egyező összehasonlítást számol.
2. A részösszeg kezeli az üres és érvénytelen tartományt, az előkészítés túlcsordulást nem nyel el.
3. A rendezett keresés megtartja az eredeti adatot, és nincs időmérésből származó sebességállítás.

Összefoglaló és továbblépés

A modell a döntés indoklását szolgálja: mit előlegezünk meg, mennyi plusz adatot tartunk, és hányszor használjuk újra? Írd fel a feltételezett bemenetméretet és lekérdezésszámot is, különben a választás nem lesz később felülvizsgálható. A következő allokációs lecke ugyanennek a gondolkodásnak a memóriafoglalási oldalát vizsgálja.