2

これを書く：

N = args[1].split("\\s+").length;

: のようなコマンドライン引数を使用すると、文字列配列を使用して文字列をecho "A B C D E F G H I" | java Subset 3解析した場合と同様のメモリが消費されますか?"A B C D E F G H I".split()

私の課題は、(課題として) 学生 (私) が、N 文字列 (上記の N = 9、A から I) 入力から、K 文字列 (上記のコマンド行で K = 3) を一様にランダムに表示しようとすることができると述べています。 N ではなく K に比例するメモリを消費しながら、それが基本的にやろうとしていることです。

編集： mvpの答えは大いに役立ちます. 問題をよりよく理解するようになりました。

しかし、私はこれを使用することしか許可されていないことを追加する必要があると感じています:

private static Scanner scanner = new Scanner(new BufferedInputStream(System.in), charsetName);

Scanner私は自分でクラスを使用することはできませBufferedReaderん。この制限を考えると、どのように進めるかについては少しわかりません。

4

3 に答える 3

2

これは、未知の長さの入力データ ストリーム (つまり、EOF でのみ停止し、N が何であるかは気にしない) に対して解決でき、K に比例するメモリを使用します。

まず、K=1 について解いてみましょう。入力ストリームの読み取りを開始する場合、最初の項目 (この例では A) が答えであると想定する必要があります。入力がない場合は、それが必要だからです。2 番目の項目を読むときは、確率 の A ではなく、それを答えとして考える必要があります1/2。3 番目の項目 C を読み取るとき、確率 でそれを取る必要があり1/3ます。このアルゴリズムは、事前にアイテムの数を知らなくても、入力ストリームから 1 つのアイテムをランダムに選択します (各アイテムが選択される確率は等しくなります)。

K=2、K=3 (またはそれ以上) の場合、同様のアプローチを採用します。例えば、K=3 の場合、 、 の 3 項目を読んでA答えとしてください。4 番目のアイテムを読み取るとき、(K/N) の確率でそれを選択し、アクティブなアイテムの 1 つを の等しい確率で置き換えるために使用する必要があります。次に、入力ストリームの EOF までそれを続け、最後に 3 つのアクティブなアイテムを出力します。BC3/41/3

于 2013-09-01T03:48:44.053 に答える
1

はい、明示的にどこにも格納しなくても、String[]配列は の結果として作成されるため、同じものを使用します。split

次の方法で入力から単語を抽出することをお勧めします。

  1. List wordList3 ワードを格納する を作成します。
  2. 0 と入力の長さから 1 を引いた値の間の乱数を生成します。
  3. 乱数に対応する位置が空白の場合、その位置が空白でなくなるまで新しい乱数を生成します。
  4. 最後の乱数を開始点として使用して、入力に戻り、空白または入力の開始を検索します。この (+1) は、単語の開始を定義します。
  5. 同じ乱数を開始点として再び使用して、空白または入力の末尾を検索して入力を進めます。この (-1) は単語の終わりを定義します。
  6. この単語がすでに にある場合はwordList、破棄して手順 2 から繰り返します。
  7. そうでない場合は、リストに追加します。
  8. リストのサイズが 3 未満の場合も、手順 2 から繰り返します。
  9. リストを印刷します。

このプロセス中に、9 (N) ではなく、3 つの単語 (K) のみをメモリに格納しました。

スキャンは次の方法でも実行できます。

    import java.util.Scanner;

    public class MyProgram {
        public static void main(String... args) {
            final int K= 3 ;
            String[] words= new String[K] ;
            int wordCount= 0 ;
            int nextWord= 0 ;
            Scanner scanner= new Scanner(System.in) ;
            while( scanner.hasNext() ) {
                String word= scanner.next();
                wordCount++;
                if( nextWord < K ) {
                    words[nextWord]= word ;
                    nextWord++;
                } else {
                    int replacePos= (int)(Math.random()*wordCount) ; 
                    if( replacePos < K ) {
                        words[replacePos]= word ;
                    }
                }
            }
            scanner.close();
            for(String word: words ) {
                System.out.println(word);
            }
        }
    }
于 2013-09-01T03:46:37.013 に答える
1

@mvp には K = 1 の場合の正しい解がありますが、K > 1 の場合、アイテム M を取得する正しい確率は 1/M ではなく K/M です (この場合、確率 3/4 で 4 番目のアイテムを選択する必要があります。確率 3/5 で 5 番目など)。

ちなみに、これは貯水池サンプリングとして知られています。

于 2013-09-01T05:41:11.710 に答える