Durchschnittliche statischtische Trefferanzahl pro Zeit

[Zacherl]

Hey Leute,

ich versuche grade einen Algorithmus zu optimieren und denke, dass mir dabei die durchschnittliche statistische Trefferanzahl pro Zeit helfen könnte. Und zwar habe ich folgenden Algo:

Code:

a = gesamtmenge;
b = teilmenge von a; // vielleicht ca. 1% der elemente aus a
for (time) do 
begin
  e = wähle zufälliges element aus a
  if (e element von b) then
  begin
    // führe eine operation durch
  end;
end;

Hier sieht man ja schnell, dass der Aufwand vor allem linear zur Zeit wächst. Da mich aber nur die Elemente interessieren, die auch wirlich in b vorkommen, dachte ich mir das so:

Code:

n = durchschnittliche treffer von b pro zeit;
foreach (e aus b) do
begin
  for (n) do
  begin
    // führe eine operation durch
  end;
end;

Dadurch würde der Aufwand dann ja primär von der Anzahl der Elemente in b abhängen. Natürlich ist die Zeit immer noch ein Faktor, aber da b wie beschrieben in den meisten Fällen sehr sehr wenige Elemente hat, dürfte diese Lösung deutlich performanter ausfallen.

Jetzt meine Frage: Wie ermittele ich die durchschnittlichen Treffer abhängig von der Zeit?

Viele Grüße
Zacherl

[Medium]

Wie wäre es ganz banal mit "zeit' := zeit * (Length(b) / Length(a))", und dann über zeit' iterieren? Ohne mehr Wissen um das was du da überhaupt machst (ist schon recht abstrakt so), kann ich gerade nicht nachvollziehen, warum du dieses "n" bräuchtest.

[himitsu]

treffer := versuche * (Length(b) / Length(a))

treffer := versuche_pro_zeit * zeit * (Length(b) / Length(a))


Entspricht dann dem statistischen Mittel, bei Optimalverteilung des "Zuffals", über unendlich Zeit (oder irgendwie so). :stupid:


Wobei du hier noch ein Problem hast, denn wenn "führe eine operation durch" nur etwas Länger dauert, als die Auswahl eines elemente, dann ist das "Suchen" nach dem nächsten passenden Element viel schneller, als das Ausführen.

Es kann also rechnerisch am Ende sogar auf nahezu O(1) kommen, da die Suche verhältnismäßig keine relevante Zeit verbrauchen könnte.
Also
treffer := zeit / dauer_pro_durchführen

Die oberen Formeln würden dann quasi das maximale Optimium (oder so) darstellen.

[Zacherl]

Danke euch für eure Antworten, ich habe es aufgrund eurer Hinweise nun folgendermaßen gelöst:

Code:

// Hier bin ich noch am überlegen, ob ich 1 / Length(a) oder wirklich Length(b) / Length(a) nehme, weil mir der Wert recht hoch vorkommt
n := versuche_pro_zeit * zeit * (Length(b) / Length(a)) 
für jedes element {
  // Um die Sache etwas zufälliger zu gestalten
  m = random(n) + n / 2; 
  for (m) {
    führe operation durch
  }
}

Die Elemente zu iterieren, statt zufällig auszuwählen, ist auf jeden Fall auch deshalb performanter, weil jedes Element eine maximale Anzahl an möglichen Operationen besitzt. Das heißt es kann sein, dass nach 3 Durchläufen alles "fertig" ist und ich zum nächsten Element übergehen kann. Ob eine Operation erfolg hat, wird allerdings nochmal über einen Zufallsfaktor bestimmt, weshalb hier natürlich auch im schlechtesten Falle wirklich m - Durchläufe stattfinden können.

[himitsu]

Wieso hoch?

Trefferwahrscheinlichkeit_als_0bis1 = Length(b) / Length(a)
Trefferwahrscheinlichkeit_in_Prozent = (Length(b) / Length(a)) * 100

je mehr B, um so öfters trifft man

[Zacherl]

Logisch. Je mehr B, desto höher die Wahrscheinlichkeit, dass man ein Element aus B trifft. Da ich aber in jedem Fall über alle Elemente iteriere, muss ich da ja irgendwie wieder ausgleichen und dann durch Length(B) teilen, bzw 1 statt Length(B) in der Anfangsberechnung verwenden. Oder sehe ich das falsch?

Nur weil in meinen Tests der optimierte Algorithmus mit 1 / Length(A) ziemlich nah an die Originalergebnisse herankommt, wobei mit Length(B) / Length(A) vie zu viele Operationen ausgeführt werden. Kann natürlich sein, dass ich bei meinen Stichproben einfach Pech hatte ...

[himitsu]

Nein, du suchst ja in B in A und nicht 1 in A. :zwinker:


Je mer B es gibt, um so mehr Elemente (B) gibt es in A, welche man dann auch treffen könnte.

[Zacherl]

Stimmt natürlich. Das war der Denkfehler :P Danke!