[C++] Za długie usuwanie największego elementu z maksymalnego kopca binarnego
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

[C++] Za długie usuwanie największego elementu z maksymalnego kopca binarnego

AutorWiadomość
Temat założony przez niniejszego użytkownika
[C++] Za długie usuwanie największego elementu z maksymalnego kopca binarnego
» 2019-11-27 18:22:05
Cześć! Implementuję kopiec binarny, w którym największa wartość jest korzeniem.
Program działa, ale kiedy powtarzam operację usuwania z kopca największego elementu aż kopiec nie będzie pusty trwa to zdecydowanie za długo, dłużej niż zbudowanie kopca od 0. Kopiec wypełniam losowymi wartościami, ale nie wiem czy ma to jakieś znaczenie.
Zaimplementowany algorytm wygląda w porządku, więc nie wiem co może być powodem tak wolnego działania.
Mój kod:
C/C++
#include "pch.h"
#include <iostream>
#include "time.h"
#include <random>
#include <string>
#include <functional>
#include <vector>
using namespace std;
template < typename T >
class BinaryHeap;

template < typename T >
class BinaryHeap
{
    vector < T > heap;
    int getParent( int childInd )
    {
        if( heap.size() == 0 )
        {
            return - 1;
        }
        //int parent = 0;
        int parent = floor(( childInd - 1 ) / 2 );
        if( heap.size() <= childInd )
        {
            cout << "Nie ma takiego elementu!" << endl;
            return - 1;
        }
        else
             return parent;
       
    }
    int leftChild( int parentInd )
    {
        int left = floor( 2 * parentInd + 1 );
        if( heap.size() <= parentInd )
        {
            cout << "Ten element nie ma dzieci!" << endl;
            return - 1;
        }
        else
             return left;
       
    }
    int rightChild( int parentInd )
    {
        int right =( 2 * parentInd + 2 );
        if( heap.size() <= parentInd )
        {
            cout << "Ten element nie ma dzieci!" << endl;
            return - 1;
        }
        else
             return right;
       
    }
    void heapifydown( int index )
    {
        int left = leftChild( index );
        int right = rightChild( index );
        int largest = index;
        if( heap.size() > left && heap[ left ] > heap[ index ] )
        {
            largest = left;
        }
        if( heap.size() > right && heap[ right ] > heap[ largest ] )
        {
            largest = right;
        }
        if( largest != index )
        {
            int temp = heap[ index ];
            heap[ index ] = heap[ largest ];
            heap[ largest ] = temp;
            heapifydown( largest );
        }
    }
    void heapifyup( int index )
    {
        int p = getParent( index );
        if( heap.size() > index && heap[ p ] < heap[ index ] )
        {
            int temp = heap[ index ];
            heap[ index ] = heap[ p ];
            heap[ p ] = temp;
            heapifyup( p );
        }
    }
   
public:
    BinaryHeap() { };
    ~BinaryHeap()
    {
        heap.clear();
    }
    void addElement( T el )
    {
        heap.push_back( el );
        int index = heap.size() - 1;
        heapifyup( index );
    }
    void printHeap()
    {
        if( heap.size() == 0 )
        {
            cout << "Pusty kopiec!" << endl;
            return;
        }
        for( int i = 0; i < heap.size(); i++ )
        {
           
            cout << heap[ i ] << endl;
        }
    }
    T delMax()
    {
        if( heap.size() == 0 )
        {
            return - 1;
        }
        T temp = heap[ 0 ];
        T temp2 = heap[ 0 ];
        heap[ 0 ] = heap.at( heap.size() - 1 );
        heap.pop_back();
        //T parent = 0;
        //T child = 2 * parent + 2;
        heapifydown( 0 );
        return temp;
        //delete &temp;
    }
    void clearHeap()
    {
        for( int i = heap.size(); i > 0; --i )
        {
            heap.pop_back();
        }
    }
    void print()
    {
        if( heap.size() == 0 )
        {
            cout << "Pusty kopiec!" << endl;
            return;
        }
        cout << "Rozmiar: " << heap.size() << endl;
        cout << " Korzen: " << heap[ 0 ] << endl;
        cout << "L. dziecko: " << heap[ 1 ] << endl;
        cout << "P. dziecko: " << heap[ 2 ] << endl;
        cout << "3 ostatnie elementy: " << heap[ heap.size() - 3 ] <<
        " " << heap[ heap.size() - 2 ] <<
        " " << heap[ heap.size() - 1 ] << endl;
    }
};
int randomInt()
{
    static default_random_engine generator { 10 };
    static uniform_int_distribution < int > rozklad { 0, 11000000 };
    static function < int() > los { bind( rozklad, generator ) };
    int l = los();
    return l;
}
int main()
{
    BinaryHeap < int >* bh = new BinaryHeap < int >();
    const int MAX_ORDER = 7; // maksymalny rzad wielkosci dodawanych danych
    for( int i = 1; i <= MAX_ORDER; i++ )
    {
        const int n = pow( 10, i );
        clock_t start1 = clock();
        for( int i = 0; i < n; i++ )
        {
            int el = randomInt();
            bh->addElement( el );
        }
        clock_t stop1 = clock();
        double adding_time =( stop1 - start1 ) /( double ) CLOCKS_PER_SEC;
        cout << "Czas dodawania: " << adding_time << "s" << endl;
        bh->print();
        clock_t start2 = clock();
        for( int j = 0; j < n; j++ )
        {
            bh->delMax();
            //cout << "WyciagniEty: "<<bh->delMax()<<endl;
            //delete &out;
        }
        clock_t stop2 = clock();
        double polling_time =( stop2 - start2 ) /( double ) CLOCKS_PER_SEC;
        cout << "Czas usuwania: " << polling_time << "s" << endl;
        bh->print();
        bh->clearHeap();
    }
    delete bh;
    return 0;
}
P-175671
» 2019-11-27 19:05:25
C/C++
int left = floor( 2 * parentInd + 1 );
if( heap.size() <= parentInd )
{
    cout << "Ten element nie ma dzieci!" << endl;
    return - 1;
}
Prędzej, "ten parent nie istnieje". I co to w ogóle za bzdura z tym floor()? Wszystkie użycia tej funkcji są błędne, wywal je. Arytmetyka na liczbach całkowitych jest zawsze całkowita i, w przeciwieństwie do implikowanej przez floor() arytmetyki zmiennoprzecinkowej, jest dokładna. Tym zaokrągleniem nie naprawiasz niczego, a dla odpowiednio dużych kopców to nawet nie będzie działać poprawnie.

