Ugrás a tartalomhoz

multiset data type

A Wikiszótárból, a nyitott szótárból


Főnév

multiset data type (tsz. multiset data types)

  1. (informatika) multihalmaz

A multiset vagy bag egy olyan absztrakt adattípus (ADT), amely egy elemekből álló kollekciót reprezentál, amelyben egy elem többször is előfordulhat (tehát a példányok száma, azaz a multiplicitás számít). Ez megkülönbözteti a szokásos set-től (halmaz), ahol minden elem legfeljebb egyszer szerepel.

Például egy multiset: {a, a, b, b, b, c} Itt az “a” kétszer, a “b” háromszor, a “c” egyszer van jelen.

2. Miért hasznos a Multiset ADT?

A multisetelemeket gyakran használjuk olyan helyzetekben, amikor az előfordulások száma számít, például:

  • statisztikák, gyakoriságszámítások (pl. szógyakoriság egy szövegben),
  • számlálós adatstruktúrák,
  • kártyajátékok (ugyanaz a lap többször is előfordulhat),
  • matematikai vagy kombinatorikai problémák.

3. Multiset ADT – műveletek (interface)

A multiset absztrakt adattípus az alábbi főbb műveleteket biztosítja:

Művelet Leírás
Create() Üres multiset létrehozása
Insert(M, x) x elem beszúrása a multisetbe
Remove(M, x) x egyik példányának eltávolítása
RemoveAll(M, x) x összes példányának eltávolítása
Count(M, x) x előfordulásainak száma
Contains(M, x) Van-e x a multisetben?
Size(M) Összes elem száma (ismétlődésekkel)
UniqueSize(M) Különböző elemek száma
IsEmpty(M) Üres-e a multiset?
Clear(M) Multiset kiürítése
Union(M1, M2) Két multiset uniója (összes példányt tartalmaz)
Intersection(M1, M2) Két multiset metszete (minimális példányszámok)
ToList(M) Lista minden elemmel (ismétlődésekkel)
ToSet(M) Lista csak az egyedi elemekkel

Egyes programnyelvekben további műveletek is lehetnek, pl. összehasonlítás, iterálás, stb.

4. Matematikai háttér

Formálisan egy multiset minden elemhez hozzárendel egy nemnegatív számosságot (multiplicitás), amely azt jelzi, hogy az elem hányszor szerepel. Jele: M: U → ℕ, ahol U az univerzum, M(x) az x elem multiplicitása a multisetben.

Például: M(a) = 2 M(b) = 3 M(c) = 1

5. Multiset ADT – implementációk

A multiset ADT különféle módokon valósítható meg:

5.1. Vektor/lista

Egyszerű megoldás: minden példányt explicit eltárolunk egy tömbben vagy listában. Pl. {a, a, b, b, b, c} → [“a”,“a”,“b”,“b”,“b”,“c”]

  • Előny: gyors beszúrás, könnyű felsorolás
  • Hátrány: Count művelet lassú lehet (végig kell menni az összes elemen), helypazarló nagy példányszám esetén

5.2. Szótár (hash map) vagy fa (tree map)

A multiset implementálható egy kulcs-érték párokat tároló struktúrával, ahol a kulcs az elem, az érték a példányszám: Pl. {“a”:2, “b”:3, “c”:1}

  • Előny: Count, Insert, Remove gyors (O(1) vagy O(log n))
  • Hátrány: Több memória, de nagyobb példányszámnál előnyösebb

5.3. Rendezett tömb (sorted array)

Ha az elemeket rendezve tartjuk, a Count/Remove gyorsabb lehet, de a beszúrás lassú.

5.4. Multiset ADT C++ STL-ben:

  • std::multiset (rendezett, minden példány külön tárolva, O(log n) műveletek)
  • std::unordered_multiset (hash-tábla alapú, O(1) átlagosan)
  • std::map<T,int> (típus, példányszám párosítással)

6. Példa műveletek (pszeudokód / C++ STL)

#include <set>
std::multiset<int> ms;
ms.insert(2);
ms.insert(3);
ms.insert(2);
std::cout << ms.count(2); // 2
ms.erase(ms.find(2)); // csak egy 2-est töröl
ms.erase(3); // az összes 3-ast törli

7. Multiset unió és metszet

Unió:

A két multiset uniója minden elemhez a maximális példányszámot rendeli: M1 = {a,a,b,b}, M2 = {a,b,b,b,c} Unió: {a,a,b,b,b,c}

Metszet:

A két multiset metszete minden elemhez a minimális példányszámot rendeli: M1 = {a,a,b,b}, M2 = {a,b,b,b,c} Metszet: {a,b,b}

Különbség:

Az egyikből kivonjuk a másik példányszámát, de minimum 0-ig: M1 = {a,a,b,b}, M2 = {a,b,b,b,c} Különbség: {a}

8. Felhasználási területek

  • Statisztikai elemzés (gyakoriságeloszlás)
  • Szövegfeldolgozás (szóelőfordulások, betűgyakoriság)
  • Kártya- vagy dobókocka játékok (azonos lap, érték többször)
  • Multimultihalmazok (pl. képfeldolgozás szín-gyakoriság)
  • Komplex algoritmusok (pl. backtracking, keresések, kombinatorika)

9. Multiset vs. Set

  • Set: minden elem legfeljebb egyszer, multiplicitás = 1 vagy 0.
  • Multiset: minden elem tetszőleges sokszor, multiplicitás tetszőleges nemnegatív egész.

A multiset általánosabb a set-nél.

10. Absztrakt példa (ADT szinten)

ADT Multiset
  Insert(M, x) → növeli x példányszámát 1-gyel
  Remove(M, x) → csökkenti x példányszámát 1-gyel, ha van ilyen
  Count(M, x) → visszaadja x példányszámát
  ...

11. Összegzés

A multiset absztrakt adattípus lehetővé teszi, hogy többszörös előfordulásokat kezeljünk egy kollekcióban, és műveleteket végezzünk rajtuk, mint beszúrás, törlés, példányszám lekérdezés, unió, metszet, stb. Gyakori a programozásban és matematikában, amikor az elemek sokszoros előfordulása is jelentőséggel bír.

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=multiset_data_type&oldid=3502711”