Mittelwert und Standardabweichung

[negaH]

Hi

du solltest mehrere Dinge berücksichtigen bei dieser Datenmenge:

1.) mit Stream arbeiten, statt den alten Blockread() etcpp.
2.) mit Buffern arbeiten, dh. deine Daten werden in einen Bufferspeicher geladen und von da ausgewertet
3.) die Konvertierung der Strings live durchführen, quasi "on the fly"
4.) die Berechnung des Durchschnittes und der Standardabweichung mit einer speziellen Formel durchführen. Dabei wird die normale Formel der Standardabweichung so umgestellt das sie auf Grund des Binomials nun sequientiell berechnet werden kann. Man kann also sequientiell deine Zahlen einlesen und wiederum "on the fly" diese Werte berechnen.

Anbei mal ein Lösungsvorschlag:

Delphi-Quellcode:

procedure XYZ;
const
  BufferSize = 1024 * 4;
var
  Stream: TFileStream;
  Buffer: String;
  Value: Integer;            // aktuelle Zahl in der Datei
  ValueSign: Integer;        // Vorzeichen von Value
  ValueCount: Integer;       // Anzahl der gelesenen Zahlen aus der Datei
  ValueValid: Boolean;       // enthält Value eine gültige Zahl ?
  Avg: Double;               // kummulierte Summe aller Zahlen -> Avg / ValueCount == Durchschnitt
  Dev: Double;               // kummulierte Quadrate aller Zahlen -> Dev * ValueCount - Avg / (ValueCount * (ValueCount -1)) == Standardabweichung
  CurChar,EndChar: PChar;    // Anfang/Ende des Buffer
  Symbol: Char;              // aktuell auszuwertende Ziffer/Buchstabe
begin
// initialisierung
  CurChar := nil;
  EndChar := nil;
  Value := 0;
  ValueSign := +1;
  ValueValid := False;
  ValueCount := 0;
  Avg := 0;
  Dev := 0;
// Buffer allozieren, Stream öffnen
  SetLength(Buffer, BufferSize);
  Stream := TFileStream.Create('Filename', fmOpenRead or fmShareDenyNone);
  try
    repeat
    // solange noch Zeichen im Buffer diese in Zahlen umwandeln
      while CurChar < EndChar do
      begin
        Symbol := CurChar^;
        if Symbol in ['0'..'9'] then
        begin // String in Zahl umwandeln
          Value := Value * 10 + Ord(Symbol) - Ord('0');
          ValueValid := True;
        end else
          if ValueValid then
          begin // falls in Value eine gültige Zahl war diese in Avg/Dev kummulieren
            Value := Value * ValueSign;
            Avg := Avg + Value;
            Dev := Dev + Sqr(Value);
            Inc(ValueCount);
            // 1.)
            ValueValid := False;
            Value := 0;
            ValueSign := +1;
          end else
            if Symbol = '-' then 
              ValueSign := -1;
        Inc(CurChar);
      end;
    // Buffer aus Datei laden
      CurChar := PChar(Buffer);
      EndChar := CurChar + Stream.Read(Buffer[1], BufferSize);
    until EndChar = CurChar;
    if ValueValid then
    begin // letzte eventuell nicht per Leerzeichen abgeschlossene Zahl berücksichtigen
      Value := Value * ValueSign;
      Avg := Avg + Value;
      Dev := Dev + Sqr(Value);
      Inc(ValueCount);
    end;
  finally
    Stream.Free;
  end;
// Standardabweichung berechnen
  Dev := (Dev * ValueCount - Sqr(Avg)) / (Sqr(ValueCount) - ValueCount);
// Durchschnitt berechnen
  Avg := Avg / ValueCount;
// Auf Grund obiger Formeln kann die Standardabweichung und der Durchschnitt zu jedem
// Zeitpunkt in Source bei 1.) fortlaufend berechnet werden -> also sequientiell
end;

Gruß hagen

[Hobbyprogrammierer]

Hallo!

Bin wieder wach!

Freue mich wirklich über derart viel Resonanz! Ist aber für einen *Hobbyprogrammierer* ganz schön harter Stoff. Werd ich wohl die ganze nächste Woche dran zu knacken haben. Aber danke nochmal vielmals!

[Hobbyprogrammierer]

Bin wieder da

Ich gebe zu, ich habe negaH´s Code einfach nur blind abgetippt. Aber mit Online-Hilfe, zwei Büchern und mehreren Stunden Konzentration ist´s gar nich mal so schwer. Wenn man erstmal durch ist. Zwei Fragen sind allerdings offen geblieben:

1. Was genau macht diese Zeile?

Value:= Value*10 + Ord(Symbol) - Ord('0');


2. An welcher Stelle kann ich einsteigen, wenn ich nur z.B. die Werte zwischen 200.000 und 300.000 berechnet haben will? Kann ich CurChar und EndChar gleich zu Beginn die Positionen zuweisen?

