Naz Naz - 1 month ago 6
Java Question

Why is HashSet solution to finding unique characters slow?

I made a O(n^2) and O(n) solution to finding unique characters and was curious to really see the performance difference. I would have expected the

HashSet
solution would have blew the O(n^2) solution out of the water, but it's actually slower than just doing nested loops.

import java.util.HashSet;

class AllUnique
{
// O(n^2) solution
static boolean isUnique(String str)
{
int ind = 0;
boolean unique = true;
while (ind != str.length())
{
int inner_ind = ind + 1;
while (inner_ind != str.length())
{
if (str.charAt(ind) == str.charAt(inner_ind))
{
unique = false;
}
inner_ind++;
}
ind++;
}
return unique;
}

// O(n) solution
static boolean isUnique2(String str)
{
HashSet<Character> set = new HashSet<>();
for (int i = 0; i < str.length(); i++)
{
set.add(str.charAt(i));
}
return set.size() == str.length();
}
}


With a really simple driver that tests millisecond differences:
public class Program {

public static void main(String[] args) {
String[] stringArr = new String[10000];
for (int i = 0; i < 10000; i++)
{
stringArr[i] = "wefwefwefwefwefalkjegb";
}
long startTime = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
{
AllUnique.isUnique(stringArr[i]);
}
long endTime = System.currentTimeMillis();
System.out.println("Total execution time: " + (endTime-startTime) + "ms");

long startTime2 = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
{
AllUnique.isUnique2(stringArr[i]);
}
long endTime2 = System.currentTimeMillis();
System.out.println("Total execution time: " + (endTime2-startTime2) + "ms");
}
}


Does hashing
Character
objects really take that long?

Usually, the nested loop solution is about 5-10ms faster than the HashSet solution.

Answer

O(n) faster then O(n^2) on infinite set of data. In practice it is not necessary true for finite values of n. Your size is not big enough to see the difference. Try to make stringArr[i] biger. Like 1000 long.

If you want practical advise replace set.add(str.charAt(i)) with

if(set.contains(str.charAt(I)) return false;
set.add(str.charAt(i));