Doppelte Werte in einem Array zählen...

[Meflin]

Hi,
ich habe zwei array of integer: z.B.

Code:

3 5 15

und

Code:

3 3 3 4 5 5 6 7 7 8 10 15 15 20 100

wie kann ich jetzt die Einträge aus dem zweiten array zählen, die aus den werten des ersten arrays doppelt oder öfter vorhanden sind? das ergebnis in diesem falle wäre 3, da sowohl die 3 als auch die 5 als auch die 15 jeweils öfter als einmal im zweiten array vorkommen. allerdings bin ich etwas ratlos, wie man das programmiertechnisch machen soll

*MFG*

[Nuclear-Ping]

Du nimmst dir zwei verschachtelte Schleifen und vlt. noch ein Array of Record: In der ersten durchläufst du das ursprüngliche Array und in der zweiten das zu prüfende Array.

Delphi-Quellcode:

var
  a, b: Integer;
  Counter: Array of record
                      Value: Integer;
                      Count: Integer;
                    end;
begin
  SetLength (Counter, Length (UrsprungsArray));
  
  // Zählen
  for a := 0 to Length (UrsprungsArray) - 1 do
    begin
      Counter[a].Value := UrsprungsArray[a];
      Counter[a].Count := 0;
      for b := 0 to Length (PruefArray) - 1 do
        if (UrsprungsArray[a] = PruefArray[b]) then
          inc (Counter[a].Count);
    end;

  // Werte ausgeben
  for a := 0 to Length (Counter) - 1 do
    showmessage ('Wert ' + inttostr (Counter[a].Value) + ' ist ' + inttostr (Counter[a].Count) + ' mal vorhanden');
end;

Ist ungetestet, aber ich hoffe, ich hab nix vergessen.

Grüße,
Mario

[Meflin]

ok, das ist zwar nicht alles, hat aber weitergeholfen
wenn ich jetzt noch alle arraywerte des counter durchlaufe und eine countervariable nur dann erhöhe wenn der wert im array größer als 1 ist, dann sollte ich genau das gewünschte ergebnis erhelten.

[negaH]

Wie groß können die Zahlen im Array werden ? Und wie viele Zahlen sind im Array gespeichert ?

Angenommen im Array sind nur zahlen zwischen 0 bis 255, dann kann man sehr effektiv so vorgehen:

Delphi-Quellcode:

var
  Count: array[Byte] of Integer;
  ZweitesArray: array of Byte;
  I,Result: Integer;
begin
  FillChar(Count, Sizeof(Count), 0);
  for I := 0 to High(Data) do
    Inc(Count[ZweitesArray[I]]);

  Result := 0;
  for I := 0 to High(ErstesArray) do
    if Count[ErstesArray[I]] > 1 then 
      Inc(Result);      
end;

Bei dieser Methode fallen zwei Schleifen mit Length(ErstesArray) + Length(ZweitesArray) an Durchläufen an.
Bei der Methode von Meflin fallen Length(ErstesArray) * Length(ZweitesArray) an Durchläufen an.
Angenommen Length(ErstesArray) == 1000 und Length(ZweitesArray) == 100;
1.) Methode == 1000 + 100 = 1100
2.) Methode == 1000 * 100 = 100000

Wenn du also den Zahlenbereich in den Arrays beschränken kannst dann solltest du meine Methode benutzen, da sie eine geringere mathematische Komplexität besitzt.

Gruß Hagen

[Meflin]

du meinst wohl nuklear pings methode
das spielt jedenfalls eher keine rolle, da es nicht so viele werte sind (und ausserdem weis ich nicht wie viele genau), also sozusagen undefiniert niedrige anzahl von werten vorhanden ist.

[Nuclear-Ping]

Stimmt, das ist auch eine ziemlich effektive Lösung. Könnte man die 255er Grenze nicht durch Count: Array[Integer] of Integer aufheben?

[negaH]

Jo das könnte man, wenn du einen Gray mit 4 * 4.294.967.296 Bytes == 16 Giga Bytes an Hauptspeicher hast

Gruß Hagen

[Nuclear-Ping]

Stimmt, Integer ist ja 32bit

Aber @Meflin: Wie groß könnten denn die Werte max. werden? Weisst du das?
Weil dann könnte man Hagen's Methode "Count: Array[Byte] of Integer" etwas "erweitern", z.B. "Count: Array[0..10000] of Integer" könnte Werte zw. 0 und 10.000 erfassen. Dadurch kannst du dir nämlich das verschachtelte "Rumgeschleife" schenken.

Mit dem Problem, dass nur Werte gezählt werden sollen, die mehr als 1x in dem Array vorkommen: Könnte man das nicht so lösen, dass man nach dem Zähl-Durchlauf einfach prüft, welche Werte im Count-Array >= 1 sind und diese dann einfach um eins verringert?

Delphi-Quellcode:

