2

だから私は最近インタビューの質問としてこれを持っていて、最適な解決策は何だろうと思っていました. コードは Objective-c です。

非常に大きなデータ セットがあり、新しいツールをテストするためにそこから項目のランダム サンプルを取得したいとします。物事へのアクセスの詳細について心配するのではなく、システムがこれらのものを提供すると仮定しましょう:

// Return a random number from the set 0, 1, 2, ..., n-2, n-1.
int Rand(int n);

// Interface to implementations other people write.
@interface Dataset : NSObject

// YES when there is no more data.
- (BOOL)endOfData;

// Get the next element and move forward.
- (NSString*)getNext;

@end


// This function reads elements from |input| until the end, and
// returns an array of |k| randomly-selected elements.
- (NSArray*)getSamples:(unsigned)k from:(Dataset*)input
{
  // Describe how this works.
}

編集：したがって、特定の配列からアイテムをランダムに選択することになっています。したがって、k = 5 の場合、データセットから 5 つの要素をランダムに選択し、それらの項目の配列を返します。データセット内の各要素は、選択される可能性が等しくなければなりません。

4

6 に答える 6

1

これは、 Reservoir Samplingを使用するのに適した時期のようです。以下は、このユース ケースの Objective-C 適応です。

NSMutableArray* result = [[NSMutableArray alloc] initWithCapacity:k];

int i,j;

for (i = 0; i < k; i++) {
    [result setObject:[input getNext] atIndexedSubscript:i];
}

for (i = k; ![input endOfData]; i++) {
    j = Rand(i);

    NSString* next = [input getNext];

    if (j < k) {
        [result setObject:next atIndexedSubscript:j];
    }
}

return result;

上記のコードは、最も効率的なリザーバー サンプリング アルゴリズムではありません。これは、 index のエントリを超えるリザーバーのすべてのエントリに対して乱数を生成するためkです。一般的なカテゴリ「リザーバー サンプリング」の下には、もう少し複雑なアルゴリズムが存在します。これは、「Algorithm Z」という名前のアルゴリズムに関する興味深い読み物です。この記事は 1985 年に発行されたので、人々が貯留層サンプリングに関する新しい文献を見つけたら、私は興味があります.

于 2013-01-23T19:30:05.190 に答える
0

(タグが示唆するように) 効率を重視し、母集団内のアイテムの数がわかっている場合は、 reservior sampling を使用しないでください。それには、データセット全体をループして、それぞれに対して乱数を生成する必要があります。

代わりに、0からn-1までの 5 つの値の範囲を選択します。万一、5 つのインデックスに重複がある場合は、重複を別のランダムな値に置き換えます。次に、5 つのインデックスを使用して、母集団の i 番目の要素へのランダム アクセス ルックアップを実行します。

これは簡単です。乱数ジェネレーターの呼び出しの最小数を使用します。また、関連する選択に対してのみメモリにアクセスします。

データ要素の数が事前にわからない場合は、データを 1 回ループオーバーして母集団のサイズを取得し、上記のように進めることができます。

データを複数回反復することが許可されていない場合は、チャンク形式のリザーバー サンプリングを使用します。1) 最初の 5 つの要素を初期サンプルとして選択します。それぞれの確率は 1/5 です。2) 大量のデータを読み込み、新しいセットから 5 つの新しいサンプルを選択します (Rand への 5 つの呼び出しのみを使用)。3) ペアごとに、新しいサンプル項目または古いサンプル要素を保持するかどうかを決定します (オッズは 2 つのサンプル グループのそれぞれの確率に比例します)。4) すべてのデータが読み取られるまで繰り返します。

たとえば、1000 個のデータ要素があるとします (ただし、これは事前にはわかりません)。

  • 最初のサンプルとして最初の 5 つを選択します。 current_sample = read(5); 人口=5。
  • n 個のデータポイントのチャンクを読み取ります(この例ではおそらく n=200):
    • サブポップ = 読み取り (200);
    • m = len(サブポップ);
    • new_sample = choose(5, サブポップ);
    • 2 つのサンプルをペアでループオーバーします。
      • for (a, b) in (current_sample and new_sample): ランダム (0 から母集団 + m) < 母集団の場合は a を維持し、それ以外の場合は *b) を維持します。
    • 人口 += m
    • 繰り返す
于 2013-01-24T04:43:25.093 に答える
0

