4
\$\begingroup\$

I'm trying to print the top 5 most queried strings from a text file. I can't use other third-party libraries to make it easier w.r.t hashmap implementations.

I need to improve on these if possible:

  1. cyclomatic complexity
  2. Memory usage
  3. Execution time
  4. Page faults

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

class Topfive {

    private HashMap<String, Integer> hashmap = new HashMap<String, Integer>();

    public HashMap<String, Integer> getHashmap() {
        return hashmap;
    }

    public void putWord(String main) {
        Integer frequency = getHashmap().get(main);
        if (frequency == null) {
            frequency = 0;
        }
        hashmap.put(main, frequency + 1);
    }

    public TreeMap<String, Integer> process(File fFile)
    throws FileNotFoundException {
        Scanner scanner = new Scanner(new FileReader(fFile));
        while (scanner.hasNextLine()) {
            String wordp = scanner.nextLine();
            int j = wordp.indexOf("query=") + 6;
            int k = wordp.length() - 1;
            String fut = wordp.substring(j, k).trim();
            this.putWord(fut);
        }
        scanner.close();
        ValueComparator bvc = new ValueComparator(getHashmap());
        TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(bvc);
        sorted_map.putAll(getHashmap());
        return sorted_map;
    }
    public static void main(String[] args) {
        if (args.length > 0) {
            File fFile = new File(args[0]);
            Topfive topfive = new Topfive();
            try {
                TreeMap<String, Integer> sorted_map = topfive.process(fFile);
                int count = 0;
                for (String key : sorted_map.keySet()) {
                    System.out.println(key);
                    count++;
                    if (count >= 5) {
                        break;
                    }
                }
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
    }
}
class ValueComparator implements Comparator<Object> {

    private Map<String, Integer> base;

    public ValueComparator(Map<String, Integer> base) {
        this.base = base;
    }

    @Override
    public int compare(Object first_obj, Object second_obj) {
        int ret = -1;
        if (base.get(first_obj) < base.get(second_obj)) {
            ret = 1;
        }
        return ret;
    }
}

Sample text in text file which is given as command line argument:

 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=60.112.154.0, query=this year]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=116.161.234.129, query=fashion]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=38.214.87.66, query=big lies]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=60.112.154.0, query=this year]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=116.161.234.129, query=fashion]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=38.214.87.66, query=big lies]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=68.175.141.150, query=seven levels]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=114.235.27.231, query=head]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=67.238.116.254, query=special]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=220.153.109.208, query=present]
\$\endgroup\$
7
\$\begingroup\$

Your names could be improved, e.g. hm isn't a good name for a member variable.

You could replace the HashMap by a multiset implementation, e.g. HashMultiset from Google Guava. Then you get putWord for free.

The Comparator (and its Map) should be generified. Further, it seems to be plain wrong, as it never gives 0 as result of compare, but that is the expected outcome if two values are "equal" (whatever this means in the actual context). Without looking too deep in the code, it might even be that a simple priority queue could replace all the Comparator and TreeMap stuff.

The main method is too long and should be split in logical parts. Probably it would be better to avoid static methods, but to create a Topfive instance which does most of the work.

If you can use Java 7, try out the ARM block feature for your file access.

For your question you used the tag "clean code", but it looks like you didn't read the book by Uncle Bob. Check it out!

[Edit]

Based on your clarification I would write the class as follows:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.SortedSet;
import java.util.TreeSet;

public class TopWords {
    private final SortedSet<Freq> frequencies = new TreeSet<Freq>();

    public TopWords(File file)
            throws IOException {
        List<String> wordList = readWords(file);
        Map<String, Integer> freqMap = getFrequencies(wordList);
        sortFrequencies(freqMap);
    }

    public SortedSet<Freq> getFrequencies() {
        return frequencies;
    }

