Wert [Word] in Liste/Array vorhanden

[Alex_ITA01]

Hallo zusammen,
folgende Aufgabe:

Ich habe eine Variable vom Typ Word und möchte wissen, ob diese in einer bestimmten dynamisch langen Liste/Array vorhanden ist. Ich will nix sortieren oder sonst etwas. Nur wissen ob vorhanden.
Wie das geht, weiß ich.
Ich möchte eigentlich nur wissen, was wohl die eleganteste/schnellste Lösung von euch wäre?

Meine Lösungswege:

1)
Stringliste mit Aufnahme von den ganzen Einträgen als Integer. Meine Variable mit StringListe.IndexOf abfragen
2)
array of Integer und dieses bei der Abfrage durchsuchen

Habt ihr noch andere Ansätze?

Oder gibt es vielleicht sowas wie:

Delphi-Quellcode:

var
  MyValue : Word;
  MyFeld : array of Word;

if MyValue in MyFeld then
begin
  //Wert vorhanden
end;

Gruß

[Neutral General]

Methode 2 ist die einzig sinnvolle.
Die Stringliste macht intern nichts anderes als die Liste zu durchlaufen und nach dem String zu schauen der bei IndexOf angegeben wurde. Und Strings zu vergleichen ist sogar aufwendiger als Zahlen.

Brauchst ne einfache Funktion in der du per for-schleife dein Array nach dem Wert durchsuchst.

[Mokus]

Delphi-Quellcode:

var 
      test2: Tlist<Word>;
      Myvalue: word;


//....

if test2.indexof(Myvalue) >= 0 
then
begin
//VOrhanden
end;

Listen sind doch schon was tolles ;-)

oder muss das ein Array sein ?

[himitsu]

Der IN-Operator geht nur für Byte (0..255), weshalb er auch nicht mehr für Unicode funktioniert. :zwinker:

Es gibt eine InArray-Suchfunktion für integer, aber ich weiß grade nicht wie die heißt und ob die in D2006 schon drin war. (mal in der Unit Math oder SysUtils suchen)

[Alex_ITA01]

Also es muss kein Array sein...

Ich nutze XE4, vielleicht gibts da ja eine entsprechende Funktion?!

Eigentlich ist Integer auch nicht das richtige Format. Word reicht vollkommen, da es nur positive Zahlen von 0 bis max 9999 enthalten kann.

Gruß

[jfheins]

Wäre für diese Aufgabe ein THashSet<T> nicht geeigneter?

[Mokus]

ich würde die Unit ; "Generics.Collections" einbinden,
dir ne Liste erstellen die die nur Daten von Typ word aufnehmen kann, somit hast du eine Sicherheit, was in deiner Liste kommt, und musst
nicht noch erst schauen das es wirklich der richtige typ ist.

Delphi-Quellcode:

Var 
DeineListeMitDenWert : TList<Word>;
MyValue: Word;

dann kannst du mit ner einfachen if abfrage schauen ob der Index größer gleich 0 ist, wenn ja ist der wert drin.

Delphi-Quellcode:

if DeineListeMitDenWert.indexof(MyValue) >= 0 then
begin
Showmessage('Der wert ist schon vorhanden, YOU WILL LOSE !');
end;

[Aphton]

Delphi-Quellcode:

function DynWordArrContainsWord(const dynWordArr; value: Word): LongBool;
asm
  MOV   EDI, [EAX]
  MOV   ECX, [EDI-4]
  INC   ECX
  MOV   AX, DX
  REPNZ SCASW
  XCHG  EAX, ECX
end;

// --

procedure main();
var
  i: Integer;
  a: Array of Word;
begin
  SetLengtH(a, 100);
  for i := 0 to high(a) do a[i] := i;
  writeln(DynWordArrContainsWord(a, 99));
  writeln(DynWordArrContainsWord(a, 100));
  readln;
end;

Code:

TRUE
FALSE

Grenzfälle: DynWordArr = NIL oder Length(DynWordArr) = 0
nicht abgefangen!

[DeddyH]

