In Java zijn er de SortedSet
en 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 SortedList
in 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 Set
of Bag
collecties 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 SortedSet
en NavigableSet
interfaces 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 Set
die 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 List
s 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 Comparator
in de sort
methode. Java biedt ook enkele implementaties voor de Comparator
zoals de Collator
wat 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 Ordering
klasse 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.PriorityQueue
klasse.
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 PriorityQueue
iterator
De klasse PriorityQueue
implementeert 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 SortedList
klasse
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:
- Het verbreekt het contract dat de
List<E>
-interface heeft, omdat deadd
-methoden ervoor moeten zorgen dat het element zich in de index bevindt die de gebruiker opgeeft. - 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 AbstractList
UnsupportedOperationException
s 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.
De boomgegevensstructuur SortedSet
en SortedMap
interfaces implementeert respectievelijk TreeSet
en TreeMap
met 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
).
List
heeft al een geordende verzameling en op index gebaseerde gegevensstructuur, bomen zijn geen op index gebaseerde gegevensstructuren.Tree
kan per definitie geen duplicaten bevatten.- In
List
kunnen we duplicaten hebben, dus er is geenTreeList
(d.w.z. geenSortedList
). - 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 equals
of compare
niet implementeren.
Antwoord 8
Zie het als volgt: de List
interface 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:
- Gebruik een lijst met willekeurige toegang voor opslag (bijv.
ArrayList
) - Zorg ervoor dat het altijd gesorteerd is
Om vervolgens een element toe te voegen of te verwijderen, kunt u Collections.binarySearch
om 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,
- 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)
- 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)
- 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.