2
\$\begingroup\$

I previously posted a Reservoir-Sampling program, which was basically a test version of this one. This is an assignment. In the code below, I use RunTimeException to control when scanner finishes reading data. Reasons for this being:

  1. I cannot use any other library than java.lang.
  2. I cannot use Scanner, either. We have been provided a StdIn class which has a static scanner.next() method only for reading strings.

Note: All the code is inside main() because that is how the API demands it.

Can someone review my code, and possibly tell if there's some way I can improve this?

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Subset {

    public static void main(String[] args) {
        int k = Integer.parseInt(args[0]);
        String[] arr = new String[k];
        int i = 0;
        String str;     
        while((str=stdin.readString())!=null && i < arr.length){
            arr[i++] = str;
            // System.out.println(str);
        }
        try{
            for(; (str=stdin.readString())!=null; i++){
                int r = (int)(Math.random()*(i + 1));
                if(r < k){
                    arr[r] = str;
                    //System.out.println(str);
                }
            }
        }catch(RuntimeException e){ // do nothing }     
        for(String s : arr){
            System.out.print(s + " ");
        }
        System.out.println("\n");
    }
}
class stdin{
    private stdin(){}
    private static Scanner sc = new Scanner(new BufferedInputStream(System.in));
    public static String readString(){
        return sc.next();
    }
}

Command line input: echo A B C D E F G H I J | java Subset 3
Output: A F C

To clear out confusion, I am posting what the API and the instructor demands:

Subset client. Write a client program Subset.java that takes a command-line integer k, 
reads in a sequence of N strings from standard input using StdIn.readString(), 
and prints out exactly k of them, uniformly at random. Each item from the sequence can be printed out at most once. 
You may assume that k = 0 and no greater than the number of string on standard input.

% echo A B C D E F G H I | java Subset 3       % echo AA BB BB BB BB BB CC CC | java Subset 8
C                                              BB
G                                              AA
A                                              BB
                                               CC
% echo A B C D E F G H I | java Subset 3       BB
E                                              BB
F                                              CC
G                                              BB
Your client should use only constant space plus one object either of type Deque or of type RandomizedQueue;
use generics properly to avoid casting and compiler warnings. It should also use time and space proportional to 
at most N in the worst case, where N is the number of strings on standard input. 
(For an extra challenge, use space proportional to k.) It should have the following API.

public class Subset {
   public static void main(String[] args)
}
\$\endgroup\$
  • \$\begingroup\$ Well possibly the task is bananas. Could you edit the post with what you are trying to achieve and the exact limitations of the question. If stdin is nothing to do with your solution maybe delete it and define the interface you have been given. A few easy things to tidy up though are the naming, there is no limit of characters - i, r, k, s do not convey enough information. Making it clear regarding the unusual reuse of i. Using a while loop in the second instance once we've discovered that i is being weirdly used. Are you just picking a random sample of 3 from stdin? \$\endgroup\$ – JohnMark13 Sep 6 '13 at 19:16
  • \$\begingroup\$ Just saw your edit. There are some excellent answers on the other thread. Sorry I know nothing about Resevoir Sampling but it seems that you got some great feedback. The use of the RTE is wrong, if you could update the question to make it very clear why you have to use it, and why everything has to be in the main method (as if required a separate function that catches the RTE, logs it (in your case as Unusual termination of stream to System.out I guess) and returns null to terminate your loop in the manner intended. \$\endgroup\$ – JohnMark13 Sep 6 '13 at 19:20
  • \$\begingroup\$ I'v edited my original post a bit. What i'm trying to do here is implement Reservoir Sampling edit : i know ,those were great solutions , but im stuck with this api. And iv never used exceptions to control flow. So i was asking if that part was ok.. btw, what is RTE ? \$\endgroup\$ – Somjit Nag Sep 6 '13 at 19:21
  • \$\begingroup\$ The entire structure is because of the api that i have to maintain. This is an assignment for a princeton MOOC going on at coursera , and the api they gave allows only the main() method. Trust me , It was a pain to mould to the api. \$\endgroup\$ – Somjit Nag Sep 6 '13 at 19:27
  • 2
    \$\begingroup\$ You have misunderstood at least some of the question, just because your public API is limited to the main method I do not see a restriction on what you can do beyond that. I do not see a restriction on Java packages either. So now, are you sure StdIn doesn't have a hasNext() method too? \$\endgroup\$ – JohnMark13 Sep 7 '13 at 8:47
2
\$\begingroup\$

Finished in the comments, can you post the part of the assignment question pertinent to your limited library usage and main method only code? Anyway, if you have been told that a RTE will signify the end of the reading (rather than the null) then this seems marginally better as it makes it clear why you are doing what you are doing:

while (true) {
    try {
        str = stdin.readString();
        if (str == null) {
            break;
        }
        int r = (int)(Math.random()*(i++ + 1));
        if(r < k){
            arr[r] = str;
        }
    }
    catch(RuntimeException rte) {
        //Log the crazy break condition
        break;
    }
} 

It is always a discussion point whether while(true) is acceptable and is normally held up against using a running loop variable. In this case you can intialise a boolean to true and use it as your while condition - setting it to false where the breaks are. It involves extra checks, and makes for harder to read code in my eyes, but hey!

Now, give your variables meaningful names.

EDIT: Post clarification in the comments

So importantly you do not know the length of the input but you want to randomly sample it, and a RumtimeException is unexpected and can make your code blow up? In which case why anymore complex than this?:

public class Subset {

    public static void main(String[] args) {
        int sampleSize = Integer.parseInt(args[0]);
        String[] samples = new String[sampleSize];
        int current = 0;
        String str; 

        //make sure you have at least sampleSize number of samples
        while((str=stdin.readString())!=null && current < sampleSize){
            samples[current++] = str;
        }

        //this will read until the end of the input
        while((str=stdin.readString())!=null) {
            int randomIndex = (int)(Math.random()*(current++));
            if(randomIndex < sampleSize){
                samples[randomIndex] = str;
            }
        }

        for(String sample : samples){
            System.out.print(sample + " ");
        }
        System.out.println("\n");
    }
}

EDIT post comments In your original question on Reservoir Sampling it was important to add +1 to you possible random number as you wanted to pick a value from an array of known size without excluding the final element . However in this version you are using the random number to dictate (with decreasing probability of a hit) where to write the next value read from Stdin into your array of samples.

If you know that the Stdin implementation and that it will through an Exception and that is the only thing you have been told or advised will signify an end to the data (no special characters, no nulls, no maximum length, etc) then the only thing that you can do is catch and handle it and that is perfectly acceptable - in this instance it is not really an Exception condition, it is the norm! Maybe he exercise is in working with bad APIs (which is very common)!

In the latest (very different) version of your code you have this:

for(; ; i++){ 
    int randomIndex = (int)(Math.random()*(i + 1));
    if(randomIndex < sampleSize){
        sample[randomIndex] = StdIn.readString();
    }
 }

You should replace this with code more like my first example where the exception state is handled within the loop. So:

  • Replace for loop with while loop
  • Because you are using the randomIndex to determine whether to read a value at all into the array you are no longer random sampling, you are just random inserting. Every value read from the pool will get written to the array. It is also important that this could run for a long time or more likely run to an error state when i > MAX_INT, which would be possible with a large dataset and a small sample.
\$\endgroup\$
  • \$\begingroup\$ the docs dont say anything about a null getting returned , so i went the way of the RTE.( I cant use NoSuchElementException as its part of the "forbidden" java.util pack) \$\endgroup\$ – Somjit Nag Sep 6 '13 at 20:24
  • \$\begingroup\$ How do you know it is a scanner? Why does your code already have this test (str=stdin.readString())!=null and what makes you think a RTE will be thrown (other than that the Scanner API says it might, but how do you know it is a scanner?), you could just be blocking forever :) \$\endgroup\$ – JohnMark13 Sep 6 '13 at 20:51
  • \$\begingroup\$ in your code . int randomIndex = (int)(Math.random()*(current++)); this should be (++current) , else the last position will never be reached. Also , by the docs , When scanner reads past the last valid token , and tries to read again , It Throws the NoSuchElementException. Have you run the edited version you posted above from command line ? I ask this because when i tried to run your suggestion , it throws NSEE and exits. quite understandable i suppose. \$\endgroup\$ – Somjit Nag Sep 7 '13 at 4:11
  • \$\begingroup\$ There is more to your question than you have said. My postfix increment will not affect how far into the data you can read as all it is used for is decreasing the likelihood of inserting something into the array. Your updated code above does something different too, it writes every value from stdin into the array, which I believe is wrong. Use the code I first posted to avoid the exception. \$\endgroup\$ – JohnMark13 Sep 7 '13 at 6:54
  • \$\begingroup\$ I'm looking into the last point you said about the random sampling part. Thanks a lot for pointing these things out. \$\endgroup\$ – Somjit Nag Sep 7 '13 at 9:22
1
\$\begingroup\$

Before we deal with style, let's consider the substance. I don't think that the following code leads to unbiased sampling as you intend:

for(; ; i++){ 
    int randomIndex = (int)(Math.random()*(i + 1));
    if(randomIndex < sampleSize){
        sample[randomIndex] = StdIn.readString();
    }
}

That raises the issue, are you not able to reuse the classes already developed from your previous exercise? In software development, it would be much preferable to call existing code than to reimplement an algorithm using copy-and-paste. Had you done so, this sampling error would have been avoided completely.

Next, I question your statement

All the code is inside the main() because that is how the api demands it.

As I commented in the previous exercise, the API demands that your main() take a single string parameter that will be parsed as an integer representing the number of samples to take, out of the pool of data that will be read from standard input. The API does not demand that all of your code live inside main(). (Your instructor might demand it, but that would just be silly, in my opinion.)

To address your specific question of flow control, catching RuntimeException is a horrible idea. It's much too unspecific; who knows what kind of RuntimeException actually triggered the premature termination of your loop? Furthermore, it's unclear to anyone looking at the code that it is the intended behaviour; exceptions (especially RuntimeExceptions) usually signify for unexpected events. Let's face it, you're catching RuntimeException instead of NoSuchElementException to work around the silly artificial constraint of your exercise that you must not use anything outside java.lang.*.

The correct way to detect the end of input from java.util.Scanner is to call Scanner.hasNext(), and the next best way is to catch NoSuchElementException. If both of those options are artificially closed off from you, then your question is dangerously close to being off-topic for this site, as it would violate the "Do I want the code to be good code" rule.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the detailed answer. The rules imposed are really something i had a hard time working around. I understand what you say about hasNext() and NoSuchElementException. I also understand the problem posed by RunTimeException. I shall raise these topics in the course discussion forums. Thank you all for your answers. Regarding the unbiased sampling part , why do you say that ? ill try plotting out some data for convincing evidence. \$\endgroup\$ – Somjit Nag Sep 7 '13 at 8:41
  • \$\begingroup\$ @JohnMark13 explained the sampling error in more detail than I would have, considering that this is a homework problem. I would simply have asked you, what is the maximum possible value of i in your original code? and the maximum possible i in this exercise? \$\endgroup\$ – 200_success Sep 7 '13 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.