1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Just to clarify: Each serial number can have an arbitrary number of options associated with it, and it's just a characteristic of the input format that a line contains just one option for a serial number? \$\endgroup\$ – Stingy Aug 9 '17 at 20:41
  • \$\begingroup\$ Also, I am confused how you got the number \$5668650\$, could you elaborate on that please? \${350\choose 3}=7084700\$, and \${350\choose 2}=61075\$, and \$2^{350}=2.29349861599007 \cdot 10^{105}\$, so maybe I misunderstood something in your question. \$\endgroup\$ – Stingy Aug 9 '17 at 21:43
  • \$\begingroup\$ I don't want permutations. I am interested in combinations and I don't want position specific or repetition. Formula I am using is n!/r!(n-r)! \$\endgroup\$ – Felix Torssell Aug 10 '17 at 5:46
  • \$\begingroup\$ That is correct Stingy. Each serial number has about 60 lines. 1 for each of its options. And it can't have the same option twice. \$\endgroup\$ – Felix Torssell Aug 10 '17 at 5:48
  • \$\begingroup\$ \$n\choose r\$ is equivalent to \$\frac{n!}{r!\cdot(n-r)!}\$. It doesn't count permutations. So the question how you got 5668650 still stands. \$\endgroup\$ – Stingy Aug 10 '17 at 7:16
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is a great answer and it points out my terrible shortcuts ex. currentCombo.add("");. Your point about Mapping options and serialnumbers to better reflect the relationship was also spot on and I will look into it. \$\endgroup\$ – Felix Torssell Aug 11 '17 at 11:32
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ the System.out.println is just for me to get an idea of speed while debuging. but the rest I completely agree with. \$\endgroup\$ – Felix Torssell Aug 10 '17 at 7:43
  • \$\begingroup\$ Care to not change the speed when observing it. System.out.println is horrendously slow compared to doing everything else in that loop. Generally avoid IO (as is printing to console) like the plague in "high performance" loops. \$\endgroup\$ – Vogel612 Aug 10 '17 at 7:45
  • \$\begingroup\$ I will keep that in mind. Right now I have the System.out.println in the outer loop and not the inner so it should make a big difference for the overall speed. \$\endgroup\$ – Felix Torssell Aug 10 '17 at 7:50
  • \$\begingroup\$ should not make a big difference* \$\endgroup\$ – Felix Torssell Aug 10 '17 at 7:57
  • \$\begingroup\$ I find your point on using <Object> on the right hand side of an assignment a bit unclear. Is it the use of Object as a generic parameter that you criticize, or the fact that a type parameter is explicitly specified in the constructor even though it could be inferred by the compiler? Your suggestion of using the diamond operator suggests the latter. If this is what you meant, maybe you could elaborate on why you think it is a "really bad idea", because, apart from it being redundant, I can't think of any harm done by it. \$\endgroup\$ – Stingy Aug 10 '17 at 22:49
0
\$\begingroup\$

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;
                        }
\$\endgroup\$
  • \$\begingroup\$ This is not a solution to your problem, but gambling. The only guarantee you can get from hash codes is that objects with different hash codes are unequal (provided that hashCode() and equals(Object) are implemented correctly). But the reverse is not true. Objects with equal hash codes are not necessarily equal. So in your new code, you run the risk of disregarding an option combination if another combination produces the same hash (however unlikely this may be). \$\endgroup\$ – Stingy Aug 11 '17 at 7:05
  • \$\begingroup\$ Is there a good hash function for 64 bit that you recommend? there shouldnt be any collisions in a 64 bit hash \$\endgroup\$ – Felix Torssell Aug 11 '17 at 12:01
  • \$\begingroup\$ Where did you get the information that equals(Object) "uses" hashCode() from? It just has to obey the contract of hashCode(). Furthermore, I think there are more efficient approaches to your problem than trying to design a hash-function that is collision proof for your usage. Firstly, if you find that a combo with a hash equal to that of currentCombo has already been evaluated, you can still compare the combos themselves. It's just that […] \$\endgroup\$ – Stingy Aug 11 '17 at 13:30
  • \$\begingroup\$ […] you don't need to compare two objects when the hashes don't match, because equal objects must have equal hashes. And this is what a HashSet effectively does anyway, so you don't need to re-invent the wheel. But apart from that, if you initialize j to i + 1 instead of 0, then you will never encounter the same combination twice in the first place (provided the List you're iterating over doesn't contain duplicates), rendering the variable previousCombos completely unnecessary and, in turn, automatically solving your problem. \$\endgroup\$ – Stingy Aug 11 '17 at 13:30
  • \$\begingroup\$ This is not ment for finding duplicate options i.e combo option1-1-2 but for finding if the combo is the same but with another order ex option1-2-3 is the same as 2-1-3. So intitializing j to i + 1 would not stop me from encountering same combo in different order as far as i can tell \$\endgroup\$ – Felix Torssell Aug 11 '17 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.