Skip to content

Latest commit

 

History

History
executable file
·
311 lines (220 loc) · 17.3 KB

README.md

File metadata and controls

executable file
·
311 lines (220 loc) · 17.3 KB

5.4 Σύνολα (Sets)

© Γιάννης Κωστάρας

< | Δ | >

Τα σύνολα (sets) αποθηκεύουν μόνο μοναδικά στοιχεία, δηλ. δεν επιτρέπουν διπλότυπα.

Εικόνα 5.4.1 Σύνολα στη Java

Το Συσχετισμένο Σύνολο (HashSet) είναι η πιο συνηθισμένη υλοποίηση ενός συνόλου. Όπως συνάγεται και από το όνομά του, υλοποιείται ως ένα πίνακας κατακερματισμού (HashMap).

jshell> Set<Integer> set = new HashSet<>();
set ==> []

jshell> set.add(10);
$1 ==> true

jshell> set.add(20);
$2 ==> true

jshell> set.add(20);
$3 ==> false

jshell> set
set ==> [20, 10]

Στο πιο πάνω παράδειγμα, βλέπουμε ότι η εισαγωγή της τιμής 20 δυο φορές αποτυγχάνει. Παρατηρήστε επίσης ότι τα σύνολα δεν αποθηκεύουν τα στοιχεία τους με κάποια συγκεκριμένη σειρά, όπως οι λίστες, όπου η σειρά των στοιχείων είναι ίδια με τη σειρά εισαγωγής των στοιχείων στη λίστα.

Θα μπορούσαμε ν' αρχικοποιήσουμε το σύνολο και ως εξής:

jshell> Set<Integer> set = Set.of(10, 20, 30);
set = [10, 20, 30]

Προσοχή όμως. Σ' αυτήν την περίπτωση επιστρέφεται ένα σύνολο το οποίο δεν μπορεί να μεταβληθεί. Επιπλέον, δεν επιτρέπονται null στοιχεία.

jshell> set.add(40)
|  Warning:
|  unchecked call to add(E) as a member of the raw type java.util.List
|  array.add(40)
|  ^-----------^
|  java.lang.UnsupportedOperationException thrown
|        at ImmutableCollections.uoe (ImmutableCollections.java:71)
|        at ImmutableCollections$AbstractImmutableSet.add (ImmutableCollections.java:281)
|        at (#62:1)

Για να μπορέσουμε να δημιουργήσουμε μια μεταβαλλόμενη λίστα σ' αυτή την περίπτωση, πρέπει να χρησιμοποιήσουμε την μέθοδο κατασκευής της HashSet που δέχεται μια άλλη συλλογή:

jshell> Set<Integer> set = new HashSet<>(Set.of(10, 20, 30));
set ==> [20, 10, 30]

jshell> set.add(40)
$5 ==> true

jshell> set
array ==> [10, 20, 30, 40]

Στη συνέχεια θα δούμε τις διάφορες μεθόδους της κλάσης.

Προσπέλαση στοιχείων

Παρακάτω βλέπουμε τρόπους προσπέλασης των στοιχείων ενός συνόλου. Καθώς τα στοιχεία ενός συνόλου δεν αποθηκεύονται με τη σειρά, δε μπορούμε να προσπελάσουμε κάποιο στοιχείο του συνόλου χρησιμοποιώντας δείκτες (indexes), καθώς δεν υπάρχουν δείκτες.

Για να προσπελάσουμε όλα τα στοιχεία ενός συνόλου, χρησιμοποιούμε τον επαναλήπτη (iterator):

jshell> int sum = 0;
sum ==> 0

jshell> Iterator<Integer> iter = set.iterator();
iter ==> java.util.HashMap$KeyIterator@1a1d6a08

jshell> while (iter.hasNext()) 
	...>    sum += iter.next();

Η διεπαφή Collection, την οποία επεκτείνει η Set, επεκτείνει με τη σειρά της τη διεπαφή Iterable:

interface Iterable {
	public Iterator iterator();
}

interface Iterator {
	public boolean hasNext();
	public Object next();
	public void remove();
}

Άλλος τρόπος είναι με τον αναβαθμισμένο βρόγχο for που εισήχθηκε στην έκδοση 5:

jshell> sum = 0;
sum ==> 0

jshell> for (int n : set) 
	...>    sum += n;

Εισαγωγή στοιχείων

Όπως είδαμε, η εισαγωγή δεδομένων σ' ένα σύνολο γίνεται με την μέθοδο add(). Η μέθοδος επιστρέφει true αν η εισαγωγή του στοιχείου ήταν επιτυχής, αλλοιώς επιστρέφει false.

Η μέθοδος addAll(Collection<?> c) μας επιτρέπει να προσθέσουμε μια συλλογή από στοιχεία στο σύνολό μας.

Διαγραφή στοιχείων

Η μέθοδος remove(Object o) διαγράφει το στοιχείο του συνόλου που είναι ίσο με το το ο αν βρέθηκε και επιστρέφει true σ' αυτήν την περίπτωση. Προσοχή γιατί κι εδώ η μέθοδος δεν είναι remove(E e) όπως θα έπρεπε που σημαίνει ότι σε συνδυασμό με Autoboxing μπορεί να διαγράψει λάθος στοιχεία.

Επίσης, πολύ μεγάλη προσοχή χρειάζεται αν διαγράφετε στοιχεία από ένα σύνολο ενώ προσπελάζετε τα στοιχεία του καθώς μπορεί να προκαλέσετε ConcurrentModificationException. Ένας ασφαλής τρόπος είναι να καλέσετε την μέθοδο remove() του Iterator.

jshell> set
set ==> [20, 40, 10, 30]

jshell> for (Iterator<Integer> i = set.iterator(); i.hasNext(); ) {
   ...> int n = i.next(); 
   ...> if (n == 10) i.remove();
   ...> }

jshell> set
set ==> [20, 30, 40]

jshell> for (int n : set) {
   ...> if (n == 30) set.remove(n) ;
   ...> }
}