Wenn die im Profil angegebene Delphi-Version noch stimmt, fallen Generics eh unter den Tisch, da es die erst ab Delphi 2009 gibt.

[hathor]

Generics gibt es in meinem DELPHI2009 nicht.

[DeddyH]

Ich habe kein 2009 installiert, war aber damals auf der Roadshow, wo Daniel Magin und Matthias Eißing die Generics vorgestellt haben. Von daher bin ich mir ziemlich sicher, dass es die dort gibt.

[himitsu]

Zitat:

Zitat von Alex_ITA01 (Beitrag 1240343)

Ich nutze XE4, vielleicht gibts da ja eine entsprechende Funktion?!

:-D

[TiGü]

Zitat:

Zitat von hathor (Beitrag 1240366)

Generics gibt es in meinem DELPHI2009 nicht.

Man muss schon die entsprechenden Units einbinden! :roll:

[Neutral General]

@Aphton: Super Idee mit deiner Assembler Funktion :) Das merk ich mir!
Ich glaube ich teste die Funktion mal gegen die Standard for-schleifen Variante.

Edit:

Int-Array-Länge: 100 000
100 000 Prüfungen auf den Wert 50 000

For-Variante: ~ 16 Sekunden
ASM-Methode: ~3 Sekunden

[jfheins]

Lineare Suche in ASM ist ja ganz nett, aber gegen ein HashSet immer noch langsam.

1 bis 100000 in ein Hashset, 10 Mio Mal nach 50000 suchen: Zwischen 130ms und 150ms.
Kommt natürlich auch ein bisschen auf die CPU drauf an, aber ich habe auch 100 Mal öfter gesucht!

[Neutral General]

Funktioniert aber auch nur wenn jeder Wert nur 1x vorkommt oder nicht?

[jfheins]

Sagen wir so: Die Anzahl wird nicht gespeichert. Es sollte aber trotzdem kein Problem sein, die Liste/das Array in ein Hashset zu stopfen und dann damit zu überprüfen ob die Zahl enthalten ist. Bei vielen tests ist das dann durchaus schneller als die lineare Suche.

[Alex_ITA01]

Stimmt, muss mal meine Delphi Version im Profil aktualisieren ;-)

Das mit dem Hashset muss ich mir mal angucken.
Die ASM Funktion sieht auch interessant aus, die muss ich aber erstmal genau verstehen ;-)

Danke auf alle Fälle für eure Anregungen, könnt natürlich gerne weiter machen ;-)

Gruß

[Aphton]

Der Threadstarter hat keine Aussagen über das Array getroffen - ist es z.B. sortiert? Falls ja, ginge es ja mit der binären Suche in Log(N) Zeit.
Ansonstnen über Hashes; oder ganz billig - linear!

[Aphton]

Zitat:

Zitat von Neutral General (Beitrag 1240386)

Funktioniert aber auch nur wenn jeder Wert nur 1x vorkommt oder nicht?

Beim Hashset werden meines Wissens nach mehrere Methoden vereint - zuerst einmal die Hashfunktion, die den Index zu einem Element liefert. An dieser Stelle im Hashset befindet sich dann evt. eine sortierte Liste (mit evt. mehreren kollidierenden Einträgen) dort wird wiederum binär gesucht!

Da eine Hashfunktion möglichst Kollisionsfrei vom Design her ist, enthalten die Listen im Hashset meistens nur wenige (eig. 1) Einträge. Gibts Kollisionsen, so ist das auch kein Problem!

[Alex_ITA01]

Hallo zusammen,

also das array ist nicht sortiert und kann unterschiedlich groß sein.

Ich habe es jetzt mit einer TStringList erstmal gemacht und frage dann IndexOf ab.
Generic List hätte ich auch machen können.

Die ASM Funktion muss ich gestehen, verstehe ich nicht ganz. Vielleicht hat mal einer Zeit und Lust mir das zu erklären, was da genau in jeder Zeile passiert?!

Hashset sieht erstmal für meinen "kleinen" Anwendungsfall überdimensioniert aus ;-)
Gucke mir das aber gerne mal noch genauer an.

