Big Problem search through huge amount of data ca 30 000 strings takes to long

[Ini]

Hello,

this is my Code:

void SomeClass::searchIn_identifier_listWidget()
{
    QList<Identifier*> tempList;
 
    QString text0 = ui->identifier_lineEdit_search_0->text();
    QString text1 = ui->identifier_lineEdit_search_1->text();
    QString text2 = ui->identifier_lineEdit_search_2->text();
    QString text3 = ui->identifier_lineEdit_search_3->text();
    QString text4 = ui->identifier_lineEdit_search_4->text();
 
    for (int i = 0; i < Storage::identifier.count(); i++) {
        if (Storage::identifier.at(i)->dataString.contains(text0,Qt::CaseInsensitive) &&
            Storage::identifier.at(i)->dataString.contains(text1,Qt::CaseInsensitive) &&
            Storage::identifier.at(i)->dataString.contains(text2,Qt::CaseInsensitive) &&
            Storage::identifier.at(i)->dataString.contains(text3,Qt::CaseInsensitive) &&
            Storage::identifier.at(i)->dataString.contains(text4,Qt::CaseInsensitive))
        {
            tempList << Storage::identifier.at(i);
        }
    }
 
    ui->identifier_listWidget->clear();
    for (int i = 0; i < tempList.count(); i++) {
        QTest::qWait(1);
        listWidget_addItemPlusTooltip(ui->identifier_listWidget,tempList.at(i)->dataString);
    }
}

void SomeClass::searchIn_identifier_listWidget()
{
    QList<Identifier*> tempList;

    QString text0 = ui->identifier_lineEdit_search_0->text();
    QString text1 = ui->identifier_lineEdit_search_1->text();
    QString text2 = ui->identifier_lineEdit_search_2->text();
    QString text3 = ui->identifier_lineEdit_search_3->text();
    QString text4 = ui->identifier_lineEdit_search_4->text();

    for (int i = 0; i < Storage::identifier.count(); i++) {
        if (Storage::identifier.at(i)->dataString.contains(text0,Qt::CaseInsensitive) &&
            Storage::identifier.at(i)->dataString.contains(text1,Qt::CaseInsensitive) &&
            Storage::identifier.at(i)->dataString.contains(text2,Qt::CaseInsensitive) &&
            Storage::identifier.at(i)->dataString.contains(text3,Qt::CaseInsensitive) &&
            Storage::identifier.at(i)->dataString.contains(text4,Qt::CaseInsensitive))
        {
            tempList << Storage::identifier.at(i);
        }
    }

    ui->identifier_listWidget->clear();
    for (int i = 0; i < tempList.count(); i++) {
        QTest::qWait(1);
        listWidget_addItemPlusTooltip(ui->identifier_listWidget,tempList.at(i)->dataString);
    }
}

To copy to clipboard, switch view to plain text mode 

So as you can see i want to search though someting in this case a QList and load the Strings into the ListWidget which match the search. The algorythm should stay like this I think. It takes like minutes until the Widget is filled with the new data. i have like 30 000 strings in this List. And all GUI should stay responsive to the user thats why the qWait is there. Maybe thats why it is so slow, but how can the GUI stay responsive without qwait?

What can I do???

Can somebody help me?

edit: Without qwait the whole GUI in ther widget where this QListWidget is is locked. And it also takes like 1 minute to process all data into the QListWidget

thx

[Lesiok]

First optimization - five times less method Storage::identifier.at(i) calls :

QString temp_str;
for (int i = 0; i < Storage::identifier.count(); i++) {
        temp_str = Storage::identifier.at(i)->dataString;
        if (temp_str.contains(text0,Qt::CaseInsensitive) &&
            temp_str.contains(text1,Qt::CaseInsensitive) &&
            temp_str.contains(text2,Qt::CaseInsensitive) &&
            temp_str.contains(text3,Qt::CaseInsensitive) &&
            temp_str.contains(text4,Qt::CaseInsensitive))
        {
            tempList << Storage::identifier.at(i);
        }
    }

