3
\$\begingroup\$

This is a method where a char[] will be supplied as an input and it should return an array, but without the duplicate elements. How can this be optimized?

private static char[] getMYCharArray(char[] array) {
        String myArray = "";
        for(int i = 0; i < array.length; i++) {
            if(myArray.indexOf(array[i]) == -1) // check if a char already exist, if not exist then return -1
                myArray = myArray+array[i];      // add new char
        }
        return myArray.toCharArray();
    }
\$\endgroup\$
  • \$\begingroup\$ myArray.indexOf is O(n). But on a short list not a big deal. \$\endgroup\$ – paparazzo Jul 24 '17 at 14:38
3
\$\begingroup\$

One possibility is to use a Set. Just add the elements from the array and then get the unique elements from the Set. This algorithm will be O(n) instead of O(n^2) because each element is accessed only once.

Note that you can use Arrays.asList() to simplify the coding, too.

\$\endgroup\$
  • \$\begingroup\$ I just tried using a LinkedHashSet<Character> instead of a HashSet<Character> combined with a char[], and they both seem to be about equally fast. Sometimes, one is a bit faster, sometimes the other. \$\endgroup\$ – Stingy Jul 23 '17 at 20:03
  • \$\begingroup\$ @Stingy That sounds like a reasonable result. \$\endgroup\$ – Code-Guru Jul 23 '17 at 20:09
2
\$\begingroup\$

Here is a slightly convoluted algorithm that yields the same result as yours but is faster. It takes advantage of Java's native support for arrays instead of using an internal String:

private static char[] getYOURCharArray(char[] array) {
    char[] distinctChars = new char[0];
    char[] distinctCharsInOriginalOrder = new char[array.length];

    for (int i = 0; i < array.length; i++) {
        int binarySearchResult = Arrays.binarySearch(distinctChars, array[i]);

        if (binarySearchResult < 0) {
            char[] updatedDistinctChars = new char[distinctChars.length + 1];
            int insertionPointForNewChar = -(binarySearchResult + 1);

            System.arraycopy(distinctChars, 0, updatedDistinctChars, 0, insertionPointForNewChar);
            updatedDistinctChars[insertionPointForNewChar] = array[i];
            System.arraycopy(distinctChars, insertionPointForNewChar, updatedDistinctChars, insertionPointForNewChar + 1, distinctChars.length - insertionPointForNewChar);

            distinctChars = updatedDistinctChars;
            distinctCharsInOriginalOrder[distinctChars.length - 1] = array[i];
        }
    }

    return Arrays.copyOf(distinctCharsInOriginalOrder, distinctChars.length);
}

