[C++] Obiekty - Problem Optymalizacyjny
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

[C++] Obiekty - Problem Optymalizacyjny

AutorWiadomość
Temat założony przez niniejszego użytkownika
[C++] Obiekty - Problem Optymalizacyjny
» 2018-05-26 04:44:28


mój problem polega na tym, iż program zasypuje mi całą pamięć (16 GB!! :O).

pierwotnie była to czysta wersja BruteForce i przechowywałem cały "Zbiór Kombinacji" rozmieszczeń elementów z których każdy miał wagę i wartość.
następnie pozbyłem się tego zbioru na rzecz dwóch kobminacji (nowej oraz optymalnej) uzyskując o jeden wynik więcej.
dorzuciłem destruktory / brak różnicy.
podstawiłem NULL zamiast niszczyć obiekty / brak różnicy...
dopisałem funkcję niszczącą "PodElementy" w Kombinacji / brak różnicy..

czego mógłbym jeszcze spróbować ? sprawa jest o tyle ważna, że muszę przeprowadzić badanie na ponad 100-1000 kontenerach i ładowności rzędu 100-10000.
jest to całkiem niezła ilość operacji gdy się zszereguje te silniopodobne wyrazy... :-/


C/C++
void BestBruteForce( int Ladownosc, int nKONTENEROW )
{
    int start, end;
    start = clock();
    Kombinacja * BEST, * NEWBIE;
    BEST = new Kombinacja();
   
    for( int unsigned i =( 1 << nKONTENEROW ); --i; )
    {
       
        NEWBIE = new Kombinacja();
       
        for( int unsigned k = 0; k < nKONTENEROW && NEWBIE->CiezarKombinacji() <= Ladownosc; k++ )
        {
            if(( i >> k ) & 1 ) NEWBIE->AddElement( k );
           
        }
       
        if( NEWBIE->CiezarKombinacji() <= Ladownosc && BEST->WartoscKombinacji() < NEWBIE->WartoscKombinacji() )
        {
            delete BEST;
            BEST = new Kombinacja();
            * BEST = * NEWBIE;
            //BEST->WriteWiC();
            //cout<<endl<<endl;
        };
       
        delete NEWBIE;
    }
   
   
   
   
   
    end = clock() - start;
    WynikBF = new Wynik( end, BEST->CiezarKombinacji(), BEST->WartoscKombinacji() );
    delete BEST;
   
   
}
P-171254
» 2018-05-26 10:24:40
Po pierwsze: std::unique_ptr twoim przyjacielem.

Po drugie:
C/C++
delete BEST;
BEST = new Kombinacja();
* BEST = * NEWBIE;
Dlaczego nie tak:
C/C++
delete BEST;
BEST = NEWBIE;
NEWBIE = nullptr;
?

Jeśli iteracji jest dużo, pozbyłbym się tworzenia na stercie.

Po trzecie: ten kod raczej nie powoduje tak dużego zużycia. Nie wiadomo, co się dzieje w Kombinacja.
P-171256
» 2018-05-26 11:27:48
sprawa jest o tyle ważna, że muszę przeprowadzić badanie na ponad 100-1000 kontenerach
Ten algorytm nie nadaje się do takich danych.
C/C++
for( int unsigned i =( 1 << nKONTENEROW ); --i; )
Te przesunięcie będzie miało niezdefiniowane zachowanie, gdy przekroczysz rozmiar inta. A nawet gdyby było poprawne, to powodzenia czekając na zakończenie 21000 iteracji.
P-171257
Temat założony przez niniejszego użytkownika
» 2018-05-28 13:26:19
jak można by więc inaczej dobrać się do wszystkich niepowtarzających się kombinacji mających co najmniej jedną daną?

dla zbioru {1,2,3}
będą to :
{1} {2} {3} {1,2} {1,3} {2,3}
P-171284
Temat założony przez niniejszego użytkownika
» 2018-05-28 13:35:40
Dorzucę cały kod, uwaga 450 linii! (nie zwracajcie uwagi na nic poza samym algorytmem BruteForce oraz obiektami do których się odnosi).

C/C++
#include <iostream>
#include <cstring>
#include <time.h>
#include <windows.h>
#include <conio.h>
using namespace std;



int KontenerCiezar[ 100 ];
int KontenerWartosc[ 100 ];
int WartosciWazone[ 100 ];
int WartosciWazoneINDEX[ 100 ];

class Wynik;
class Element;
class Kombinacja;
class ZbiorKombinacji;

