Eine Remove-Methode für eine Klasse schreiben, die Iterable implementiert

Question

Also habe ich eine Klasse, die Iterable implementiert, um eine Reihe von Methoden zu schreiben. Die meisten von ihnen sind ziemlich einfach zu durchdenken, aber ich habe Probleme beim Schreiben einer Remove-Methode für die Klasse.

import java.util.Iterator; 

public class Bag<Item> implements Iterable<Item> { 

    private Item[] data = (Item[]) new Object[5]; 

    // The size variable keeps track of how many items 
    private int size = 0; 

    public String toString() { 
     StringBuilder b = new StringBuilder("["); 
     for (Item i : this) 
      b.append(i + " "); 
     return b.toString() + "]"; 
    } 

    public void expandArray() { 
     int capacity = data.length * 2; 
     Item[] newData = (Item[]) new Object[capacity]; 
     for (int i = 0; i < data.length; i++) 
      newData[i] = data[i]; 
     data = newData; 
    } 

    public boolean add(Item x) { 
     if (size == data.length) 
      expandArray(); 
     data[size++] = x; 
     return true; 
    } 

    // return an Iterator for the bag 
    public Iterator<Item> iterator() { 
     return new BagIterator<Item>(); 
    } 

    // Iterator class 
    public class BagIterator<Item> implements Iterator<Item> { 

     private int i = 0; 

     public boolean hasNext() { 
      return i < size; 
     } 

     public Item next() { 
      return (Item) data[i++]; 
     } 

    } 

    public boolean contains(Item x) { 
     for (int i = 0; i < data.length; i++) { 
      if (data[i] == x) 
       return true; 
     } 
     return false; 
    } 

    public boolean addUnique(Item x) { 
     for (int i = 0; i < data.length; i++) { 
      if (data[i] == x) 
       return false; 
     } 
     this.size++; 
     this.add(x); 
     return true; 
    } 

    public boolean remove(Item x) { 

     Item lastItem = x; // holds x item 
     Item swap; // holds item to swap 
     int swapIndex; // holds index of item to swap 

     for (int i = 0; i < data.length; i++) { 
      if (data[i] == x) { 
       // Save the last item 
       lastItem = data[3]; 
       // Save the swapped item 
       swap = data[i]; 
       // Save the index of swapped item 
       swapIndex = i; 
       // move swap item to end of list 
       data[3] = swap; 
       // move last item to swap pos 
       data[swapIndex] = lastItem; 
       // remove last item in list 
       this.size--; 
       return true; 
      } 
     } 
     return false; 
    } 

    public boolean equals(Object o) { 
     Bag<Item> b = (Bag<Item>) o; 
     return false; 
    } 
} 

Meine Gedanken hinter der Methode entfernen sind wie folgt; Gehe durch die Tasche, finde den zu entfernenden Gegenstand, nimm den gleichen Gegenstand und bewege ihn zum Ende der Tasche (tausche seinen Platz mit dem letzten Gegenstand in der Tasche) und verkleinere dann die Größe der Tasche (denkend, dass sie sich entfernen würde) es).

Nun klar es gibt einige Probleme mit meinem Denken. 1) Die Tasche hat immer noch ihre Originalgröße. 2) Der Beutel ist jetzt ungeordnet, was später beim Vergleich zweier Beutel zu einem Problem führen wird.

Also meine Frage ist, wie kann ich effektiv eine remove-Methode schreiben, um einen Artikel aus meiner Tasche Klasse ohne in die Probleme, die ich bereits erwähnt, zu nehmen.

Haupt

public class Main { 

    public static void main (String[] args) { 

     Bag<Integer> bag = new Bag<>(); 

     bag.add(1); 
     bag.add(2); 
     bag.add(3); 
     bag.add(4); 

     System.out.println(bag); // [1, 2, 3, 4] 

     System.out.println(bag.remove(4)); // should remove 4 and return true **WORKING 
     System.out.println(bag.remove(1)); // should remove 1 and return true **WORKING 
     System.out.println(bag.remove(1)); // should NOT remove 1 and return false **NOT WORKING 

     System.out.println(bag); // [4 ] 

    } 
} 

Answer 1

Irgendwie habe ich deine Frage beim ersten Mal völlig falsch verstanden; Ich sehe jetzt, dass Sie nicht einmal Iterator.remove() implementieren. Iterable.remove() ist auch tricky, lassen Sie uns darüber reden!

