QHash intersection
-
I have two
QHash<int, QString>
, the first one is a list of fruits, the second is a list of selected fruits. I want to intersect them preserving the key of the fruits. For example:QHash<int, QString> fruits = { { 0, "banana" }, { 1, "mango" }, { 2, "tomato" }, { 8, "apple" }, { 9, "orange" }, { 12, "grape" }, { 13, "melon" }, { 14, "lemon" } }; QHash<int, QString> selected = { { 0, "banana" }, { 1, "mango" }, { 2, "tomato" }, { 3, "melon" }, { 4, "lemon" } };
it would return:
QHash<int, QString> intersection = { { 0, "banana" }, { 1, "mango" }, { 2, "tomato" }, { 13, "melon" }, { 14, "lemon" } };
As you can see, it preserverd the key of banana, mango, tomato, melon and lemon from the fruits.
How can I do that? As far as I know, the only list that has intersection is
QSet
but it's not suitable in this case. -
Not necessarily the best solution (depends on what you're optimising for), but how about something like:
const QSet<QString> selectedValues = QSet<QString>::fromList(selected.values()); QHash<int, QString> intersection; for (auto iter = fruits.constBegin(); iter != fruits.constEnd(); ++iter) { if (selectedValues.contains(iter.value())) { intersection.insert(iter.key(), iter.value()); } }
Cheers.
-
Not necessarily the best solution (depends on what you're optimising for), but how about something like:
const QSet<QString> selectedValues = QSet<QString>::fromList(selected.values()); QHash<int, QString> intersection; for (auto iter = fruits.constBegin(); iter != fruits.constEnd(); ++iter) { if (selectedValues.contains(iter.value())) { intersection.insert(iter.key(), iter.value()); } }
Cheers.
Not necessarily the best solution
It is the best solution, with one tiny remark: To maximize performance the resulting hash should be sized before inserting. However, I really doubt it much matters here.
-
Not necessarily the best solution
It is the best solution, with one tiny remark: To maximize performance the resulting hash should be sized before inserting. However, I really doubt it much matters here.
@kshegunov - I can't size
QHash
as I don't know how many items is going to be inserted on it. - but the answer is great. I will accept as the right answer, but if anyone else knows how to do that using other algorithm, please, share. -
@kshegunov said:
To maximize performance the resulting hash should be sized before inserting.
You're probably right, but given the lack of information we have about the use case, I'd say that's really a premature optimisation ;)
For example:
- what if
fruits
andselected
both typically contain 100's of thousands of items, while the intersection is typically only a couple of items? Then aQHash::reserve
would probably be more expensive than not; or - if all three are really large (ie there are more items in common than distinct), then it might make more sense to construct
intersection
as a copy offruits
, then make the loop remove items, rather than insert (might depend on the implementation / efficiency of QHash's copy constructor).
But yeah, an
intersection.reserve(qMin(fruits.size(), selected.size());
might be a performance improvement, depending on the details of the use case :)Cheers.
- what if
-
@kshegunov said:
To maximize performance the resulting hash should be sized before inserting.
You're probably right, but given the lack of information we have about the use case, I'd say that's really a premature optimisation ;)
For example:
- what if
fruits
andselected
both typically contain 100's of thousands of items, while the intersection is typically only a couple of items? Then aQHash::reserve
would probably be more expensive than not; or - if all three are really large (ie there are more items in common than distinct), then it might make more sense to construct
intersection
as a copy offruits
, then make the loop remove items, rather than insert (might depend on the implementation / efficiency of QHash's copy constructor).
But yeah, an
intersection.reserve(qMin(fruits.size(), selected.size());
might be a performance improvement, depending on the details of the use case :)Cheers.
@Paul-Colby said:
You're probably right, but given the lack of information we have about the use case, I'd say that's really a premature optimisation
Agreed.
- what if
-
@kshegunov said:
To maximize performance the resulting hash should be sized before inserting.
You're probably right, but given the lack of information we have about the use case, I'd say that's really a premature optimisation ;)
For example:
- what if
fruits
andselected
both typically contain 100's of thousands of items, while the intersection is typically only a couple of items? Then aQHash::reserve
would probably be more expensive than not; or - if all three are really large (ie there are more items in common than distinct), then it might make more sense to construct
intersection
as a copy offruits
, then make the loop remove items, rather than insert (might depend on the implementation / efficiency of QHash's copy constructor).
But yeah, an
intersection.reserve(qMin(fruits.size(), selected.size());
might be a performance improvement, depending on the details of the use case :)Cheers.
@Paul-Colby - The size will vary, the items change according to the user record.
That's why I said I can't put a size in QHash, but the only thing I can assure is: The size isn't always big, I mean, the example I gave is pretty much the same size as others - the selected items, but the fruits can be big.
I described for you how it will be. The fruit list will be big - most of the cases, but the selected items won't, most of the time it will have a few. The approach you presented is the best for that? I mean, inserted instead of deleting? - what if
-
@Volebab said:
The fruit list will be big - most of the cases, but the selected items won't, most of the time it will have a few. The approach you presented is the best for that? I mean, inserted instead of deleting?
Yeah, in that case inserts would probably be more efficient (both CPU and memory utilization) than deletes. If it really matters, then I'd recommend benchmarking a few alternatives after establishing where the bottlenecks really are :)
https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize
Cheers.
-
@Volebab said:
The fruit list will be big - most of the cases, but the selected items won't, most of the time it will have a few. The approach you presented is the best for that? I mean, inserted instead of deleting?
Yeah, in that case inserts would probably be more efficient (both CPU and memory utilization) than deletes. If it really matters, then I'd recommend benchmarking a few alternatives after establishing where the bottlenecks really are :)
https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize
Cheers.
@Paul-Colby I will be reading, and I was reading things about optimization related to Qt. Thank you.