void kolor( int kk );
void nadpis( const int xxxvv, const int yyyvv );
int max( int a, int b );
void Heapify( int heap_size, int i );
void buduj_kopiec( int HeapSize );
INT64 HS( int size );
void generuj_zbior( int nKONTENEROW, int WartoscMIN, int WartoscMAX, int CiezarMIN, int CiezarMAX );
void BestDynamo( int Ladownosc, int nKONTENEROW );
void BestBruteForce( int Ladownosc, int nKONTENEROW );
void BestAlgZachlanny( int Ladownosc, int nKONTENEROW );
void WykonajWartosciWazone( int nKONTENEROW );
int zastap_element( int * zastepowany, int * tymzastapiony );
void podmien_elementy( int * x, int * y );
void przeprowadz_proby( int nKONTENEROW, int LADOWNOSC, int WartoscMIN, int WartoscMAX, int CiezarMIN, int CiezarMAX );

Element * WskElement;
Kombinacja * WskKombinacja;
Wynik * WynikBF, * WynikAlgZach, * WynikAlgDyn;



class Wynik
{
public:
    int CZAS, CIEZAR, WARTOSC;
   
    Wynik( int czas, int ciezar, int wartosc )
    {
        CZAS = czas;
        CIEZAR = ciezar;
        WARTOSC = wartosc;
    };
   
    ~Wynik()
    {
    };
};

class Element
{
public:
    int Value;
    Element * NEXT;
    Element * PREV;
   
    Element( int Val, Element * prv )
    {
        Value = Val;
        PREV = prv;
        NEXT = NULL;
    };
   
    ~Element()
    {
    };
};

class Kombinacja
{
public:
    Element * FIRST;
    Element * LAST;
    Element * NEWBIE;
    Element * CURRENT;
   
    int CIEZAR;
    int WARTOSC;
   
    Kombinacja()
    {
        FIRST = NULL;
        LAST = NULL;
        CIEZAR = 0;
        WARTOSC = 0;
    };
   
    ~Kombinacja()
    {
    };
   
    void AddElement( int Value )
    {
        if( FIRST == NULL )
        {
            FIRST = new Element( Value, FIRST );
            LAST = FIRST;
            CIEZAR += KontenerCiezar[ Value ];
            WARTOSC += KontenerWartosc[ Value ];
        } else
        {
            NEWBIE = new Element( Value, LAST );
            LAST->NEXT = NEWBIE;
            LAST = NEWBIE;
        };
    };
   
    void WriteAll()
    {
        CURRENT = FIRST;
        while( CURRENT != NULL )
        {
            cout << CURRENT->Value << " ";
            CURRENT = CURRENT->NEXT;
        }
       
        cout << endl;
    };
   
    void WriteWiC()
    {
        CURRENT = FIRST;
        cout << "Ciezar Wartosc" << endl;
        while( CURRENT != NULL )
        {
            cout << KontenerCiezar[ CURRENT->Value ] << " " << KontenerWartosc[ CURRENT->Value ] << endl;
            CURRENT = CURRENT->NEXT;
        }
       
        cout << endl;
    };
   
    int WartoscKombinacji()
    {
        return WARTOSC;
    };
   
    int CiezarKombinacji()
    {
        return CIEZAR;
    };
};

void kolor( int kk )
{
    SetConsoleTextAttribute( GetStdHandle( STD_OUTPUT_HANDLE ), kk );
}

void nadpis( const int xxxvv, const int yyyvv )
{
    HANDLE hCon = GetStdHandle( STD_OUTPUT_HANDLE );
    COORD coord = { xxxvv, yyyvv };
    SetConsoleCursorPosition( hCon, coord );
}

int max( int a, int b )
{
    if( a > b )
         return a;
    else
         return b;
   
}

void Heapify( int heap_size, int i )
{
   
    int l = 2 * i;
    int r = 2 * i + 1;
    int max = i;
    if( l < heap_size && WartosciWazone[ l ] > WartosciWazone[ max ] )
         max = l;
   
    if( r < heap_size && WartosciWazone[ r ] > WartosciWazone[ max ] )
         max = r;
   
    if( max != i )
    {
        podmien_elementy( & WartosciWazone[ max ], & WartosciWazone[ i ] );
        podmien_elementy( & WartosciWazoneINDEX[ max ], & WartosciWazoneINDEX[ i ] );
        Heapify( heap_size, max );
    }
}

void buduj_kopiec( int HeapSize )
{
    for( int i = HeapSize / 2; i >= 0; i-- )
         Heapify( HeapSize, i );
   
}

