Solved

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

Posted on 2004-10-12
6
256 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
VMware Disaster Recovery and Data Protection

In this expert guide, you’ll learn about the components of a Modern Data Center. You will use cases for the value-added capabilities of Veeam®, including combining backup and replication for VMware disaster recovery and using replication for data center migration.

 
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

Complete VMware vSphere® ESX(i) & Hyper-V Backup

Capture your entire system, including the host, with patented disk imaging integrated with VMware VADP / Microsoft VSS and RCT. RTOs is as low as 15 seconds with Acronis Active Restore™. You can enjoy unlimited P2V/V2V migrations from any source (even from a different hypervisor)

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

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 contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…

773 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