Solved

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

Posted on 2004-10-12
6
251 Views
Last Modified: 2012-06-21
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
Comment
Question by:tyweed420
  • 3
  • 2
6 Comments
 
LVL 15

Expert Comment

by:JakobA
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

by:
gen718 earned 500 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

by:tyweed420
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() );

                }


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







}
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 2

Expert Comment

by:gen718
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

by:tyweed420
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

by:gen718
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

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

For customizing the look of your lightweight component and making it look opaque like it was made of plastic.  This tip assumes your component to be of rectangular shape and completely opaque.   (CODE)
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now