1

So I was developing an algorithm to count the number of repetitions of each character in a given word. I am using a HashMap and I add each unique character to the HashMap as the key and the value is the number of repetitions. I would like to know what the run time of my solution is and if there is a more efficient way to solve the problem.

Here is the code : 

public static void getCount(String name){
        public HashMap<String, Integer> names = new HashMap<String, Integer>() ;
        for(int i =0; i<name.length(); i++){

            if(names.containsKey(name.substring(i, i+1))){
                names.put(name.substring(i, i+1), names.get(name.substring(i, i+1)) +1);
            }
            else{
                names.put(name.substring(i, i+1), 1);
            }
        }

        Set<String> a = names.keySet();
        Iterator i = a.iterator();

        while(i.hasNext()){
            String t = (String) i.next();
            System.out.println(t + " Ocurred " + names.get(t) + " times");
        }
    }
RagHaven
  • 4,156
  • 21
  • 72
  • 113

4 Answers4

2

The algorithm has a time complexity of O(n), but I'd change some parts of your implementation, namely:

  • Using a single get() instead of containsKey() + get();
  • Using charAt() instead of substring() which will create a new String object;
  • Using a Map<Character, Integer> instead of Map<String, Integer> since you only care about a single character, not the entire String:

In other words:

public static void getCount(String name) {
    Map<Character, Integer> names = new HashMap<Character, Integer>();
    for(int i = 0; i < name.length(); i++) {
        char c = name.charAt(i);
        Integer count = names.get(c);
        if (count == null) {
            count = 0;
        }
        names.put(c, count + 1);
    }
    Set<Character> a = names.keySet();
    for (Character t : a) {
        System.out.println(t + " Ocurred " + names.get(t) + " times");
    }
}
João Silva
  • 89,303
  • 29
  • 152
  • 158
  • At first glance, I thought he had used get multiple times, but realized he hadn't, so dropped that whole optimization, but wasn't thinking about the containsKey – Alex Coleman Aug 30 '12 at 03:02
  • Even if I do use get() only once, doesn't the get() have a runtime of O(n) ? hence if it does then if the loop is repeated n times it would have a runtime of O(n^2) – RagHaven Aug 30 '12 at 03:05
  • @RaghavShankar: No, `get()` is constant time `O(1)`, since you are using an `HashMap`. – João Silva Aug 30 '12 at 03:07
  • Oh, okay. Is there some sort of book or site where I can find the runtimes of different functions in the java library ? Such as the get() and add() functions for LinkedLists and ArrayLists and other functions associated to in built data structures in the java library – RagHaven Aug 30 '12 at 03:10
  • Not specifically for methods in the Java API. But Java collections tend to implement very well-known algorithms that can be found in a good Algorithms book such as *Introduction to Algorithms (Cormen et al.)*. *Some* javadoc of the classes also provide the runtime of its operations http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html and http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html. – João Silva Aug 30 '12 at 03:14
  • Also see this, which provides the time complexity for many Java collections: http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf – João Silva Aug 30 '12 at 03:15
  • Not really part of the problem, but still: when you iterate to print the results, iterate on `Map.entrySet()` instead of using `Map.keySet()` + `Map.get()`, so you directly have the key and the value without doing n extra lookups. – Frank Pavageau Aug 30 '12 at 07:34
1

Your solution is O(n) from an algorithmic perspective, which is already optimal (at a minimum you have to inspect each character in the entire string at least once which is O(n)).

However there are a couple of ways that you could speed it up be reducing the constant overhead, e.g.

  • Use a HashMap<Character,Integer>. Characters will be much more efficient than Strings of length 1.
  • use charAt(i) instead of substring(i,i+1). This avoids creating a new String which will help you a lot. Probably the biggest single improvement you can make.
  • If the string is going to be long (e.g. thousands of characters or more), consider using an int[] array to count the individual characters rather than a HashMap, with the character's ASCII value used as an index into the array. This isn't a good idea if your Strings are short though.
mikera
  • 105,238
  • 25
  • 256
  • 415
  • How do you say it is O(n) ? Within the loop I have HashMap.put(),HashMap.containsKey() and HashMap.get(). I am guessing the get() and containsKey() function have a runtime of O(n) each so when the loop is repeated n times wouldnt the runtime of the program be O(n^2) ? – RagHaven Aug 30 '12 at 03:02
  • @RaghavShankar You really shouldn't be using 2 calls though (see Joao's post) – Alex Coleman Aug 30 '12 at 03:02
  • get, put and containsKey are all O(1) on a HashMap (this one of the main reasons that HashMap gets used so much!). Hence doing a combination of these n times is still O(n). – mikera Aug 30 '12 at 03:03
  • Are you sure its O(1) ? I assumed it was O(n) – RagHaven Aug 30 '12 at 03:08
  • Yep, very sure it is O(1)! (assuming the bookkeeping is amortised and the HashMap is maintained at a reasonable capacity which is generally true in the case of the Java implementation) - see http://en.wikipedia.org/wiki/Hash_table – mikera Aug 30 '12 at 03:10
0

Store the initial time to a variable, like so:

long start = System.currentTimeMillis();

then at the end, when you finish, print out the current time minus the start time:

System.out.println((System.currentTimeMillis() - start) + "ms taken");

to see the time taken to do it. As far as I can tell, that is the most efficient way to do it, but there may be another good method. Also, use char rather than strings for each individual character (as char/Character is the best class for characters, strings for a series of chars) then do name.charAt(i) rather than name.substring(i, i+1) and change your hashmap to HashMap<Character, Integer>

Alex Coleman
  • 7,216
  • 1
  • 22
  • 31
0

String s="good";

    //collect different unique characters 

    ArrayList<String> temp=new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(!temp.contains(""+c))
        {
            temp.add(""+s.charAt(i));

        }

    }

    System.out.println(temp);
    //get count of each occurrence in the string
    for (int i = 0; i < temp.size(); i++) {
        int count=0;
        for (int j = 0; j < s.length(); j++) {

            if(temp.get(i).equals(s.charAt(j)+"")){

                count++;
            }
        }
        System.out.println("Occurance of "+ temp.get(i) + " is "+ count+ " times" );
    }*/
Vinayak
  • 6,056
  • 1
  • 32
  • 30