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.


  • Qt Champions 2016

    @Paul-Colby

    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 and selected both typically contain 100's of thousands of items, while the intersection is typically only a couple of items? Then a QHash::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 of fruits, 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.


  • Qt Champions 2016

    @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.



  • @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?



  • @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.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.