jshell> set
set ==> [20, 40]

Τέλος, η διεπαφή Collection παρέχει και τις ακόλουθες δυο μεθόδους οι οποίες μπορούν να διαγράψουν με τη μία από το σύνολό μας όλα τα στοιχεία της παρεχόμενης συλλογής c (removeAll(Collection<?> c)) και επιστρέφει true αν τα κατάφερε (αν δεν κατάφερε να διαγράψει έστω και ένα από τα στοιχεία της c από το σύνολό μας, τότε επιστρέφει false).

Η retainAll(Collection<?> c) κρατάει από το σύνολό μας μόνο τα στοιχεία που περιέχονται στη c και διαγράφει όλα τα υπόλοιπα.

Η NavigableSet διαθέτει δυο ακόμα μεθόδους που διαγράφουν το πρώτο και το τελευταίο στοιχείο του ταξινομημένου συνόλου: pollFirst() και pollLast().

Αναζήτηση στοιχείων

Δυστυχώς η κλάση Collections δε διαθέτει κάποια μέθοδο για να αναζητήσει κάποιο στοιχείο σε ένα σύνολο (οι μέθοδοι binarySearch() δέχονται ως όρισμα λίστα).

jshell> set 
set ==> [40, 20]

jshell> set.contains(20); 
$9 ==> true

Οπότε, μπορούμε να εφαρμόσουμε μόνο γραμμική αναζήτηση (η οποία αφήνεται ως άσκηση στον αναγνώστη).

Ταξινόμηση

Όπως είδαμε παραπάνω, η δομή δεδομένων Σύνολο δεν είναι ταξινομημένη και δεν μπορεί να ταξινομηθεί. Υπάρχει όμως η TreeSet (η οποία κληρονομεί από τις SortedSet και NavigableSet) και ταξινομεί τα στοιχεία της:

jshell> set = new HashSet<>(Set.of(20, 10, 40, 30));
set ==> [20, 40, 10, 30]

jshell> TreeSet<Integer> sortedSet = new TreeSet<>(set);
sortedSet ==> [10, 20, 30, 40]

jshell> sortedSet.first();
$1 ==> 10

jshell> sortedSet.last();
$2 ==> 40

jshell> sortedSet.subSet(20,40);	// 20 <= στοιχεία < 40 
$3 ==> [20, 30]

jshell> sortedSet.subSet(20, true, 40, true);  // inclusive = true
$4 ==> [20, 30, 40]

jshell> sortedSet.headSet(20);	   	// στοιχεία < 20
$5 ==> [10]