Viele Grüße

[Sir Rufo]

Das mit der StringList ist aber weder elegant noch schnell.

Für solche Basics lege ich mir ein Helferlein zu und kann dann

Delphi-Quellcode:

  var
    LArray : array of Word;
    LValue : Word;
  begin
    if TArrayHandler<Word>.Contains( TArray<Word>( LArray ), LValue )
    then
      begin

      end;
  end;

oder eben eleganter

Delphi-Quellcode:

  var
    LArray : TArray<Word>;
    LValue : Word;
  begin
    if TArrayHandler<Word>.Contains( LArray, LValue )
    then
      begin

      end;
  end;

Das Helferlein selber, dem man auch noch viel mehr beibringen kann (Sortieren, etc.)

Delphi-Quellcode:

unit Utils.ArrayHandler;

interface

  uses
    System.Generics.Defaults;

  type
    TArrayHandler<T> = class
    public
      // Append
      class procedure Append( var AArray : TArray<T>; const AValue : T ); overload;
      class procedure Append( var AArray : TArray<T>; const AValues : TArray<T> ); overload;
      class procedure Append( var AArray : TArray<T>; const AValues : array of T ); overload;
      // Contains
      class function Contains( const AArray : TArray<T>; const AValue : T ) : Boolean; overload;
      class function Contains( const AArray : TArray<T>; const AValue : T; AComparer : IComparer<T> ) : Boolean; overload;
      // Shuffle
      class procedure Shuffle( var AArray : TArray<T> );
    end;

implementation

  { TArrayHandler<T> }

  class procedure TArrayHandler<T>.Append( var AArray : TArray<T>; const AValue : T );
    begin
      SetLength( AArray, Length( AArray ) + 1 );
      AArray[high( AArray )] := AValue;
    end;

  class procedure TArrayHandler<T>.Append( var AArray : TArray<T>; const AValues : TArray<T> );
    var
      LStart : Integer;
      LIdx   : Integer;
      LLow   : Integer;
    begin
      LStart := high( AArray ) + 1;
      SetLength( AArray, Length( AArray ) + Length( AValues ) );
      LLow := low( AValues );

      for LIdx := LLow to high( AValues ) do
        begin
          AArray[LStart + LIdx - LLow] := AValues[LIdx];
        end;
    end;

  class procedure TArrayHandler<T>.Append( var AArray : TArray<T>; const AValues : array of T );
    var
      LStart : Integer;
      LIdx   : Integer;
      LLow   : Integer;
    begin
      LStart := high( AArray ) + 1;
      SetLength( AArray, Length( AArray ) + Length( AValues ) );
      LLow := low( AValues );

      for LIdx := LLow to high( AValues ) do
        begin
          AArray[LStart + LIdx - LLow] := AValues[LIdx];
        end;
    end;

  class function TArrayHandler<T>.Contains( const AArray : TArray<T>; const AValue : T; AComparer : IComparer<T> ) : Boolean;
    var
      LIdx : Integer;
    begin
      for LIdx := low( AArray ) to high( AArray ) do
        if AComparer.Compare( AValue, AArray[LIdx] ) = 0
        then
          Exit( True );
      Result := False;
    end;

  class procedure TArrayHandler<T>.Shuffle( var AArray : TArray<T> );
    var
      LIdx    : Integer;
      LNewIdx : Integer;
      LTmp    : T;
    begin
      for LIdx := high( AArray ) downto low( AArray ) + 1 do
        begin
          LNewIdx := Random( LIdx + 1 );
          if LIdx <> LNewIdx
          then
            begin
              LTmp            := AArray[LIdx];
              AArray[LIdx]    := AArray[LNewIdx];
              AArray[LNewIdx] := LTmp;
            end;
        end;
    end;

  class function TArrayHandler<T>.Contains( const AArray : TArray<T>; const AValue : T ) : Boolean;
    begin
      Result := Self.Contains( AArray, AValue, TComparer<T>.Default );
    end;

end.