For loop is slow

Question

Please have a look at the following code

private StringBuffer populateStringWithUnmatchingWords(ArrayList<String>unmatchingWordsHolder)
    {
        StringBuffer unMatchingWordsStr = new StringBuffer("");

        for(int u=0;u<unmatchingWordsHolder.size();u++)
        {
             Iterator iterInWordMap = wordMap.entrySet().iterator();

             while(iterInWordMap.hasNext())
             {
                 Map.Entry mEntry = (Map.Entry)iterInWordMap.next();

                 if(mEntry.getValue().equals(unmatchingWordsHolder.get(u)))
                 {
                       //out.println(matchingWords.get(m)+" : "+true);
                       unMatchingWordsStr.append(mEntry.getKey());
                       unMatchingWordsStr.append(",");
                 }
              }
        }

        return unMatchingWordsStr;
    }

This for loop takes 8387ms to complete. The unmatchingWordsHolder is pretty big too. wordMap is a HashMap and contains somewhat around 5000 elements as well.

This loop will search whether elements in unmatchingWordsHolder are available in wordMap. If they are available, then they will be loaded into unMatchingWordsStr.

Is there any way for me to speed up this task?

Can you provide the code used to time this method running, so that we can confirm any proposed solutions are an improvement or not. — Edd, Apr 04 '14 at 15:39
You should provide sample input or code to generate input to make it easier for someone to test. — MxLDevs, Apr 04 '14 at 15:46
you should store `unmatchingWordsHolder.size()` in a variable instead of computing it at each step of your for loop. — Arnaud Denoyelle, Apr 04 '14 at 15:48
The biggest problem is you're iterating through the map rather than using `contains()`, but you should also use `StringBuilder` instead of `StringBuffer` - the former doesn't contain any unnecessary synchronisation when just using it on one thread, so is marginally faster. — Michael Berry, Apr 04 '14 at 15:49
@ArnaudDenoyelle: The `size()` method of `ArrayList` takes constant time. That's not the bottleneck. — Aman Agnihotri, Apr 04 '14 at 15:50
Two things, can you change unmatchingWordsHolder to a Set and what is the key value in iterInWordMap? The key in this example is to try not do the scaning of the whole collection, for that you need to use HashSets. Look at the differentce between HashSets and Lists. If you can use HashSets this will take milliseconds — Shawn Vader, Apr 04 '14 at 15:56

score 1 · Accepted Answer · edited May 23 '17 at 11:57

1

Does using Collection.contains() help at all? That would be much more readable, if nothing else, to my mind. It depends on the relative sizes of the List and the Map though, as the easiest way to do it would be something like this, although since you're iterating over the Map and doing the lookup on the List, if the Map is far larger than the List this isn't going to be ideal:

private StringBuffer populateStringWithUnmatchingWords(ArrayList<String>unmatchingWordsHolder) {
    StringBuffer unMatchingWordsStr = new StringBuffer();

    for (Entry<String, String> entry : wordMap.entrySet()) {
        if(unmatchingWordsHolder.contains(entry.getValue())) {
            //out.println(matchingWords.get(m)+" : "+true);
            unMatchingWordsStr.append(entry.getKey());
            unMatchingWordsStr.append(",");      
        }
    }
    return unMatchingWordsStr;
}

As noted elsewhere, if you don't need thread safety, StringBuilder is generally preferred to StringBuffer, but I didn't want to mess with your method signatures.

edited May 23 '17 at 11:57

Community

1
1

answered Apr 04 '14 at 15:48

Edd

3,724
3
26
33

Why not check the other way around? I mean, use: `wordMap.contains(word)` where `word` is a word from the iterable `unmatchingWordsHolder` list. That would be much faster. – Aman Agnihotri Apr 04 '14 at 16:25
Hi, the code has errors. IDE says `for-each not applicable to expression type required: array or java.lang.Iterable found: HashMap` – PeakGen Apr 04 '14 at 16:42
Thanks for the reply. Problem here is that I need to pass the "value" to get the "key" in this map. Because what I need is located in "Key" not in "value". – PeakGen Apr 04 '14 at 17:22
@AmanAgnihotri I did originally look at doing it that way round, but then the issue is looking up the key from a value is O(n), so without using a bi-directional map of some sort I figured this way was probably easier. – Edd Apr 04 '14 at 18:23
@GloryOfSuccess Fixed now - Should have read `for (Entry entry : wordMap.entrySet()) {` – Edd Apr 04 '14 at 18:24
Thanks for the reply. I used another way to achieve this, but yes, same technique, using `contains()` – PeakGen Apr 05 '14 at 08:21

score 1 · Answer 2 · answered Apr 04 '14 at 15:48

1

You are iterating through every element in the Map. A better way to do this is to use a HashMap and use contains() to determine if it exists in the HashMap.

answered Apr 04 '14 at 15:48

Sujen

1,614
5
19
25

1

Thanks for the reply. Problem here is that I need to pass the "value" to get the "key" in this map. Because what I need is located in "Key" not in "value". – PeakGen Apr 04 '14 at 17:21

score 0 · Answer 3 · answered Apr 04 '14 at 16:23

Not sure if I got your problem statement correctly, but if you want to return a comma separated string of all the words that are found in another set of words then here's how you would do in Java 8:

private String populateContainedWords(List<String> words, Set<String> wordSet)
{
  StringJoiner joiner = new StringJoiner(", ");

  words.stream().filter(wordSet::contains).forEach(joiner::add);

  return joiner.toString();
}

And if you only want to have distinct words in this comma separated string, then use the following approach:

private String populateDistinctlyContainedWords(List<String> words, Set<String> wordSet)
{
  StringJoiner joiner = new StringJoiner(", ");

  words.stream().distinct().filter(wordSet::contains).forEach(joiner::add);

  return joiner.toString();
}

And if you want a comma separated string of words from the words list that are NOT contained in the wordSet then here's how that's done:

private String populateDisjointWords(List<String> words, Set<String> wordSet)
{
  StringJoiner joiner = new StringJoiner(", ");

  words.stream().filter(n -> !wordSet.contains(n)).forEach(joiner::add);

  return joiner.toString();
}

For loop is slow

3 Answers3