INT64 HS( int size )
{
    INT64 start, end;
    int n = size;
   
    /*
                            for(int i=0;i<size;i++)
                                cout<<WartosciWazone[i]<<" ";
                            cout<<endl;
                            for(int i=0;i<size;i++)
                                cout<<WartosciWazoneINDEX[i]<<" ";
                            cout<<endl;
                            getch();
                        */
   
    start = clock();
   
    buduj_kopiec( n );
    for( int i = n - 1; i >= 0; i-- )
    {
        podmien_elementy( & WartosciWazone[ i ], & WartosciWazone[ 0 ] );
        podmien_elementy( & WartosciWazoneINDEX[ i ], & WartosciWazoneINDEX[ 0 ] );
        n--;
        Heapify( n, 0 );
    }
    /*
                            for(int i=0;i<size;i++)
                                cout<<WartosciWazone[i]<<" ";
                            cout<<endl;
                            for(int i=0;i<size;i++)
                                cout<<WartosciWazoneINDEX[i]<<" ";
                            cout<<endl;
                            getch();
                        */
    end = 1000 *( clock() - start ) / CLOCKS_PER_SEC;
    return( end );
}



void generuj_zbior( int nKONTENEROW, int WartoscMIN, int WartoscMAX, int CiezarMIN, int CiezarMAX )
{
    //cout<<"Ciezar|Wartosc"<<endl;
    for( int i = 0; i < nKONTENEROW; i++ )
    {
        if( CiezarMAX - CiezarMIN != 0 )
             KontenerCiezar[ i ] =( rand() %( CiezarMAX - CiezarMIN + 1 ) ) + CiezarMIN;
        else KontenerCiezar[ i ] = CiezarMAX;
       
        if( WartoscMAX - WartoscMIN != 0 )
             KontenerWartosc[ i ] =( rand() %( WartoscMAX - WartoscMIN + 1 ) ) + WartoscMIN;
        else KontenerWartosc[ i ] = WartoscMAX;
       
        //cout<<KontenerCiezar[i]<<" "<<KontenerWartosc[i]<<endl;
       
    }
   
}

void BestDynamo( int Ladownosc, int nKONTENEROW )
{
   
    int start, end;
    start = clock();
    int ** tablica = new int *[ nKONTENEROW + 1 ];
    for( int i = 0; i <= nKONTENEROW; i++ )
         tablica[ i ] = new int[ Ladownosc + 1 ];
   
    for( int i = 0; i <= nKONTENEROW; i++ )
    {
       
        for( int l = 0; l <= Ladownosc; l++ )
        {
            if( i == 0 ) tablica[ i ][ l ] = 0;
            else if( l == 0 ) tablica[ i ][ l ] = 0;
            else if( l < KontenerCiezar[ i - 1 ] ) tablica[ i ][ l ] = tablica[ i - 1 ][ l ];
            else tablica[ i ][ l ] = max( tablica[ i - 1 ][ l - KontenerCiezar[ i - 1 ] ] + KontenerWartosc[ i - 1 ], tablica[ i - 1 ][ l ] );
           
            /*
            cout<<tablica[i][l]<<" ";
            getch();
            */
        }
       
        //cout<<endl;
    }
   
    for( int i = 0; i <= nKONTENEROW; i++ )
         delete[] tablica[ i ];
   
    delete[] tablica;
   
    end = clock() - start;
    WynikAlgDyn = new Wynik( end, 0, tablica[ nKONTENEROW ][ Ladownosc ] );
   
}

void BestBruteForce( int Ladownosc, int nKONTENEROW )
{
    int start, end;
    start = clock();
   
    Kombinacja * BEST, * NEWBIE;
    BEST = new Kombinacja();
   
    for( int unsigned i =( 1 << nKONTENEROW ); --i; )
    {
       
        NEWBIE = new Kombinacja();
       
        for( int unsigned k = 0; k < nKONTENEROW && NEWBIE->CiezarKombinacji() <= Ladownosc; k++ )
        {
            if(( i >> k ) & 1 ) NEWBIE->AddElement( k );
           
        }
       
        if( NEWBIE->CiezarKombinacji() <= Ladownosc && BEST->WartoscKombinacji() < NEWBIE->WartoscKombinacji() )
        {
            delete BEST;
            BEST = new Kombinacja();
            * BEST = * NEWBIE;
            //BEST->WriteWiC();
            //cout<<endl<<endl;
        };
       
        delete NEWBIE;
    }
   
   
   
   
   
    end = clock() - start;
    WynikBF = new Wynik( end, BEST->CiezarKombinacji(), BEST->WartoscKombinacji() );
    delete BEST;
   
   
}

void BestAlgZachlanny( int Ladownosc, int nKONTENEROW )
{
    int start, end;
    start = clock();
   
    Kombinacja * blabla;
    blabla = new Kombinacja();
   
    int MaxCiezar = 0;
    int MaxValue = 0;
    WykonajWartosciWazone( nKONTENEROW );
    HS( nKONTENEROW );
    int i = nKONTENEROW - 1;
   
    for( int i = nKONTENEROW - 1; MaxCiezar + KontenerCiezar[ WartosciWazoneINDEX[ i ] ] <= Ladownosc && i >= 0; i-- )
    {
        MaxValue += KontenerWartosc[ WartosciWazoneINDEX[ i ] ];
        MaxCiezar += KontenerCiezar[ WartosciWazoneINDEX[ i ] ];
        blabla->AddElement( WartosciWazoneINDEX[ i ] );
    }
    end =( clock() - start );
    WynikAlgZach = new Wynik( end, blabla->CiezarKombinacji(), blabla->WartoscKombinacji() );
   
}