Zunächst einmal möchten Sie wahrscheinlich Iterable nicht direkt implementieren. Es nur können Sie über eine Sequenz von Elementen iterieren (und optional rufen Sie Iterator.remove()), sonst nichts. Ihre Bag Klasse sollte stattdessen wahrscheinlich implementieren Collection (oder erweitern AbstractCollection), die die allgemeine Schnittstelle die meisten Java-Datenstrukturen implementieren (es gibt .add(), .remove(), .size(), und so weiter).

Beim Erstellen einer Datenstruktur, z. B. bag, ist es wichtig, dass Sie Ihre invariants erzwingen. Grob gesagt ist eine Invariante eine Garantie dafür, wie sich Ihre Datenstruktur oder Methode verhält. Wenn Sie beispielsweise .size() für eine leere Datenstruktur aufrufen, wird 0 zurückgegeben. Sobald Sie .add() anrufen, werden alle zukünftigen Aufrufe an .size()1 zurückgeben (bis Sie die Datenstruktur weiter ändern). Das ist eine Invariante. Es mag offensichtlich erscheinen, aber wenn Ihre Datenstrukturen komplexer werden, vereinfachen diese einfachen Garantien das Nachdenken über Ihren Code erheblich.

Auf zu Ihrer spezifischen Frage. Erstens ist Ihre Idee, den Gegenstand zu entfernen, bis zum Ende zu entfernen, eine gute Intuition. Es ist viel effizienter, als die restlichen Elemente in neue Indizes zu kopieren.

Ihre erste Sorge, dass die Bag immer noch die gleiche Größe ist, ist eigentlich kein Problem. Da Sie size dekrementieren, wird das Element am Ende des Arrays - effektiv - entfernt. Sie können es auf null setzen, um die Referenz zu entfernen, aber es ist nicht notwendig in Bezug auf die Richtigkeit. Stattdessen sollten Sie Ihre anderen Methoden wie betrachten und sicherstellen, dass sie size respektieren. Sie sollten nur auf Indizes kleiner als size statt data.length schauen, da die Werte zwischen size und data.length möglicherweise unbrauchbar sind.

Ihre zweite Sorge, über den Vergleich von zwei Bag s, macht ein anderes Problem. Ihre Klasse liefert eigentlich keine Invariante (es gibt dieses Wort noch einmal), dass das Array je bestellt werden muss, so dass die erneute Bestellung während .remove() die Dinge nicht schlechter macht, als sie vorher waren. Welche ist ein Problem Ihrer Klasse ist nicht außer Kraft setzen .equals() und .hashcode() (Sie haben weder oder beides zu tun), was bedeutet, dass keine zwei Bag Instanzen je Äquivalent angesehen werden kann, unabhängig von der Reihenfolge ihrer Elemente. Wenn Sie beabsichtigen, Bag s zu vergleichen, müssen Sie diese Methoden korrekt implementieren. Angenommen, Sie möchten das tun, wie ist definitiv schwierig. Im Allgemeinen gibt es keine effiziente Möglichkeit, zwei ungeordnete Sammlungen von Objekten zu vergleichen - Sie haben nur die Möglichkeit, alle Elemente beider Sammlungen zu durchlaufen, bis Sie sichergestellt haben, dass sie dieselben Elemente enthalten. Dies ist O (n^2) oder eine quadratische Leistung (d. H. Ziemlich langsam).

Sie haben zwei grundlegende Auswahlmöglichkeiten; Stellen Sie sicher, dass Ihr Backing-Array immer sortiert ist (das ist eine Invariante - am Ende jeder Methode, nach der das Array sortiert wird), oder verwenden Sie eine effizientere Datenstruktur für Gleichheitsprüfungen wie Set. Beide Optionen haben Kompromisse. Die korrekte Sortierung eines Arrays ist immer sehr schwierig. Javas TreeMap macht dies und die meisten Menschen betrachten dies als die Art von Code, den sie niemals selbst implementieren möchten. Mit einem Set können Sie effizient überprüfen, ob ein Element in Ihrer Sammlung vorhanden ist, aber es geht um die Vermeidung von doppelten Elementen. Eine "Taschen" -Datenstruktur erlaubt im Allgemeinen Duplikate, so dass die Verwendung einer Set als Hintergrunddatenstruktur für Ihren Anwendungsfall möglicherweise nicht akzeptabel ist. Verwenden Sie eine Map<E, Integer>, wo der Wert eine Anzahl wäre, würde funktionieren, aber ist ein wenig mehr Papierkram zu verfolgen.

