Waarom is er geen SortedList in Java?

In Java zijn er de SortedSeten SortedMap-interfaces. Beide behoren tot het Java Collections-frameworken bieden een gesorteerde manier om toegang te krijgen tot de elementen.

Naar mijn idee is er echter geen SortedListin Java. U kunt java.util.Collections.sort()om een ​​lijst te sorteren.

Enig idee waarom het zo is ontworpen?


Antwoord 1, autoriteit 100%

Lijstiterators garanderen eerst en vooral dat u de elementen van de lijst in de interne volgorde van de lijst krijgt (ook wel invoegvolgordegenoemd). Meer specifiek is het in de volgorde waarin je de elementen hebt ingevoegd of hoe je de lijst hebt gemanipuleerd. Sorteren kan worden gezien als een manipulatie van de gegevensstructuur en er zijn verschillende manieren om de lijst te sorteren.

Ik zal de manieren rangschikken in de volgorde van nutzoals ik het persoonlijk zie:

1. Overweeg om in plaats daarvan Setof Bagcollecties te gebruiken

OPMERKING:ik heb deze optie bovenaan gezet omdat dit is wat je normaal gesproken toch wilt doen.

Een gesorteerde set sorteert automatisch de verzameling bij het invoegen, wat inhoudt dat het sorteert terwijl u elementen aan de verzameling toevoegt. Het betekent ook dat u het niet handmatig hoeft te sorteren.

Bovendien, als u zeker weet dat u zich geen zorgen hoeft te maken over (of heeft) dubbele elementen, kunt u de TreeSet<T>. Het implementeert SortedSeten NavigableSetinterfaces en werkt zoals je waarschijnlijk zou verwachten van een lijst:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding
for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Als je de natuurlijke volgorde niet wilt, kun je de constructorparameter gebruiken die een Comparator<T>.

Als alternatief kunt u Multisets(ook bekend als Bags), dat is een Setdie in plaats daarvan dubbele elementen toestaat en er zijn uitvoeringen ervan. Met name uit de Guava-bibliothekenis er een TreeMultiset, dat werkt een veel zoals de TreeSet.

2. Sorteer uw lijst met Collections.sort()

Zoals hierboven vermeld, is het sorteren van Lists een manipulatie van de gegevensstructuur. Dus voor situaties waarin u “één bron van waarheid” nodig heeft die op verschillende manieren wordt gesorteerd, is handmatig sorteren de juiste keuze.

U kunt uw lijst sorteren met de java.util.Collections.sort()methode. Hier is een codevoorbeeld over hoe:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");
Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Comparatoren gebruiken

Een duidelijk voordeel is dat u Comparatorin de sortmethode. Java biedt ook enkele implementaties voor de Comparatorzoals de Collatorwat handig is voor locale gevoelige sorteerstrings. Hier is een voorbeeld:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing
Collections.sort(strings, usCollator);

Sorteren in gelijktijdige omgevingen

Houd er echter rekening mee dat het gebruik van de sort-methode niet vriendelijk is in gelijktijdige omgevingen, aangezien de verzamelingsinstantie zal worden gemanipuleerd, en u zou moeten overwegen om in plaats daarvan onveranderlijke verzamelingen te gebruiken. Dit is iets wat Guava biedt in de Orderingklasse en is een simpele one-liner:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Sluit uw lijst af met java.util.PriorityQueue

Hoewel er geen gesorteerde lijst in Java is, is er echter een gesorteerde wachtrij die waarschijnlijk net zo goed voor u zou werken. Het is de java.util.PriorityQueueklasse.

Nico Haase linkte in de reacties naar een gerelateerde vraagdie dit ook beantwoordt.

In een gesorteerde verzameling wil je hoogstwaarschijnlijk de interne gegevensstructuur niet manipuleren. Daarom implementeert PriorityQueue de List-interface niet (omdat je dan rechtstreeks toegang zou hebben tot de elementen ervan) .

Voorbehoud bij de PriorityQueueiterator

De klasse PriorityQueueimplementeert de interfaces Iterable<E>en Collection<E>zodat deze zoals gewoonlijk kan worden herhaald. Het is echter niet gegarandeerd dat de iterator elementen in de gesorteerde volgorde retourneert. In plaats daarvan (zoals Alderath aangeeft in de opmerkingen) moet je de wachtrij poll()totdat deze leeg is.

Houd er rekening mee dat u een lijst kunt converteren naar een prioriteitswachtrij via de constructor die elke verzameling aanneemt:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");
PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Schrijf je eigen SortedListklasse

OPMERKING:u zou dit niet moeten doen.

