Posortowana lista tablic w Javie

Jestem zdumiony, że nie mogę znaleźć szybkiej odpowiedzi na to pytanie. Zasadniczo szukam infrastruktury danych w Javie, która implementuje java.util.Listinterfejs, ale która przechowuje swoje elementy w posortowanej kolejności. Wiem, że możesz używać normalnego ArrayListi używać Collections.sort()na nim, ale mam scenariusz, w którym od czasu do czasu dodam i często pobieram członków z mojej listy i nie chcę sortować tego za każdym razem, gdy pobieram członka na wypadek nowy został dodany. Czy ktoś może wskazać mi coś takiego, co istnieje w JDK lub nawet bibliotekach innych firm?

EDYCJA : infrastruktura danych będzie musiała zachować duplikaty.

PODSUMOWANIE ODPOWIEDZI : Wszystko to wydało mi się bardzo interesujące i wiele się nauczyłem. Szczególnie Aioobe zasługuje na wyróżnienie za jego wytrwałość w próbach spełnienia moich powyższych wymagań (głównie posortowana implementacja java.util.List, która obsługuje duplikaty). Przyjąłem jego odpowiedź jako najdokładniejszą w odniesieniu do tego, o co pytałem, i najbardziej prowokowała do myślenia na temat implikacji tego, czego szukałem, nawet jeśli to, o co zapytałem, nie było dokładnie tym, czego potrzebowałem.

Problem z tym, o co prosiłem, tkwi w samym interfejsie List i koncepcji opcjonalnych metod w interfejsie. Cytując javadoc:

Użytkownik tego interfejsu ma precyzyjną kontrolę nad tym, gdzie na liście wstawiany jest każdy element.

Wstawianie do posortowanej listy nie ma precyzyjnej kontroli nad punktem wstawiania. Następnie musisz pomyśleć, jak poradzisz sobie z niektórymi metodami. Weźmy addna przykład:

public boolean add (Object o)

 Appends the specified element to the end of this list (optional operation).

Jesteś teraz w niewygodnej sytuacji: 1) Zerwanie kontraktu i zaimplementowanie posortowanej wersji add 2) Pozwolenie na adddodanie elementu na koniec listy, zerwanie posortowanego porządku 3) Opuszczenie add(jako opcjonalne) UnsupportedOperationExceptioni wdrożenie innej metody, która dodaje elementy w posortowanych.

Opcja 3 jest prawdopodobnie najlepsza, ale uważam za nieprzyjemne posiadanie metody dodawania, której nie możesz użyć, i innej metody sortowanej, której nie ma w interfejsie.

Inne powiązane rozwiązania (w dowolnej kolejności):

• java.util.PriorityQueue, która jest prawdopodobnie najbliższa temu, czego potrzebowałem, niż to, o co prosiłem. W moim przypadku kolejka nie jest najdokładniejszą definicją zbioru obiektów, ale funkcjonalnie robi wszystko, czego potrzebuję.
• net.sourceforge.nite.util.SortedList . Jednak ta implementacja przerywa kontrakt interfejsu List przez zaimplementowanie sortowania w add(Object obj)metodzie i, co dziwne, nie ma wpływu na metodę add(int index, Object obj). Ogólny konsensus sugeruje, throw new UnsupportedOperationException()że w tym scenariuszu może być lepszym wyborem.
• TreeMultiSet Guavy Zestaw implementacji, który obsługuje duplikaty
• ca.odell.glazedlists.SortedList Ta klasa zawiera zastrzeżenie w jej javadoc:Warning: This class breaks the contract required by List

Minimalistyczne rozwiązanie

Oto „minimalne” rozwiązanie.

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

Wstawianie przebiega w czasie liniowym, ale i tak uzyskasz to, używając ArrayList (wszystkie elementy na prawo od wstawionego elementu musiałyby zostać przesunięte w taki czy inny sposób).

Wstawienie czegoś nieporównywalnego powoduje wyjątek ClassCastException. (Jest to również podejście przyjęte przez PriorityQueue: kolejka priorytetowa oparta na naturalnym porządku również nie pozwala na wstawianie nieporównywalnych obiektów (może to spowodować ClassCastException). )

Nadrzędny List.add

Zwróć uwagę, że nadpisywanie List.add(lub List.addAllo to chodzi) wstawiania elementów w sposób posortowany byłoby bezpośrednim naruszeniem specyfikacji interfejsu . Co mógł zrobić, to zastąpić tę metodę, aby rzucić UnsupportedOperationException.

Z dokumentów List.add:

boolean add(E e)
    Dołącza określony element na końcu tej listy (operacja opcjonalna).

To samo rozumowanie dotyczy obu wersji add, obu wersji addAlli set. (Wszystkie z nich są operacjami opcjonalnymi zgodnie z interfejsem listy).

Kilka testów

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

.... wydruki:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Użyj java.util.PriorityQueue.

Spójrz na SortedList

Ta klasa implementuje posortowaną listę. Jest zbudowany z komparatorem, który może porównać dwa obiekty i odpowiednio je posortować. Kiedy dodajesz obiekt do listy, jest on wstawiany we właściwym miejscu. Obiekty, które są równe według komparatora, będą na liście w kolejności, w jakiej zostały dodane do tej listy. Dodaj tylko obiekty, które komparator może porównać.

Gdy lista zawiera już obiekty, które są równe według komparatora, nowy obiekt zostanie wstawiony natychmiast po tych innych obiektach.