C/C++
heap[ 0 ] = heap.at( heap.size() - 1 );
Czemu użyłeś at() tylko w jednym miejscu, gdzie i tak sam już poprawnie sprawdzasz dostęp do tablicy?
P-175675
Temat założony przez niniejszego użytkownika
» 2019-11-27 19:42:14
Racja, mój błąd jeśli chodzi o rodzica i dzieci. Floora użyłem z tego powodu, że kiedy chcę znaleźć indeks rodzica elementu i to jest indeks będzie pod numerem (i-1)/2 zaogkrąglone w dół. Jeżeli szukam np. rodzica elementu 4 to bez tego zaokrąglenia w dół wyjdzie mi, że rodzic jest pod indeksem 1,5. Chyba, że kompilator jakoś to i tak ogarnia.
Posłuchałem się jednak rady i usunąłem z kodu wszystkie floory. Czas usunięcia wszystkich elementów spadł o około 1 sekundę. Ten .at to wynik mojej wesołej twórczości szukając optymalnego rozwiązania. Zmieniłem na
heap[ 0 ] = heap.back();
.
P-175677
» 2019-11-27 21:24:44
Operacje na typach całkowitoliczbowych zawsze mają całkowity wynik. Nigdy żadnych ułamków.

Losowe wartości sprawiają, że wybór między lewym a prawym potomkiem jest nieprzewidywalny. Dla MAX_ORDER u mnie jest to 0.84s gdy wypełniam kontener kolejnymi liczbami i 2.76s dla losowych liczb. Do tego struktura kodu zawiera sporo powtórzeń. Przykładowo prawy potomek ma indeks większy od lewego, więc jeśli lewy jest poza zakresem, to prawy też.
P-175684
Temat założony przez niniejszego użytkownika
» 2019-11-27 21:30:08
W sumie zrobiłem mały research i stwierdziłem, że byłem w błędzie myśląc, że "usuwanie do zera" powinno się wykonywać tak szybko.
P-175685
« 1 »
 Strona 1 z 1