Using Arrays.binarySearch(char[], char) to look for a char in a char[] seems to be faster than searching for a char in a String using String.indexOf(int). On the other hand, Arrays.binarySearch(char[], char) requires the char[] to be sorted, which is why we need a second char[] that stores all distinct characters in the order they were first encountered in the original char[], assuming the returned char[] must fulfill this requirement (if it doesn't, then the array distinctCharsInOriginalOrder is actually not needed and you can return distinctChars directly at the end of this method, which might speed up the process a little bit). To ensure that distinctChars stays sorted, it is important to insert new chars at the correct position when updating distinctChars, which is why two calls to System.arraycopy are needed.

I did some simulations with random char arrays, each containing 100000 random characters. Here are the results of a set of 10 simulations:

With String: 9.183 seconds
With char arrays: 2.404 seconds

With String: 4.159 seconds
With char arrays: 2.075 seconds

With String: 4.721 seconds
With char arrays: 2.116 seconds

With String: 4.758 seconds
With char arrays: 2.056 seconds

With String: 4.517 seconds
With char arrays: 2.056 seconds

With String: 4.707 seconds
With char arrays: 2.038 seconds

With String: 4.803 seconds
With char arrays: 2.049 seconds

With String: 4.706 seconds
With char arrays: 2.024 seconds

With String: 4.683 seconds
With char arrays: 2.045 seconds

With String: 4.549 seconds
With char arrays: 2.052 seconds

I have no idea why the first simulation with the String algorithm takes twice as long as all the others. It was like that every time I ran the program, even when I switched the order of the two tests (meaning the first String algorithm still took twice as long as the others, even when the char[] algorithm was tested first). Maybe I did something wrong, or the JVM does something mysterious here.

Apparently, the larger the original char array, the greater the difference between the performance of the two algorithms. Here are the results of 10 simulations with 500000 random characters:

With String: 20.44 seconds
With char arrays: 4.474 seconds

With String: 21.344 seconds
With char arrays: 3.489 seconds

With String: 22.064 seconds
With char arrays: 3.315 seconds

With String: 22.155 seconds
With char arrays: 3.351 seconds

With String: 22.325 seconds
With char arrays: 3.386 seconds

With String: 22.149 seconds
With char arrays: 3.335 seconds

With String: 22.175 seconds
With char arrays: 3.352 seconds

With String: 22.16 seconds
With char arrays: 3.343 seconds

With String: 22.502 seconds
With char arrays: 3.362 seconds

With String: 22.122 seconds
With char arrays: 3.351 seconds
\$\endgroup\$
  • \$\begingroup\$ It turns out that, if the order of chars in the returned char[] does not matter, using a HashSet<Character> is much, much faster than this approach. \$\endgroup\$ – Stingy Jul 23 '17 at 19:27
  • \$\begingroup\$ Actually, even if the order does matter, using a HashSet<Character> to store all distinct characters, and a char[] to store these characters in their original order, is way faster than using two char[]s. So the simplest approach wins, after all … \$\endgroup\$ – Stingy Jul 23 '17 at 19:40
  • \$\begingroup\$ Most likely, the original String solution is slower because it creates a new String each time it adds a character. This will copy the entire previous String each time a character is appended. \$\endgroup\$ – Code-Guru Jul 23 '17 at 20:08
  • \$\begingroup\$ @Code-Guru Well, the char array version also creates a new array every time a new character is encountered, copying the characters of the old array, so I don't think Object creation itself is what makes the char[] version faster than the String version. I rather suspect it's because System.arraycopy(Object, int, Object, int, int) is a native method, but I'm no expert, so it's just an assumption. \$\endgroup\$ – Stingy Jul 23 '17 at 20:19
1
\$\begingroup\$

(sorry for the brevity and typos, writing on a phone)

Assuming that you are only using ASCII characters you can simply keep a boolean array and keep track of characters seen like so:

char noDupes(char[] input) {
    boolean[] seen = new boolean [256];
    StringBuilder sb = new StringBuilder (input.length);
    for ( char c : input){
        if(!seen[c]){
            sb.append(c);
            seen[c]=true;
        }
    }
    return sb.toString().toCharArray();
}

If input isn't limited to ASCII, simply use a HashSet instead of the boolean array but the array is faster.

\$\endgroup\$
  • \$\begingroup\$ If we're assuming ASCII input, then 128 bools are sufficient. 256 are required for Latin-1 characters (and, obviously, 65536 for all the UTF-16 code-points a Java char can actually hold). \$\endgroup\$ – Toby Speight May 25 '18 at 7:34
  • \$\begingroup\$ @TobySpeight Extended ASCII still contains code points in the upper 128. I should have specified better. \$\endgroup\$ – Emily L. May 25 '18 at 13:31
  • \$\begingroup\$ Well, that's not ASCII (arguably, you could call Unicode and ISO 10646 - up to the astral planes - "extended ASCII", given the superset relationship, but that's not very helpful). I've actually seen a hybrid approach work well - a bool array for small values (up to 128 or 256, perhaps), and a hash table for larger values. That's a good technique for Latin-script languages, where most characters take the fast path. \$\endgroup\$ – Toby Speight May 25 '18 at 14:14

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.