asked on

Trying to count occurences in an array list then display the statistics

I have an array list of length 10,000 which hold the heights of binarysearch trees. My job is to take this array list go through it and count how many occurences of heights.

Example this is a sample small array list...

2 this array list after i went through it would read
5 ============================================
6 HEIGHTS oCCURENCES
2 2 3
2 5 1
3 6 1
3 1
=============================================

i have thought this through and because it is an arraylist of 10,000 i'm trying to optimize ther algorith. I'm thinking i'll first call sort(list)
so that it takes frequency of occurences and places them next to each other. so that i can stop comparing as soon as target doesn't equal the index value. Then once that happens change target to the current index and continue this all the way through the list. I'm having a hell of a time implementing this idea.

I'm thinking

int target = list.get(0);
int i=0;
while(!list.isEmpty() )
{
if( target == list.get(i).intValue() )
{
count++;
list.remove(i); // as you go down remove top index
}
else
target = list.get(i); // if it is not = to target target becomes next item to count and repeat

}
will this work?i'm not able to implement it first the ints in the list are new Integer. So when i try to call intValue on the particular index it gives me an error i'v tried casting and everything.

Does this algorithm appear to be possible? is there a better way! This is very important to me so i will be giving max points to help me to get it functioning

JakobA

1) find the largest value in the long array.
2) make a second integer array with a length equal to the largest value +1
3) run the below code:

for (int i=0; i<longarray.length(); i++ ) {
shortarray[ longarray[i] ]++;
}
for ( i=0; i<shortarray.length(); i++ ) {
System.out.println( "Path Length " +i +" occur " +shortarray[i] +" times." );
}

regards JakobA

ASKER CERTIFIED SOLUTION

gen718

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

tyweed420

ASKER

gen718 thanks for the code your test works great. However my array list holds objects how can i implement this for my class i'v added your code to my Random Genertaor class but i can not call the method because i have an arraylist not int[]. any ideas??

===========my code now==========================================
import java.util.Random;
import java.util.ArrayList;
import java.util.*;

public class RandomGenerator
{

      public static void main(String [] args)
      {
ArrayList binarylist = new ArrayList();
ArrayList Avllist = new ArrayList();

       AvlTree a;
       BinarySearchTree b ;
       Random random = new Random();
int numtrees = 10000; //Integer.parseInt(args[0]);
int sizetrees = 100; //Integer.parseInt(args[1]);

//create binary trees
       for (int i=0; i < numtrees ;i++)
       {
                  b = new BinarySearchTree();
a = new AvlTree();

              //create # int's inside tree
                  for(int j=0; j < sizetrees; j++)
                  {
                   b.insert(random.nextInt() );
                   a.insert(random.nextInt() );

              }

binarylist.add(new Integer(b.height()) );
//Avllist.add(new Integer(a.getHeight(a.getRoot() ) ) );

            }

Collections.sort(binarylist);

numOfOccurances(binarylist); this does not work because binarylist is anm arraylist
numOfOccurances(binarylist.toArray()); i tried turning it into an array but no luck

}

public static TreeMap numOfOccurances(int[] heights)
{
TreeMap heightmap = new TreeMap(); // key is height value
int newvalue;
for (int i=0; i < heights.length; i++) {
Integer key = new Integer(heights[i]);
if (heightmap.containsKey(key)) {
Integer count = (Integer)heightmap.get(key);
newvalue = count.intValue()+1;
}
else {
newvalue = 1;
}
Integer newcount = new Integer(newvalue);
heightmap.put(key,newcount);
}
return heightmap;
}

static void print(Map map)
{
Iterator it = map.keySet().iterator();
while (it.hasNext())
{
Object key = it.next();
Object value = map.get(key);
System.out.println("Height = "+ key +" Occurances = "+ value);
}
}

}

gen718

Try this method:

      public static TreeMap numOfOccurances(ArrayList heights) {
            TreeMap heightmap = new TreeMap(); // key is height value
            int newvalue;
            for (int i=0; i < heights.size(); i++) {
                  Integer key = (Integer)heights.get(i);
                  if (heightmap.containsKey(key)) {
                        Integer count = (Integer)heightmap.get(key);
                        newvalue = count.intValue()+1;
                  }
                  else {
                        newvalue = 1;
                  }
                  Integer newcount = new Integer(newvalue);
                  heightmap.put(key,newcount);
            }
            return heightmap;
      }

Also there is no need to sort the array prior to calling numOfOccurances(binarylist).
Take out the Collections.sort(binarylist) call.

tyweed420

ASKER

gen718 i really appreciate the help it worked excellent! since you were able to get me setup so nicely i'm now trying to understand how your count occurences method works. I had a few questions about it if you don't mind.
1. Integer key = (Integer)heights.get(i);
if (heightmap.containsKey(key)) this checks if my arraylist at(i) is somewhere in heightmap? I'm confused heightmap does not appear to have anything in it you called new and the constructor but i can't see how it has anything in iit to check if it contains anytrhing.

any way in a few short lines you could explain what the method is doing.

Thanks again,

points are yours

gen718

Thx.

Heightmap initially does NOT contain any objects. The Integer objects relating to the height values are used as keys in the map. The values associated with the key is simply the count of the number of times the value shows up in your original arraylist.
"heightmap.containsKey(key)" checks if the key exists in the treemap NOT in your arraylist.

So when "heightmap.containsKey(key)" is called and null is returned, that means that this is the first time that particular height is come across in your arraylist. Therefore, the value(newcount) associated with the height/key is set to one via "newvalue = 1"
and the value is stored in the map via
Integer newcount = new Integer(newvalue);
heightmap.put(key,newcount) call.

From that point on, if the "heightmap.containsKey(key) returns true, then the associated value is extracted from the map and incremented by 1 via
Integer count = (Integer)heightmap.get(key);
newvalue = count.intValue()+1;

The newvalue is re-stored in the map via
Integer newcount = new Integer(newvalue);
heightmap.put(key,newcount);

Sorta rambling but I hopes this helps. :)