0

In Java, working with binary strings (e.g. "00010010", zeroes are added in the beginning when creating these binary strings for the purpose of my program). I have the function

private static boolean isJinSuperSets(String J, List<String> superSets) {

    for (String superJ : superSets)
        if (superJ.equals(J)) return true;

    return false;
}

that checks if a binary string J is contained in the list of binary strings superSets.

I use equals() on the String object but I would like to speed up this code by converting binary strings to binary numbers and doing bitwise operation AND to see if they are equal.

Could you please give me a few tricks on how to accomplish that?

Sophie Sperner
  • 4,428
  • 8
  • 35
  • 55
  • 5
    If you want your program to be as slow as possible, by all means do math with strings. – harold Jul 15 '12 at 08:58
  • 2
    Probably the answer to http://stackoverflow.com/questions/4211705/binary-to-text-in-java will do. – vainolo Jul 15 '12 at 08:58
  • 3
    I don't think this will speed up anything (quite the contrary) if you only do the conversion within the scope of the method. You'd need to change your interface to use the binary format throughout. BigInteger can be used for that, by the way. – Thilo Jul 15 '12 at 08:58
  • why do you think that will speed up the code? – Cacho Santa Jul 15 '12 at 08:59
  • "Yes, maybe it is better to store ArrayList instead if List, but I see on the web everywhere only how to store binary as a String.", - oh, sorry, I though about bit representation of the Integer and then I do not need to bother about strings. Not sure how BigInteger can help, it just a big integer, like Long? ) – Sophie Sperner Jul 15 '12 at 09:00
  • 2
    Could your method not be simplified to return superSets.contains(J);? In terms of improving performance, I feel doing the conversion from binary string to number will negate this. – JamesB Jul 15 '12 at 09:02
  • @SophieSperner I have *never* seen on the web how to store binary as a string, except as a continuously used anti-pattern in questions on SO. You may be able to use fixed size ints by the way, depending on the range of values. – harold Jul 15 '12 at 09:03
  • 2
    int is actually a pretty decent way to store bits and it offers quite a lot of operations (masks, shifts, ...) ;-) – Jean Logeart Jul 15 '12 at 09:09
  • @SophieSperner: what BigInteger is is well described in its javadoc. Read it. It helps if your binary data is too large to fit into an int (32 bits) of a long (64 bits). – JB Nizet Jul 15 '12 at 09:36
  • 1
    @JB Bad idea in this case. There's this perfect class for a bitset in the JDK, which incidentally is even called Bitset ;) – Voo Jul 15 '12 at 10:55
  • Yeah, `BigInteger` is decimal notation-oriented. It wouldn't help here. – Marko Topolnik Jul 15 '12 at 12:05
  • BTW OP, that method you've posted is a reimplementation of `List.contains`. Also, you could at least have used a `Set` which would dramatically speed up your query (of course, you'll need to call `contains`, not the method you've posted). – Marko Topolnik Jul 15 '12 at 12:07

1 Answers1

1

Here for int:

for (String superJ : superSets)
        return Integer.valueOf(superJ,2) == Integer.valueOf(J,2);
}

You have to test with benchmarks (take care first time is always slower) for speed.

The best way to optimize if J is more than once used : have J2 as Integer somewhere and test on it.

cl-r
  • 1,264
  • 1
  • 12
  • 26