Dynamiczna alokacja pamięci, optymalizacja kodu

Cześć
Mam taki mały problem, z którym walczę już od tygodnia. Na studiach mamy sprawdzarkę algorytmiczną, na którą wrzucamy zadanka. Określona jest dozwolona ilość pamięci oraz czas, w jakim algorytm musi się wykonać.
Mój program przechodzi 4/6 testów, a 2 mają za długi czas wykonania. Zauważyłem że w jednym z nich samo wczytywanie dużych danych zajmuje około 70% czasu, więc w tych 30 się cięzko wyrobić z algorytmem i jakimiś obliczeniami.
Strumienie mam przyspieszone przez

ios_base::sync_with_stdio(false);

oraz

cin.tie(NULL);

Czy alokacja pamieci przy użyciu new jest aż tak czasochłonna? Jak efektywnie alokowac duże obszary pamięci?

• pokaz kod

• napisz tresc zadania

• napisz na co trzeba wzrocic uwage (szybkosc / czytelnosc / zuzycie pamieci etc)

• nie zgaduj, lepiej po prostu sprawdz jakis profilerem, albo porob sam testy na kodzie

Na 99% cierpisz na problem XY. Twój problem raczej leży w samym algorytmie rozwiązania, niż jest zależny od wydajności alokatora pamięci (a jeśli tak jest - to źle skonstruowano zadanie/testy).

Pokaż kod i zadanie.

Nie za bardzo mogę pokazać kod, uczulali nas zeby nie wrzucac swoich kodów nigdzie, bo antyplagiat sprawdzają.
Potrzebuję na początek odpowiedzi na pytanie jak najlepiej alokować pamięć oraz czy może nie robić tego dynamicznie?
Mogę napisać co program przyjmuje na wyjsciu.

*W pierwszej linii wejścia program otrzymuje liczbę n określającą ilość list ze stemplami. W kolejnych n liniach program otrzymuje n opisów zawartości dysku. Każdy opis składa się z liczby m określającej początkową liczbę stempli na dysku a następnie w m liniach pary składające się z ciągu znaków s oraz liczby całkowitej c. Następnie program otrzymuje liczbę l po czym l numerów kontrolnych samochodów w kolejności rosnącej. W dalszym kroku program otrzymuję sekwencję sterującą rozpoczynając od liczby h a potem h par liczb całkowitych x i y gdzie x określa o ile dysków przesunąć manipulator a y o ile stempli obrócić dysk.
*
Ogólnie zadanie jest implementacją listy cyklicznej dwukierunkowej.

W takim razie w jaki sposób oczekujesz pomocy w znalezieniu problemu w rozwiązaniu, którego nie chcesz nam pokazać?

 Maszyna maszyna;
 maszyna.ustawLiczbeDyskow(n);

    Dysk** tmpDysk = new Dysk*[n];

    for(int i=0; i<n; ++i){
        cin >> m;
        tmpDysk[i] = new Dysk;
        for(int j=0; j<m; ++j){
            cin >> s >> c;
            tmpDisc[i]->dodaj(new Znaczek(s, c));
        }
        maszyna.DodajDysk(tmpDysk[i]);
    }

Pokazuję "pseudokod" wczytywania danych i alokacji pamięci.
Obiektami zarządza instancja klasy Machine. To tam destruktor zwalnia całą przydzielona pamięc i uruchamia destruktory poszczególnych klas. Ten fragment kodu wykonuje się ponad 5.6s, a mam dostępnego czasu 6.9 . Cały moj program wykonuje się 7.30, więc o 0.4 za duzo. Sprawdziłem juz wszystko i z najbardziej czasochłonnych rzeczy zostało wczytywanie danych i alokacja pamięci. Czy powyższy sposób wygląda na poprawny? Zakładając ze metoda dodaj i dodaj dysk działa jak nalezy.

Faktycznie przekombinowałeś z tą pamięcią. Za dużo masz tych alokacji małych prostych obiektów.

    std::vector<Dirve> drives(n);
    for(auto& drive : drives) {
        cin >> m;
        for(int j=0; j<m; ++j){
            cin >> s >> c;
            drive.addBlock(s, c);
        }
    }

machine.installDrives(drives);

Mimo to nadal uważam (jak inni), że to nie jest źródłem problemu.
Problem musi być złożoność czasowa algorytmu, który rozwiązuje problem (przypuszczalnie defragmentacji dysku).

https://dsp.krzaq.cc/post/176/ucze-sie-cxx-kiedy-uzywac-new-i-delete/

Spróbuję trochę bardziej sprecyzować swoj problem.
A mianowicie mam klasę Lista. Ponizej pokaze szkic bardziej znaczących pól i metod.