QString temp_str;
for (int i = 0; i < Storage::identifier.count(); i++) {
        temp_str = Storage::identifier.at(i)->dataString;
        if (temp_str.contains(text0,Qt::CaseInsensitive) &&
            temp_str.contains(text1,Qt::CaseInsensitive) &&
            temp_str.contains(text2,Qt::CaseInsensitive) &&
            temp_str.contains(text3,Qt::CaseInsensitive) &&
            temp_str.contains(text4,Qt::CaseInsensitive))
        {
            tempList << Storage::identifier.at(i);
        }
    }

To copy to clipboard, switch view to plain text mode 

[anda_skoa]

Also, since QTest::qWait() suggests this is a unit test, is it really that problematic?

In a real application blocking the UI would be bad, but in an automated test you will have to wait for the result state anyway.

Cheers,
_

[Ini]

Can qWait not stay in the endprogramm?

I cannot cut qWait cause GUI stays unresponsive then. I would consider this as big problem...

---

Added after 20 minutes:

First optimization - five times less method Storage::identifier.at(i) calls :

QString temp_str;
for (int i = 0; i < Storage::identifier.count(); i++) {
        temp_str = Storage::identifier.at(i)->dataString;
        if (temp_str.contains(text0,Qt::CaseInsensitive) &&
            temp_str.contains(text1,Qt::CaseInsensitive) &&
            temp_str.contains(text2,Qt::CaseInsensitive) &&
            temp_str.contains(text3,Qt::CaseInsensitive) &&
            temp_str.contains(text4,Qt::CaseInsensitive))
        {
            tempList << Storage::identifier.at(i);
        }
    }

QString temp_str;
for (int i = 0; i < Storage::identifier.count(); i++) {
        temp_str = Storage::identifier.at(i)->dataString;
        if (temp_str.contains(text0,Qt::CaseInsensitive) &&
            temp_str.contains(text1,Qt::CaseInsensitive) &&
            temp_str.contains(text2,Qt::CaseInsensitive) &&
            temp_str.contains(text3,Qt::CaseInsensitive) &&
            temp_str.contains(text4,Qt::CaseInsensitive))
        {
            tempList << Storage::identifier.at(i);
        }
    }

To copy to clipboard, switch view to plain text mode 

is this really faster? whats the problem with .at(i) calls

[Lesiok]

---

Added after 20 minutes:

is this really faster? whats the problem with .at(i) calls

The problem is "this is a procedure calling". What do you think is faster: one call or five calls ?
Besides, my experience is that many operations on the Qt containers is very slow in debug mode because of the control parameters with ASSERT.

PS.

Have you tried to determine which loop will give you such a long time?

[Ini]

I dont know im not expert in memeory management. In my opionion both "point" to a location. I will check on that.

edit: I work in Release Mode.

But thats really not the Problem. Problem is the second loop.

I added qApp->processEvents. That helps but then there is a another Problem.
This Slot is connected to textChanged() of the LineEdits. So when text changes the slot will get triggerd, then text changes again, and it seems the slot then stops and performs the new instance of the slotcall and when this new instance is finsihed the old one continues. Am I right there? How to solve that upcoming problem?

[anda_skoa]

Can qWait not stay in the endprogramm?

If you want the real program to link to QtTest, sure.
Usually one doesn't want artifical dependencies.

I cannot cut qWait cause GUI stays unresponsive then. I would consider this as big problem...

Then I would suggest looking for a solution instead.

E.g. putting the result list into a model and having a QListView work on that model.

Cheers,
_

[Ini]

If you want the real program to link to QtTest, sure.
Usually one doesn't want artifical dependencies.


Then I would suggest looking for a solution instead.

E.g. putting the result list into a model and having a QListView work on that model.

Cheers,
_

why is that faster then QListWidget

"Usually one doesn't want artifical dependencies."

I dont find a good description what that is. Can you explain pls?

[anda_skoa]

I dont know im not expert in memeory management. In my opionion both "point" to a location.

Yes, but one is a direct "pointer" to the data, the other is repeatedly calculating the "pointer".
Using a variable can even more likely lead to the pointer to be cached by the CPU than the result of a function evaluation which just incidentally (as far as the CPU knowns) returns the same value five times in a row.

I added qApp->processEvents. That helps but then there is a another Problem.

Yes, this new problem is called "nested event loop".

