Mam pytanko jak zrobić coś takiego w jawie jak najprościej. Tworzę sobie pusty wektor obiektów, do których mam komparator. Następnie dodaję do niego obiekty i kiedy wektor ma długość powiedzmy 20 to robię:
Collections.sort(wektor, mojComparator);
Teraz dodaję kolejne obiekty, sortuję wektor i usuwam ostatni (ale to usuwanie w sumie nie ma znaczenia dla problemu).
Jak zrobić, aby po dodaniu nowego elementu do posortowanego wektora ustawiał się on we właściwym miejscu tak, aby wektor był nadal posortowany? Mogę oczywiście po każdym dodaniu sortować wektor, ale to mi się wydaje za mało wydajne.
Zasadniczo powinienem zrobić wyszukiwanie binarne i znaleźć miejsce gdzie wstawić nowy element ze złożonością O(log n).
Chodzi mi o to, czy w jawie jest jakaś gotowa kolekcja, która potrafi takie rzeczy sama z automatu realizować? W opisie opieram się na klasie Vector, ale nie jest to konieczne, nie muszę mieć indeksowanego dostępu, wystarczy iterator.
- Używanie Vector to zwykle bardzo słaba opcja bo jest defaultowo synchronizowany i zwykle jednak chciałbyś używać List a nie Vector.
- Jeśli elementy są unikalne to użycie SortedSet byłoby najłatwiejsze.
- Guava ma TreeMultiset
- Możesz też użyć PriorityQueue ;]
Z tym PriorityQueue już wcześniej próbowałem, ale mi nie wyszło. Coś jest nie tak, ale nie wiem co. Poniżej kod testowy. Chodzi o to, żeby podać własny komparator, a nie używać natural ordering.
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.TreeSet;
public class QueueManager {
public static void main(String args[]) {
Random r = new Random();
PriorityQueue<Item> queue = new PriorityQueue<Item>(10, new Comparator<Item>() {
@Override
public int compare(Item left, Item right) {
return left.value - right.value;
}
});
for (int i = 0; i < 20; i++) {
int value = r.nextInt(100);
System.out.println("" + value);
queue.add(new Item(value));
System.out.println(queue);
}
}
}
class Item {
final int value;
public Item(int value) {
this.value = value;
}
@Override
public String toString() {
return "" + value;
}
}
Jak widać biorę losową liczbę, tworzę obiekt Item z tą liczbą, wypisuję ją na ekran, dodaję do kolekcji i wypisuję kolekcję, która powinna być posortowana. Ale wyniki tego programu wyglądają tak:
35
[35]
72
[35, 72]
58
[35, 72, 58]
21
[21, 35, 58, 72]
62
[21, 35, 58, 72, 62]
72
[21, 35, 58, 72, 62, 72]
19
[19, 35, 21, 72, 62, 72, 58]
49
[19, 35, 21, 49, 62, 72, 58, 72]
33
[19, 33, 21, 35, 62, 72, 58, 72, 49]
...
Nie jest to posortowana kolekcja, a więc chyba PriorityQueue jest do czegoś innego.
Sprawa ma się o wiele lepiej, jeżeli zmienna queue jest taka:
SortedSet<Item> queue = new TreeSet<Item>(new Comparator<Item>() {
@Override
public int compare(Item left, Item right) {
return left.value - right.value;
}
});
No ale set jak to set, nie pozwala na takie same elementy. Być może w mojej kolekcji będą one unikatowe i SortedSet mi wystarczy, ale gdyby jednak okazało się, że muszę mieć powtarzające się obiekty, to czy jest jakieś rozwiązanie w standardowej bibliotece?
PriorityQueue daje gwarancję, że głowa kolejki jest najmniejszym elementem (dla danego komparatora). Inaczej mówiąc, peek() lub poll() zwracają najmniejszy element z kolejki i jeśli chcesz wyciągnąć posortowane dane to musisz wyczyścić kolejkę za pomocą poll() a wyciągnięte elementy powkładać do listy.
Tak podejrzewałem, że gdzieś jest haczyk w tym PriorityQueue, skoro nie nazywa się SortedQueue.
To może inaczej zapytam: mam listę obiektów, kilka tysięcy, dla których porównanie jest dość kosztowną operacją. Potrzebuję znaleźć kilkadziesiąt najmniejszych wartości.
Na tą chwilę mam dwa plany:
- Użyć SortedSet i jakoś zabezpieczyć się, aby obiekty się nie powtarzały.
- Zmienić komparator, użyć PriorityQueue i po dodaniu wyrzucać z kolejki największy element, a na końcu ją posortować ewentualnie.
Można jakoś inaczej jeszcze?
chodnik napisał(a):
Mam pytanko jak zrobić coś takiego w jawie jak najprościej. Tworzę sobie pusty wektor obiektów, do których mam komparator. [...] Zasadniczo powinienem zrobić wyszukiwanie binarne i znaleźć miejsce gdzie wstawić nowy element ze złożonością O(log n).
Chodzi mi o to, czy w jawie jest jakaś gotowa kolekcja, która potrafi takie rzeczy sama z automatu realizować? W opisie opieram się na klasie Vector, ale nie jest to konieczne, nie muszę mieć indeksowanego dostępu, wystarczy iterator.
Masz rację. Oczywiście, że istnieje w Javie prosty i gotowy sposób na wykonanie wstawiania z wyszukiwaniem binarnym. Twoim częściowym rozwiązaniem jest przeciążona metoda Arrays.binarySearch:
http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html
Wynikiem jej działania jest liczba nieujemna w przypadku znalezienia elementu o równej wartości (w sensie wywołania CompareTo == 0), albo liczba ujemna podająca zakodowany indeks pod który należy wstawić nowy element aby tablica była nadal posortowana. Wynik podawany przez binarySearch, to (-(insertion point) - 1). Wystarczy więc z wyniku wyciągnąć insertion point i już masz indeks pod który należy wstawić nowy element z rozsunięciem już istniejących. Tu wchodzi kolejny mały problem ponieważ o ile wiem standardowa tablica nie ma takiej operacji wstawiania - potrafi tylko przypisać nową wartość. Trzeba więc takie rozsuwanie elementów samemu sobie napisać za pomocą np. System.arraycopy.
Ponieważ kiedyś było mi to też potrzebne, więc coś takiego sobie napisałem, ale potem wyrzuciłem do kosza gdy uznałem, że można zrobić coś jeszcze lepszego. Tym czymś lepszym było dla mnie wykorzystanie uniwersalnej listy, czyli typu java.util.List (którą obecnie implementuje również Vector) zamiast nieco zbyt prymitywnych tablic. Listy mają operację insert i zależnie od implementacji (RandomAcces lub sekwencyjnej) można takie "sortowanie" przeprowadzić efektywnie (O(log n)) lub kompromisowo: Wstawianie w ArrayList jest problematyczne z powodu przesuwania elementów wewnętrznej tablicy, za to indeksowanie błyskawiczne. I odwrotnie w LinkedList: Wstawianie jest błyskawiczne, ale indeksowanie fatalne - złożoność w najlepszym wypadku liniowa (O(n/2) dla list dwukierunkowych).
Drugim drobnym problemem była konieczność przepisania szukania połówkowego dla list (które jakimś cudem w standardzie Javy nie istnieje, albo ja go nie znalazłem).
Oto kod tego co dobrze mi działa dla list:
abstract public class Lists
{
//...
/**
* Przeszukuje za pomocą podziałów połówkowych całą posortowaną rosnąco
* listę o dostępie swobodnym i zwraca indeks znalezionego elementu toFind
* lub wartość -ins - 1, gdzie ins jest pozycją wstawienia elementu, czyli
* większy od pierwszego mniejszego elementu na liście. Metoda może być
* wykorzystana do szybkiego określenia występowania elementu toFind na
* liście list, czyli efektywnie zastąpić metodę contains().
* @param <E> typ elementu listy
* @param list posortowana rosnąco lista elementów
* @param toFind element, którego indeks jest do znalezienia
* @param c obiekt komparatora porównującego dwa elementy listy
* @return nieujemny indeks znalezionego elementu lub -punkt_wstawienia-1
*/
public static <E>
int binarySearch(E toFind, List<E> list, Comparator<? super E> c)
{
int l = 0;
int r = list.size() - 1;
for(int cmp, mid = (l + r) >>> 1; l <= r; mid = (l + r) >>> 1)
{
cmp = c.compare(toFind, list.get(mid));
if(cmp > 0) l = ++mid;
else if(cmp < 0) r = --mid;
else return mid; //toFind found
}
return -(l + 1); //toFind not found.
}
/**
* Wstawia element toInsert do podanej posortowanej listy w taki sposób,
* aby znalazł się on między elementem mniejszym i większym. Elementy są
* porównywane za pomocą podanego komparatora. Parametr allowReplace
* pozwala na zastępowanie równych elementów już występujących na liście,
* czyli wymusza unikalność wartości wstawianych elementów.
* Wstawienie elementu unikalnego lub tak aby zachowana została unikalność
* (allowReplace) zwraca true, a w przeciwnym wypadku false.
* Metoda może być efektywnie wykorzystana do szybkiego
* tworzenia posortowanych list.
* Nie jest efektywne tworzenie komparatora w wywołaniu tej metody. Należy
* utworzyć go wcześniej i wykorzystywać w miarę potrzeby.
* @param <E> typ elementu
* @param toInsert element do wstawienia na listę list
* @param list posortowana lista (może być pusta)
* @param comparator obiekt porównujący elementy
* @param allowReplace true pozwala na zastępowanie elementów istniejących
* i wymusza zachowanie unikalności wartości elementów listy, false
* zabrania eliminacji toInsert z listy gdy istnieje równy (Comparable).
* @return true w przypadku wstawienia zachowującego unikalność
*/
public static <E> boolean sortedInsert(E toInsert, List<E> list,
boolean allowReplace, Comparator<? super E> comparator)
{
return sortingInsert(toInsert, list, allowReplace,
comparator) < 0 || allowReplace;
}
/**
* Wstawia element toInsert do podanej rosnąco posortowanej listy w taki
* sposób, aby znalazł się on między elementem mniejszym i większym.
* Elementy są porównywane za pomocą podanego komparatora.
* Parametr allowReplace pozwala na zastępowanie równych elementów już
* występujących na liście, czyli wymusza unikalność wartości wstawianych
* elementów.
* Zwracany jest indeks znalezionego elementu toInsert lub wartość
* -ins - 1, gdzie ins jest pozycją wstawienia elementu, czyli większy
* od pierwszego mniejszego elementu na liście.
* Nie jest efektywne tworzenie komparatora w wywołaniu tej metody. Należy
* utworzyć go wcześniej i wykorzystywać w miarę potrzeby w wywołaniach.
* Metoda może być przydatna do zastępowania {@literal sortedInsert}
* w sytuacji gdy położenie pozycji dla wstawianego elementu (wstawionego
* lub znalezionego z tym samym porządkiem) jest informacją potrzebną
* do ponownego wykorzystania.
* @param <E> typ elementu
* @param toInsert element do wstawienia na listę list
* @param list posortowana lista (może być pusta)
* @param comparator obiekt porównujący elementy
* @param allowReplace true pozwala na zastępowanie elementów istniejących
* i wymusza zachowanie unikalności wartości elementów listy, false
* zabrania eliminacji toInsert z listy gdy istnieje równy (Comparable).
* @return nieujemny indeks już istniejącego równego elementu lub
* -punkt_wstawienia-1 dla elementu nie istniejącego
*/
public static <E> int sortingInsert(E toInsert, List<E> list,
boolean allowReplace, Comparator<? super E> comparator)
{
final int found = binarySearch(toInsert, list, comparator);
if(found < 0)
list.add(-found - 1, toInsert); //odwrócenie ujemnej daje nieujemną
else if(allowReplace)
list.set(found, toInsert); //dozwolone zastępowania
else //dostawia element równy przed istniejący
list.add(found, toInsert);
return found;
}
//...
}
Metoda wstawiająca została podzielona na dwie ponieważ czasem jest potrzeba usuwania znalezionego elementu po jego indeksie, a nie warto w tym celu jeszcze raz odpalać binarySearch skoro ta informacja jest już dostępna w wywołaniu sortingInsert. Dodatkowo dodałem sobie parametr allowReplace, który pozwala efektywnie zmienić posortowaną listę w posortowany zbiór bo każde wstawianie będzie eliminować elementy o tej samej wartości wg compareTo. Efektywność jest podobna do efektywności drzew czerwono-czarnych, czyli w Javie TreeSet.
Zamiast babrania się z tablicą wolałem mieć rozwiązanie równie szybkie, lecz bardziej uniwersalne. Dzięki temu tą "mityczną kolekcją" stała się zwykła lista. :)
Dodatkowo jeżeli używa się super biednych implementacji Javy (które nie mają nawet Vectora), to można sobie sprawić własną wersję listy indeksowanej oderwanej od standardowych kolekcji Javy i kod ten nadal będzie działać (po eliminacji generyków).
Dodatkowo przydaje mi się jeszcze prosta metoda do sortowania:
/**
* Tworzy listę elementów E o zawartości identycznej jak podawana lista,
* lecz posortowaną wg klucza podawanego przez comparator.
* @param <E> typ elementów
* @param list lista elementów
* @param comp comparator dwóch elementów typu E
* @return lista elementów posortowanych wg podanego indeksera
*/
public static <E> List<E> sortedBy(List<E> list, final Comparator<E> comp)
{
final List<E> result = new ArrayList<>(list.size()); //tu może być również Vector
for(E element: list) //wstawia również elementy nieunikalne
Lists.sortedInsert(element, result, false, comp);
return result;
}
chodnik napisał(a):
Z tym PriorityQueue już wcześniej próbowałem, ale mi nie wyszło. Coś jest nie tak, ale nie wiem co. Poniżej kod testowy. Chodzi o to, żeby podać własny komparator, a nie używać natural ordering.
Kiedyś wrzucano osobne przeciążane wersje różnych metod do uwzględniania naturalnego porządku, ale od Javy 1.5 wystarczyło robić tylko wersje z komparatorem i dodać jeden uniwersalny komparator taki jak ten:
/**
* Klasa obiektu naturalnie porównującego obiekty typu E.
* Wszędzie gdzie potrzeba komparatora dla typu elementów mających swój
* naturalny porządek (E), tam można umieścić komparator w takiej postaci
* {@code new NaturalOrder<E>()}, gdzie E jest klasą posiadającą swój
* naturalny porządek wyrażony implementacją interfejsu
* {@literal Comparable<E>}.
* @param <E> elementy listy mające swój naturalny porządek
*/
public static class NaturalOrder<E extends Comparable<? super E>>
implements Comparator<E>
{
@Override public int compare(E e1, E e2) { return e1.compareTo(e2); }
}
Działa to wszędzie gdzie jest wymagany jakikolwiek komparator dla zupełnie dowolnego typu E, a nie wmuszonego E extends Comparable<? super E>. Nie wiem dlaczego tak nie zrobiono skoro była okazja. W każdym razie można "olać system" i zdefiniować to sobie samemu. ;)
Jest to bardzo wygodny komparator dla kodu, który podałem w poprzednim poście. Zamiast babrać się z nową wersją wszystkich trzech metod dla naturalnego porządku podaję po prostu komparator, który ten porządek na starcie uwzględnia. Ewentualne błędy wychodzą już w trakcie kompilacji zależnie od tego co sobą reprezentuje typ E.
@Olamagato, dzięki za obszerne wyjaśnienia. Rozważałem to binarySearch, ale nie brałem pod uwagę, że albo indeksowanie, albo przesuwanie tablicy będzie aż tak problematyczne. W związku z tym na tą chwilę wybieram TreeSet i zobaczę, jak to się będzie sprawdzać w boju. Jak nie będzie dobrze działać, to wrócę do implementacji jak w powyższych przykładach. Ponieważ obiekty mam unikalne, to mogę sobie pominąć problem pomijania identycznych.
Zrezygnuję jednak z PriorityQueue, bo naszły mnie poważne wątpliwości. Otóż po usunięciu czoła kolejki pozostaje lista, która jest nieuporządkowana i teraz jest w niej znajdowany minimalny element, a więc złożoność O(n). A to więcej niż utrzymywanie SortedSet. Chyba, że znowu gdzieś się mylę co do działania PriorityQueue.
PriorityQueue to zwykły http://pl.wikipedia.org/wiki/Kopiec_binarny . Zarówno dodawanie elementu do kopca jak i usuwanie elementu ze szczytu kopca (czyli tutaj chyba najmniejszego) wymaga O(lg n) porównań. Sprawdzenie jaki element jest na szczycie kopca (tzn jest najmniejszy) zajmuje czas stały - bo wiadomo od razu, który element zwrócić. Kopiec nie udostępnia operacji wyszukiwania bezpośrednio, ale można iterować po prostu po wszystkich elementach, co jak wiadomo zabiera czas O(n).
Użyłem takiego kodu
NavigableSet<Item> queue = new TreeSet<Item>(new Comparator<Item>() {
@Override
public int compare(Item left, Item right) {
return left.value - right.value;
}
});
Okazało się, że cały misterny plan w...
Wbrew temu, co jest napisane w dokumentacji metoda add z klasy TreeSet nie używa equals do sprawdzenia, czy element jest w zbiorze. Zamiast tego używany jest komparator. Tak więc nie ma możliwości dodania dwóch różnych elementów, dla których komparator zwraca wartość 0.
Czas na plan B i implementację w oparciu o binarySearch, no bo co jeszcze można zrobić?
//Edit: A jednak mam inny pomysł, muszę zrobić w komparatorze a by w momencie kiedy ma zwrócić zero porównywał jeszcze id. Tu kolejność nie ma znaczenia, ale komparator nigdy zera nie zwróci.
Nie rozumiem czemu nie możesz użyć PriorityQueue. Napisałeś, że chcesz:
- móc przetrzymywać w kolekcji wiele elementów, dla których compareTo daje 0 parami (tzn są równe wobec tej operacji porównania),
- w miarę szybko dodawać elementy do kolekcji (tzn w czasie logarytmicznym),
- co jakiś czas usuwać najmniejszy element i też w miarę szybko (tzn w czasie logarytmicznym),
PriorityQueue idealnie się do tego nadaje. No chyba, że potrzebujesz jeszcze jakichś dodatkowych funkcjonalności.
Może być tak w końcu opisał swój problem, mamy wróżyć z fusów czy jak?
Wibowit napisał(a):
Może być tak w końcu opisał swój problem, mamy wróżyć z fusów czy jak?
Problem to kategoryzacja wektorów metodą k-nn. Wybieram sobie wektor badany i porównuję z nim wszystkie ze zbioru uczącego i potrzebuję odczytać kategorie z k najbliższych. Tak więc dodaję po kolei do zbioru kolejne wektory i wyrzucam pozostawiając tylko te najbliższe. Dodatkowo mam zbadać dokładność dla różnych k. I wtedy układając kolejność wektorów dla k=10 mam też dla wszystkich mniejszych k. Z powodu tego usprawnienia zrezygnowałem z PriorityQueue bo jednak całość muszę mieć uporządkowaną.
Jeśli dobrze zrozumiałem to problem jest taki:
- masz dany wektor v oraz n wektorów x[1..n], które są zadane z góry,
- do tego masz metrykę, dzięki której mierzysz odległość,
Ja bym to zrobił tak:
- opakował bym wektory x w klasę która ma dwa pola: wektor + odległość wektora od v,
- wrzuciłbym tak opakowane wektory x do ArrayList,
- posortował Collections.sort(),
- voila :)
No chyba, że jednak źle sprecyzowałeś problem i masz układać wektory wielokrotnie, tzn mieć poprzekładane kategoryzację i dorzucanie wektorów x[i].
@Wibowit, dzięki za sugestię, ale są powody, dla których tak nie mogę zrobić. Pierwszy jest taki, że nie chcę przechowywać całej kolekcji x[1..n], bo to jest kilka tysięcy wektorów o długości nawet kilka tysięcy. A więc jest obawa, że program się wywali z powodu braku pamięci. Moja koncepcja ogranicza zużycie do wektora długości k<=200 najbliższych zamiast wszystkich (kilka tysięcy).
Druga sprawa jest taka, że za pomocą tych n wektorów muszę sklasyfikować więcej niż jeden dokument (kilka tysięcy), a więc nie mogę go opakować w klasę razem z odległością, bo tych odległości jest więcej.
Dlatego właśnie chodziło mi głównie o to jak dodawać obiekty do listy, aby były posortowane, żeby usuwać najdalszy. Wstępne testy z NavigableSet dają zadowalający rezultat, więc na razie tak to będę robił.