Możesz wypróbować TreeMultiSet firmy Guava .

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);

Podejście Aioobe jest drogą do zrobienia. Chciałbym jednak zasugerować następujące ulepszenia w stosunku do jego rozwiązania.

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else {
                return mid; // key found
            }
        }

        return low;  // key not found
    }
}

Rozwiązanie aioobe działa bardzo wolno podczas używania dużych list. Wykorzystanie faktu, że lista jest posortowana, pozwala nam znaleźć punkt wstawienia dla nowych wartości za pomocą wyszukiwania binarnego.

Użyłbym również kompozycji zamiast dziedziczenia, coś w stylu

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Listy zazwyczaj zachowują kolejność, w jakiej są dodawane elementy. Czy na pewno potrzebujesz listy , czy posortowany zestaw (np. TreeSet<E>) Byłby dla Ciebie w porządku? Zasadniczo, czy musisz zachować duplikaty?

Może to być dla Ciebie trochę za ciężkie, ale GlazedLists ma SortedList, który jest idealny do użycia jako model tabeli lub JList

Możesz utworzyć podklasę ArrayList i wywołać Kolekcje.sort (this) po dodaniu dowolnego elementu - aby to zrobić, musisz zastąpić dwie wersje add i dwie wersje addAll.

Wydajność nie byłaby tak dobra, jak inteligentniejsza implementacja, w której elementy zostałyby wstawione we właściwym miejscu, ale spełniłaby swoje zadanie. Jeśli dodanie do listy jest rzadkie, amortyzowany koszt wszystkich operacji na liście powinien być niski.

Po prostu utwórz nową klasę, taką jak ta:

public class SortedList<T> extends ArrayList<T> {

private final Comparator<? super T> comparator;

public SortedList() {
    super();
    this.comparator = null;
}

public SortedList(Comparator<T> comparator) {
    super();
    this.comparator = comparator;
}

@Override
public boolean add(T item) {
    int index = comparator == null ? Collections.binarySearch((List<? extends Comparable<? super T>>)this, item) :
            Collections.binarySearch(this, item, comparator);
    if (index < 0) {
        index = index * -1 - 2;
    }
    super.add(index+1, item);
    return true;
}

@Override
public void add(int index, T item) {
    throw new UnsupportedOperationException("'add' with an index is not supported in SortedArrayList");
}

@Override
public boolean addAll(Collection<? extends T> items) {
    boolean allAdded = true;
    for (T item : items) {
        allAdded = allAdded && add(item);
    }
    return allAdded;
}

@Override
public boolean addAll(int index, Collection<? extends T> items) {
    throw new UnsupportedOperationException("'addAll' with an index is not supported in SortedArrayList");
}

}

Możesz to przetestować w ten sposób:

    List<Integer> list = new SortedArrayList<>((Integer i1, Integer i2) -> i1.compareTo(i2));
    for (Integer i : Arrays.asList(4, 7, 3, 8, 9, 25, 20, 23, 52, 3)) {
        list.add(i);
    }
    System.out.println(list);

Myślę, że wybór między SortedSets / Lists i „normalnymi” sortowalnymi kolekcjami zależy od tego, czy potrzebujesz sortowania tylko do celów prezentacji, czy w prawie każdym momencie podczas działania. Korzystanie z posortowanej kolekcji może być znacznie droższe, ponieważ sortowanie odbywa się za każdym razem, gdy wstawiasz element.

Jeśli nie możesz zdecydować się na kolekcję w JDK, możesz zajrzeć do kolekcji Apache Commons

Ponieważ obecnie proponowane implementacje, które implementują posortowaną listę przez zerwanie Collection API, mają własną implementację drzewa lub coś podobnego, byłem ciekawy, jak będzie działać implementacja oparta na TreeMap. (Szczególnie, ponieważ TreeSet również opiera się na TreeMap)

Jeśli ktoś też jest tym zainteresowany, może śmiało się temu przyjrzeć:

TreeList

Jest to część podstawowej biblioteki , możesz ją oczywiście dodać za pomocą zależności Maven. (Licencja Apache)

Obecnie implementacja wydaje się całkiem dobrze porównywać na tym samym poziomie co guawa SortedMultiSet i TreeList z biblioteki Apache Commons.

Ale byłbym szczęśliwy, gdyby nie tylko ja przetestowałbym implementację, aby mieć pewność, że nie przegapiłem czegoś ważnego.

Z poważaniem!

Miałem ten sam problem. Więc wziąłem kod źródłowy java.util.TreeMap i napisałem IndexedTreeMap . Implementuje moją własną IndexedNavigableMap :

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

Implementacja polega na aktualizowaniu wag węzłów w czerwono-czarnym drzewie po zmianie. Waga to liczba węzłów potomnych pod danym węzłem plus jeden własny. Na przykład, gdy drzewo jest obracane w lewo:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight po prostu aktualizuje wagi aż do katalogu głównego:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

A kiedy musimy znaleźć element według indeksu, jest to implementacja, która używa wag:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Przydaje się również znalezienie indeksu klucza:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);

    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Wynik tej pracy można znaleźć pod adresem http://code.google.com/p/indexed-tree-map/

TreeSet / TreeMap (jak również ich indeksowane odpowiedniki z projektu mapy indeksowanego drzewa) nie zezwalają na zduplikowane klucze, możesz użyć 1 klucza dla tablicy wartości. Jeśli potrzebujesz SortedSet z duplikatami, użyj TreeMap z wartościami jako tablicami. Zrobiłbym to.