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.

0

Dziękuje za odpowiedź. Rzeczywiście sprawdzę czy to podziała, chociaż teoretycznie moja funkcja to najzwyklejsze przejście inorder :-/

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

Przechowuję id w stringu gdyż wszystkie elementy obiektu QStringList są wrzucane jako item do comboboxa, którego klasa posiada funkcję QComboBox::addItem() z argumentem typu const QString & text. :)

[EDIT]:
Co do zamiany rekurencji na iterację to zrobiłem taką oto funkcję:

 

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

Co ciekawe bez obiektu 'v' też działa prawidłowo. Dopisałem jednakże ten obiekt do struktury drzewa i też działa.
Pytanie tylko... Dlaczego nie działa inorder?? :-/ Wciąż mnie to zastanawia. I dlaczego nie działa z listą QStringList, a działa ze zwykłą QList?

Wczytałem 500tyś węzłów, jak już wcześniej pisałem i błąd się nie pojawił w generycznej wersji listy :)

Pozdrawiam
Grzesiek

1

Sprawdziłem valgrind-em twój kod i zarządzanie pamięcią jest prawie dobrze. Trzeba poprawić destruktor:

OknoGlowne::~OknoGlowne()
{
    delete uw;
    delete mw;
    delete up;
    delete pz;
    delete op;
    delete dw;

    delete ui;
    delete this->drzewo;
    this->drzewo = 0;
}

Nie jest to wyciek pamięci, bo każda z tych alokacji dzieje się tylko raz na uruchomienie aplikacji i stworzone obiekty powinny żyć tak długo jak działa aplikacja. Jednak poprawienie destruktora powoduje, że log valgrinda jest czysty.

Co do samego, błędu to u mnie nie występuje. Całkiem możliwe, że masz inne ustawienia kompilatora i przykładowo stos masz mniejszy (zmiana na wersję iteracyjną to potwierdza).
Drzewo BST do bazy danych nie jest najszczęśliwszym pomysłem, tak samo wczytywanie wszystkiego do pamięci powoduje, że twoja aplikacja jest bardzo ociężała.
Ten combobox na wybieranie id studenta to już totalna klęska (perfomace pada).
Radzę zaimplementować model tabeli (zapomnij o standardowym modelu), wtedy zarządzanie i wyświetlanie danych będzie szybsze.

0

Dziękuję za odpowiedź. Rzeczywiście w klasie OknoGlowne nie usuwam wskaźników do okien potomnych.
Wiem, że takie drzewo jako baza danych to nie jest najlepszy pomysł ale po prostu chciałem przetestować sobie algorytmy drzewa na czymś używalnym. Wsadziłem id do comboboksa, ponieważ nie miałem innego pomysłu. Zauważyłem jak program dławi się przy większej liczbie węzłów.

Wspomniałeś coś o modelu tabeli? O co chodzi dokładnie? O tablicę haszowaną? O jakąkolwiek dynamiczną strukturę danych czy po prostu zwykłą tablicę dynamicznie alokowaną?

0

Mam jeszcze jedno małe pytanko. Nie wiem dlaczego ale kiedy postawicie sobie trap debugera w zaznaczonym miejscu to zobaczycie, że slot 'wcisnietoDodaj()' wykona się dwa razy.

 
void DodawanieWezla::wcisnietoDodaj(){
    unsigned int id = this->ui->leIdentyfikator->text().toInt();

    if(this->drzewo == 0){
        this->drzewo = new DrzewoBST;
    }
    bool x = this->czyWypelnione();



    // TUTAJ <- Kiedy postawi się trap na poniższym ifie zauważymy dziwne zachowanie
    // jakby funkcja this->czyWypelnione wykonała się dwa razy albo cały slot wykonał się dwa razy
    if(x){
        if(this->drzewo->czyIstniejeWezel(id)){
            this->wiad->setText("Student o identyfikatorze nr '"
                                + this->ui->leIdentyfikator->text()
                                + "' istnieje już w bazie danych.\n"
                                + "Proszę wprowadzić inny identyfikator.");
            this->wiad->setWindowTitle("Wystąpiło powtórzenie identyfikatora");
            this->wiad->setStandardButtons(QMessageBox::Ok);
            this->wiad->setIcon(QMessageBox::Critical);
            this->wiad->show();
        }
        else{
            this->drzewo->dodaj(this->ui->leIdentyfikator->text().toInt(),
                                this->ui->leImie->text().toStdString(),
                                this->ui->leNazwisko->text().toStdString(),
                                this->ui->leUlica->text().toStdString(),
                                this->ui->leMiasto->text().toStdString(),
                                this->ui->leKodPocztowy->text().toStdString(),
                                this->ui->leUczelnia->text().toStdString(),
                                this->ui->leWydzial->text().toStdString());

            this->wiad->setText("Student '"
                                + this->ui->leImie->text()
                                + " "
                                + this->ui->leNazwisko->text()
                                + "' został pomyślnie dodany do bazy danych.\n");

            this->wiad->setWindowTitle("Dodano pomyślnie");
            this->wiad->setStandardButtons(QMessageBox::Ok);
            this->wiad->setIcon(QMessageBox::Warning);
            this->wiad->show();

            emit dodanoPomyslnie();
        }
    }
    else{
        this->wiad->setText("Nie wszystkie pola zostały wypełnione!");
        this->wiad->setWindowTitle("Brak dostatecznych danych");
        this->wiad->setStandardButtons(QMessageBox::Ok);
        this->wiad->setIcon(QMessageBox::Critical);
        this->wiad->show();
    }
}

Podczas dodawania pierwszego studenta wszystko jest ok. Klikamy sobie 'Dodaj' i program wyświetla komunikat o pomyślności operacji. Wygląda, że wszystko jest ok tylko spróbujcie teraz zamknąć okno dodawania i otworzyć je jeszcze raz, a następnie dodać studenta.

Funkcja 'this->czyWypelnione()' zwróci true... a następnie zwróci false, tak jakby wykonała się dwa razy! W rezultacie program pomyślnie doda studenta ale wyrzuci komunikat o niewypełnionych formatkach zamiast komunikatu o pomyślności operacji dodawania.

A przecież raz kliknąłem przycisk Dodaj.

O co chodzi? Nie rozumiem tego.
Serdecznie proszę o pomoc.

Pozdrawiam
Grzegorz

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