QList vs QHash - faster "contains" with QHash?

maximus

Hi,

I want to store a List of integer QList<int>.
I'm not sure how fast is ".contains" when using a QList.

I want it to be very fast (O(n)), because the list will grow big, is that the case with QList?
Or maybe I should look at QHash instead?

example of use.
lst.insert(23);
lst.insert(35);

if (lst.contains(35)) {
do something
}

SGaist

Hi,

QVector would be recommended for that use case. How big can it become ?

maximus

@SGaist

The List could be between 1 and 1000.

I'm more concerned about the time to execute if (lst.contains(x))
There will be a lot of check with that kind of if, so I would prefer to have a constant check, I know QHash .contains is constant, but haven't found info on QList lookup

Thanks

Chris Kawa

Algorithm complexity is only half of the story. The other, significantly more important on hardware today, is memory access pattern. As @SGaist said, a QVector and its indexOf might be a lot faster because of cache friendliness. QList is almost always a worse idea because of the reverse - it's extremely cache unfriendly.
The only way to be sure though is by actually measuring. Theoretical algorithm complexity is not a good indicator of anything these days, especially on a small data set like this (yes, i consider 1000 elements small).

maximus

Thanks for the insight,

I think I may be overthinking this one. I will start with a QList<int> and change later if my data set get bigger.

An example of my data set:
Data is received from Sensors over the air, a sensor can send 4 messages per second. When receiving a message from a sensor, I need to check the Sensor ID to see if it's my list before doing some calculation. The Max I can see getting is around 100 sensors (4*100) messages per second. So that's basically 400 "if check" every second to check if the sensor ID is in my list.

Chris Kawa

I would reconsider. QList should always be at the end of your choice list. It has very little benefits. I would (always?) start with QVector and then, only if needed, move to something else.
400 vector checks per second is not a big load for modern CPUs which get into thousands of MIPS these days. Cache unfriendly structures (like QList) is what kills performance most of the time.

maximus

Perfect, QVector has the same method so nothing to do on my side, I like that. QVector it will be!

Asperamanca

@Chris-Kawa said:

I would reconsider. QList should always be at the end of your choice list. It has very little benefits. I would (always?) start with QVector and then, only if needed, move to something else.
400 vector checks per second is not a big load for modern CPUs which get into thousands of MIPS these days. Cache unfriendly structures (like QList) is what kills performance most of the time.

Just out of interest: Why not use QSet in this case? (Assuming the ID is unique)

Chris Kawa

@Asperamanca said:

Just out of interest: Why not use QSet in this case? (Assuming the ID is unique)

Same reason - QSet is not a contiguous memory chunk.
It is basically a QHash<T, DummyType>, which in turn is basically a list of buckets. Although a little better than a full blown linked list it potentially still has poor cache locality qualities.

For the record - I'm not saying you should not use a QSet or any other container type or that they are always slower. What I am saying is you should measure, and if you're not interested enough to do that then QVector is a very good default, that will in many cases perform better than faster on paper specialized containers. But please do measure your particular cases.

maximus

Thanks for the added details.

Maybe the Qt docs could be a little more specific on the best-case and worst-case use on each containers.
I see diverging opinions, see answer here that favors QList.

For my use case, I will probably use a QHash that can check directly (O(1)) if an item is present in the bucket or not since I do not know the algorithm complexity of ".contains" of QVector and QList.

Chris Kawa

For vector or a list contains is a linear search (simply calls std::find in the implementation), no way around it. If you can guarantee the vector is sorted you can use std::lower_bound to reduce that to binary search (logarithmic complexity).

Note that the 1 in O(1) of QHash might be expensive for some types and it's possible that a vector lookup (for some sizes) is still faster (operator==). If in doubt - measure.