Danke!

[cruiser]

1.) Bei mehreren Ziffern hintereinander sorgt das für die Multiplikation:
1. Ziffer: 5 > Value = 0 > Value*10+5 = 5
2. Ziffer: 2 > Value = 5 > Value*10+2 = 52
... usw.

2.) Ich würd hier einsteigen und Value mit logischen and's mitprüfen:

Delphi-Quellcode:

        end else
          if ValueValid then
          begin // falls in Value eine gültige Zahl war diese in Avg/Dev kummulieren

{--- zu: ---}

        end else
          if ValueValid and (Value >= 200) and (Value <= 300) then
          begin // falls in Value eine gültige Zahl war diese in Avg/Dev kummulieren

[Hobbyprogrammierer]

Klingt absolut logisch. Schonwieder ärgerlich nicht selbst drauf gekommen zu sein.

Danke, werds gleich mal einbauen.

[negaH]

Zitat:

2. An welcher Stelle kann ich einsteigen, wenn ich nur z.B. die Werte zwischen 200.000 und 300.000 berechnet haben will?

Delphi-Quellcode:

  if ValueValid then 
  begin // falls in Value eine gültige Zahl war diese in Avg/Dev kummulieren 
    Inc(ValueCount); 
    Value := Value * ValueSign; 

// hier nur die 100000'te bis 200000'te Zahl in berechnung berücksichtigen
    if (ValueCount >= 100000) and (ValueCount < 200000) then
    begin
      Avg := Avg + Value; 
      Dev := Dev + Sqr(Value); 
    end else
      if (ValueCount = 200000) then
      begin // hier bei 200000 Zahl die realen werte ausrechnen
        Dev := (Dev * (200000-100000) - Sqr(Avg)) / (Sqr((200000-100000)) - (200000-100000)); 
        Avg := Avg / (200000-100000); 
      end;

    ValueValid := False; 
    Value := 0; 
    ValueSign := +1;    
  end else

Zitat:

Kann ich CurChar und EndChar gleich zu Beginn die Positionen zuweisen?

Nein das geht nicht, es sei denn alle Zahlen verbrauchen exakt die gleiche Anzahl an Ziffern. Also angenommen bei einer 3 stelligen Zahl wären 2 Leerzeichen davor = 5 zeichen, bei einer 1 stelligen Zahl also 4 Leerzeichen == 5 zeichen, ergo alle Zahlen belegen 5 Bytes in der Datei, dann geht das direkt zu poitionieren. Statt aber CurChar etc. zu verändern einfach mit Stream.Position := 5 * 100000 auf die 100000'te Zahl positionieren und dann valueCount nur bis 100000 hochzählen lassen.

Gruß Hagen

[cruiser]

hum... da hab ich das wohl falsch verstanden. Ich hab es so gelesen dass er Nur Werte zw. 200 und 300 prüfen wollt. Aber stimmt... bei Integer gibbet keine Nachkommastellen.

[negaH]

Zitat:

1. Was genau macht diese Zeile?

Value:= Value*10 + Ord(Symbol) - Ord('0');

Kurz: das Gleiche wie StrToInt(),
es wandelt einen ASCII Zeichstrom aus Dezimalziffern zwischen '0' bis '9' in eine Zahl um.

Zuerstmal multiplizieren wir Value mit 10, weil ja die Daten in deiner Datei Dezimalzalhen sind, Zahlen zu Basis 10. Somit macht die Multiplikation mit 10 quasi eine weitere Stelle in der Zahl frei.

Ord(Symbol) - Ord('0') wandelt nun ein ASCII Zeichen das zwischen '0' bis '9' liegt in die entsprechende Zahl um. Wir machen un dabei den Fakt zu nutze das im ACSII Zeichsatz die Zeichen für die Ziffren 0 bis 9 einfach sequientiell kodiert sind. Das ASCII Zeichen für '0' hat den Bytewert Ord('0'), qausi der Index in die ASCII Zeichentabelle.

Du hast ja nun den Source eingebaut, und wie schnell ist es jetzt ?

Gruß Hagen

[Hobbyprogrammierer]

*Flupp*

Ungefähr so schnell.

Aber so ganz richtig bin ich noch nicht dahintergestiegen. Also zwischen bestimmten Positionen zu lesen. Aber ich sag mal lieber, wie das Ergebnis genau aussehen soll:

Also in der Datei stehen meinetwegen *128 *130 *129 *129 *128.... und zwar meinethalben 5Mio. dieser 4er Blöcke. Von diesen muss ich jetzt immer 20 nacheinander einlesen, Mittelwert und Standardabweichung berechnen, dann die nächsten 20 u.s.w.

Wenn ich alles richtig verstanden habe, müsste ich eigentlich nur auf ValueCount schauen und immer bei 20+ die Berechnung durchführen. Oder?

[negaH]

Korrekt.