Je kunt je eigen List-klasse schrijven die elke keer dat je een nieuw element toevoegt, sorteert. Dit kan nogal rekenintensief worden, afhankelijk van je implementatie en is zinloos, tenzij je het als een oefening wilt doen, om twee hoofdredenen:

  1. Het verbreekt het contract dat de List<E>-interface heeft, omdat de add-methoden ervoor moeten zorgen dat het element zich in de index bevindt die de gebruiker opgeeft.
  2. Waarom het wiel opnieuw uitvinden? U zou in plaats daarvan de TreeSet of Multisets moeten gebruiken, zoals aangegeven in het eerste punt hierboven.

Als u het echter als een oefening wilt doen, is hier een codevoorbeeld om u op weg te helpen, het gebruikt de abstracte klasse AbstractList:

public class SortedList<E> extends AbstractList<E> {
    private ArrayList<E> internalList = new ArrayList<E>();
    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }
    @Override
    public E get(int i) {
        return internalList.get(i);
    }
    @Override
    public int size() {
        return internalList.size();
    }
}

Merk op dat als je de methoden die je nodig hebt niet hebt overschreven, de standaardimplementaties van AbstractListUnsupportedOperationExceptions zullen genereren.


Antwoord 2, autoriteit 10%

Omdat het concept van een lijst onverenigbaar is met het concept van een automatisch gesorteerde collectie. Het punt van een lijst is dat na het aanroepen van list.add(7, elem), een aanroep naar list.get(7)elem. Met een automatisch gesorteerde lijst kan het element op een willekeurige positie terechtkomen.


Antwoord 3, autoriteit 4%

Aangezien alle lijsten al zijn “gesorteerd” op de volgorde waarin de items zijn toegevoegd (FIFO-volgorde), kunt u ze “resorteren” met een andere volgorde, inclusief de natuurlijke volgorde van elementen, met behulp van java.util.Collections.sort().

BEWERKEN:

Lijsten als datastructuren zijn gebaseerd op wat interessant is, is de volgorde waarin de items zijn ingevoegd.

Sets hebben die informatie niet.

Als je wilt bestellen door tijd toe te voegen, gebruik dan List. Als u op andere criteria wilt bestellen, gebruikt u SortedSet.


Antwoord 4, autoriteit 3%

Set en Map zijn niet-lineaire gegevensstructuren. Lijst is lineaire datastructuur.

voer hier de afbeeldingsbeschrijving in


De boomgegevensstructuur SortedSeten SortedMapinterfaces implementeert respectievelijk TreeSeten TreeMapmet behulp van de gebruikte Rood-Zwarte boomimplementatie-algoritme. Het zorgt er dus voor dat er geen dubbele items zijn (of sleutels in het geval van Map).

  • Listheeft al een geordende verzameling en op index gebaseerde gegevensstructuur, bomen zijn geen op index gebaseerde gegevensstructuren.
  • Treekan per definitie geen duplicaten bevatten.
  • In Listkunnen we duplicaten hebben, dus er is geen TreeList(d.w.z. geen SortedList).
  • Lijst onderhoudt elementen in invoegvolgorde. Dus als we de lijst willen sorteren, moeten we java.util.Collections.sort()gebruiken. Het sorteert de gespecificeerde lijst in oplopende volgorde, volgens de natuurlijke volgorde van de elementen.

Antwoord 5, autoriteit 2%

JavaFX SortedList

Hoewel het even duurde, heeft Java 8 wel een gesorteerde List.
http://docs.oracle.com/javase /8/javafx/api/javafx/collections/transformation/SortedList.html

Zoals je kunt zien in de javadocs, maakt het deel uit van de JavaFX-collecties, bedoeld om een gesorteerde weergave bieden op een ObservableList.

Update: merk op dat met Java 11 de JavaFX-toolkit buiten de JDK is verplaatst en nu een aparte bibliotheek is. JavaFX 11 is beschikbaar als een downloadbare SDK of via MavenCentral. Zie https://openjfx.io


Antwoord 6

Voor alle nieuwkomers heeft Android vanaf april 2015 een SortedListklasse in de ondersteuningsbibliotheek, speciaal ontworpen om te werken met RecyclerView. Hier is de blogposterover.


Antwoord 7

Een ander punt is de tijdscomplexiteit van invoegbewerkingen.
Voor een lijst-insert verwacht je een complexiteit van O(1).
Maar dit kon niet worden gegarandeerd met een gesorteerde lijst.

En het belangrijkste is dat lijsten niets veronderstellen over hun elementen.
U kunt bijvoorbeeld lijsten maken met dingen die equalsof compareniet implementeren.


Antwoord 8

Zie het als volgt: de Listinterface heeft methoden zoals add(int index, E element), set(int index, E element). Het contract is dat als je eenmaal een element op positie X hebt toegevoegd, je het daar zult vinden, tenzij je elementen ervoor toevoegt of verwijdert.