jshell> sortedSet.headSet(20, true);	// inclusive = true
$6 ==> [10, 20]

jshell> sortedSet.tailSet(20);			// στοιχεία >= 20
$7 ==> [20, 30, 40]

jshell> sortedSet.tailSet(20, false);	// inclusive = false
$8 ==> [30, 40]

jshell> sortedSet.tailSet(25);		// στοιχεία >= 25
$9 ==> [30, 40]

jshell> sortedSet.tailSet(25, true);	// inclusive = true
$10 ==> [30, 40]

jshell> sortedSet.ceiling(25);		// το μικρότερο στοιχείο >= 25
$11 ==> 30

jshell> sortedSet.floor(25);		// το μεγαλύτερο στοιχείο <= 25
$12 ==> 20

jshell> sortedSet.higher(20);		// το μικρότερο στοιχείο > 20
$13 ==> 30

jshell> sortedSet.lower(20);		// το μεγαλύτερο στοιχείο < 20
$14 ==> 10

jshell> sortedSet.descendingSet()
$15 ==> [40, 30, 20, 10]

jshell> Iterator<Integer> i = sortedSet.descendingIterator();
i ==> java.util.TreeMap$NavigableSubMap$DescendingSubMapKeyIterator@544fe44c

jshell> while (i.hasNext()) 
   ...> System.out.print(i.next() + " ");
40 30 20 10

Αντιγραφή

Ήδη είδαμε τον copy constructor HashSet(Collection<?> c) που δημιουργεί ένα νέο HashSet από τη συλλογή που του περνάμε ως όρισμα και την addAll(Collection<?> c). Υπάρχει επίσης και η στατική μέθοδος copyOf(Collection<? extends E> c).

Συγχώνευση

Σαν άσκηση, γράψτε μια μέθοδο union() στο jshell που θα ενώνει τα στοιχεία δυο συνόλων που περνάτε ως ορίσματα στη μέθοδο.

Διαχωρισμός

Σαν άσκηση, γράψτε μια μέθοδο split() στο jshell που θα διαχωρίζει ένα σύνολο με ακέραια στοιχεία σε δυο νέα σύνολα που το ένα θα αποθηκεύει τα ζυγά και η άλλη τα μονά στοιχεία του αρχικού συνόλου.

Ισότητα

jshell> src
src ==> [1, 2, 3, 4, 5]

jshell> dest
dest ==> [1, 2, 3, 4, 5]

jshell> dest.equals(src); 
$1 ==> true

Συνδεδεμένα Συσχετισμένα Σύνολα (LinkedHashSet)

Το Συνδεδεμένο Συσχετισμένο Σύνολο (LinkedHashSet) κληρονομεί από την κλάση HashSet αλλά επιπλέον διατηρεί και μια συνδεδεμένη λίστα (LinkedList) με τα στοιχεία του που βελτιώνει την απόδοσή του σε σχέση με το HashSet αν θέλετε να προσπελάσετε όλα τα στοιχεία του. Με αυτόν τον τρόπο οι επαναλήπτες της (iterators) επιστρέφουν τα στοιχεία της με τη σειρά που εισήχθηκαν (θυμηθείτε ότι στην κλάση HashSet δεν υπάρχει κάποια σειρά στα στοιχεία).

jshell> Set<Character> characterSet = new LinkedHashSet<>();
characterSet ==> []
jshell> Collections.addAll(characterSet, 'z', 'y', 'x');
$2 ==> true
jshell> characterSet.toString().equals("[z, y, x]");
$3 ==> true

Οι πράξεις στα συνδεδεμένα συσχετισμένα σύνολα είναι ίδιες με αυτές των συσχετισμένων συνόλων (HashSets).

Σύνολα Απαριθμημένων Τύπων (EnumSet)

Χρησιμοποιείται όταν ο αριθμός των στοιχείων είναι γνωστός εξ' αρχής και δεν αλλάζει και μπορούμε να αναθέσουμε ένα ευρετήριο (index) σ' αυτά. Ως αποτέλεσμα, είναι πολύ πιο αποδοτικό από τις υπόλοιπες υλοποιήσεις.

jshell> enum Faces {JACK, QUEEN, KING};
|  created enum Faces
jshell> Set<Faces> faceCards = EnumSet.of(Faces.JACK, Faces.QUEEN, Faces.KING);
faceCards ==> [JACK, QUEEN, KING]
jshell> Set<Faces> faceCards = EnumSet.allOf(Faces.class);
faceCards ==> [JACK, QUEEN, KING]