void WykonajWartosciWazone( int nKONTENEROW )
{
    for( int i = 0; i < nKONTENEROW; i++ )
    {
        WartosciWazone[ i ] = KontenerWartosc[ i ] / KontenerCiezar[ i ];
        WartosciWazoneINDEX[ i ] = i;
        //cout<<WartosciWazone[i]<<" ";
    }
   
}


int zastap_element( int * zastepowany, int * tymzastapiony )
{
    * zastepowany = * tymzastapiony;
}

void podmien_elementy( int * x, int * y )
{
    int temp;
    temp = * x;
    * x = * y;
    * y = temp;
}



int main()
{
    int LADOWNOSC = 300;
    int nKONTENEROW = 50;
    int WartoscMIN = 50;
    int WartoscMAX = 500;
    int CiezarMIN = 20;
    int CiezarMAX = 50;
   
    nadpis( 8, 0 ); cout << "Czas [ms]";
    nadpis( 25, 0 ); cout << "| Wartosc";
    nadpis( 35, 0 ); cout << "| Ciezar";
    nadpis( 44, 0 ); cout << "| BladWzgledny";
    nadpis( 59, 0 ); cout << "| KONTENEROW";
    nadpis( 72, 0 ); cout << "| LADOWNOSC";
   
    nadpis( 2, 1 );
    kolor( 5 ); cout << "BF";
    nadpis( 8, 1 );
    kolor( 6 ); cout << "AlgZach ";
    nadpis( 17, 1 );
    kolor( 7 ); cout << "AlgDyn ";
   
    int pocz = 20;
    int kk = 4;
    for( int i = 50; i < LADOWNOSC; i += 5 )
    for( int j = pocz; j < nKONTENEROW; j += 1 )
    {
       
        generuj_zbior( j, WartoscMIN, WartoscMAX, CiezarMIN, CiezarMAX );
        BestBruteForce( i, j );
        BestAlgZachlanny( i, j );
        BestDynamo( i, j );
       
        nadpis( 1, kk );
        cout << WynikBF->CZAS;
        nadpis( 9, kk );
        cout << WynikAlgZach->CZAS;
        nadpis( 17, kk );
        cout << WynikAlgDyn->CZAS;
       
        nadpis( 26, kk );
        cout << WynikBF->WARTOSC << "|" << WynikAlgZach->WARTOSC << "|" << WynikAlgDyn->WARTOSC;
       
        nadpis( 42, kk );
        cout << WynikBF->CIEZAR << "|" << WynikAlgZach->CIEZAR << "|" << WynikAlgDyn->CIEZAR;
       
        nadpis( 55, kk );
        cout << float(( float( WynikAlgDyn->WARTOSC ) - float( WynikAlgZach->WARTOSC ) ) / float( WynikAlgDyn->WARTOSC ) );
       
        if( kbhit() )
        {
            cout << "pause";
            getch();
            cout << "\b\b\b\b\b     ";
        }
        delete WynikAlgDyn;
        delete WynikBF;
        delete WynikAlgZach;
        //getch();
       
        kk++;
    };
   
   
   
   
    return 0;
}
P-171286
» 2018-05-28 16:56:11
Zobacz na kod destruktora Kombinacji i na sposób w jaki dodajesz nowy element.
P-171287
Temat założony przez niniejszego użytkownika
» 2018-05-28 19:43:20
co do kodu destruktora powinienem w nim aktywować również destrukcję poszczególnych Elementów?
mniej więcej na tej zasadzie?

C/C++
~Kombinacja()
{
    CURRENT = FIRST->NEXT;
    while( CURRENT != NULL )
    {
        CURRENT->PREV->~Element();
        CURRENT = CURRENT->NEXT;
    }
}

w przypadku użycia poniższego kodu od razu wyrzuca komunikat "program przestał działać"

C/C++
delete BEST;
BEST = NEWBIE;
NEWBIE = NULL;
P-171289
» 2018-05-28 20:21:44
Mniej więcej tak tylko musisz gdzieś użyć
delete
. Zobacz też na takie zagadnienia jak Tablice Haszujące, Open Addressing możliwe że te bardziej nadają się do tego co chcesz osiągnąć. I może jak jest to takie obciążenie dla pamięci warto gdzieś co jakiś czas zapisać to do jakiegoś pliku txt czy bazy danych.
EDIT:
Niech się wypowie ktoś bardziej doświadczony.
P-171290
« 1 » 2
 Strona 1 z 2Następna strona