This Slot is connected to textChanged() of the LineEdits. So when text changes the slot will get triggerd, then text changes again, and it seems the slot then stops and performs the new instance of the slotcall and when this new instance is finsihed the old one continues.

Yes, nested event loops can lead to behavior similar to re-entrancy.

why is that faster then QListWidget

Because you don't have to create all items, a list view only displays as many entries as it can fit.

I dont find a good description what that is. Can you explain pls?

A dependency on a library that you actually don't need.

Cheers,
_

[Ini]

Yes, but one is a direct "pointer" to the data, the other is repeatedly calculating the "pointer".
Using a variable can even more likely lead to the pointer to be cached by the CPU than the result of a function evaluation which just incidentally (as far as the CPU knowns) returns the same value five times in a row.


Yes, this new problem is called "nested event loop".


Yes, nested event loops can lead to behavior similar to re-entrancy.


Because you don't have to create all items, a list view only displays as many entries as it can fit.


A dependency on a library that you actually don't need.

Cheers,
_

Ok good to know what it is and that I figured that out right. What can I do against the nested event loops or reentrency? Is there a solution for that?

Can I cancel the outstanding calls of the function except the newest one?

And does it immediately pauses the old slot when the new instance get called, and when the new instance is finsihed does the old one continue in the line where its paused? If its like that I cannot know where to put a condition on something to return;

---

Added after 5 minutes:

I think I found a solution but its really ugly and I would have to add that in the first loop too:

void SomeClass::searchIn_identifier_listWidget()
{
var = false;
//...
ui->identifier_listWidget->clear();
for (int i = 0; i < tempList.count(); i++) {
qApp->processEvents();
if (var) {
return;
}
listWidget_addItemPlusTooltip(ui->identifier_listWidget,tempList.at(i)->dataString);
}
}

var = true;

[anda_skoa]

Ok good to know what it is and that I figured that out right. What can I do against the nested event loops or reentrency? Is there a solution for that?

Yes, the best solution is to not use nested event loops.

Can I cancel the outstanding calls of the function except the newest one?

You can return from a function whenever you decide to return.
So, in a nested loop case, you need to check after the nested loop return whether to still continue with the function.

And does it immediately pauses the old slot when the new instance get called

It does not pause anything.
You call processEvents(), it processes another text change, that calls the function again, then that returns, the processEvent might return (if there are no further events) then you are right where you left.

and when the new instance is finsihed does the old one continue in the line where its paused?

Yes, that's how C++ works.
If you call a function, your code executed right after the function call when the function returns.

Cheers,
_

[Ini]

"Yes, the best solution is to not use nested event loops."

I cannot see that that I can avoid nested event loops in that case. Is there something that could help avoiding the nested loops?

"You can return from a function whenever you decide to return.
So, in a nested loop case, you need to check after the nested loop return whether to still continue with the function."

but thats pretty ugly to put a processEvents() in every loop and then a condition wheter to exit the function with return; or not

[anda_skoa]

I cannot see that that I can avoid nested event loops in that case. Is there something that could help avoiding the nested loops?

As simple as not using them in the first place

but thats pretty ugly to put a processEvents() in every loop and then a condition wheter to exit the function with return; or not

Yes, hence the suggestion to not use them.

You need to ask yourself: "Why do I hate myself, why do I need to make my life more complicated than necessary".

Once you have forgiven yourself for whatever you are currently hating yourself for and are punishing yourself, you can go and make your life better by appling suggested improvements.

Cheers,
_

[Ini]

but I cannot find the same algorythm without an event loop. It is possible that event loops are needed for some algorythms.

Is there no command to cancel all outstanding events of an object except the actual one?

[anda_skoa]

but I cannot find the same algorythm without an event loop.

So you now have an nested event loop inside the filtering loop as well?

Maybe it is time to post some updated code?

It is possible that event loops are needed for some algorythms.

Highly unlikely.

Cheers,
_

[Ini]

