Mine sisu juurde

Hulk (andmestruktuur)

Allikas: Vikipeedia

Hulk on arvutiteaduses abstraktne andmestruktuur, mis suudab salvestada unikaalseid väärtusi ilma kindla järjekorrata[1]. Hulk on arvutisse rakendatud lõplik matemaatiliste mõistete kogum. Erinevalt enamikust teistest andmestruktuuridest testitakse konkreetse elemendi kättesaamise asemel tavaliselt liikmelisuse väärtust, kas element kuulub hulka või mitte.

Staatilised hulgad võimaldavad nendel elementidel teha ainult päringuoperatsioone - kontrollida, kas antud väärtus on hulgas, loendada väärtused mingis suvalises järjekorras. Hulgad, mida nimetatakse dünaamilisteks, võimaldavad ka elementide sisestamist ja kustutamist hulgast.

Põhioperatsioonid

[muuda | muuda lähteteksti]

Põhioperatsioonid, mis tavaliselt rakendatakse hulgas.

Põhilised teoreetilised operatsioonid

[muuda | muuda lähteteksti]

Põhilised operatsioonid seotud matemaatika hulga põhimõistega.

union(S,T): tagastab hulga S ja T ühendi.

intersection(S,T): tagastab hulga S ja T ühisosa.

difference(S,T): tagastab hulga S ja T vahe.

subset(S,T): kontrollib, kas hulk S on hulga T alamhulk.

Täiendavad operatsioonid

[muuda | muuda lähteteksti]

Täiendavad operatsioonid hulgaga töötamiseks kui andmestruktuurina.

pop(S): tagastab S suvalise elemendi, kustutades S hulgast.[2]

filter(P,S): tagastab alamhulga, mis sisaldab kõiki S elemente, mis rahuldab P predikaati.

clear(S): kustutab kõik S elemendid.

equal(S1', S2'): kontrollib, kas kaks antud hulka on võrdsed.

Hulka saab rakendada mitmesuguste andmestruktuuride abil, mis pakuvad eri operatsioonide jaoks erinevaid kompromisse ajas ja ruumis. Mõned rakendused on mõeldud väga spetsiifiliste operatsioonide tõhususe parandamiseks, näiteks nearest või union. Enamasti kasutatakse rakendamiseks loendit, ignoreerides elementide järjestust ja kontrollides korduvate väärtuste ilmumist. See lahendus on lihtne, kuid ebaefektiivne, kuna sellised toimingud nagu hulga lisamine või elementide kustutamine võtavad O (n) aega, sest need nõuavad kogu loendi skannimist [3]. Hulgad rakendatakse sageli teiste andmestruktuuride (kahendpuud, massiivid või pinumälu) abil.

Hulga kasutamise näide

[muuda | muuda lähteteksti]
const union = (s1, s2) => new Set([...s1, ...s2]); 
// Hulkade s1 ja s2 ühend

const intersection = (s1, s2) => new Set(  
  [...s1].filter(v => s2.has(v))
);
// Hulkade s1 ja s2 ühihiosa

const difference = (s1, s2) => new Set( 
  [...s1].filter(v => !s2.has(v))
);
// Hulga s1 ja s2 vahe

const complement = (s1, s2) => difference(s2, s1);
// Hulga s2 ja s1 vahe

const cities1 = new Set(['Beijing', 'London']);
const cities2 = new Set(['Tallinn', 'London', 'Baghdad']);

const operations = [union, intersection, difference, complement];

const results = operations.map(operation => ({
  [operation.name]: operation(cities1, cities2)
}));


console.dir({ cities1, cities2 });
console.dir(results);
  1. Nell Dale, Henry M. Walker (1996). Abstract data types: Specifications, implementations, and applications.
  2. "Python: pop()".
  3. kjellkod. "Number crunching: Why you should never, ever, EVER use linked-list in your code again".