Find frequency of combinations in large data set

Question

My concern is performance of the code. It takes way longer than I would like. I would be willing to give up some memory for higher performance.

I have JTable with serial numbers in column1 and options in column2. With every option the person has chosen on a new row.

Each serial number can only have 1 of each options. Each serial number usually has around 60 options.

My dataset is very large (100k-1m rows).

I have a total of 350 options but I realize that it is impossible to get combinations of all of them as that would be 7084700 combinations.

My combinations are not position specific.

ex:

option1 option2 option3

is the same as

option2 option1 option3

Here is an Example of how my data looks:

1   a
1   b
1   c
2   a
2   b
2   c
3   a
3   b
4   b
4   c
4   d
5   a
5   b
5   c
5   d
6   c
6   d
6   e
8   d
8   e

And here is the output after calculation:

a   b       57%
a   c       42%
a   d       14%
a   e       0%
b   c       42%
b   d       14%
b   e       0%
c   d       14%
c   e       0%
d   e       0%
a   b   c   42%
a   b   d   14%
a   c   d   14%
b   c   d   14%
a   b   e   0%
a   c   e   0%
a   d   e   0%
b   c   e   0%
b   d   e   0%
c   d   e   0%

Here is my code to get the frequency of combinations of 3 options.

//used to get number of combinations (n!/(r!(n-r)!)
    static BigInteger binomial(final int N, final int K) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 0; k < K; k++) {
            ret = ret.multiply(BigInteger.valueOf(N - k)).divide(BigInteger.valueOf(k + 1));
        }
        return ret;
    }

    // method for calculalating combinations of 3
    public void calc3(JTable table) {
        currentSerialNums2 = new ArrayList<Object>(1500);
        options = new ArrayList<Object>(table.getRowCount());
        serialNum = new ArrayList<Object>(table.getRowCount());
        currentSerialNums = new ArrayList<Object>(1000);
        DistinctOptions = new ArrayList<Object>();

        // Loop through all rows and extract options and serial numbers to lists
        for (int i = 0; i < table.getRowCount(); i++) {
            // add all objects from 2nd column in table to options list
            options.add(table.getModel().getValueAt(table.convertRowIndexToModel(i), 1));

            // add all objects from first column in table to serialNum list
            serialNum.add(table.getModel().getValueAt(table.convertRowIndexToModel(i), 0));

        }

        // Extract unique options and save to List<Object> DistinctOptions. This is a github library called jstreams but I could use hashset aswell
        DistinctOptions = Stream.create(options).distinct().toList();

        // declaring these ArrayLists with custom capacity to avoid constant resizing
        previousCombos = new ArrayList<List<Object>>(binomial(DistinctOptions.size(), 3).intValue());
        SerialNumsPerOption = new ArrayList<List<Object>>(DistinctOptions.size());

        // Adding all serial numbers for each option in a List<List<Object>>
        for (int i = 0; i < DistinctOptions.size(); i++) {
            for (int y = 0; y < table.getRowCount(); y++) {
                if (DistinctOptions.get(i).equals(options.get(y))) {
                    currentSerialNums.add(serialNum.get(y));
                }
            }

            if (!currentSerialNums.isEmpty()) {
                if (i == 0) {
                }
                currentSerialNums2 = new ArrayList<Object>(currentSerialNums);
                SerialNumsPerOption.add(currentSerialNums2);
                currentSerialNums.clear();
            }
        }

        for (int i = 0; i < SerialNumsPerOption.size(); i++) {
            compareSerialNums = new HashSet<>(SerialNumsPerOption.get(i));
            System.out.println("next");
            outerloop2: for (int j = 0; j < SerialNumsPerOption.size(); j++) {
                if (DistinctOptions.get(i).equals(DistinctOptions.get(j))) {
                    continue;
                }
                currentCombo = new ArrayList<Object>();
                currentCombo.add(DistinctOptions.get(i));
                currentCombo.add(DistinctOptions.get(j));
                currentCombo.add("");
                for (int a = 0; a < previousCombos.size(); a++) {
                    if (previousCombos.get(a).containsAll(currentCombo)) {
                        continue outerloop2;
                    }
                }

                compare2 = new HashSet<>(SerialNumsPerOption.get(j));
                compare2.retainAll(compareSerialNums);             
                currentCombo.add(compare2.size());
                previousCombos.add(currentCombo);
                innerloop: for (int j2 = 0; j2 < SerialNumsPerOption.size(); j2++) {
                    if (DistinctOptions.get(i).equals(DistinctOptions.get(j2))) {
                        continue;
                    }
                    if (DistinctOptions.get(j).equals(DistinctOptions.get(j2))) {
                        continue;
                    }
                    currentCombo = new ArrayList<Object>(4);
                    currentCombo.add(DistinctOptions.get(i));
                    currentCombo.add(DistinctOptions.get(j));
                    currentCombo.add(DistinctOptions.get(j2));
                    for (int a = 0; a < previousCombos.size(); a++) {
                        if (previousCombos.get(a).containsAll(currentCombo)) {
                            continue innerloop;
                        }
                    }
                    SerialNumsPerOption.get(j2).retainAll(compare2);
                    currentCombo.add(SerialNumsPerOption.get(j2).size());
                    previousCombos.add(currentCombo);

                }
            }
        }
        System.out.println("Saving to list");
        tabledata = new Object[previousCombos.size()][4];
        for (int i = 0; i < previousCombos.size(); i++) {
            for (int j = 0; j < 4; j++) {
                if (previousCombos.get(i).get(j) != null) {
                    tabledata[i][j] = previousCombos.get(i).get(j);
                }
            }
        }
        System.out.println("Calculations completed");
    }