少し確率論が必要です。他の場合と同様に、n < k の場合は無視します。n 番目のアイテムがサイズ k のセットに選択される確率は、ちょうど C(n-1, k-1) / C(n, k) です。ここで、C は二項係数です。ちょっとした数学は、これがちょうど k/n であることを示しています。残りについては、n 番目の項目の選択は他のすべての選択から独立していることに注意してください。つまり「過去はどうでもいい」。

したがって、アルゴリズムは次のとおりです。

S = set of up to k elements
n = 0
while not end of input
   v = next value
   n = n + 1
   if |S| < k add v to S
   else if random(0,1) >= k/n replace a randomly chosen element of S with v

コーダーにこれをコーディングさせます！それはかなり些細なことです。必要なのは、サイズ k の配列と、データに対する 1 つのパスだけです。

于 2013-01-23T19:57:51.500 に答える
0

これは私がインタビューでした答えではありませんが、私がしたかったことは次のとおりです。

  1. データセットの最初の要素へのポインターを格納する
  2. データセットをループしてカウントを取得する
  3. 最初の要素を指すようにデータセットをリセットする
  4. ランダム インデックスを格納するための NSMutableDictionary を作成する
  5. i=0 から i=k まで for ループを実行します。反復ごとに、ランダムな値を生成し、値が辞書に存在するかどうかを確認します。その場合は、新しい値が得られるまでランダムな値を生成し続けます。
  6. データセットをループします。現在のインデックスがディクショナリ内にある場合は、それをランダムなサブセット値の配列に追加します。
  7. ランダムなサブセットの配列を返します。
于 2013-01-23T19:33:18.173 に答える
0

これを行うには複数の方法があります。最初の方法は次のとおりです。

1. use input parameter k to dynamically allocate an array of numbers
    unsigned * numsArray = (unsigned *)malloc(sizeof(unsigned) * k);

2. run a loop that gets k random numbers and stores them into the numsArray (must be careful here to check each new random to see if we have gotten it before, and if we have, get another random, etc...)

3. sort numsArray

4. run a loop beginning at the beginning of DataSet with your own incrementing counter dataCount and another counter numsCount both beginning at 0.  whenever dataCount is equal to numsArray[numsCount], grab the current data object and add it to your newly created random list then increment numsCount.

5. The loop in step 4 can end when either numsCount > k or when dataCount reaches the end of the dataset.

6. The only other step that may need to be added here is before any of this to use the next command of the object type to count how large the dataset is to be able to bound your random numbers and check to make sure k is less than or equal to that.

これを行う 2 番目の方法は、実際のリストを複数回実行することです。

// one must assume that once we get to the end, we can start over within the set again
1. run a while loop that checks for endOfData
    a. count up a count variable that is initialized to 0

2. run a loop from 0 through k-1
    a. generate a random number that you constrain to the list size
    b. run a loop that moves through the dataset until it hits the rand element
    c. compare that element with all other elements in your new list to make sure it isnt already in your new list
    d. store the element into your new list

現在のリストの場所を保存することで2番目の方法を高速化する方法があるかもしれません.取得したい要素。

これを行うための潜在的な 3 番目の方法は次のとおりです。

1. run a loop from 0 through k-1
    a. generate a random
    b. use the generated random as a skip count, move skip count objects through the list
    c. store the current item from the list into your new list

この 3 番目の方法の問題は、リストの大きさがわからないため、ランダム スキップ カウントを制限する方法がわからないことです。さらに、そうしたとしても、リストの最後の要素に簡単に到達できるランダムに取得されたサブセットのようには見えない可能性があります。選択されているのと同じショット。)

おそらく、これを行う最も速い方法は方法 1 です。最初にランダムな数値を生成し、次にリストを 1 回だけトラバースします (はい、実際には 2 回、データセット リストのサイズを取得するために 1 回、次にランダムな要素を取得するために 1 回)。

于 2013-01-23T19:04:50.623 に答える
0

興味深い質問ですが、DataSet には count または同様のメソッドがなく、複数回反復することは許可されていないため、適切なランダム サンプルを取得するためにこのソリューションしか考えられません (k > データサイズ処理なし):

- (NSArray *)getSamples:(unsigned)k from:(Dataset*)input {
    NSMutableArray *source = [[NSMutableArray alloc] init];
    while(![input endOfData]) {
      [source addObject:[input getNext]];
    }

    NSMutableArray *ret = [[NSMutableArray alloc] initWithCapacity:k];
    int count = [source count];
    while ([ret count] < k) {
        int index = Rand(count);
        [ret addObject:[source objectAtIndex:index]];
        [source removeObjectAtIndex:index];
        count--;
    }
    return ret;
}
于 2013-01-23T19:15:59.337 に答える