Clarifications (Project #6)
- DenseBag.choose( )
From the choose( ) method project documentation:
Given a random number generator, randomly choose an element from the Bag
according to the distribution of objects in the Bag (e.g., if a Bag
contains 7 a's and 3 b's, then 70% of the time choose should return an a,
and 30% of the time it should return a b.
This operation can take time proportional to the number of unique objects
in the Bag, but no more.
This operation should not affect the Bag.
Your choose() method will be tested to ensure that:
- The results of choose( ) reflect the distribution of objects in the Bag.
I.e., if a DenseBag contains 9 a's and 1 b, invoking choose( ) 100 times would yield around 90 a's and 10 b's.
- The algorithm you use for choose( ) is proportional to the # of unique elements, not the total # of elements. I.e., the choose( ) method should take about the same time for a DenseBag containing 10 a's and a DenseBag containing 10 million a's.
To generate random numbers, use the nextInt(int n) method of the class Random, which will return a random integer value between 0 and n-1 with uniform probability
To randomly choose between events with different probabilities, you can assign events to different ranges of numbers corresponding to the probabilities, then select the event corresponding to the random number generated within this range.
- Given 3 events A(50%), B(45%), C(5%) & object r from class Random
- Assign the range of values between 0-99 to A, B, C in some combination preserving their probability
- Assignment 1: A(0-49), B(50-94), C(95-99)
- Assignment 2: C(0-4), B(5-49), A(50-99)
- Generate x = r.nextInt(100), where x will be between 0 and 99
- Choose between A, B, C depending on the value of x
- For Assignment 1, if x=44, then pick A. If x=96, then pick C.
- For Assignment 2, if x=44, then pick B. If x=96, then pick A.
- DenseBag.hashcode( )
From the hashcode( ) method project documentation:
Return a hashCode that fulfills the requirements for hashCode (such as
any two equal DenseBags must have the same hashCode) as well as desired
properties (two unequal DenseBags will generally, but not always, have
Your hashcode() method will be tested to ensure that:
- Two DenseBag objects that are equal (according to equal( )) have the same hashcode.
- Two DenseBag objects that are not equal will usually not have the same hashcode.
In general, a hashcode( ) method should also be significantly less expensive to compute than the equals( ) method (otherwise why even use a hashcode?), but we will not be testing for efficiency.
The hashcode( ) method should thus compute the hashcode from the same attributes of an object that are used by the equals( ) method, but do it in a simpler/superficial way.
Example hashcode( ) implementations:
- For String.hashcode( )
- could simply take the first letter of the String and convert it to an integer value
- two equal strings would be guaranteed to have the same hashcode (1st letters must be identical)
- would be more efficient than comparing the entire string
- BUT, would perform poorly if tested with multiple strings beginning with same letter
- For List.hashcode( )
- could simply take the hashcode( ) of the first element in the list
- two equal lists would be guaranteed to have the same hashcode (1st elements must be identical)
- would be more efficient than comparing the entire list
- assumes hashcode( ) is implemented properly for elements in the list
- BUT, would perform poorly if tested with multiple lists beginning with same element
- For Set.hashcode( )
- could add the hashcode( ) of all the elements in the Set
- two equal Sets would be guaranteed to have the same hashcode (integer sums are equal regardless of order of addition)
- simply taking the hashcode( ) of the first element in the Set would not work (since Sets are unordered, and two equal Sets could have different 1st elements)
Simply converting an object to a String and using the string's hashcode( ) would not work if two equal objects generate different strings, and would probably be inefficient in any case since the toString() method would likely do more work than equals( ).