Efficient Intersection and Union of Lists of Strings

Question

I need to efficiently find the ratio of (intersection size / union size) for pairs of Lists of strings. The lists are small (mostly about 3 to 10 items), but I have a huge number of them (~300K) and have to do this on every pair, so I need this actual computation to be as efficient as possible. The strings themselves are short unicode strings -- averaging around 5-10 unicode characters.

The accepted answer here Efficiently compute Intersection of two Sets in Java? looked extremely helpful but (likely because my sets are small (?)) I haven't gotten much improvement by using the approach suggested in the accepted answer.

Here's what I have so far:

protected double uuEdgeWeight(UVertex u1, UVertex u2) {
    Set<String> u1Tokens = new HashSet<String>(u1.getTokenlist());
    List<String> u2Tokens = u2.getTokenlist();

    int intersection = 0;
    int union = u1Tokens.size();
    for (String s:u2Tokens) {
        if (u1Tokens.contains(s)) {
            intersection++;
        } else {
            union++;
        }
    }
    return ((double) intersection / union);

My question is, is there anything I can do to improve this, given that I'm working with Strings which may be more time consuming to check equality than other data types.

I think because I'm comparing multiple u2's against the same u1, I could get some improvement by doing the cloning of u2 into a HashSet outside of the loop (which isn't shown -- meaning I'd pass in the HashSet instead of the object from which I could pull the list and then clone into a set)

Anything else I can do to squeak out even a small improvement here?

Thanks in advance!

Update

I've updated the numeric specifics of my problem above. Also, due to the nature of the data, most (90%?) of the intersections are going to be empty. My initial attempt at this used the clone the set and then retainAll the items in the other set approach to find the intersection, and then shortcuts out before doing the clone and addAll to find the union. That was about as efficient as the code posted above, presumably because of the trade of between it being a slower algorithm overall versus being able to shortcut out a lot of the time. So, I'm thinking about ways to take advantage of the infrequency of overlapping sets, and would appreciate any suggestions in that regard.

Thanks in advance!

Answer 1

You would get a large improvement by moving the HashSet outside of the loop.

If the HashSet really has only got a few entries in it then you are probably actually just as fast to use an Array - since traversing an array is much simpler/faster. I'm not sure where the threshold would lie but I'd measure both - and be sure that you do the measurements correctly. (i.e. warm up loops before timed loops, etc).

One thing to try might be using a sorted array for the things to compare against. Scan until you go past current and you can immediately abort the search. That will improve processor branch prediction and reduce the number of comparisons a bit.

Answer 2

If you want to optimize for this function (not sure if it actually works in your context) you could assign each unique String an Int value, when the String is added to the UVertex set that Int as a bit in a BitSet.

This function should then become a set.or(otherset) and a set.and(otherset). Depending on the number of unique Strings that could be efficient.