Maksymalna ilość elementów w QStringList

0

Witam,

Czy wie ktoś z Was może jaki jest górny limit w ilości elementów wrzucanych do obiektu QStringList? Napisałem program oparty na drzewie BST zapisanym do pliku na dysku i w obiekcie klasy QStringList zapisuje sobie wartości klucza każdego węzła drzewa.

W przedziale pomiędzy 40000, a 50000 elementem, podczas wrzucania obiektu klasy QString na listę, program się wywala. Patrząc w debuger wyśledziłem, że problemem jest ilość elementów w obiekcie QStringList.

Nie wiem... Może przekraczam maksymalną dozwoloną ilość obiektów na takiej liście?
Szukałem informacji o maksymalnej ilości elementów listy stringów ale nie znalazłem.

Pozdrawiam
Grzegorz

0

Nie mam jak teraz sie pobawic z tym, ale czy po prostu Ci sie pamiec nie konczy? Wywala to dosc malo informacji, wrzuc jakies logi/informacje z debuggera czy cokolwiek. + Tak na chlopski rozum 40k-50k to nie sa zadne okragle liczby, na ktore zdrowy czlowiek by jakies limity ustawial (zreszta po co limity jakiekolwiek w liscie...).

0

Dobrze,

napisałem taką oto funkcję, która przechodzi sobie moje drzewo metodą inorder i zbiera klucze (nazwane identyfikatorami węzła) wrzucając je na listę stringów:

Oto i ta funkcyjka:


void DrzewoBST::tworzCiagId(BST *wezel){
	if(wezel){
	this->tworzCiagId(wezel->syn_lewy);
	        this->listaId.append(QString::number(wezel->id));
        this->tworzCiagId(wezel->syn_prawy);
    }
}

Debuger Qt wyrzuca segfaulta w tej funkcji systemu Windows (plik ntdll.dll):


ntdll!RtlQueryEnvironmentVariable_U

Jeżeli ktoś kojarzy coś w assemblerze to wrzucę jeszcze kod po deassemblacji ze wskazaniem miejsca segfaulta:


Function: ntdll!RtlQueryEnvironmentVariable_U
0x77573de3  <+0x005a>         clc
0x77573de4  <+0x005b>         add    (%eax),%eax
0x77573de6  <+0x005d>         add    %dl,-0x6f6f6f70(%eax)
0x77573dec  <+0x0063>         mov    %edi,%edi
0x77573dee  <+0x0065>         push   %ebp
0x77573def  <+0x0066>         mov    %esp,%ebp
0x77573df1  <+0x0068>         sub    $0x18,%esp
0x77573df4  <+0x006b>         mov    0xc(%ebp),%al
// Poniższa linijka wywala segfault.
0x77573df7  <+0x006e>         push   %ebx
0x77573df8  <+0x006f>         push   %esi
0x77573df9  <+0x0070>         push   %edi
0x77573dfa  <+0x0071>         mov    0x8(%ebp),%edi
0x77573dfd  <+0x0074>         mov    %ecx,%ebx
0x77573dff  <+0x0076>         mov    %al,0x2(%edi)
0x77573e02  <+0x0079>         movb   $0x0,0x7(%edi)

Patrząc na kod asm wnioskuję jakieś przepełnienie tylko gdzie? Jedyna możliwa odpowiedź to przekroczenie limitu elementów na liście stringów.

Może jest coś o czym nie wiem? :-D

[EDIT] - QStringList::append wyrzuca segfault kiedy chcę dodać 43101 element do listy. Nadal nie wiem dlaczego. Kiedy usunę z powyższej funkcji linijkę odpowiedzialną za dodawanie wartości do listy przechodzenie drzewa działa.

Pozdrawiam
Grzegorz

0

Postanowiłem napisać rozwiązanie / obejście problemu w kolejnym poście.

Okazało się, że zadziałała tutaj lista generyczna QList<unsigned int="int">. Po zastąpieniu obiektu typu QStringList obiektem generycznym, od którego dziedziczy QStringList wszystko działa prawidłowo.
Wyśledziłem dodatkowo, że może występować tutaj problem z konwersją typów z unsigned int do QString.

Taki kod nie wyrzuca błędów (this->listaId jest typu QList<unsigned int="int">):


void DrzewoBST::tworzCiagId(BST *wezel){
	if(wezel){
		this->tworzCiagId(wezel->syn_lewy);
		this->listaId.append(wezel->id);
		this->tworzCiagId(wezel->syn_prawy);
	}
}

Ciekawostka:
kiedy this->lista jest typu QList<QString>, a funkcja wygląda tak jak poniżej też jest segfault:


void DrzewoBST::tworzCiagId(BST *wezel){
	if(wezel){
		this->tworzCiagId(wezel->syn_lewy);
		this->listaId.append(QString::number(wezel->id));
		this->tworzCiagId(wezel->syn_prawy);
	}
}

Bardzo dziwna sprawa. Albo to jest wspomniany problem konwersji QString::number(zmienna), albo samej funkcji QList::append() gdzie jako typ dla obiektu QList podany jest QString.

Konkludując: W dalszym ciągu nie wiem dlaczego program wyrzucał segfault'a :-)

0

Musisz mieć gdzieś poważny błąd. Tutaj dałem wyszukiwawcza do krzyżówek/scrable, gdzie QStringList radzi sobie ze słownikiem 200000 słów (jeśli dobrze pamiętam).
Gdy stosujesz QStringList to zużywasz dużo więcej pamięci. Ten błąd sugeruje, że gdzieś naruszasz strukturę sterty, a w tym miejscu pojawiają się konsekwencje. Zmiana na QList<int> jest rozsądna tak czy tak, ale jedynie zmiesza też szanse, że ten błąd się ujawni.

