algorithm - Delphi セットから最高の価値を得るには?

Question

セット内の最高値 (または最低値) を抽出する方法はありますか? たとえば、次の「バイトのセット」があるとします。

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

その上で実行して、結果として 199 を返すことができる関数はありますか?

編集: for..in ループを含む明らかなブルート フォース ソリューションがあります。可能であれば、それよりも良い方法を見つけたいと思います。

Answer 1

セットは順序付けされていないため、ループよりも優れたものになることはありません。セットの最小値/最大値を常に検索している場合は、O(1) ルックアップを提供して最小値/最大値を取得し、他の値に対して O(log n) ルックアップを提供するヒープ データ構造を使用します。

Answer 2

これは、バイト セットの内部構造の知識を使用する少し高速なバージョンです。

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;

セットのタイプ TByteSet をほぼすべてのセット タイプに変更できます。この関数は引き続き機能します。関数 decl と body 内の TByteSet をセットのタイプに置き換えるだけです。AnsiChar のセットまたはいくつかの列挙型のセットを使用している場合は、実際の要素の型を返すように変更することもできます。最小値を取得するには、"I" for ループを "0 to SizeOf(TByteSet) - 1" に変更し、"J" ループの if テストを "if (B shl J) and $80 <> 0" に変更します。

Answer 3

ほぼ同じですが、より短い:

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;