void SomeClass::searchIn_identifier_listWidget()
{
searchIn_identifier_listWidget_eventLoopControl = false;

QList<Identifier*> tempList;

QString text0 = ui->identifier_lineEdit_search_0->text();
QString text1 = ui->identifier_lineEdit_search_1->text();
QString text2 = ui->identifier_lineEdit_search_2->text();
QString text3 = ui->identifier_lineEdit_search_3->text();
QString text4 = ui->identifier_lineEdit_search_4->text();

for (int i = 0; i < Storage::identifier.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
if (Storage::identifier.at(i)->dataString.contains(text0,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text1,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text2,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text3,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text4,Qt::CaseInsensitive))
{
tempList << Storage::identifier.at(i);
}
}

ui->identifier_listWidget->clear();
for (int i = 0; i < tempList.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
listWidget_addItemPlusTooltip(ui->identifier_listWidget,tempList.at(i)->dataString);
}

searchIn_identifier_listWidget_eventLoopControl = true;
}

Thats working but its really not beatiful. Still searching for a better solution. I'm thinking about some filtering, but I dont know, filter what, a function? How can I filter a Slot.

---

Added after 9 minutes:

and like that I need an extra varaible for every of those "Search-ListWidgets" and cannot write generic code for every of those "Search-ListWidgets"

[Lesiok]

OK, try this (lines 12,13,30,40) and write what is debug output :

void SomeClass::searchIn_identifier_listWidget()
{
searchIn_identifier_listWidget_eventLoopControl = false;
 
QList<Identifier*> tempList;
 
QString text0 = ui->identifier_lineEdit_search_0->text();
QString text1 = ui->identifier_lineEdit_search_1->text();
QString text2 = ui->identifier_lineEdit_search_2->text();
QString text3 = ui->identifier_lineEdit_search_3->text();
QString text4 = ui->identifier_lineEdit_search_4->text();
QElapsedTimer timer;
timer.start();
 
for (int i = 0; i < Storage::identifier.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
if (Storage::identifier.at(i)->dataString.contains(text0,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text1,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text2,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text3,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text4,Qt::CaseInsensitive))
{
tempList << Storage::identifier.at(i);
}
}
 
qDebug() << "First loop : " << timer.elapsed();
 
ui->identifier_listWidget->clear();
for (int i = 0; i < tempList.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
listWidget_addItemPlusTooltip(ui->identifier_listWidget,tempList.at(i)->dataString);
}
qDebug() << "Second loop : " << timer.elapsed();
 
searchIn_identifier_listWidget_eventLoopControl = true;
}

void SomeClass::searchIn_identifier_listWidget()
{
searchIn_identifier_listWidget_eventLoopControl = false;

QList<Identifier*> tempList;

QString text0 = ui->identifier_lineEdit_search_0->text();
QString text1 = ui->identifier_lineEdit_search_1->text();
QString text2 = ui->identifier_lineEdit_search_2->text();
QString text3 = ui->identifier_lineEdit_search_3->text();
QString text4 = ui->identifier_lineEdit_search_4->text();
QElapsedTimer timer;
timer.start();

for (int i = 0; i < Storage::identifier.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
if (Storage::identifier.at(i)->dataString.contains(text0,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text1,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text2,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text3,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text4,Qt::CaseInsensitive))
{
tempList << Storage::identifier.at(i);
}
}

qDebug() << "First loop : " << timer.elapsed();

ui->identifier_listWidget->clear();
for (int i = 0; i < tempList.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
listWidget_addItemPlusTooltip(ui->identifier_listWidget,tempList.at(i)->dataString);
}
qDebug() << "Second loop : " << timer.elapsed();

searchIn_identifier_listWidget_eventLoopControl = true;
}

To copy to clipboard, switch view to plain text mode 

[anda_skoa]

Thats working but its really not beatiful.

I see, still in the hate yourself phase.

Still searching for a better solution.

Like not creating potentially thousands of items nobody is every going to see?

Oh my, if only someone would have suggested something like that.
It would be so great if there were something that would only need as many items as it can display at the same time!

In such an utopian world one could then look into optimizing the filtering itself.
Wouldn't it be wonderful if could store a previous result and filter that when the criteria gets more precise instead of filtering everything over again?
Boy, if only we could know what the previous search looked for!

Cheers,
_

[Ini]

OK, try this (lines 12,13,30,40) and write what is debug output :