Nichtsdestoweniger kann als Ausgangspunkt eine Brute-Force-Standard-Implementierung gut genug sein. Ein zentraler Mieter guter Softwareentwicklung ist es, eine Überoptimierung zu vermeiden. Beginne mit etwas, das funktioniert und mache es dann besser, anstatt von Anfang an etwas vollkommen effizientes zu machen.

Answer 2

Iterator.remove() ist eine wirklich schwierige Methode richtig zu machen, vor allem angesichts der möglichen gleichzeitigen Modifikation (siehe ConcurrentModificationException). Wenn Sie sich die Implementierungen einiger Standardsammlungen ansehen, erhalten Sie einige gute Hinweise: ArrayList.Itr, LinkedList.ListItr, HashMap.HashIterator, TreeMap.PrivateEntryIterator und ConcurrentSkipListMap.Iter sind gute Startpunkte.

einige der wichtigsten Dinge zu erinnern:

• Correct wichtiger als schnelle ist - Sie immer Iterator.remove() als Aufruf an die Trägersammlung .remove() (zusammen mit der Iterator ‚s Zustand Aktualisierung nach Bedarf) implementieren können . Dies ist möglicherweise nicht der effizienteste Weg, um das Problem zu lösen, aber Sie werden am zuversichtlichsten sein, dass es funktioniert. Wenn Sie nicht sicher sind, dass diese naive Implementierung eine ernsthafte Schwachstelle in Ihrer Anwendung darstellt, ist dies wahrscheinlich gut genug.
• Iterator.remove() ist eine optionale Methode - eine vollkommen korrekte Implementierung ist einfach throw new UnsupportedOperationException();. Es ist nicht glamourös, aber es funktioniert in den allermeisten Fällen. Wenn für Ihren Anwendungsfall keine effiziente Operation zum Entfernen der mittleren Iteration erforderlich ist, kann es am einfachsten sein, sie einfach nicht implementiert zu lassen.
• Extend bestehende abstrakte Klassen - Die JDK eine Reihe von abstrakten Klassen als Ausgangspunkte liefert (z.B. AbstractCollection), die für eine Reihe von Methoden heikel angemessene Standardwerte bereitzustellen. Guava bietet auch eine Anzahl von Forwarding* decorators, die nützlich sein kann, wenn die Abstract* Klassen nicht tun. Wenn es Ihnen gelingt, bestehendes Verhalten zu nutzen, sollten Sie das Rad nicht neu erfinden.
• Setzen Sie auf gemeinsames Verhalten von der Backing-Klasse - eine Sache, die Sie beim Betrachten der JDKs Iterator s bemerken, ist, dass sie versuchen, so wenig Arbeit wie möglich zu tun, lieber Arbeit an die Backing-Klasse auslagern. Angenommen, Sie können ein Element effizient aus Ihrer Sammlung entfernen, sobald Sie den Index kennen. Definieren Sie einen private void removeByIndex(int) Helfer, den beide Ihre Collection.remove() und Iterator.remove() Methoden aufrufen können. Je mehr gemeinsames Verhalten Sie haben, desto weniger Randfälle werden Ihre Iterator s einführen.
• Achten Sie auf Ihre Invarianten - Ihre Datenstruktur bietet bestimmte Garantien darüber, wie es sich verhält, und beide Java (.equals(), .hashcode()) und die Sammlungen Rahmen (Iterable, Collection, etc.) zusätzliche Anforderungen definieren. Es ist wichtig, dass Sie diese Anforderungen bei der Implementierung von Helper-Klassen wie Iterator Implementierungen beachten. Wenn Sie nicht sicher sein können, dass Ihre optimierten Iterator die Invarianten, die die Backing-Klasse bietet, immer noch respektiert, sollten Sie die Optimierung verwerfen und einfach die öffentlichen Methoden der Klasse aufrufen.
• Beachten Sie gleichzeitige Änderungen - eine wirklich nützliche Funktion der JDK-Sammlungen ist ihre Fähigkeit, gleichzeitige Änderungen zu erkennen (z.B. Mid-Iteration etwas anderes, auch im selben Thread, ruft Collection.remove()). Während Ihre Iterator technisch immer noch korrekt sein kann, ohne diese Änderungen zu erkennen, ist es viel weniger nützlich und toleriert sehr viel leichtere Fehler. Wenn Sie Ihre eigene Iterator implementieren möchten, müssen Sie versuchen, Änderungen an der Backing-Datenstruktur in der Mitte der Iteration zu erkennen.

Und last but not least, kommt Guava mit Multiset und Multimap Implementierungen. Sofern es sich nicht um eine Schulaufgabe handelt, gibt es keinen Grund, einen eigenen Bag Typ zu implementieren.