Moja rada: kompilacja z opcją -Wall by wyłapać błędy, które może zauważyć kompilator, a w drugim kroku jakieś narzędzie do sprawdzania spójności pamięci, np Valgrind (nie wiem, czy pod Windows to działa, ale pod Linux Qt Creator standardowo go obsługuje).

Załęże się, że sknociłeś BST i gdzieś masz "dangling pointer" zamiast null-a.

0

Spróbuj stworzyć QStringList na stercie bo z tego co widzę to jest na stosie - może tutaj tkwi problem, choć nie sądzę. Myślę tak jak przedmówcy, że może być gdzieś jakiś wskaźnik niepoprawny i przez to program działa niepoprawnie.

0

Witam,

Stworzyłem na stercie tą listę i rezultat był ten sam. Co do "dangling pointer" to ustawiłem sobie odpowiednio trapy debugera żeby zobaczyć jak wyglada to drzewo.
Okazuje się, że wskaźnik następnika ustawiony jest prawidłowo. Użyłem zwrotu następnik, gdyż drzewo zapisałem sobie w pliku w postaci listy liniowej z tylko prawymi synami.
Wszystko jest w porządku:

Element drzewa nr 43101 posiada swojego prawidłowo zaadresowanego syna o id 43102 etc.. etc..
Widzicie... nie powiedziałbym, że coś tutaj jest nie tak z drzewem gdyż kiedy puszczę funkcję w takiej postaci, czyli bez przetwarzania węzła inorder:


void DrzewoBST::tworzCiagId(BST *wezel){
        if(wezel){
                this->tworzCiagId(wezel->syn_lewy);
                this->tworzCiagId(wezel->syn_prawy);
        }
}

To nie ma żadnego segfaulta :-/
Jeżeli gdzieś wisiałby wskaźnik o złej adresacji lub odwołanie do niezaalokowanego obszaru to rozumiem, ale tak...

[EDIT] Ciekawostka: Właśnie załadowałem do programu 500tyś. węzłów drzewa ze zmianami w postaci listy wskaźnikowej jako dodatkowe pole drzewa i... działa w oparciu o QList<unsigned int="int">. Tak sobie myślę: skoro z QStringList segfault był widoczny przy 43101 elemencie to w normalnej liście generycznej przy tak wielkiej ilości rekordów powinien się już ujawnić, czy tak?

0

Wystaw zip-a z projektem, będzie prościej.
Przestań upierać się, że to jest problem z QStingList bo to do niczego nie prowadzi. Na pewno używasz niewyzerowanego wskaźnika lub wskaźnika do elementu, który został już zwolniony i dlatego program ci się sypie w nieprzewidywalnym miejscu.
Pierwszy krok to sprawdzenie czy program kompiluje się bez ostrzeżeń, drugi krok valgrind lub analiza kodu pod kontem zarządzania pamięcią.

0

Witam,

wstawiłem zipa z projektem jako załącznik. W zipie są trzy katalogi:

  • generator: program, który generuje plik bazy danych o podanej ilości węzłów oraz plik zawierający zapisaną ilość węzłów drzewa (obiekt 'int koniec'):

    • bazaDanych.dat - drzewo w postaci listy liniowej. Tak było najprościej je wygenerować. Można je zrównoważyć zapisując na dysku.
    • iloscWezlow.dat - plik z ilością węzłów, potrzebny do prawidłowego działania paska postępów wczytywania danych z dysku.
      Oba pliku wrzucamy do katalogu głównego programu. Żeby program zaczytał sobie bazę danych trzeba wybrać w 'Opcjach dyskowych'
      pozycję 'Wczytaj drzewo'. Później podczas wybierania z menu głównego opcji np. 'Modyfikuj dane' program się wywali :). Podczas debugowania
      zobaczycie ładnego segfaulta po 43101 węźle.
  • projekt: tutaj jest cały projekt napisany w Qt Creatorze:

    • klasa, która zawiera feralną listę to DrzewoBST w pliku drzewobst.h/cpp.
    • obiekt, który powoduje problemy to QStringList listaId oraz QStringList listaIdZmian.
      • generalnie jeżeli rozwiąże się problem z obiektem listaId to automatycznie także z tym drugim:)
  • pliki: jak komuś nie będzie chciało się generować plików to można użyć gotowców z tego katalogu.

Jak już pisałem QList działa QStringList nie działa. Wyzerowałem wszystkie usuwane wskaźniki i dalej ten sam rezultat. Jestem szalenie ciekawy dlaczego tak się dzieje.

Aha, jeżeli ktoś będzie miał jakieś uwagi co do stylu kodu czy jakiś algorytmów to chętnie je przeczytam, bo chcę się rozwijać w dziedzinie programowania.

Pozdrawiam
Grzesiek

0

Mnie się osobiście wydaje, że problemem tutaj jest głębokość rekursji i przepełnienie stosu. Spróbuj zaimplementować wersję iteracyjną. W najprostszej postaci potrzebujesz do jej stworzenia dodatkowej informacji o tym czy węzeł został już odwiedzony ("bool v" w BST) - chociaż można i bez tego bo sposobów jest kilka:

void DrzewoBST::tworzCiagId(BST *wezel){
    QStack<BST* > stack;
    stack.push(wezel);
    while(!stack.isEmpty())
    {
        BST * top = stack.top();
        if(top)
        {
            if(!top->v)
            {
              stack.push(top->syn_lewy);
            }
            else
            {
                listaId.append(QString::number(stack.pop()->id));
                stack.push(top->syn_prawy);
            }
        }
        else
        {
            stack.pop();
            if(!stack.isEmpty())
                stack.top()->v = true;
        }
    }
}

oczywiście pomijam już wspomniany wyżej fakt bezsensowności przechowywania liczby w stringu.

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