Comment obtenir la valeur la plus élevée d'un ensemble Delphi?

Question

Existe-t-il un moyen d'extraire la valeur la plus élevée (ou la plus faible) d'un ensemble? Par exemple, si je donne les résultats suivants « ensemble de l'octet »:

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

est-il une fonction que je pouvais courir sur ce point et revenir 199 comme résultat?

EDIT: Il existe une solution de force brute évidente impliquant une boucle for..in. Si possible, j'aimerais trouver un meilleur moyen que cela.

Answer 1

Une boucle est vraiment le moyen formellement correct de le faire.

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; 

Toute autre solution exigera type de coulée ou assembleur, tous deux vous forcer à perdre à la sécurité de type - ils vont « en dehors de la langue », pour ainsi dire. Si vous pouvez garantir que votre ensemble ne contient pas plus de 32 éléments possibles, alors l'ensemble peut être superposé avec un entier ordinaire, et votre question équivaut à demander la position du bit le plus élevé défini dans un 32 bits entier. Qui a été posée ici avant, à peu près:

• Position of least significant bit that is set

Si vous ne disposez pas d'une restriction à 32 éléments sur le type de jeu, alors vous avez la limite de 256 éléments de Delphi, et tout bit La solution de -wwdling devra traiter une entrée de 32- byte.

Answer 2

Les ensembles ne sont pas ordonnés, donc vous n'obtiendrez pas beaucoup mieux qu'une boucle. Si vous recherchez constamment la valeur min/max d'un ensemble, utilisez un heap data structure, qui fournit la recherche O (1) pour obtenir la valeur min/max et la recherche O (log n) sur toute autre valeur.

Answer 3

Voici une version plus rapide qui utilise la connaissance de la structure interne du jeu d'octets.

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; 

Vous pouvez modifier le type de l'ensemble, TByteSet, à presque tout type de jeu, et cette fonction devrait fonctionner. Il suffit de remplacer TByteSet dans la fonction decl et body avec le type de votre set. Vous pouvez également le modifier pour renvoyer le type d'élément réel si vous utilisez un ensemble de AnsiChar ou un ensemble d'un type d'énumération. Pour obtenir la valeur la plus basse, changez le "I" pour la boucle à "0 à SizeOf (TByteSet) - 1" et le test if dans la boucle "J" à "if (B shl J) et 80 $ <> 0"

Answer 4

pratiquement la même, mais plus courte:

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

la plus haute et la plus basse, ne pas utiliser l'unité mathématique:

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;