Und wenn deine Zahlen immer aus 4 Zeichen bestehen dann hast du enormes Glück gehabt denn du kannst sehr schnell positionieren. Das kann unter Umständen dir dabei helfen deine 8 Millionen Zahlen quasi in parallel abzuarbeiten. Dazu teilst du die Datei in sagen wir mal 20 kleinere Dateien die eine Größe besitzen die ein Vielfaches von 4 * 20 ist. 4 weil deine Zahlen ja immer aus 4 zeichen bestehen und * 20 weil du ja immer 20 solcher Zahlen bewerten möchtest.

Du kannst also ohne großen Aufwand die Verarbeitung mit mehreren CPUs bzw. Rechnern beschleunigen. Denn 8 Millionen Zahlen sind nicht wenige Zahlen, und selbst die schnellste Umsetzung als program wird denoch einiges an Reechenzeit benötigen.

Du solltest jetzt einfach folgendes abändern:

Delphi-Quellcode:

procedure ProcessFile(const AFilename: String; AOffset,ACount: Integer); 
// AOffset = Index der Zahl mit der begonnen werden soll, jede Zahl besteht aus 4 Zeichen in der Datei
// ACount = Anzahl der Zahlen die berechnet werden sollen
const 
  BufferSize = 1024 * 4; 
var 
  Stream: TFileStream; 
  Buffer: String; 
  Value: Integer;            // aktuelle Zahl in der Datei 
  ValueSign: Integer;        // Vorzeichen von Value 
  ValueCount: Integer;       // Anzahl der gelesenen Zahlen aus der Datei 
  ValueValid: Boolean;       // enthält Value eine gültige Zahl ? 
  Avg: Double;               // kummulierte Summe aller Zahlen -> Avg / ValueCount == Durchschnitt 
  Dev: Double;               // kummulierte Quadrate aller Zahlen -> Dev * ValueCount - Avg / (ValueCount * (ValueCount -1)) == Standardabweichung 
  CurChar,EndChar: PChar;    // Anfang/Ende des Buffer 
  Symbol: Char;              // aktuell auszuwertende Ziffer/Buchstabe 

  procedure Calculate;
  begin
    Value := Value * ValueSign; 
    Avg := Avg + Value; 
    Dev := Dev + Sqr(Value); 
    Inc(ValueCount); 
    if ValueCount = 20 then  
    begin
// Standardabweichung/Durchschnitt berechnen 
      Dev := (Dev * 20 - Sqr(Avg)) / (20*19); 
      Avg := Avg / 20; 
// hier Werte Avg/Dev speichern oder so...
// alle kumulativen Werte auf 0 setzen  
      ValueCount := 0; 
      Avg := 0;
      Dev := 0;
    end; 
    ValueValid := False; 
    Value := 0; 
    ValueSign := +1; 
    Dec(ACount); 
  end;

begin 
// initialisierung 
  CurChar := nil; 
  EndChar := nil; 
  Value := 0; 
  ValueSign := +1; 
  ValueValid := False; 
  ValueCount := 0; 
  Avg := 0; 
  Dev := 0; 
// Buffer allozieren, Stream öffnen 
  SetLength(Buffer, BufferSize); 
  Stream := TFileStream.Create(AFilename, fmOpenRead or fmShareDenyNone); 
  try 
    Stream.Position := AOffset * 4;
    repeat 
    // solange noch Zeichen im Buffer diese in Zahlen umwandeln 
      while (CurChar < EndChar) and (ACount > 0) do 
      begin 
        Symbol := CurChar^; 
        if Symbol in ['0'..'9'] then 
        begin // String in Zahl umwandeln 
          Value := Value * 10 + Ord(Symbol) - Ord('0'); 
          ValueValid := True; 
        end else 
          if ValueValid then // falls in Value eine gültige Zahl war diese in Avg/Dev kummulieren 
            Calculate 
          else 
            if Symbol = '-' then 
              ValueSign := -1; 
        Inc(CurChar); 
      end; 
    // Buffer aus Datei laden 
      CurChar := PChar(Buffer); 
      EndChar := CurChar + Stream.Read(Buffer[1], BufferSize); 
    until (EndChar = CurChar) and (ACount <= 0); 
    if ValueValid then // letzte eventuell nicht per Leerzeichen abgeschlossene Zahl berücksichtigen 
      Calculate;
  finally 
    Stream.Free; 
  end; 
end;

Gruß Hagen

[edit]
Da fällt mir ein das du aber sehr aufpassen musst. Betrachte deine Datei nochmal genau mit einem HEX Editor ob wirklich nur Zahlen in 4 Zeichen Gruppen darin vorkommen. Im speziellen beziehe ich mich auf den Zeilenumbruch, Zeilenvorschub -> Carrige Return, Linefeed -> #13,#10 und eventuell Tabs -> #9. Solche Sonderzeichen sollten darin nicht enthalten sein !
[/edit]