Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Testdaten mit Reservoir (Sampling) (Simulationen)

Beim Aussuchen von Testdaten aus einer Datenmenge kann man sehr einfach vorgehen. Wir suchen aus einer gegebenen Menge mit n Elementen t Testdaten (t ≤ n) folgendermaßen: Wir mischen die gegebene Menge und wählen danach die ersten t Elemente aus der gemischten Menge aus.

Ist jedoch n (die gegebene Menge aller Datensätze) so groß, dass die Daten nicht im Hauptspeicher Platz finden, oder ist n überhaupt nicht bekannt, da die gegebene Datenmenge nur Datensatz um Datensatz eintrifft, so bietet sich folgende Methode mit Reservoir an:

  1. Erstellen Sie ein Array mit t Plätzen. Das ist das Reservoir, das zunächst gefüllt werden muss; am Ende enthält das Reservoir die gesuchte Testdatenmenge.

  2. Die ersten t Daten werden einfach ins Reservoir geschrieben (ist n = t, so sind wir fertig).

  3. Für jeden weiteren k-ten Datensatz (t < k ≤ n) wird eine Zufallsposition p zwischen 1 und k (bzw. zwischen 0 und k-1, falls das Reservoir ab 0 indexiert ist) erzeugt. Ist pt (bzw. ≤ t - 1), so wird der Datensatz an Stelle p ins Reservoir geschrieben. Ist p jedoch größer als t (bzw. t - 1), so wird der Datensatz ignoriert.

Erklärung: Ist t = n, so ist die Sache trivial. Jeder weitere Datensatz (k = n + 1) wird nur mit Wahrscheinlichkeit (t/k) ins Reservoir einsortiert. Der Beweis kann leicht über die vollständige Induktion geführt werden. Beweisen Sie zunächst (Induktionsanfang) den Fall n = t + 1.

Dateien:

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

3 Lösung(en)

import java.util.Scanner;

public class Sampling {
  public static void main(String[] args) {
     new Sampling().start();  }
  
  
  String reservoir[]; // 0..t-1 (t = anzahl gesuchte testdaten)
  String nextLine   ;
  
  
  void start() {
      initReservoir(3);
      while(nextData()) {
          addData();  }
      output();  }


  /**
   * @param i The number of samples to store.
   */
  private void initReservoir(int i) {
    reservoir = new String[i]; }
  
  
  /**
   * Read a line into "nextLine".
   * After the last line false will be returned.
   * @return true, iff the "nextLine" is valid.
   */
  boolean nextData() {
      Scanner sc = new Scanner(System.in);
      System.out.println("Next data (<empty> to quit): ");
      nextLine = sc.nextLine();
      if(null == nextLine) {
          return false; }
      if("".equals(nextLine)) {
          return false; }
      return true; }
  
  
  void output() {
      // reservoir evtl hier mischen.
      if(alreadyRead < reservoir.length) {
          System.out.println("Not enough data."); }
      for(String act : reservoir) {
          System.out.println("Sample: " + act); }
  }
  
  
  /**
   * Add the "nextLine" if required to the reservoir.
   */
  int alreadyRead = 0;
  void addData() {
     int positionToAdd;
     if(alreadyRead < reservoir.length) {
         positionToAdd = alreadyRead;   } 
     else {
         positionToAdd = intRnd(alreadyRead); }
     if(positionToAdd < reservoir.length) {
         reservoir[positionToAdd] = nextLine; }
     alreadyRead = alreadyRead + 1;
  }

  
  /**
   * Generate an integer random number between
   * 0 and "size - 1".
   */
  private int intRnd(int size) {
    return (int) (Math.random() * (size + 1)); }

}  // end of class Sampling
                
public class Reservoir {

    double[] reservoir;
    int size;
    int numIns;

    public static void main(String[] args) {
        Reservoir m = new Reservoir( 1000 );

        for( double j = 0; j <= 1000000; j++ )
            m.Add( j );

        System.out.println( "Mittelwert im Reservoir : " + m.Average() );
    }

    public Reservoir( int size ) {
        reservoir = new double[size];
        this.size = size;
        numIns = 0;
    }

    public void Add( double val ) {
        if ( numIns < size )
            reservoir[numIns] = val;
        else {
            int curIndex = (int) Math.floor( Math.random() * (numIns+1) );
            if ( curIndex < size )
                reservoir[curIndex] = val;
        }        
        numIns++;
    }

    public void Reset( ) {
        numIns = 0;
    }

    public void Print( ) {
        for( int i = 0; i < size; i++ )
            System.out.println( reservoir[i] );
    }

    public double Average( ) {
        double sum = 0;

        for( int i = 0; i < size; i++ )
            sum += reservoir[i];
        sum /= size;
        return sum;
    }
}

                
package g2.testdaten;

import java.io.*;
import java.util.Arrays;


public class Testdaten {
    
  public static void main(String[] args) {
    try {
        new Testdaten().top();
    } catch (IOException e) {
       System.out.println("Fehler im File: " + e);
        e.printStackTrace();
    }
  }
  
  int RESERVOIR_ANZAHL = 20;
  String[]       reservoir;
  BufferedReader br;
  
  void top() throws IOException {
     br = readerInitialisieren();
     reservoirInitialisieren();
     sampling();
     br.close();
     reservoirAusgeben();
  }

  void sampling() throws IOException {
     String line;
     int k = RESERVOIR_ANZAHL  + 1;
     while(null != (line = br.readLine())) {
        int zufallszahl = zufall(0, k-1);
        if(zufallszahl < RESERVOIR_ANZAHL) {
          reservoir[zufallszahl] = line;
        }
        k = k + 1;
     }
  }
  
  void reservoirAusgeben() {
      Arrays.sort(reservoir);
      for(String wort: reservoir) {
          System.out.println(wort);
      }
  }
     
  int zufall(int min, int max) {
      return min + (int) (Math.random() * (max - min + 1)); 
  }
  
  BufferedReader readerInitialisieren() {
    try {
        FileReader fr = new FileReader("deutsch.txt");
        return new BufferedReader(fr);
    } catch(IOException ex) {
        System.out.println("Fehler beim File öffnen: " + ex);
    }
    return null;
  }
      
  void reservoirInitialisieren() throws IOException {    
      reservoir = new String[RESERVOIR_ANZAHL];
      for(int i = 0; i < RESERVOIR_ANZAHL; i = i + 1) {
         reservoir[i] = br.readLine();
      }
  }
  
} // end of class Testdaten
                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Verifikation/Checksumme:

Füllen Sie zum einfachen Test die drei Zahlen 1, 2 und 3 der Reihe nach in ein Reservoir der Größe 2. Testen Sie dies einige Male. Jedes der Paare (1; 2), (1; 3) und (3; 2) sollte mit Wahrscheinlichkeit 1/3 auftreten.

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 1
Schwierigkeit: k.A.
Webcode: x8kv-r9ij
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen