Solved

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

Posted on 2004-10-12
Medium Priority
265 Views
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
0
Question by:tyweed420
• 3
• 2

LVL 15

Expert Comment

ID: 12294584
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

0

LVL 2

Accepted Solution

gen718 earned 2000 total points
ID: 12294586
I tried a different approach using a TreeMap. This makes one pass thru the data to get the results.

import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;

public class Test{

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);
}
}
public static void main(String[] args)
{
Random rand = new Random();
int n = 50;
int num_elements = 10000;
//            int[] heights = {1,2,5,4,3,3,3,5,6,1,5};  // quick test values
int[] heights = new int[num_elements];
for (int h=1; h < num_elements; h++) {
heights[h] = rand.nextInt(n+1);  // generate random heights from 0 to 50
}
TreeMap results = numOfOccurances(heights);
print(results);
}

}

0

Author Comment

ID: 12300573
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() );

}

}

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);
}
}

}
0

LVL 2

Expert Comment

ID: 12301061
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.

0

Author Comment

ID: 12303652
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
0

LVL 2

Expert Comment

ID: 12303884
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. :)

0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.