Kasutaja:Pomalit/Hulk(andmestruktuur)

Hulk on arvutiteaduses abstraktne andmestruktuur, mis suudab salvestada unikaalseid väärtusi ilma kindla järjekorrata. Hulk on arvutisse rakendatud lõplik matemaatiliste mõistete kogum. Erinevalt enamikust teistest andmestruktuuridest, konkreetse elemendi kättesaamise asemel testitakse 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

Põhioperatsioonid, mis tavaliselt rakendatakse hulgas.

Põhilised teoreetilised operatsioonid

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

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

•pop(S): tagastab S suvalise elemendi, kustutades S hulgast.

•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.

Rakendused

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 skännimist . Hulgad rakendatakse sageli teiste andmestruktuuride (kahendpuud, massiivid või pinumälu) abil.

Hulga kasutamise näide

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);