Autor Wątek: Problem z SortedDictionary  (Przeczytany 2333 razy)

Offline amd

  • Użytkownik

# Luty 24, 2010, 20:45:25
Mam taki problem
SortedDictionary<string, int> sortedDict = new SortedDictionary<string, int>();
 sortedDict["Jeden"] = 1;
 sortedDict["Dwa"] = 2;
 sortedDict["Trzy"] = 3;
 foreach (KeyValuePair<string, int> item in sortedDict)
 {
     Console.Write("{0} ", item); //aktualny wynik sortowania  [Dwa, 2] [Jeden, 1] [Trzy, 3]
 }

Mając dany słownik SortedDictionary<TKey, TValue>()

Jak posortować taki słownik po TValue
Aby wynik powyższego kodu był taki
  [Jeden, 1] [Dwa, 2] [Trzy, 3]
Czy w ogóle jest taka możliwość?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline raver

  • Użytkownik
    • Moja strona domowa.

# Luty 24, 2010, 21:01:14
SortedDictionary<int, string> sortedDict = new SortedDictionary<int, string>();
 sortedDict[1] = "Jeden";
 sortedDict[2] = "Dwa";
 sortedDict[3] = "Trzy";
 foreach (KeyValuePair<int, string> item in sortedDict)
 {
     Console.Write("{0} ", item);
 }

Może być?

Offline krajek

  • Użytkownik

# Luty 24, 2010, 21:03:55
Nie znam się dokładnie, ale podejrzewam, że nie ma możliwości sortować po TValue. Najlepiej po prostu zamień TKey i TValue :
[...]
sortedDict[1] = "Jeden";
[...]

Offline amd

  • Użytkownik

# Luty 24, 2010, 21:19:30
zamiana TKey z TValue w moim przypadku nie jest rozwiązaniem
gdyż ten kod wyżej to po prostu najprostszy możliwy kod z użyciem słownika
w moim realnym kodzie używam
SortedDictionary<int, MyClass> sortedDict

i zamiana tego na SortedDictionary< MyClass,int> sortedDict
nic mi nie da chyba że potem można się do takiej listy jakoś odwołać według TValue
gdyż ja potrzebuje mieć możliwość odwołania się do konkretnego elementu

Offline krajek

  • Użytkownik

# Luty 24, 2010, 21:46:36
Nie mówisz zbyt jasno i nie jestem pewien czy wiem o co Ci dokładnie chodzi. Mimo to spróbuję zgadnąć i pomóc :).
Trzymaj sobie dane w słowniku<int,MyClass>, a w momencie kiedy potrzebne Ci posortowanie po MyClass po prostu utwórz drugi słownik<MyClass,int>, bądź przepisz dane do innej tablicy i tam posortuj. Możesz też równocześnie utrzymywać oba słowniki.

Offline nilphilus

  • Użytkownik
    • wordpress

# Luty 24, 2010, 21:56:56
            Dictionary<string, int> sortedDict = new Dictionary<string, int>();
            sortedDict["Jeden"] = 1;
            sortedDict["Dwa"] = 2;
            sortedDict["Trzy"] = 3;

            var dict = from s in sortedDict orderby s.Value select s;

            foreach (KeyValuePair<string, int> item in dict)
            {
                Console.Write("{0} ", item); //aktualny wynik sortowania  [Dwa, 2] [Jeden, 1] [Trzy, 3]
            }
           

Ale możesz również napisać sobie metodę sortującą wg. Value

Offline revo

  • Użytkownik

# Luty 24, 2010, 21:59:47
SortedDictionary jest po kluczu. Jeżeli chcesz posortować po wartości, zawsze możesz zrobić to tak:

static void Main(string[] args)
{
    SortedDictionary<string, int> sortedDict = new SortedDictionary<string, int>();
   
    sortedDict["Jeden"] = 1;
    sortedDict["Dwa"] = 2;
    sortedDict["Trzy"] = 3;

    foreach (var item in sortedDict.OrderBy(i => i.Value))
    {
        Console.Write("{0} ", item);
    }
}

// edit: nilphilus byłeś szybszy z linq ;) Ja osobiście wolę formę której użyłem :P

Offline nilphilus

  • Użytkownik
    • wordpress

# Luty 24, 2010, 23:15:06
@revo, faktycznie ładniejsza, nawet nie pomyślałem, że tak można, więc dzięki ;-)

próbowałem jeszcze znaleźć funkcję sortującą z jakimś delegatem do porównywania, ale coś mnie nie wyszło ;-)

Offline amd

  • Użytkownik