Als een lijstimplementatie elementen in een andere volgorde zou opslaan dan op basis van de index, zouden de bovenstaande lijstmethoden geen zin hebben.


Antwoord 9

De eerste regel in de List API zegt dat het een geordende verzameling is (ook wel een reeks genoemd). Als u de lijst sorteert, kunt u de volgorde niet handhaven, dus er is geen TreeList in Java.
Zoals API zegt, is Java List geïnspireerd op Sequence en zie de sequentie-eigenschappen http://en.wikipedia.org /wiki/Sequence_(wiskunde)

Het betekent niet dat je de lijst niet kunt sorteren, maar Java is strikt volgens zijn definitie en biedt standaard geen gesorteerde versies van lijsten.


Antwoord 10

Als u op zoek bent naar een manier om elementen te sorteren, maar ze ook op een efficiënte manier via index kunt benaderen, kunt u het volgende doen:

  1. Gebruik een lijst met willekeurige toegang voor opslag (bijv. ArrayList)
  2. Zorg ervoor dat het altijd gesorteerd is

Om vervolgens een element toe te voegen of te verwijderen, kunt u Collections.binarySearchom de invoeg-/verwijderingsindex te krijgen. Aangezien uw lijst willekeurige toegang implementeert, kunt u de lijst efficiënt wijzigen met de vastgestelde index.

Voorbeeld:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;
    public SortingList() {
        delegate = new ArrayList<>();
    }
    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);
        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }
        delegate.add(insertionIndex, e);
    }
    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }
    public E get(int index) {
        return delegate.get(index);
    }
}

Antwoord 11

Ik denk dat al het bovenstaande deze vraag om de volgende redenen niet beantwoordt,

  1. Omdat dezelfde functionaliteit kan worden bereikt door andere collecties te gebruiken, zoals TreeSet, Collections, PriorityQueue..etc (maar dit is een alternatief dat ook hun beperkingen oplegt, dwz Set zal dubbele elementen verwijderen. legt geen enkele beperking op, het geeft geen antwoord op de vraag waarom SortedList niet is gemaakt door de java-gemeenschap)
  2. Aangezien List-elementen geen methodes voor vergelijken/gelijken implementeren (Dit geldt ook voor Set & Map waar in het algemeen items geen vergelijkbare interface implementeren, maar wanneer we deze items in gesorteerde volgorde willen hebben en willen gebruik TreeSet/TreeMap, items moeten een vergelijkbare interface implementeren)
  3. Aangezien List indexering gebruikt & vanwege het sorteren zal het niet werken (Dit kan gemakkelijk worden afgehandeld door een tussenliggende interface/abstracte klasse te introduceren)

maar niemand heeft de exacte reden erachter verteld & omdat ik geloof dat dit soort vragen het best kunnen worden beantwoord door de Java-gemeenschap zelf, aangezien deze maar één & specifiek antwoord, maar laat me mijn best doen om dit als volgt te beantwoorden,

Zoals we weten is sorteren een dure operatie en er is een fundamenteel verschil tussen List & Set/Map die lijst kan duplicaten hebben, maar Set/Map niet.
Dit is de belangrijkste reden waarom we een standaardimplementatie hebben voor Set/Map in de vorm van TreeSet/TreeMap. Intern is dit een roodzwarte boom met elke bewerking (invoegen/verwijderen/zoeken) met de complexiteit van O(log N)waar door duplicaten List niet in deze gegevensopslagstructuur paste.

Nu rijst de vraag of we ook een standaard sorteermethode voor Lijst kunnen kiezen, ook zoals MergeSortdie wordt gebruikt door de Collections.sort(list)methode met de complexiteit van O(N log N). Community heeft dit niet opzettelijk gedaan, omdat we meerdere keuzes hebben voor het sorteren van algoritmen voor niet-onderscheiden elementen zoals QuickSort, ShellSort, RadixSort…etc. In de toekomst kunnen er meer zijn. Soms werkt hetzelfde sorteeralgoritme ook anders, afhankelijk van de te sorteren gegevens. Daarom wilden ze deze optie open houden en lieten ze dit aan ons over om te kiezen. Dit was niet het geval met Set/Map aangezien O(log N)de beste sorteercomplexiteit is.


Antwoord 12

https://github.com/geniot/indexed-tree-map

Overweeg het gebruik van indexed-tree-map. Het is een verbeterde TreeSet van JDK die toegang biedt tot element voor index en het vinden van de index van een element zonder iteratie of verborgen onderliggende lijsten die een back-up van de boom vormen. Het algoritme is gebaseerd op het bijwerken van de gewichten van gewijzigde knooppunten elke keer dat er een wijziging is.

Other episodes