Επιστρέφει τα στοιχεία του με τη σειρά που ορίζονται στο enum.

Μπορείτε να πειραματιστείτε περαιτέρω εδώ javaalmanac.io.

Σύγκριση των διαφόρων υλοποιήσεων της Set

| | add | contains | next | | HashSet | O(1) | O(n) | O(k*/n) |
| LinkedHashSet | O(1) | O(1) | O(1) | | EnumSet | O(1) | O(n) | O(1)** | | TreeSet | O(logn) | O(logn) | O(logn) |

*k είναι η χωρητικότητα του συνόλου

** για EnumSets μέχρι 64 στοιχείων, μετά γίνεται O(logn)

Πηγή: Naftalin, Wadler (2006)

Αν η εφαρμογή σας διαβάζει συχνότερα στοιχεία τότε καλύτερη απόδοση έχει η LinkedHashSet.

| Ιδιότητα | HashSet | LinkedHashSet | TreeSet | | Δομή δεδομένων | Hashtable | Hashtable+LinkedList | Ισοζυγισμένο (red-black) δέντρο |
| Σειρά εισαγωγής | Δε διατηρείται | Διατηρείται | Δε διατηρείται | | Διπλότυπα αντικείμενα | Δεν επιτρέπονται | Δεν επιτρέπονται | Δεν επιτρέπονται | | Δυνατότητα ταξινόμησης | Όχι | Όχι | Ναι | | Ετερογενή αντικείμενα | Ναι | Ναι | Όχι | | null στοιχεία | Ναι | Ναι | Όχι, μόνο ως πρώτη εισαγωγή, δηλ. ως ρίζα του δέντρου |

Ασκήσεις

  1. Γράψτε ένα πρόγραμμα που θα εισάγει ακέραιους αριθμούς σε ένα TreeSet με φθίνουσα ταξινόμηση.
  2. Γράψτε ένα πρόγραμμα που θα εισάγει συμβολοσειρές σε ένα TreeSet ταξινομημένες ως προς το μήκος τους. Αν δυο συμβολοσειρές έχουν ίδιο μήκος τότε θα πρέπει να ληφθεί υπόψιν η λεξικογραφική σειρά των χαρακτήρων.
  3. Γράψτε μια μέθοδο που θα δέχεται μια List ως παράμετρο και θα επιστρέφει μια νέα List εξαφανίζοντας τα διπλότυπα στοιχεία της αρχικής. Π.χ. αν η αρχική λίστα περιέχει ["ένα", "δυο", "δυο", "τρία", "τρία", "τρία"] η μέθοδος θα επιστρέφει: ["ένα", "δυο", "τρία"].
  4. Υλοποιήστε μια νέα κλάση ListSet<E>. Η ListSet<E> είναι μια List<E> που όμως δεν επιτρέπει διπλότυπες τιμές. Η υλοποίησή σας θα πρέπει να είναι αντίστοιχη της SetUniqueList<E>.
  5. Ο μαθηματικός όρος συμμετρική διαφορά (△ ή ⊕) δυο συνόλων είναι το σύνολο εκείνων των στοιχείων που είναι είτε στο ένα σύνολο είτε στο άλλο αλλά όχι και στα δυο. Π.χ. έστω τα σύνολα A = {1, 2, 3} και B = {2, 3, 4}, τότε A △ B = {1, 4}. Αν θέλουμε να υπολογίσουμε την συμμετρική διαφορά παραπάνω των δυο συνόλων τότε θα πρέπει να την υπολογίσουμε για τα πρώτα δυο και το αποτέλεσμα με το τρίτο κ.ο.κ. Δηλ. (A △ B △ C) == ((A △ B) △ C)). Π.χ. για τα σύνολα A και B που είδαμε παραπάνω και Γ = {2, 3}, A △ B △ Γ = (A △ B) △ Γ = {1, 4} △ {2, 3} = {1, 2, 3, 4}. Δημιουργήστε μια μέθοδο που θα δέχεται δυο ή περισσότερα σύνολα και θα επιστρέφει ένα σύνολο με την συμμετρική διαφορά τους.

< | Δ | >