Informatika4-2018/Gyakorlat9

A MathWikiből
(Változatok közti eltérés)
a
(Set)
57. sor: 57. sor:
  
 
== Set ==
 
== Set ==
 +
A Set olyan tároló, amiben egyedi elemek vannak, nem lehet benne kétszer ugyan az (halmaz).
 +
De cserébe nem beszélhetek adott indexű elemről, mert az elemet sorrendje nem kötött.
 +
Egy elem beszúrása mind az előtte, mind az utána lévőket étrendezheti.
 +
Sőt nem is lehet egy adott pozícióba beszúrni elemet, csak ''beszúrni'' lehet, ha már benne volt az elem, akkor nem történik semmi, ha nem, akkor benne lesz, de nem tudjuk, hogy hol.
 +
 
=== HashSet ===
 
=== HashSet ===
 +
[https://hu.wikipedia.org/wiki/Kriptogr%C3%A1fiai_hash_f%C3%BCggv%C3%A9ny Hash] függvény segítségével határozza meg, hogy hova kerüljön egy elem.
 +
Az elemek sorrendje látszólag véletlen.
 +
* Egy elem beszúrása, megkeresése és törlése is időben várhatóan konstans!
 +
** de legrosszabb esetben lineáris!
 +
** ez azt jelenti, hogy általában gyorsak a fent említett műveletek, de néha lehet lassú, várható értékben még mindig nagyon gyors.
 +
 +
=== TreeSet ===
 +
Elemeit rendezett fában tárolja. Beszúrás/törlés határa a sorrend garantáltan nem romlik el.
 +
A lenti példában az [1,2,3,5,7] elemeket tároljuk.
 +
 +
    2
 +
    / \
 +
  1  5
 +
      / \
 +
    3  7
 +
 +
A fa [https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree kiegyensúlyozott], ami azt jelenti, hogy nem engedi, bármelyik ága is túl hosszú legyen.
 +
Széles és sekély fára törekszik az implementáció.
 +
 +
Ennek következménye, hogy:
 +
* a beszúrás, keresés, törlés időben logaritmikus
  
 
== SortedSet ==
 
== SortedSet ==

A lap 2018. november 20., 11:41-kori változata

Előző - Fel - Következő

Tartalomjegyzék

Generics

C++ template megfelelője.

Tetszőleges metódust vagy osztályt megírhatunk úgy, hogy működjön több osztályra is. Például:

public class Main
{
    public static <T> boolean IsIn(T[] a, T v)
    {
        for( int i = 0; i < a.length; ++i)
        {
             if (a[i].equals(v))
                 return true;
        }
        return false;
    }
}

Wildcards

Collections

Kollekciókban lehet objektumokat tárolni.

List

Sorrendet őrző kollekció. Lehet beszúrni, kitörölni elemet, tetszőleges pozícióban. Le lehet kérdezni az adott pozícióban lévő elemet.

ArrayList

A List-nek olyan megvalósítása, ahol az elemek egy összefüggő memóriatartományban (tömb) helyezkednek el.

  • Időben konstans költsége van egy elem elérésének
  • Időben lineáris egy elem beszúrása vagy törlése, mert az összes többi elemet is mozgatni kell hozzá.
|a|b|c|d|e|f|g| -> |a|b|x|c|d|e|f|g|
    ^
    x

LinkedList

Láncolt lista, az elemek helye nem rögzített a mamóriában, de mindegyik eltárol egy-egy referenciát ez előtte és a mögötte álló elemre, így őrzi a sorrendet.

   +-+ -> +-+ -> +-+ -> +-+ -> 
   |a|    |b|    |c|    |d|
<- +-+ <- +-+ <- +-+ <- +-+
  • Egy adott pozíció elérése időben lineáris, mert az elejétől lépkedve lehet eljutni minden elemhez.
  • Egy elem beszúrása időben konstans, mert csak a szomszédos elemeket érinti a beszúrás
   +-+          +-+ -> +-+ -> +-+ -> 
   |a|\        /|b|    |c|    |d|
<- +-+ \      / +-+ <- +-+ <- +-+
      \ \    / /
       \ +-+  /
        \|x| /
         +-+

Set

A Set olyan tároló, amiben egyedi elemek vannak, nem lehet benne kétszer ugyan az (halmaz). De cserébe nem beszélhetek adott indexű elemről, mert az elemet sorrendje nem kötött. Egy elem beszúrása mind az előtte, mind az utána lévőket étrendezheti. Sőt nem is lehet egy adott pozícióba beszúrni elemet, csak beszúrni lehet, ha már benne volt az elem, akkor nem történik semmi, ha nem, akkor benne lesz, de nem tudjuk, hogy hol.

HashSet

Hash függvény segítségével határozza meg, hogy hova kerüljön egy elem. Az elemek sorrendje látszólag véletlen.

  • Egy elem beszúrása, megkeresése és törlése is időben várhatóan konstans!
    • de legrosszabb esetben lineáris!
    • ez azt jelenti, hogy általában gyorsak a fent említett műveletek, de néha lehet lassú, várható értékben még mindig nagyon gyors.

TreeSet

Elemeit rendezett fában tárolja. Beszúrás/törlés határa a sorrend garantáltan nem romlik el. A lenti példában az [1,2,3,5,7] elemeket tároljuk.

    2
   / \
  1   5
     / \
    3   7

A fa kiegyensúlyozott, ami azt jelenti, hogy nem engedi, bármelyik ága is túl hosszú legyen. Széles és sekély fára törekszik az implementáció.

Ennek következménye, hogy:

  • a beszúrás, keresés, törlés időben logaritmikus

SortedSet

Map

SortedMap

Feladat

Implementáljunk egy gráf osztályt.

Előző - Fel - Következő

Személyes eszközök