Jak policzyć, ile miejsca w pamięci zajmuje kolejka?

0

Cześć. Napisałem algorytm, w którym używam tablicy kolejek o wielkości 1 000 000. Cały algorytm może zużywać max. 64MB. Wszystkie kolejki w tablicy łącznie przechowują maksymalnie 1 000 000 int'ów. Chciałem sprawdzić za pomocą sizeof() ile zajmuje kolejka. Zależnie od kompilatora wynik wynosił 80 lub 40 bajtów (dlaczego?), więc razem maksymalna ilość pamięci jaką zajmie tablica kolejek policzyłem tak:
10^6 * sizeof(queue<int>) + 10^6 * 4
przy czym 4 to oczywiście wielkość 1 int'a. Niestety jeśli wielkość kolejki to 80B, to algorytm nie mieści się w 64MB. Z czego wynika różnica w wynikach sizeof() i w jaki sposób mogę policzyć wielkość takiej tablicy kolejek?

0

Pokaż definicje struktur.

0

Ale sizeof da Ci rozmiar typu a nie faktyczny rozmiar zajmowanej pamieci.

Mozesz sprawdzic to uzywajac sizeof na dwoch kolejkach o roznej liczbie elementow - wynik powinien byc taki sam

0
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

const int MAX_LENGTH = 1000000;
queue<int> indexes[MAX_LENGTH];

int main()
{
    // algorytm
}
0

No i ogolnie milion intow bez zadnego overheadu to juz prawie 4MB a Ty jeszcze chcesz milion takich kolejek

3

Zależnie od kompilatora wynik wynosił 80 lub 40 bajtów (dlaczego?)

Każdy kompilator może mieć nieco odmienną implementację queue, może inaczej podchodzić do spraw paddingu etc.

Niestety jeśli wielkość kolejki to 80B, to algorytm nie mieści się w 64MB

Na 99% w ogóle źle podchodzisz do problemu - czy to jakieś zadanie ze SPOJa?

0

Możesz uporać się z tym stosując ręcznie zaklepaną listę z dowiązaniami.

0
licealista skomentował(a):

to zadanie ze szkopuł: https://szkopul.edu.pl/proble[...]ulN1gixfW/site/?key=statement To było po prostu pierwsze rozwiązanie jakie przyszło mi do głowy, zdaję sobie sprawę z tego, że raczej nie jest to rozwiązanie wzorcowe (choćby dlatego, że jak się przekonałem, nie mieści się w pamięci). Mój algorytm miał polegać na przejściu ciągu wejściowego i wpisanie w kolejkę indeksów na których w tym ciągu występuje dana liczba. Potem szukanie podciągów byłoby już proste. Złożoność by była o ile dobrze liczę O(n) i dlatego chciałem spróbować.

To załóż nowy wątek, załącz ten link do zadania, oraz swój kod. Dokładnie opisz błąd jaki zgłasza ci sędzia. Ktoś ci na pewno wytłumaczy co robisz źle.
Licznie ile zajmuje kolejka tak jak to sobie wyobrażasz (i jak niektórzy ci odpowiadają powyżej), nie ma sensu z bardzo wielu technicznych powodów, których nie musisz znać.

1

Jak się okazuje, sposób rozumowania miałem prawidłowy. Żeby zmieścić się w ograniczeniach zadania wystarczyło queue<int> zamienić na vector<int>. Wydaje mi się to nieintuicyjne, że kolejka mająca mniej funkcji niż vector zajmuje więcej miejsca (na niektórych platformach). Poczytam jeszcze podesłane linki i może mi się coś rozjaśni. Dziękuję wszystkim za pomoc.

0
licealista napisał(a):

Wydaje mi się to nieintuicyjne, że kolejka mająca mniej funkcji niż vector zajmuje więcej miejsca (na niektórych platformach).

Kolejka/vector (ogolnie kolekcja jako typ) to tylko takie opakowanie. Mozliwe, ze (na niektorych platformach) kolejka jest zaimplementowana jako lista (byc moze dwukierunkowa). I wtedy jesli mamy vector no to jest rozmiar samego pudelka i jakas referencja do tablicy przez co elementy vektora nie maja narzutu. Lista to juz narzut conajmniej jednego wskaznika na kazdy wezel.

Ale nie wiem jak wyglada implementacja std::queue, wiec nie wykluczam ze tam jakis bufor cykliczny siedzi

0
licealista napisał(a):

Jak się okazuje, sposób rozumowania miałem prawidłowy. Żeby zmieścić się w ograniczeniach zadania wystarczyło queue<int> zamienić na vector<int>. Wydaje mi się to nieintuicyjne, że kolejka mająca mniej funkcji niż vector zajmuje więcej miejsca (na niektórych platformach). Poczytam jeszcze podesłane linki i może mi się coś rozjaśni. Dziękuję wszystkim za pomoc.

Działa nie znaczy, że to jest dobre rozwiązanie.
Swój problem powinieneś rozpatrywać w kategorii złożoności pamięciowej i czasowej.
Zapewne twój algorytm źle się skaluje na duże wartości. Ograniczenia zwykle są dobrane tak, by przy prawidłowym algorytmie, zadanie zostało zaliczone bez względu na rodzj użytego kontenera (dopóki jego złożoność pamięciowa jest taka sama).
Posłuchaj mojej pierwsze rady.

Po przeczytaniu treści zadania stwierdzam, że faktycznie queue<int> pasuje tu jak pięść do oka.

1 użytkowników online, w tym zalogowanych: 0, gości: 1