Kakerergodt's Profile User Rating: *****

Reputation: 87 Whiz
Group:
Active Members
Active Posts:
201 (0.23 per day)
Joined:
01-May 12
Profile Views:
1,526
Last Active:
User is offline Dec 14 2012 05:58 PM
Currently:
Offline

Previous Fields

Country:
Who Cares
OS Preference:
Windows
Favorite Browser:
FireFox
Favorite Processor:
Intel
Favorite Gaming Platform:
PC
Your Car:
Who Cares
Dream Kudos:
0

Latest Visitors

Icon   Kakerergodt has not set their status

Posts I've Made

  1. In Topic: Efficient removal of duplicates in unsorted linked list

    Posted 3 Dec 2012

    The purpose of this discussion:

    Now, I'm wondering what is the more efficient way of doing this.
    


    Does this:
    OP's Method: 53624 ms 
    HashSet Method: 16 ms
    
    

    ..not indicate that there might be a more efficient way of doing what he wants?
    Are they not "accurate enough for the purposes of this discussion".
    Is System.currentTimeMillis() so inaccurate that it would be consistently off by several hundred percent in every consecutive run of the previously posted code, if you ran it multiple times(i.e. 10)?

    Edit: that last question was rethorical btw, the answer being no, backed up by comparison to other more precise measure-methods in combination with empirical evidence.
  2. In Topic: Efficient removal of duplicates in unsorted linked list

    Posted 3 Dec 2012

    View Postpbl, on 03 December 2012 - 06:46 PM, said:

    Sorry but don't trust your stats at all:

    System.currentTimeMillis(); refresh its value 60 times a second so very 16.66666 milli
    so depending when, on that 16 milli second time fram, the time is picked up you can completly screw up the statistics

    All I/O operations completly screwup statistics... when running benchmarks, save everything in memory and print the results/calculations at the end

    Always perform your stats in a for loop and grab tehm a few times, exe activiation might burn CPU cycles for a small program


    Exactly why I wrote in my post that the timings wasn't excactly accurate, but they're accurate enough for the purposes of this discussion. If I for instance was going to test which of the methods, removeDuplicatesIhatesegfault(1691ms) and removeDuplicatesBackandForth(1670), were the more efficient then yeah I probably would be more precise.

    Edit: thank you for enlighting me though, didn't know the particulars of System.currentTimeMillis().
  3. In Topic: Efficient removal of duplicates in unsorted linked list

    Posted 3 Dec 2012

    Added a few extra methods, one that sorts first and Ihatesegfault's, to CasiOo's list:
    My results:
    removeDuplicatesVichot: > 1min
    removeDuplicatesSortFirst: 70 ms
    removeDuplicatesIhatesegfault: 1691 ms
    removeDuplicatesHashSet: 20 ms
    removeDuplicatesBackandForth: 1670 ms
    removeDuplicatesUsingGet: > 1min
    


    The measuring might not be very accurate, but I think it's fairly obvious the hashset-method is the most
    efficient, followed by the sort method.

    Code:
    import java.util.Collections;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.ListIterator;
    import java.util.Random;
    
    public class Test
    {
    	public static void main(String[] args)
    	{	
    		LinkedList<Integer> list = new LinkedList<>();
    		LinkedList<Integer> list2 = new LinkedList<>();
    		LinkedList<Integer> list3 = new LinkedList<>();
    		LinkedList<Integer> list4 = new LinkedList<>();
    		LinkedList<Integer> list5 = new LinkedList<>();
    		LinkedList<Integer> list6 = new LinkedList<>();
    		
    		Random r = new Random();
    		
    		//Create lists equal.
    		for (int i = 0; i < 50000; i++)
    		{
    			int in = r.nextInt(3000);
    			list.add(in);
    			list2.add(in);
    			list3.add(in);
    			list4.add(in);
    			list5.add(in);
    			list6.add(in);
    		}
    		
    		long tid = System.currentTimeMillis();
    		removeDuplicatesVichot(list);
    		System.out.println("removeDuplicatesVichot: " + (System.currentTimeMillis()-tid));
    		
    		tid = System.currentTimeMillis();
    		removeDuplicatesSortFirst(list2);
    		System.out.println("removeDuplicatesSortFirst: " + (System.currentTimeMillis()-tid));		
    
    		tid = System.currentTimeMillis();
    		removeDuplicatesIhatesegfault(list3);
    		System.out.println("removeDuplicatesIhatesegfault: " + (System.currentTimeMillis()-tid));		
    		
    		tid = System.currentTimeMillis();
    		removeDuplicatesHashSet(list4);
    		System.out.println("removeDuplicatesHashSet: " + (System.currentTimeMillis()-tid));		
    		
    		tid = System.currentTimeMillis();
    		removeDuplicatesBackandForth(list5);
    		System.out.println("removeDuplicatesBackandForth: " + (System.currentTimeMillis()-tid));
    		
    		tid = System.currentTimeMillis();
    		removeDuplicatesUsingGet(list6);
    		System.out.println("removeDuplicatesUsingGet: " + (System.currentTimeMillis()-tid));
    		
    	}
    	
    	public static <E extends Comparable> void removeDuplicatesVichot(LinkedList<E> list)
    	{
    		for (int i = 0; i < list.size(); i++)
    		{
    			for (int j = i + 1; j < list.size(); j++)
    			{
    				if (list.get(i).equals(list.get(j)))
    				{
    					list.remove(j);
    				}
    			}
    		}
    	}
    
    	public static <T extends Comparable> void removeDuplicatesSortFirst(LinkedList<T> list)
    	{
    		if(list.size() < 2)
    		{
    			return;
    		}
    		Collections.sort(list);
    		ListIterator<T> li = list.listIterator();
    		T tmp = li.next();
    
    		while(li.hasNext())
    		{
    			T tp = li.next();
    			if(tp.equals(tmp))
    				li.remove();
    			else
    				tmp = tp;
    		}
    	}
    	
    	public static <T extends Comparable> void removeDuplicatesIhatesegfault(LinkedList<T> list)
    	{
    		for(int i = 0; i < list.size(); ++i)
    		{
    			if (list.lastIndexOf(list.get(i)) != i)
    			{
    				list.remove(i);
    				i--;
    			}
    		}
    	}
    	
    	public static <T extends Comparable> void removeDuplicatesHashSet(LinkedList<T> list)
    	{
    		HashSet<T> set = new HashSet<>(list);
    		list.clear();
    		list.addAll(set);
    	}	
    	
    	public static <T extends Comparable> void removeDuplicatesBackandForth(LinkedList<T> list)
    	{
    		ListIterator<T> iterator = list.listIterator();
    		T element;
    		int left = 0;
    		int right = list.size();
    
    		//While they have not crossed
    		while (left < right)
    		{
    			left = iterator.nextIndex() + 1;
    			element = iterator.next();
    			for (int k = left; k < right; k++)
    			{
    				if (iterator.next().equals(element))
    				{
    					iterator.remove();
    				}
    			}
    
    			right = iterator.previousIndex();
    			element = iterator.previous();
    			for (int k = right; k > left; k--)
    			{
    				if (iterator.previous().equals(element))
    				{
    					iterator.remove();
    					right--; //One less element in the list
    				}
    			}
    		}
    	}	
    	
    	public static <T extends Comparable> void removeDuplicatesUsingGet(LinkedList<T> list)
    	{
    		int size = list.size(); //Avoid multiple calls to size()
    
    		for (int i = 0; i < size; i++)
    		{
    			T element = list.get(i);
    
    			for (int k = i + 1; k < size; k++)
    			{
    				if (element.equals(list.get(k)))
    				{
    					list.remove(k);
    					size--; //Adjust the size to one less element
    					k--; //We do not want to jump over an element on the next k++
    				}
    			}
    		}
    	}	
    }
    
    
  4. In Topic: Efficient removal of duplicates in unsorted linked list

    Posted 2 Dec 2012

    Using get(i) on an ArrayList is of constant order, but using it on a linkedlist requires at worst n/2, so yeah an iterator would be better. I think the best way is to create a new list that doesnt support duplicates and add all elements to it. Otherwise I think doing a quicksort then iterating through would have the least order.
  5. In Topic: give task to make simple word analyser from a text file

    Posted 30 Nov 2012

    What excatly do you want to do?

My Information

Member Title:
D.I.C Head
Age:
Age Unknown
Birthday:
Birthday Unknown
Gender:

Contact Information

E-mail:
Private

Friends

Comments

Kakerergodt has no profile comments yet. Why not say hello?