void SomeClass::searchIn_identifier_listWidget()
{
searchIn_identifier_listWidget_eventLoopControl = false;
 
QList<Identifier*> tempList;
 
QString text0 = ui->identifier_lineEdit_search_0->text();
QString text1 = ui->identifier_lineEdit_search_1->text();
QString text2 = ui->identifier_lineEdit_search_2->text();
QString text3 = ui->identifier_lineEdit_search_3->text();
QString text4 = ui->identifier_lineEdit_search_4->text();
QElapsedTimer timer;
timer.start();
 
for (int i = 0; i < Storage::identifier.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
if (Storage::identifier.at(i)->dataString.contains(text0,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text1,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text2,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text3,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text4,Qt::CaseInsensitive))
{
tempList << Storage::identifier.at(i);
}
}
 
qDebug() << "First loop : " << timer.elapsed();
 
ui->identifier_listWidget->clear();
for (int i = 0; i < tempList.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
listWidget_addItemPlusTooltip(ui->identifier_listWidget,tempList.at(i)->dataString);
}
qDebug() << "Second loop : " << timer.elapsed();
 
searchIn_identifier_listWidget_eventLoopControl = true;
}

void SomeClass::searchIn_identifier_listWidget()
{
searchIn_identifier_listWidget_eventLoopControl = false;

QList<Identifier*> tempList;

QString text0 = ui->identifier_lineEdit_search_0->text();
QString text1 = ui->identifier_lineEdit_search_1->text();
QString text2 = ui->identifier_lineEdit_search_2->text();
QString text3 = ui->identifier_lineEdit_search_3->text();
QString text4 = ui->identifier_lineEdit_search_4->text();
QElapsedTimer timer;
timer.start();

for (int i = 0; i < Storage::identifier.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
if (Storage::identifier.at(i)->dataString.contains(text0,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text1,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text2,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text3,Qt::CaseInsensitive) &&
Storage::identifier.at(i)->dataString.contains(text4,Qt::CaseInsensitive))
{
tempList << Storage::identifier.at(i);
}
}

qDebug() << "First loop : " << timer.elapsed();

ui->identifier_listWidget->clear();
for (int i = 0; i < tempList.count(); i++) {
qApp->processEvents();
if (searchIn_identifier_listWidget_eventLoopControl) {
return;
}
listWidget_addItemPlusTooltip(ui->identifier_listWidget,tempList.at(i)->dataString);
}
qDebug() << "Second loop : " << timer.elapsed();

searchIn_identifier_listWidget_eventLoopControl = true;
}

To copy to clipboard, switch view to plain text mode 

I don't see the point of the timer, but nvm here is the data:

First loop : 6
First loop : 12
First loop : 24
First loop : 24
First loop : 30
First loop : 29
First loop : 33
First loop : 24
First loop : 35
First loop : 25
First loop : 33
Second loop : 96
First loop : 30
Second loop : 92
First loop : 26
Second loop : 78
Second loop : 606
First loop : 35
Second loop : 82
First loop : 29
Second loop : 76
Second loop : 1128
First loop : 25
Second loop : 73
Second loop : 1641
Second loop : 5734

Its as expected first loop always constant and second loop depends on what i typed in. If I type in only 1 character second loop takes like 3 minutes or so

I see, still in the hate yourself phase.


Like not creating potentially thousands of items nobody is every going to see?

Oh my, if only someone would have suggested something like that.
It would be so great if there were something that would only need as many items as it can display at the same time!

In such an utopian world one could then look into optimizing the filtering itself.
Wouldn't it be wonderful if could store a previous result and filter that when the criteria gets more precise instead of filtering everything over again?
Boy, if only we could know what the previous search looked for!

Cheers,
_

I dont understand why should nobody see them. If there is no Word in the searchlines all are visible. Its just a standard-filter, it seems Qt has no Functions to deal with the nested-loops or I did not find them so far. Thats why the wortkaround.

Thank you for all help, but the hate stuff is not very helpfull . Helpful it would be so make a suggestion without nested loops. But i think there is no.

And thats true what you say it would be faster to store the previous data. But that does not solve the problem.

[Lesiok]

Temporarily remove procesEvents() from code and show debug output. All outputs are in ms. 5734 ms is less then 6 seconds ! You are talking about minutes.