# Luty 24, 2010, 23:44:38
SortedDictionary jest po kluczu. Jeżeli chcesz posortować po wartości, zawsze możesz zrobić to tak:

static void Main(string[] args)
{
    SortedDictionary<string, int> sortedDict = new SortedDictionary<string, int>();
   
    sortedDict["Jeden"] = 1;
    sortedDict["Dwa"] = 2;
    sortedDict["Trzy"] = 3;

    foreach (var item in sortedDict.OrderBy(i => i.Value))
    {
        Console.Write("{0} ", item);
    }
}

// edit: nilphilus byłeś szybszy z linq ;) Ja osobiście wolę formę której użyłem :P

to rozwiązanie bardzo mi się podoba
tylko że mój SortedDictionary nie ma metody OrderBy?
co do linq to również znalazłem takie rozwiązanie ale odrzuciłem je gdyż zakładam że takie zapytanie to dodatkowy narzut przy złożoności sortowania.(może się mylę)
A ja w moim algorytmie potrzebuje złożoności log(n)

Offline revo

  • Użytkownik

# Luty 25, 2010, 00:02:28
Moje rozwiązanie to też LINQ, tylko inaczej zapisane. Której wersji C# używasz? LINQ powinno być dostępne od 3.5 (2008).

Co do złożoności -- w pętli przechodzisz przez każdy element raz, więc poniżej O(n) nie zejdziesz, jakkolwiek byś się nie starał. Napisz może co chcesz osiągnąć to wtedy pomyśli się nad lepszym rozwiązaniem :)

Offline nilphilus

  • Użytkownik
    • wordpress

# Luty 25, 2010, 00:04:04
W zasadzie to nie potrzebnie masz SortedDictionary, bo tam się sortuje wg. klucza. Po co robić to dwa razy? ;->   Jak potrzebujesz takie rozwiązanie to tak jak napisałem, możesz stworzyć własną metodę sortującą ;-)  Ja takie coś zacząłem robić:
   public static class Extension
    {
        public static T[] BubbleSort<T>(this T[] tab, Comparison<T> cmp)
        {
            //klonujemy sobie tablicę :-)
            T[] Tab = (T[])(tab.Clone());
           
            //sortujemy
            for(int i=0;i<Tab.Length-2;i++){
                for(int j=Tab.Length-1; j>=i+1;j--){
                    if(cmp(Tab[j-1],Tab[j]) > 0) {
                        var tmp = Tab[j - 1];
                        Tab[j - 1] = Tab[j];
                        Tab[j] = tmp;
                    }
                }
            }

            return Tab;
        }
}

Pozostanie Ci tylko napisanie funkcji która pobiera dwa elementy ze słownika i zwraca int ;-)
hmm.. albo
dict.BubbleSort( (a,b) => (a.Value - b.Value ));   //chyba dobrze piszę :D

edit:
dobra, trochę źle:

            var dict = sortedDict.ToArray().BubbleSort((a, b) => (a.Value - b.Value));
« Ostatnia zmiana: Luty 25, 2010, 00:06:58 wysłana przez nilphilus »

Offline revo

  • Użytkownik

# Luty 25, 2010, 00:20:44
Bubble sort? 0_o

Array.Sort -- z dokumentacji wygląda na to, że jest to QuickSort lub coś podobnego ;)

Offline amd

  • Użytkownik

# Luty 25, 2010, 00:28:12
faktycznie OrderBy pojawił się po dodaniu bibliotek LINQ
co do zadania to
chodzi o algorytm Johnsona do szeregowanie zadań.
a dokładniej o jak największą jego optymalizacje.
W związku z tym że w tym algorytmie jest p-sortowań w zależności od ilości procesorów pomyślałem że nada się tutaj struktura słownika już posortowanego.

oczywiście wiem że złożoność przejścia i wypisania elementów to już jest O(n)
ale nie chciałbym dorzucać dodatkowego obciążenia

bo z tego co rozumiem SortedDictionary działa tak że wkładając tam elementy są one bezpośrednio sortowane
więc nie chciałbym dodatkowego narzutu w postaci zapytania LINQ które (prawdopodobnie) sortuje sobie samo cała strukturę jeszcze raz


Offline nilphilus

  • Użytkownik
    • wordpress

# Luty 25, 2010, 00:28:27
Bubble sort? 0_o

Array.Sort -- z dokumentacji wygląda na to, że jest to QuickSort lub coś podobnego ;)

To przykład ;-) Po prostu w ramach sprawdzenie wpierw poszło banalne ;-p<br/><br/>
Jakoś wątpię żeby Sorted miało złożoność O(n) ;-)