    private List<String> readWords(File file) throws IOException {
        List<String> result = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new FileReader(file));
        for (String line = br.readLine(); line != null; line = br.readLine()) {
            result.add(line);
        }
        return result;
    }

    private Map<String, Integer> getFrequencies(List<String> wordList) throws IOException {
        Map<String, Integer> freqMap = new HashMap<String, Integer>();
        for (String line : wordList) {
            int start = line.indexOf("query=") + 6;
            int end = line.length() - 1;
            String word = line.substring(start, end).trim();
            Integer frequency = freqMap.get(word);
            freqMap.put(word, frequency == null ? 1 : frequency + 1);
        }
        return freqMap;
    }

    private void sortFrequencies(Map<String, Integer> freqMap) {
        for (Entry<String, Integer> entry : freqMap.entrySet()) {
            frequencies.add(new Freq(entry.getKey(), entry.getValue()));
        }
    }

    public List<String> getTop(int count) {
        List<String> result = new ArrayList<String>(count);
        for (Freq freq : frequencies) {
            if (count-- == 0) {
                break;
            }
            result.add(freq.word);
        }
        return result;
    }

    public static void main(String[] args) {
        if (args.length > 0) {
            try {
                TopWords topFive = new TopWords(new File(args[0]));
                List<String> topList = topFive.getTop(5);
                for (String word : topList) {
                    System.out.println(word);
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    public class Freq implements Comparable<Freq> {
        public final String word;
        public final int frequency;

        private Freq(String word, int frequency) {
            this.word = word;
            this.frequency = frequency;
        }

        public int compareTo(Freq that) {
            int result = that.frequency - this.frequency;
            return result != 0 ? result : that.word.compareTo(this.word);
        }
    }
}

Of course this might be suboptimal depending on the intended use, but I think you get the general idea.

[Update]

After some meditation I came to the conclusion that I thought way too complicated. Try the following version:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TopWords {

    private final List<Freq> frequencies = new ArrayList<Freq>();

    public TopWords(File file)
            throws IOException {
        List<String> wordList = getSortedWordList(file);
        sortFrequencies(wordList);
    }

    public List<Freq> getFrequencies() {
        return frequencies;
    }

    private List<String> getSortedWordList(File file) throws IOException {
        List<String> result = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new FileReader(file));
        for (String line = br.readLine(); line != null; line = br.readLine()) {
            int start = line.indexOf("query=") + 6;
            int end = line.length() - 1;
            String word = line.substring(start, end).trim();
            result.add(word);
        }
        br.close();
        Collections.sort(result);
        return result;
    }

    private void sortFrequencies(List<String> wordList) {
        String lastWord = null;
        int count = 0;
        for (String word : wordList) {
            if (word.equals(lastWord)) {
                count++;
            } else {
                if (lastWord != null) {
                    frequencies.add(new Freq(lastWord, count));
                }
                lastWord = word;
                count = 1;
            }
        }
        if (lastWord != null) {
           frequencies.add(new Freq(lastWord, count));
        } 
        Collections.sort(frequencies);
    }

    public List<Freq> getTop(int count) {
        return frequencies.subList(0, Math.min(frequencies.size(), count));
    }

    public static void main(String[] args) {
        if (args.length > 0) {
            try {
                TopWords topFive = new TopWords(new File(args[0]));
                List<Freq> topList = topFive.getTop(5);
                for (Freq freq : topList) {
                    System.out.println(freq.word + " " + freq.frequency);
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    public class Freq implements Comparable<Freq> {

        public final String word;
        public final int frequency;

        private Freq(String word, int frequency) {
            this.word = word;
            this.frequency = frequency;
        }

        public int compareTo(Freq that) {
            int result = that.frequency - this.frequency;
            return result != 0 ? result : that.word.compareTo(this.word);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ @I cannot use third-party libraries ( Google guava) :) Regarding return 0, it makes list populated with Unique items. Regarding ARM feature , I can use only Java(SUN 1.6.0_20) \$\endgroup\$ – cypronmaya Dec 24 '11 at 18:01
  • \$\begingroup\$ @cypronmaya: See my new version. \$\endgroup\$ – Landei Dec 25 '11 at 13:00
  • \$\begingroup\$ Well written if i must say, no clutter etc., thanks for your time to write it. \$\endgroup\$ – cypronmaya Dec 25 '11 at 15:15
  • \$\begingroup\$ Regarding metric comparison, FYI 1) Cyclomatic complexity -- Your version beats mine by reducing 5->4 2) Memory usage -- Your's = 4* Mine 3) Execution time -- Yours's = 1/2 * Mine 4) Page Faults -- Your's = 4*Mine May be i've picked wrong language to do it :) To compare such metrics with others.I Couldn't even stood a chance against C,Perl,PHP w.r.t metrics ofcourse Java is the easiest one for me :) Anyway i've learned something, will try to write better code next time. Again thanks for your time to write it . :) \$\endgroup\$ – cypronmaya Dec 25 '11 at 15:26
  • 1
    \$\begingroup\$ I think sortFrequencies is responsible for that. It is quite ugly, but I found no better way to count the elements in one go. Java collections should really contain a multiset implementation, then this would be a no-brainer. \$\endgroup\$ – Landei Dec 28 '11 at 7:26
0
\$\begingroup\$

Your compare method should be as follows:

@Override
public int compare(Object a, Object b) 
{
    return (Integer)base.get(a) - (Integer)base.get(b);
}
\$\endgroup\$
  • \$\begingroup\$ That only populates sorted_map with unique key's.(Utmost query'ed term's can also be multiple). \$\endgroup\$ – cypronmaya Dec 24 '11 at 18:01
  • \$\begingroup\$ Don't leave out generics. Every single cast in your code is sign that your code works outside the type system (so either the type system is too weak, or you were not clever enough to find a solution without bending the rules) and is a possible source of error. \$\endgroup\$ – Landei Dec 27 '11 at 13:06
  • \$\begingroup\$ @Landei sure, I just did not want to deviate too much from the existing compare method in the OP's code. \$\endgroup\$ – Mike Nakis Dec 27 '11 at 13:09

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.