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 testitakse konkreetse elemendi kättesaamise asemel tavaliselt liikmesuse 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 skannimist . 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);

 Viited 

Kategooria:Andmestruktuurid