var
  Count: Array[0..10000] of Integer;
  i: Integer;
begin
  // Alles im Count-Array auf 0 setzen
  FillChar (Count, Sizeof (Count), 0);

  // Count anhand des Wertes von Data[i] erhöhen
  for i := 0 to High (Data) do
    inc (Count[Data[i]]);

  // Generell eins abziehen, wenn Count[i] >= 1
  for i := 0 to High (Count) do
    if (Count[i] >= 1) then
      dec (Count[i]);
end;

Grüße,
Mario

[negaH]

Warum willst du die Arbeit doppelt machen :=) ???

Schau mal:

Delphi-Quellcode:

 Result := 0; 
  for I := 0 to High(ErstesArray) do 
    if Count[ErstesArray[I]] > 1 then 
      Inc(Result);

Beim zusammenzählen der mehrfachen Werte wird doch implizit schon > 1 überprüft.

Es gibt aber auch andere Möglichkeiten dieses Problem sehr effizient (zeitlich, nicht speichermäßig) hinzubekommen. Dabei wird nur Length(ZweitesArray) an Durchläufen nötig. Also angenommen der Zahlenbereich geht von 0 bis 65535. Wir bauen nun einen Binären Datenbaum auf und sortieren einfach linear erstmal die Zahlen aus dem Vergleichsarray dort ein. Jede Zahl wird in diesem Baum als Wert + Anzahl gespeichert. Nun gehen wir Element für Element im zweiten Array durch und suchen wiederum in unserem Binären Baum die entsprechende Zahl. Falls vorhanden erhöhen wir die Anzahl dieser Node. Nun nehmen wir an das maximal 2^16 Zahlen vorkommen, dann benötigen wir im Suchbau maximal 16 Vergleiche um eine Zahl zu finden (Worstcase). Wir haben ein Array[] mit 2^16 Elementen das ergibt 16 * 2^16 Vergleichsoperatonenund eine Schleife mit 2^16 Durchläufen.
Bei meiner Methode benötigte man viel zu viel Speicher, aber man brüchte theoretisch dann 2^16 + x Vergleiche. Bei Deiner Methode 2^16 * x Vergleicheund beim binären Baum 2^16 * 16 maximal. Damit errechnet sich sehr leicht der Breakeven Point zwischen deiner Methode und einem binären Baum > 16 muß die Anzahl des Vergleichsarrays sein. Angenommen im Vergleichsarray sind 256 Zahlen = 2^8, dann benötigt deine methode 2^16 * 2^8 = 16.777.216 Vergleiche, und der binäre Suchbaum 2^16 * 8 = 524.288 Vergleiche.

Der Vorteil des Baumes liegt nun darin das er unabhängig von der Anzhal der Elementeim Vergleichsarray ist. Er speichert nur die Zahlen die gesucht werden sollen. Dazu benötigt man 2 Zeiger auf Linke/Rechte Node + 1 Integer als Zahlenwert + 1 Integer als Anzahl. Der Speicherverbrauch ist also bei weitem geringer als bei meiner Methode.

Diese Methode funktioniert auch einfach mit einer sortierten Liste von Zahlen. Dort nennt man sie binäre Suche. Dabei hätte man das Vergleichsarray[] erstmal aufsteigend sortiert. Dann noch ein AnzahlArray[] parallel zum Vergleichsarray[]. Nun geht man das Datenarray[] sequentiell durch und sucht per binärer Suche im VergleichsArray[]. Nach Ln2(Length(VergleichsArray[])) findet man die passende Zahl im Array[]. Also bei 2^16 Elementen im Array[] findet man nach spätestens 16 Vergleichen die Zahl.

Gruß Hagen

[Nuclear-Ping]

Delphi-Quellcode:

  Result := 0;
  for I := 0 to High(ErstesArray) do
    if Count[ErstesArray[I]] > 1 then
      Inc(Result);

Yep, das hab ich gesehen, mich allerdings gefragt, was du damit erreichen willst. Denn kommt da nicht einfach eine "große" Zahl raus?

Result ist ja vor der Schleife 0 und wird in der Schleife bei jedem Wert, der > 1 ist erhöht. Das heisst, dass Result dann nach der Schleife die Anzahl der Werte enthält, die > 1 sind, oder lieg ich da falsch?

Angenommen wir haben in Count durch die Zählung folgendes Ergebnis:

Code:

Index:  0 1 2 3 4 5 6 n
Zähler: 0 0 2 0 2 3 0 n
Result:     1   2 3 ...

Result wäre also in dem Beispiel nach dem Durchlauf 3.

Zitat:

Es gibt aber auch andere Möglichkeiten dieses Problem sehr effizient (zeitlich, nicht speichermäßig) hinzubekommen. [...]

Ja, ich glaub, ich weiss, was du meinst. Richtig klick gemacht hats zwar nicht, jedoch gedämmert.

Grüße,
Mario