Autor Wątek: Problem z drzewem binarnym.  (Przeczytany 3359 razy)

Offline ASTROMAG

  • Użytkownik

# Listopad 04, 2007, 00:25:37
Witam, zacząłem pisać sobie klasę reprezentującą drzewo binarne. Niestety podczas testów okazało się, że czas potrzebny na dodanie dużej liczby elementów(np. 10000 elementów to ok. 5 sekund). Wyszukiwanie też jest powolne. W testach mój kod był znacznie wolniejszy od „System.Collections.Generic.Dictionary<>”. Nie wiem co robie źle, proszę o pomoc!

public class BinaryTree<K, V> where K : IComparable<K>
    {
        #region Zmienne
        // główny węzeł (korzeń) drzewa
        private BinaryTreeNode<K, V> root = null;
        // liczba węzłów
        private int nodeCount = 0;
        // węzeł drzewa wykorzystywany w czasie róznych operacji
        private BinaryTreeNode<K, V> binaryTreeNode = null;
        #endregion

        #region BinaryTree
        /// <summary>
        /// Klasa reprezentuje drzewo binarne.
        /// </summary>
        public BinaryTree()
        {
           
        }


Kod dodający klucz i wartość do drzewa:
public void Add(K key, V value)
{
    if (key != null)
    {
        if (root != null)
        {
            binaryTreeNode = root;

            while (true)
            {
                if (key.CompareTo(binaryTreeNode.GetNodeKey) > 0)
                {
                    if (binaryTreeNode.GetLeftNode == null)
                    {
                        binaryTreeNode.GetLeftNode = new BinaryTreeNode<K, V>(key, value);
                        nodeCount++;

                        break;
                    }
                    else
                    {
                        binaryTreeNode = binaryTreeNode.GetLeftNode;
                    }
                }
                else if (key.CompareTo(binaryTreeNode.GetNodeKey) < 0)
                {
                    if (binaryTreeNode.GetRightNode == null)
                    {
                        binaryTreeNode.GetRightNode = new BinaryTreeNode<K, V>(key, value);
                        nodeCount++;

                        break;
                    }
                    else
                    {
                        binaryTreeNode = binaryTreeNode.GetRightNode;
                    }
                }
                else
                {
                    throw new Exception("Key repeat.");
                }
            }
        }
        else
        {
            root = new BinaryTreeNode<K, V>(key, value);
            nodeCount++;
            //Console.WriteLine("root = {0}", root.GetNodeValue.ToString());
        }
    }
}

Kod wyszukujący wartość powiązaną z kluczem:
public V GetValue(K key)
{
    if (key != null && root != null)
    {
        binaryTreeNode = root;

        while (true)
        {
            if (binaryTreeNode == null)
            {
                throw new Exception("Key: '" + key.ToString() + "' not exist.");
            }
            else if (binaryTreeNode.GetNodeKey.CompareTo(key) == 0)
            {
                return binaryTreeNode.GetNodeValue;
            }
            else if (binaryTreeNode.GetNodeKey.CompareTo(key) < 0)
            {
                binaryTreeNode = binaryTreeNode.GetLeftNode;
            }
            else
            {
                binaryTreeNode = binaryTreeNode.GetRightNode;
            }
        }
    }
    else
    {
        throw new Exception("Key '" + key.ToString() + "' not exist.");
    }
}

private class BinaryTreeNode<K_, V_> where K_ : IComparable<K_>
        {
            #region Zmienne
            // klucz węzła
            private K_ nodeKeyValue;
            // wartość węzeła
            private V_ nodeValue;
            // lewy węzeł drzewa
            private BinaryTreeNode<K_, V_> leftNode = null;
            // prawy węzeł drzewa
            private BinaryTreeNode<K_, V_> rightNode = null;
 
            public BinaryTreeNode(K_ key, V_ value)
            {
                nodeKeyValue = key;
                nodeValue = value;
            }

            public V_ GetNodeValue
            {
                get
                {
                    return nodeValue;
                }
            }

            public K_ GetNodeKey
            {
                get
                {
                    return nodeKeyValue;
                }
            }

            public BinaryTreeNode<K_, V_> GetLeftNode
            {
                get
                {
                    return leftNode;
                }
                set
                {
                    leftNode = value;
                }
            }

            public BinaryTreeNode<K_, V_> GetRightNode
            {
                get
                {
                    return rightNode;
                }
                set
                {
                    rightNode = value;
                }
            }
        }

Z góry dziękuję wszystkim za pomoc!!

ASTROMAG

Offline Mr. Spam

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

Offline Kot

  • Użytkownik

# Listopad 04, 2007, 01:14:38
Kodu nie przejrzałem, ale w porównaniach weź poprawkę na to, że drzewo binarne nie jest w żaden sposób równoważone i w pesymistycznym przypadku przeradza się w listę jednokierunkową, a taki Generic.Dictionary<> jest pewnie zorganizowany na drzewie czerwono-czarnym albo innym wydajnym algorytmie tego typu.

RageX

  • Gość
# Listopad 04, 2007, 01:34:52
Słownika nie porównuj z drzewem binarnym... Taki słownik to zwykła lista z dodatkowym kluczem oprócz int'a.
W zasadzie to samo można osiągnąć obudowując w banalny sposób listę o dowolną ilość kluczy.
Ale drzewo działa inaczej... np. zawsze tworzenie drzewa będzie wolniejsze, a wyszukiwanie - jeżeli drzewo jest posortowane - szybsze...
Ale co chcesz osiągnąć? To może i pomóc będzie łatwiej.

Offline Kot

  • Użytkownik

# Listopad 04, 2007, 01:59:15
RageX, nikt rozsądny nie zaimplementuje słownika jako zwykłej listy. A już na pewno nie w takiej klasy bibliotece, jaką chce być .Net Framework.
Idąc tym tropem - pierwszy wynik w Google dla Generic.Dictionary:
Cytuj
Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.
Czyli jest jeszcze lepiej niż wcześniej przypuszczałem ;).

