Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[Java] TreeSet - spory problem, a w sobote egzamin...

Kamil Wolski 02 Wrz 2010 16:14 2792 10
  • #1 02 Wrz 2010 16:14
    Kamil Wolski
    Poziom 12  

    Witam wszystkich...

    W sobotę mam egzamin poprawkowy z Podstaw Programowania i Algorytmów. Przez większość zdobytego materiału przebrnąłem bez większych problemów. Jednym z kilku zadań na egzaminie jest zadanie polegające na zapoznaniu się z fragmentem kodu i wypisaniu wartości, które w efekcie program ten wypluje. Z programami pracującymi na listach sobie radzę, jednak mam fragment programu, którego przegryźć nie mogę... oto on:

    Code:

    Public class sortowanie {
       Public static void main(String[] args) {
          SortedSet<Integer> x = new TreeSet<Integer>(
          New Comparator<Integer>()
          {public int compare(Integer ob1, Integer ob2)
             {ob2=!(ob2%2!=0)?ob2+=10:ob2;
             ob1=!(ob1%2!=0)?ob1+=10:ob1;
             Return ob1-ob2;} });
       x.add(10); x.add(1);
       x.add(9); x.add(6);
    x.add(4); x.add(8);
    x.add(7); x.add(5);
    x.add(3); x.add(2);

    System.out.print(x.subSet(1, 10)+”,”); }}


    Czy byłby ktoś tak dobry, i dopomógł, chociaż co nieco wyjaśnił? Chcę mieć 100% pewności, że dam radę na tym egzaminie, stąd ta desperacka prośba w ostatnich godzinach...

    0 10
  • Pomocny post
    #2 02 Wrz 2010 19:35
    pallid
    Poziom 20  

    A w czym konkretniej problem?

    Podany przez Ciebie kod przedstawia jeden ze sposobow wykorzystania zbioru. Zbior (Set w Java) to kolekcja obiektow, nie zawierajaca duplikatow (moze tez zawierac co najwyzej jedna wartosc "null", ale to mniej istotne). Dodatkowo, w tym przypadku mamy do czynienia z posortowanym zbiorem liczb (SortedSet<Integer>), dokladniej TreeSet.

    W jaki sposob sortowane sa elementy zbioru?
    Domyslnie, kolekcje w Java wykorzystuja wlasny wbudowany komparator, ktory wymaga, aby porownywane obiekty implementowaly interfejs Comparable<T>. Wiekszosc prostych obiektow (typu String, Character, Date) lub wrapperow dla typow prymitywnych (tj. Byte, Integer, itd.), ma juz ten interfejs zaimplementowany. Dla innych obiektow trzeba sobie samemu zdefiniowac ten interfejs lub...

    ... inna metoda, uzyta w tym przypadku, jest zdefiniowanie wlasnego komparatora i podanie go jako argument konstruktora. Taki komparator zostanie wstawiony na miejsce domyslnego i zostanie uzyty do ustawiena nowego obiektu na odpowiednim miejscu w posortowanym zbiorze (lub liscie, w przypadku java.util.List).

    Interfejs Comparator ma tylko jedna metode: public int compare(T o1, T o2), ktora zwraca "0", jesli o1 i o2 maja byc rowne lub wartosc ujemna lub dodatnia w przypadku gdy o1 jest, odpowiednio, mniejsze lub wieksze od o2.

    Podany tutaj algorytm komparatora:

    Code:
    new Comparator<Integer>() {
    
        public int compare(Integer ob1, Integer ob2) {
            ob2 = !(ob2%2!=0) ? ob2+=10 : ob2;
            ob1 = !(ob1%2!=0) ? ob1+=10 : ob1;
            return ob1-ob2;
        }
    }


    pozwoli poustawiac wartosci liczbowe w kolejnosci rosnacej, z tym, ze wartosci parzyste sa "wieksze" od nieparzystych. Jak pewnie nie trudno sie domyslic, algorytm zadziala dla wartosci <0, 10>, a dla innych moze zaczac generowac bzdury. Troche przekombinowany jest sposob sprawdzania parzystosci.

    Ostatnia linijka wyswietla wszystkie elementy majace wartosc z przedzialu <1, 10) (przedzial domkniety lewostronnie). Uwaga: to nie musi byc 10 elementow, wszystko zalezy od tego, jak posortowana jest kolekcja.

    PS: warto dokladniej przyjrzec sie temu, co dzieje sie w metodzie compare(Integer, Integer). Oba parametry, tj. ob1 i ob2 sa typu Integer natomiast w kodzie metody znajduja sie takie operacje, jak ob2+=10 i ob1-ob2. Mechanizm, ktory pozwala na traktowanie wrapperow typow prymitywnych jak same prymitywy, nazywa sie auto-boxing (dostepny od Java 5).

    0
  • Pomocny post
    #3 02 Wrz 2010 19:39
    enemyhilator
    Poziom 15  

    Code:
    [1, 3, 5, 7, 9, 2, 4, 6, 8],

    0
  • #4 02 Wrz 2010 19:56
    Kamil Wolski
    Poziom 12  

    Dziękuję bardzo za wyczerpującą wypowiedź.

    Doszedłem do tego co wypisuje, wypisałem sobie wartości przed zadziałaniem comparatora jak i po jego zadziałaniu oraz wyniki odejmowania, czyli ich wzajemne stosunki.

    Nie wiem tylko dlaczego akurat tak, a nie inaczej porównuje podane liczby, tj dla przykładu (liczby przed zwiększeniem o 10 liczb parzystych):

    1 i 10
    9 i 10
    9 i 1
    itd.

    Rozumiem, że już na wstępie, do jest zanim zadziała komparator, wszystkie te elementy liczbowe są umieszczone w drzewie. Do pełnego zrozumienia problemu brakuje mi "wizualizacji" tego drzewa i poszczególnych porównań, ale być może za wiele wymagam?

    ---

    Pytanie dodatkowe, korzystając z uprzejmości:

    x.subSet(1,10) wypisze posortowane liczby wszystkie z zakresu od (włącznie) 1 do (wyłącznie) 10. Jaką wartość musiałby przybrać "x" w wyrażeniu x.subSet(1,x) by wypisane zostały wszystkie cyfry z zakresu 1..10 w tym przykładzie? Zdaję sobie sprawę, że można użyć innego polecenia, ale wykorzystując subSet?

    ---

    Niestety, są to braki wynikające ze zbyt małej liczby godzin przeznaczonych na studiach dla studentów. Praktycznie rzecz biorąc drzewa, kolejki, listy, przerobione zostały jedynie teoretycznie na wykładzie, bez nawet 30min poświęconych temu na ćwiczeniach, stąd być może braki... Pomijam fakt innych przyzwyczajeń prof. od wykładów a innych od ćwiczeń, stąd np w praktyce nigdy nie używaliśmy zapisów jak poniżej (a dokładniej znaków wytłuszczonych):

    Cytat:
    ob2 = !(ob2%2!=0) ? ob2+=10 : ob2;

    0
  • #5 02 Wrz 2010 20:29
    McMonster
    Poziom 32  

    Wewnętrzna struktura TreeSet, którą jest drzewo czerwono-czarne, Cię w tym konkretnym przypadku nie interesuje (chyba, że pojawi się w innym miejscu na egzaminie ;)), istotne tutaj jest tylko to, że zbiór jest posortowany przy użyciu komparatora, który już wyżej koledzy opisali. Właściwie cały ten przykład opiera się na tym komparatorze, musisz tylko wiedzieć, jak jest używany.

    W przypadku podzbioru wystarczy x.subSet(1,11).

    Ten dziwny zapis to wyrażenie warunkowe, opisane choćby tutaj: http://naukajavy.pl/kurs-jezyka-java/89-wyrazenie-warunkowe

    0
  • Pomocny post
    #6 02 Wrz 2010 21:48
    pallid
    Poziom 20  

    McMonster napisał:
    W przypadku podzbioru wystarczy x.subSet(1,11).


    Otoz nie. Set.subSet() rowniez korzysta z komparatora, a wartosc 11 nadal bedzie ponizej zakresu liczb parzystych (dokladniej miedzy 9 a 2).
    Drugi argument powinien byc nie mniejszy niz 12 dla liczb parzystych lub nie mniejszy niz 21, dla nieparzystych (poniewaz: 21-10 > 10).

    0
  • #7 02 Wrz 2010 22:35
    Kamil Wolski
    Poziom 12  

    McMonster - dzięki bardzo. Taka już moja natura, że nawet jak teoretycznie wiem wszystko jak zrobić, dłubie temat dalej, często w nieskończoność i zawsze mi się wydaje że jeszcze czegoś nie wiem lub nie rozumiem ;).

    Pallid, czyli rozumiem by wypisać wszystkie posortowane liczby z zakresu 1..10 korzystając z tego komparatora, trzeba użyć subSet(1,21). W takim razie nie rozumiem, czemu przy ustawieniu subSet(1,10), program wypisuje ósemkę, która to po użyciu komparatora wynosi 8+10=18, więc ustawienie winno być minimum subSet(1,19)... innymi słowy, co w tej chwili motam?

    ---

    Właśnie sprawdziłem program w NetBeansie. Ciąg: [1, 3, 5, 7, 9, 2, 4, 6, 8, 10] wyświetla się już od parametru subSet(1,16)...

    0
  • Pomocny post
    #8 02 Wrz 2010 23:01
    McMonster
    Poziom 32  

    Komparator nie modyfikuje podanych wartości, bo to by było tak, że porównujesz liczby 2 i 3 pod kątem tego, która jest większa, wychodzi Ci, że 3 jest większe, ale po porównaniu zostają 12 i 3, co jest bez sensu. Komparator posługuje się metodą, a w Javie wszystkie parametry przekazywane są przez wartość, czyli te wszystkie dodawania w komapartorze modyfikują lokalną zmienną o o wartości początkowej takiej, jak porównywane elementy, a elementy faktycznie dodane do zbioru pozostają nienaruszone.

    Z działaniem subSet() to racja, nie pomyślałem o tym.

    0
  • Pomocny post
    #9 02 Wrz 2010 23:29
    pallid
    Poziom 20  

    Kamil Wolski napisał:
    Pallid, czyli rozumiem by wypisać wszystkie posortowane liczby z zakresu 1..10 korzystając z tego komparatora, trzeba użyć subSet(1,21).

    Zapoznaj sie dokladnie z algorytmem komparatora. Dla ulatwienia rozpisz go sobie na instrukcje if() {...}. Dodam tylko, ze nie liczy sie zwracany wynik, a tylko jego znak (wartosc dodatnia, ujemna lub zero).

    Kamil Wolski napisał:
    W takim razie nie rozumiem, czemu przy ustawieniu subSet(1,10), program wypisuje ósemkę, która to po użyciu komparatora wynosi 8+10=18, więc ustawienie winno być minimum subSet(1,19)... innymi słowy, co w tej chwili motam?


    Poniewaz 8 (8+10=18) jest nadal mniejsze od 10 (10+10=20), podobnie jak 19 (19=19). Dla komparatora najmniejsza calkowita liczba nieparzysta wieksza od 10 (10+10=20) jest 21, ale za to liczba parzysta to juz 12 (12+10 > 10+10).


    Kamil Wolski napisał:
    Właśnie sprawdziłem program w NetBeansie. Ciąg: [1, 3, 5, 7, 9, 2, 4, 6, 8, 10] wyświetla się już od parametru subSet(1,16)...


    Juz 12 wystarczy (patrz powyzej).

    0
  • #10 03 Wrz 2010 00:19
    Kamil Wolski
    Poziom 12  

    McMonster napisał:
    Komparator nie modyfikuje podanych wartości(...)


    Zdaję sobie z tego sprawę - skrót myślowy.

    Pallid, jasne i klarowne, czytając poprzednią wiadomość nie zaskoczyłem bo sprawdzałem w biegu. Masz rację. Super. Wygląda na to, że wiem wszystko co i jak ;). Jeszcze raz dziękuje za pomoc.

    0
  • #11 07 Paź 2010 15:14
    Kamil Wolski
    Poziom 12  

    Dziękuję wszystkim za pomoc, egzamin zaliczony ;).

    0