Wie erhalte ich den höchsten Wert eines Delphi-Sets?

Question

Gibt es eine Möglichkeit, den höchsten (oder niedrigsten) Wert in einer Menge zu extrahieren? Zum Beispiel, wenn ich die folgenden „Satz von Byte“ habe:

[0, 1, 2, 4, 5, 28, 199] 

gibt es eine Funktion, die ich auf das laufen könnte und zurück 199 als Ergebnis bekommen?

EDIT: Es gibt eine offensichtliche Brute-Force-Lösung mit einer For..in-Schleife. Wenn möglich, würde ich gerne einen besseren Weg finden.

Answer 1

Eine Schleife ist wirklich der formal korrekte Weg, es zu tun.

type 
    TSetType = set of TEnumType; 

function HighestMember(const s: TSetType): TEnumType; 
begin 
    for Result := High(Result) downto Low(Result) do 
    if Result in s then 
     exit; 
    raise Exception.Create('empty sets have no highest member'); 
end; 

Jede andere Art der Lösung wird Typ-Casting oder Assembler erfordern, die Sie beide Typsicherheit zu verlieren zwingen - sie gehen „außerhalb der Sprache“, sozusagen.

Wenn Sie garantieren können, dass Ihr Set nicht mehr als 32 mögliche Elemente enthält, kann das Set mit einer gewöhnlichen Ganzzahl überlagert werden und Ihre Frage entspricht der Position des höchsten in einem 32-Bit gesetzten Bits ganze Zahl. Das wurde hier vor gefragt, so ziemlich:

• Position of least significant bit that is set

Wenn Sie nicht über eine 32-Element Beschränkung des Satztyp haben, dann haben Sie Delphi 256-Element Grenze, und jedes Bit Die Lösung zum Umgehen muss einen 32- Byte Eingang verarbeiten.

Answer 2

Sätze sind ungeordnet, so dass Sie nicht viel besser als eine Schleife werden. Wenn Sie ständig nach dem Min/Max-Wert einer Menge suchen, verwenden Sie eine heap data structure, die O (1) -Lookup für den Min/Max-Wert und O (LogN) für jeden anderen Wert liefert.

Answer 3

Hier ist eine etwas schnellere Version, die Kenntnisse über die interne Struktur des Byte-Satzes verwendet.

type 
    TByteSet = set of Byte; 

function HighestElement(const ByteSet: TByteSet): Byte; 
type 
    TSetBytes = array[0..SizeOf(TByteSet) - 1] of Byte; 
var 
    I, J: Integer; 
    B: Byte; 
    SetBytes: TSetBytes; 
begin 
    if ByteSet <> [] then 
    begin 
    SetBytes := TSetBytes(ByteSet); 
    // Start at the top and work down, one byte at a time 
    for I := SizeOf(TByteSet) - 1 downto 0 do 
    begin 
     // Any bits set here 
     B := SetBytes[I]; 
     if B <> 0 then 
     begin 
     Result := I * 8; 
     for J := 0 to 7 do 
      if (B shr J) and 1 <> 0 then 
      begin 
      Result := Result + J; 
      Exit; 
      end; 
     end; 
    end; 
    end else 
    // No elements set 
end; 

Sie können den Typ des Satzes ändern, TByteSet, auf fast jedem Satz-Typ, und diese Funktion sollte immer noch funktionieren. Ersetzen Sie einfach TByteSet innerhalb der Funktion decl und body mit dem Typ Ihres Sets. Sie können sie auch ändern, um den tatsächlichen Elementtyp zurückzugeben, wenn Sie einen Satz von AnsiChar oder einen Satz eines Aufzählungstyps verwenden. Um den niedrigsten Wert zu erhalten, ändern Sie das "I" für die Schleife auf "0 bis SizeOf (TByteSet) - 1" und den if-Test in der "J" -Schleife auf "if (B shl J) und $ 80 <> 0"

Answer 4

nahezu die gleiche, aber kürzer:

type 
    TByteSet = set of Byte; 

function MaxSet(S: TByteSet): Byte; 
var 
    CardArr: Array [0..7] of Cardinal absolute S; 
    i: Byte; 
begin 
    i := 7; 
    while (i > 0) AND (CardArr[i] = 0) do 
    Dec(i); 
    Result := i + Floor(Log2(CardArr[i])); 
end; 

Answer 5

höchste und niedrigste, nicht von Math-Einheit verwendet werden:

type 
    TCharSet = set of Char; 

function MaxOfSet(aSet: TCharSet):Char; 
var 
    Data:array[0..SizeOf(TCharSet)-1] of Byte absolute aSet; 
    i,r:Byte; 
begin 
    if aSet<>[] then begin 
    i:=SizeOf(TCharSet)-1; 
    while (i>0) and (Data[i]=0) do 
     Dec(i); 
    r:=i*8; 
    i:=Data[i]; 
    while (i and $80)=0 do begin 
     i:=i shl 1; 
     Dec(r) 
    end; 
    Result:=Chr(r+7) 
    end 
    else 
    raise Exception.Create('Unable to extract max value from an empty set'); 
end; 

function MinOfSet(aSet: TCharSet):Char; 
var 
    Data:array[0..SizeOf(TCharSet)-1] of Byte absolute aSet; 
    i,r:Byte; 
begin 
    if aSet<>[] then begin 
    i:=0; 
    while (i<SizeOf(TCharSet)-1) and (Data[i]=0) do 
     Inc(i); 
    r:=i*8; 
    i:=Data[i]; 
    while (i and 1)=0 do begin 
     i:=i shr 1; 
     Inc(r) 
    end; 
    Result:=Chr(r) 
    end 
    else 
    raise Exception.Create('Unable to extract min value from an empty set'); 
end;