Cytat: RageX
a wyszukiwanie - jeżeli drzewo jest posortowane - szybsze
Z tego co pamiętam wyszukiwanie w drzewie binarnym to w średnim przypadku O(lg n), a w pesymistycznym O(n).
Raczej nie ma co tego porównywać do O(1) dla tablicy mieszającej.


Natomiast do samego problemu autora tematu: zależy jak dodajesz te wartości do swojego drzewa w tym teście, jeżeli masz
for(int i = 0; i < 10000; i++)
  tree.Add(i);
to to na pewno będzie dramatycznie wolne.

Jeżeli koniecznie chcesz dodawać tak wiele elementów do drzewa, to zainteresuj się drzewami zrównoważonymi: drzewa czerwono-czarne, drzewa AVL.
« Ostatnia zmiana: Listopad 04, 2007, 02:03:34 wysłana przez Kot »

RageX

  • Gość
# Listopad 04, 2007, 02:34:45
Nie rozumiem twojej uwagi...
Użyłem porównania do listy, aby ASTROMAGowi uzmysłowić diametralną logiczną różnicę między drzewem binarnym, a słownikiem... nie zamierzam się z tobą wdawać w dyskusję na temat hashtable'i.
EDIT: i chyba w optymistycznym przypadku O(n)... jest to funkjca liniowa, szybsza niż logartymiczna, ale to chyba twoja literówka :)

EDIT2: No i muszę ci przyznać rację. Słownik będzie szybszy zawsze (hashtable vs hierarchia) sorr ... :)

http://msdn2.microsoft.com/en-us/library/ms379571(VS.80).aspx#datastructures20_2_topic6
http://creators.xna.com/files/folders/7155/download.aspx