What is taking all the time:

Comparing the two lists to see how many serial numbers the two/three options share using the retainAll. Is there an alternative here? Since there are all unique values, converting to a set works but it takes more time to convert the values than it takes to do retainAll on two Lists.

comparing current combination with all the previous ones to eliminate ones that I already have (order doesn't matter)

for (int a = 0; a < previousCombos.size(); a++) {
                        if (previousCombos.get(a).containsAll(currentCombo)) {
                            continue innerloop;
                        }
                    }

EDIT:

Stingy´s answer made my improvements obsolete

Answer 1

First, a general note on this answer: I am going to use the type names SerialNumber and Option, even though in your code they're both represented by Objects, because it's easier to understand that way.

• The first thing that struck me as a potential source of unnecessary complication is the fact that, in your code, you mimic the input format of the data (i.e. two columns) by storing the serial numbers and options in two separate lists, even though this format doesn't reflect the actual relationship between serial numbers and options at all. Why don't you, instead, store the data in a Map<SerialNumber, Set<Option>>? I think that this alone would make everything easier, even if it's just by making the code more readable. The same is true for the reverse. Instead of making a List<List<SerialNumber>> whose indexes just happen to be related to the indexes of DistinctOptions, it would be much clearer if you used a Map<Option, Set<SerialNumber>>, because then, the relationship you want to represent would be directly reflected by the code, reducing the potential for both bugs and headaches when trying to figure out the large for loop where you compare the "combos".
• Regardless of the above, you make SerialNumsPerOption a List<List<SerialNumber>>, but later, when you access the elements of this List, you convert them to a Set before using them. So why don't you make SerialNumsPerOption a List<Set<SerialNumber>> in the first place (which implies making currentSerialNums2 and currentSerialNums Sets instead of Lists)? Creating these effectively unnecessary Lists just to convert them to a Set later on when you need their contents makes the code unnecessarily complicated.
• Also, where are all those variables used in calc3(JTable) (currentSerialNums2, options etc.) declared? Judging by the code you provided, they seem to fulfill the purpose of local variables because you assign them at the beginning of the method, yet I see no declarations of them. I shudder to think what kind of object (or class, in case they are static fields) this must be that holds all those fields.
• Regardless of whether they are local variables or fields, what makes your code appear more intimidating than it actually is is where you first use these variables in the method. For instance, the variables currentSerialNums2 and currentSerialNums are needed exclusively in the for loop accompanied by the comment "Adding all serial numbers for each option in a List<List<Object>>" (at least within the method calc3(JTable), who knows what horrifying scenarios outside it call for them …), and they don't even have to keep their state from one loop iteration to the next, so you might as well "introduce" (or declare if they should indeed be local) them inside this for loop.

• I had a "?????" moment when I saw this line:

  if (DistinctOptions.get(i).equals(DistinctOptions.get(j))) {
  

  I thought DistinctOptions was supposed to contain only distinct options. So how can DistinctOptions.get(i) and DistinctOptions.get(j) be equal? Right, if i and j are equal. But then, why not just do this:

  if (i == j) {
  

  Actually, you can save yourself this trouble entirely by initializing j as int j = i + 1 instead of int j = 0, since the order of options doesn't matter and, for your purpose, i and j are interchangeable.

• What is this:

  currentCombo.add("");
  

  A red herring? But wait, it gets even more confusing:

  currentCombo.add(compare2.size());
  

  So now, currentCombo also contains an Integer apart from two Options and a mysterious empty String. Ah, the integer is just the number of serial numbers that have both of the options. But then, what is this integer doing in currentCombo itself? It is not an Option but just a value associated with a combination of Options and therefore should not be placed on the same level as the Options. Again, a better way to represent this relationship would be a Map<Set<Option>, Integer> (note the use of Set instead of List).

• After looking at the innerloop, the for loop where you declare j2, it finally becomes apparent what the purpose of this mysterious empty String observed earlier was, and the revelation is not relieving at all. It turns out that you seem to try to hard code a recursive process using multiple nested loops. Apart from the fact that this is a form of code duplication, what will you do if you want to include combinations of 4 options instead of only 3? Create another nested loop and add more empty Strings in the outer loops? This simply cannot be it. You are implementing a recursive process, so the code design should reflect this.

Taking all of the above into account, a final remark about your code in general. I think your code would be clearer if you separated the logic of generating all possible n-size option combinations from the logic of determining their frequency in your input data. Actually, once you have the first part working, the second part should be a piece of cake, since, for every combination, you only have to go through every serial number and check if the combination is contained in the serial number's options.

But note that it will only be a piece of cake if the types of your variables actually reflect what you are trying to represent with them. The loop construct you yourself criticized in your question is a prime example:

for (int a = 0; a < previousCombos.size(); a++) {
    if (previousCombos.get(a).containsAll(currentCombo)) {
        continue innerloop;
    }
}

Here, both previousCombos.get(a) and currentCombo should be a Set that only contains options (a Set fits here perfectly, because it cannot contain duplicate elements and the order of the elements doesn't matter). The number of serial numbers containing this combination is only a value that is associated with this combination and not a part of the combination itself, and an empty String belongs here even less, because it is only relevant for the output format and has nothing to do with the combinatorial logic itself. If you apply these changes, the above code could be replaced by this:

if (previousCombos.contains(currentCombo) {
    continue innerloop;
}

And the simpler the design of your code is, the easier it will be to spot opportunities where you can improve performance, which is, after all, what your question was originally about.

Answer 2

I don't know what your whole setup is, but I would recommend that you use the model/view separation. Your data is stored somewhere as decent Java objects in memory or some database; your JTable is purely for displaying the data and not for storing and retrieving data (Object ouch!).

Another tip that could be useful: look at BitSet. You could fill those up with your options and they easily compare different bitsets.

Answer 3

Soo ... some egregious pain points in your code. I strongly recommend you return to get another review:

1. <Object> on the right hand side of an assignment is a really bad idea. Instead of using something messy like this, you should be using the "Diamond Operator" (RHS Type Inference) like so:

   currentSerialNums2 = new ArrayList<>(1500);
   

2. 1500 is a magic number. Why 1500? The same applies for 1000.

3. DistinctOptions as well as SerialNumsPerOption should be written as lowerCamelCase

4. Because Swing is older than most university undergraduates by now it's generally considered to be sucky and bad. First and foremost, it doesn't support proper strong typing for input retrieval from Tables and similar components. You'll have significantly cleaner code when you move from Swing to JavaFX which is integrated significantly better with the "new" language features like Generics (Java 6) and syntactic sugars.

5. The declarations for all these more or less local variables you have there seem to be on the class-level, which is ... bad. Declare variables in the smallest possible scope to reduce how much things a maintainer / reader needs to juggle in their head to understand the code.

6. Comments should describe the Why not the What. The What is always already described by the code. When the code mismatches with the comments, what are you going to do? Trust the code and delete the comment, because the code is always right? Or Adjust the code to the comment, because comments are business requirements?

7. Don't use System.out.println to communicate with the user when you have a GUI. Swing has Dialogs and JOptionPane for this exact purpose. Similar facilities exist for JavaFX

Answer 4

I did some changes and managed to speed up the function 10x.

This is the loop that was taking all the time. Its purpose was to check if the current combination has already been viewed.

Old code:

for (int a = 0; a < previousCombos.size(); a++) {
                    if (previousCombos.get(a).containsAll(currentCombo)) {
                        continue outerloop2;
                    }
                }

New code:

    public static Comparator<Object> comboSorter = new Comparator<Object>() {

    public int compare(Object o1, Object o2) {
       String object1 = o1.toString();
       String object2 = o2.toString();
       return object2.compareTo(object1);
    }};

Collections.sort(currentCombo, comboSorter);
                        if (previousCombosList.contains(currentCombo.hashCode())) {
                            continue innerloop;
                        }