class List{
struct Node{
        Node* previous;
        Obiekt obiekt;
        Node* next;

Node(Obiekt obiekt)
     : obiekt(obiekt){
previous = next = this;
}

Node(Node* previous, Obiekt obiekt, Node* next)
	: previous(previous)
         , obiekt(obiekt)
         , next(next){
}

};

public:
 void add(Obiekt obiekt){
      Node* node = new Node(obiekt);
            ptr = node;
        } else{
            Node* node = new Node(ptr, obiekt, ptr->next);
            node->previous->next = node;
            node->next->previous = node;

            ptr = node;
        }
}

No i moj problem polega na tym, że nie wiem jak to prawidłowo wywołać w mainie, aby nie było problemów z pozniejszym kasowaniem sie obiektów po wyjsciu ze scopa itd. Powinienem alokowac dynamicznie czy automatycznie?

Jeżeli nie masz konkretnych powodów do używania alokacji na stercie - a zadając takie pytanie raczej tego powodu nie masz - to powinieneś alokować na stosie, zatem automatycznie.

Przekombinowałeś z tymi new. Jeśli masz w linii x obiektów, to alokuj na nie wszystkie pamięć raz. A pozniej zamiast dodaj znaczek, raczej ustaw parametry znaczka. Tak samo jesli chodzi o dysk. Nie wiem, czy tu lezy problem, ale jesli zna sie wielkosc potrzebnej pamieci dobrze je brac jedną alokacja. Choć większość nowych kompilatorów i tak operuje poolami, więc nie powinno miec to aż takiego znaczenia (ale taka umiejętność może się przydać przy różnych rozwiązaniach embeded)

    Dysk* dysk;

    for(int i=0; i<n; ++i ){
        cin >> m;
        dysk = new Dysk;

        for(int j=0; j < m; ++j){
            cin >> s >> c;
            dysk->dodaj(new Stempel(s, c));
        }
        listaDyskow.dodajDysk(dysk);
    }

Taki sposób dodawania pasuje mi najbardziej, jednak okazuje się za wolny. Nie rozumiem jak mam zaalokować x elementów na raz? Uzywajac tablicy? Czy to nie mija się troche z celem, skoro zadanie jest implementacją list (Dysk to lista oraz listaDyskow jest listą).
Kiedy zamieniłem obiekty na automatyczne to wszystko działa, testy przechodzą, pod warunkiem że wywalę destruktor, bo po wyjsciu z jednej petli dysk za kazdym razem jest usuwany.
Może ktoś dałby wskazówki jak to zrobić na obiektach stackowych? Wiem że trzeba zmodyfikowac nody listy, aby przechowywały nie wskazniki, lecz dane, tak robię, no ale problem z kasowaniem jakims jest.

A ogólnie wydaje mi się, że to co najpisałem powyżej jest poprawne, kontrolę nad nowo utworzonymi obiektami przejmuje juz lista i to jej destruktory mają zadbac o wyczyszczenie pamięci.

Nie rozumiem tez dlaczego zmiana obiektów na automatyczne przyspieszyła działanie programu o prawie 2 sekundy.... :/

Doszedłem do wniosku że przy pamięci automatycznej należałoby w pierwszej liscie (w dysku) dodać konstruktor kopiujący, ponieważ w przeciwnym wypadku wskazniki zostaną tylko przepisane, a po wyjsciu ze scopa nie będą istniały. Dlatego własnia dynamiczna alokacja była dla mnie wygodniejsza.

Ale co? Konstruktor kopiujacy przy wskaźnikach jako składowych jest niezbędny, nawet jeśli tworzysz obiekt przez New.

Wielkie dzięki chłopaki, mimo że nie umiałem/nie mogłem doprezyzować swojego problemu, to udało mi się z waszą pomocą go rozwiązać. Przyczyną wszelkich błędów był .... konstruktor kopiujący, a własciwie jego brak. Teraz zaalokowałem sobie te wszystkie obiekty na stacku automatycznie, napisałem dobrze konstruktor kopiujacy i nie mam juz problemów że coś mi się samo usuwa. Dziękuję za dobre chęci i wszelkie wskazówki. Następnym razem jak będę potrzebował pomocy, to lepiej określę swój problem (którego w tym przypadku sam nawet nie znałem).

A ja nadal nie rozumiem po co Ci tam konstruktor kopiujący.
Po co w ogóle chcesz tworzyć te znaczki tak

dysk.DodajZnaczek( new Znaczek(s,c ) )

przecież to powinno działać tak

dysk.DodajZnaczek({s,c})

bez żadnych new