?
Solved

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

Posted on 2004-10-12
6
Medium Priority
?
261 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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 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

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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
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

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

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

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
Suggested Courses
Course of the Month12 days, 19 hours left to enroll

777 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