Thread: Eliminating duplicate values

I've done a similar sort of parsing quite a few times. A very simplistic way to do it is outlined below. It essentially makes a list and adds objects of type Website to the list. Website overrides the equals and hashCode methods (allows you to check for identical entries in the list), and add unique or merge previous. An alternative way to do this with simple data that you have, is to have a HashMap rather than a list, using the url as key, and an Integer object as value.

This works for smaller types of files, but a major problem in doing it this way is the memory issues for really large files because this method requires that you read it all into memory (YUCK). Of course you can increase the memory of the JVM, but sometimes for really large files this code may not be optimal.

An alternative to overcome the file size problem is write out to several files - either dynamically or in chunks - based upon some type of sorting (say alphabetize by the url), then merge these at the end. It makes checking the url's much faster because you can search smaller files rather than one large output file, and you may not have the memory problems because you don't have to read everything into an array as you can dynamically check them.

import java.util.Arraylist;
imprt java.io.*;
 
public class Parser{
 
	public static void main(String[] args){
		///do all the file opening here
		ArrayList<Website> list = new ArrayList<Website>();
		String line = null;
		while ( ( line = reader.readLine() ) != null ){
			String splittee[] = line.split(",");
 
			Website site = new Website(splittee[0].trim(), Integer.parseInt(splittee[1].trim()) );
			if ( !list.contains(site) ){
				list.add(site);
			}else{
				int index = list.indexOf(site);
				list.get(index).merge(site);
 
			}
		}
		//do all the file closing and cleanup
		//write out to the output file
	}
	public static class Website{
		private String url;
		private int		count;
		public Website( String u, int c ){
			super();
			this.url = u;
			this.count = c;
		}
		@Override public boolean equals(Object o){
			return url.equals((String)o);
		}
		@Override public int hashCode(){
			return url.hashCode();
		}
		public void merge(Website s){
			count += s.count;
		}
	}
}

Unfortunately, sets don't keep stuff in an ordered format

The easiest solution to this dilemma is to use a list (probably an array) to store everything you read in, but on read-in, run through all the elements already added to see if the element you're adding is a duplicate of any element already in there, and handle that appropriately. Then, when you want to read out, all your elements are in a nice neat order.

Another solution is to put everything into the hash map as Json said, with the addition of an integer that keeps track of what order they were added. Then, once everything has been added, take everything out of the hash map and sort it via your favorite sorting algorithm based on the integer you added that denotes what order they were added in.

The first solution takes O(n^2) time to add everything. The second method takes O(n log(n)) time, so it is technically quicker. However, it's much more work to implement, and takes up more memory (twice as much at least, depending on how the hash table is implemented)

Thank you very much for replying....

I am using the approach suggested by Copeg in the first reply. I am using Array list. Advantage using this is that I get list in the order in which it was already present. This list is also almost sorted as the initial list with few values out of order.

I am sorting this list by taking first list item value and comparing it with second list item value. If first list item value is more then second then second is compared with third. The algo gos on until we had an item which is out of order. We insert that item at proper place and carries on. I dont know what this algorithm is called (If Someone can tell the name, it would be wonderful... ) . But good thing is that I am getting the whole thing done in less then 20 minutes for a file containing more then 4 lakh values... (Merging duplicate values and sorting resulting list)....

Thanks again to you all for posting wonderful replies...

Regards,
Harry__