LAST EDIT @ down: hehe, jaką tam agresją. Poczułem się zaatakowany - fakt, ale żebym ja ciebie atakował? Jesli tak, to jeszcze raz przepraszam. :)
A sam będę ostrożniejszy (szczególnie w godzinach nocnych)...
Te pomoce to nie dla ciebie przecież... To nie atak... :)
« Ostatnia zmiana: Listopad 04, 2007, 02:58:19 wysłana przez RageX »

Offline Kot

  • Użytkownik

# Listopad 04, 2007, 02:51:20
RageX, dziękuję za linki, ale ja wiem jak działa tablica mieszająca :).

W mojej uwadze chodziło o to, że w swoim poście.. hm.. niechlujnie porównałeś słownik do listy. Słownik to przede wszystkim tablica haszująca, a występujące tam listy są tylko jednym z możliwych sposobów rozwiązania kolizji kluczy. Nie odwrotnie.
Poza tym nie mogłem nie zwrócić uwagi na błędne twierdzenie, że drzewo binarne jest szybsze w wyszukiwaniu od słownika.

Cytat: RageX
Użyłem porównania do listy, aby ASTROMAGowi uzmysłowić diametralną logiczną różnicę między drzewem binarnym, a słownikiem
No właśnie, różnica jest diametralna, ale porównanie do listy jest co najmniej niezręczne ;).
Pojęcia: "listy" i "dostęp swobodny" powinny się kojarzyć z "no-way" a tymczasem na pewno tak nie jest w przypadku słownika.

Cytat: RageX
nie zamierzam się z tobą wdawać w dyskusję na temat hashtable'i.
Nie rozumiem Cię - napisałeś błędną tezę, ja ją sprostowałem, a Ty reagujesz do mnie z agresją?


edit do edita ;):
Cytat: RageX
i chyba w optymistycznym przypadku O(n)... jest to funkjca liniowa, szybsza niż logartymiczna, ale to chyba twoja literówka Smiley
Yyyy chwila, chwila, co Ty mi tu wmawiasz? ;)
Złożoność logarytmiczna jest o wiele lepsza od liniowej, rośnie mniej więcej tak: http://upload.wikimedia.org/wikipedia/en/thumb/e/ea/Log.svg/256px-Log.svg.png
« Ostatnia zmiana: Listopad 04, 2007, 02:58:25 wysłana przez Kot »

Offline ASTROMAG

  • Użytkownik

# Listopad 04, 2007, 12:19:28
Chciałem napisać klasę która przechowywałaby dużą ilość danych powiązanych kluczami, szybko je wyszukiwała i najlepiej jeszcze żeby je szybko usuwała(choć nie koniecznie). Czy jak udoskonalę swoją klasę o algorytm AVL będzie ona szybsza niż „System.Collections.Generic.Dictionary<>”??, a może znacie jakiś szybszy algorytm?.

Offline frea

  • Użytkownik

# Listopad 04, 2007, 13:20:52
Poczytaj ksiazke Cormena, tam jest wystarczajaco duzo na "podstawowe" potrzeby :). No i przy okazji sporo sie nauczysz.

Offline zephyr

  • Użytkownik

# Listopad 04, 2007, 16:09:16
Jeśli System.Collections.Generic.Dictionary jest na dobrze napisanej tablicy mieszającej to trudno będzie coś więcej wycisnąć, chyba że bardzo zależy ci na optymalizacji na poziomie stałej a nie rzędu funkcji.

[edit:]
Może da się usprawnić jego działanie podając mu szacunkowe parametry dla tej tablicy mieszającej, ale tu się raczej zaoszczędzi na pamięci, a nie czasie działania i nie jestem pewien czy w ogóle.
« Ostatnia zmiana: Listopad 04, 2007, 16:11:18 wysłana przez zephyr »

Offline ASTROMAG

  • Użytkownik

# Listopad 04, 2007, 17:40:17
Oki, dziękuje wszystkim za pomoc!!!! :)