Kleinster Wert in einem Set

[Amateurprofi]

Mal zwei Fragen zu Sets.
Ich habe deklariert

Delphi-Quellcode:

type
   TDirection=(drLeft,drRight,drUp,drDown);
   TDirections=Set of TDirection;

var 
   directions:TDirections;

Ich möchte wissen
1) Wieviel Werte stehen gerade in directions.
2) Welches ist der kleinste Wert, der gerade in directions enthalten ist.

(1) könnte man durch zählen der Bits in direction herausfinden.
(2) löse ich zur Zeit so

Delphi-Quellcode:

var dr:TDirection;
    smallestdr:TDirection;
begin
smallestdr:=[];
for dr in directions do begin
   smallestdr:=dr;
   break;
end

;

Weiß jemand eine elegantere Lösung ?

[Shaman]

Hey there

Hier zwei allgemeine Lösungen:

Delphi-Quellcode:

function ElemCount(const ASet; const Size: Cardinal): Byte;
var
  X, I: Integer;
begin
  Result:= 0;
  X:= Cardinal(ASet);
  for I:= 0 to Pred(Size shl 3) do
  begin
    if Odd(X) then Inc(Result);
    X:= X shr 1;
  end;
end;

function SmallestElem(const ASet; const Size: Cardinal; out Elem): Boolean;
var
  X, I: Integer;
begin
  Result:= False;
  X:= Cardinal(ASet);
  for I:= 0 to Pred(Size shl 3) do
  begin
    if Odd(X) then
    begin
      Byte(Elem):= I;
      Result:= True;
      Exit;
    end;
    X:= X shr 1;
  end;
end;

Gruss
Shaman

[Hawkeye219]

Hallo.

In der Funktion SmallestElem fehlt das Schieben von X nach rechts innerhalb der Schleife.

Beide Funktion funktionieren nicht für alle Mengen, da ein Set je nach Umfang zwischen 1 und 32 Bytes im Speicher belegt. Der TypeCast in einen Cardinal-Wert ist also nur für die Mengen korrekt, die genau 4 Bytes belegen.

Die sauberste (und von der internen Darstellung der Mengen unabhängige) Lösung dürfte wohl mit einer Schleife arbeiten und mit dem Operator IN die einzelnen Elemente prüfen.

Gruß Hawkeye

[Shaman]

hey there

Zitat:

Zitat von Hawkeye219

In der Funktion SmallestElem fehlt das Schieben von X nach rechts innerhalb der Schleife.

Ups :oops:

Zitat:

Zitat von Hawkeye219

Beide Funktion funktionieren nicht für alle Mengen, da ein Set je nach Umfang zwischen 1 und 32 Bytes im Speicher belegt. Der TypeCast in einen Cardinal-Wert ist also nur für die Mengen korrekt, die genau 4 Bytes belegen.

Ich war wohl müde... auch korrigiert. Der Cast in der ersten Funktion ist ok, da ich einfach einen ordinalen Typ benötige, in der Schleife aber die tatsächliche Grösse berücksichtig wird.

Zitat:

Zitat von Hawkeye219

Die sauberste (und von der internen Darstellung der Mengen unabhängige) Lösung dürfte wohl mit einer Schleife arbeiten und mit dem Operator IN die einzelnen Elemente prüfen.

Das stimmt, aber diese Lösung ist nicht vom Settyp unabhängig, und das wollte ich mit meiner erreichen.

Gruss
Shaman

[Hawkeye219]

Hallo Shaman,

habe ich beim ersten Mal die fehlende Initialisierung der Variablen X in der zweiten Funktion übersehen, oder ist sie der Überarbeitung zum Opfer gefallen?

Nach wie vor schiebst du in beiden Routinen einen 32-Bit-Wert nach rechts, Mengen mit mehr als 32 Elementen werden also nicht vollständig verarbeitet. Eine Lösung mit dem Assemblerbefehl BT wäre denkbar, letzten Endes würdest du aber immer nur versuchen, dir Laufzeitroutine von Delphi nachzuprogrammieren.

Gruß Hawkeye

[Shaman]

Zitat:

Zitat von Hawkeye219

habe ich beim ersten Mal die fehlende Initialisierung der Variablen X in der zweiten Funktion übersehen, oder ist sie der Überarbeitung zum Opfer gefallen?

Sie ist... :wall:

Okee, die beiden Funktionen sind nur für Mengen mit nicht mehr als 32 Elementen geeignet. Sollte für den Normalgebrauch auch reichen, für grössere Mengen wird man eh TBits verwenden.

Gruss
Shaman

[generic]

helfen euch die funktionen low() high() ord() nicht?

Delphi-Quellcode:

type
   TDirection = (drLeft, drRight, drUp, drDown);
   TDirections = Set of TDirection;

procedure TForm1.Button1Click(Sender: TObject);
var
  i: integer;
  anzahl, lowwert: integer;

  a: TDirections;

  // kann leider nicht leer sein, also ist immer noch eine prüfung auf
  // lowwert>-1 notwendig!
  lowordwert: TDirection;
begin
  a:=[drRight,drDown];
  anzahl:=0;
  lowwert:=-1;

  for i:=ord(low(TDirection)) to ord(high(TDirection)) do
  begin
    if TDirection(i) in a then
    begin
      //wert gefunden
      inc(anzahl);
 
      // niedrigsten wert merken
      if (lowwert=-1) then
      begin
        lowwert:=i;
        lowordwert:=TDirection(i);
      end;
    end;
  end;
  caption:=format('%d %d', [anzahl, lowwert]);
end;

[Hawkeye219]

Hallo generic,

die Funktionen helfen in diesem Fall nicht:

• sie sind nur auf Mengentypen anwendbar, nicht auf Mengenvariablen.
• Low und High liefern den ersten bzw. letzten möglichen Wert der Menge, Klaus wollte aber den kleinsten enthaltenen Wert ermitteln.

Gruß Hawkeye

[marabu]

Hallo.

Klaus hat für seinen Anwendungsfall schon eine sehr elegante Lösung, die allerdings so nicht auf ältere Versionen von Object Pascal übertragen werden kann. Eine allgemeingültige Lösung für die Suche nach dem "kleinsten" member könnte so aussehen:

Delphi-Quellcode:

function MinMember(const ASet; const ASize: Byte): Integer;
type
  TByteArray = array [0..31] of Byte;
  PByteArray = ^TByteArray;
var
  iByte, iBit, iOrd: Integer;
  pba: PByteArray;
  b: Byte;
begin
  pba := @ASet;
  iOrd := 0;
  for iByte := 0 downto Pred(ASize) do
    if pba[iByte] = 0 then Inc(iOrd, 8) else
    begin
      b := pba[iByte];
      while not Odd(b) do
      begin
        Inc(iOrd);
        b := b shr 1;
      end;
    end;
  if iOrd < ASize shl 3
    then Result := iOrd
    else Result := -1;
end;

Da hierbei auf Delphi-Implementierungsdetails zurückgegriffen wird, ist das aber nicht sehr professionell. Das darf Borland machen, aber wir nicht. Selbst Schuld, wer es doch tut.

Grüße vom marabu

[generic]

ich habe ein codebeispiel in meinen post oben angefügt.

Hawkeye219 man kann doch nicht immer gleich die lösung verraten.

btw. zu den anderen codebeispielen. habt ihr alle zuviel c++ und c gemacht?
das konnte sogar das std. pascal von 1970.

[marabu]

@generic: das nenne ich einen brute force Ansatz - gesucht wurde ursprünglich Eleganz und mittlerweile einfach eine "generische" Lösung. Da Object Pascal einen "ungeordneten" Mengentyp implementiert, gibt es keine Operatoren für Min() und Max(), also muss man sie selbst schreiben - oder man nimmt deine Lösung und verzichtet auf Universalität.

Freundliche Grüße

marabu

[BlackJack]

irgendwie vermisse ich hier die (mMn) einfachste lösung. naja dann poste ich sie halt mal :D

Delphi-Quellcode:

type TAufzaehlungsTyp = (a, b, c, d); //oder was auch immer
     TAufzaehlungsMenge = set of TAufzaehlungsTyp;

function ElementCount(ASet: TAufzaehlungsMenge): Integer;
  var i: TAufzaehlungsTyp;
  begin
  Result := 0;
  for i := Low(TAufzaehlungsTyp) to High(TAufzaehlungsTyp) do
    if i in ASet then
      Inc(Result);
  end;

function MinElement(ASet: TAufzaehlungsMenge): TAufzaehlungsTyp;
  var i: TAufzaehlungsTyp;
  begin
  Result := High(TAufzaehlungsTyp);
  for i := High(TAufzaehlungsTyp) downto Low(TAufzaehlungsTyp) do
    if i in ASet then
      Result := i;
  end;

hab ich zwar grade so aus dem Kopf geschrieben, aber das sollte so gehen.

edit: Man sollte sich nur gedanken machen, was MinElement zurückgeben soll, wenn eine leer Menge übergeben wird. (im Moment wird der höchste darstellbare Wert zurückgegeben)

[generic]

marabu ich finde es allerding unpraktisch auf kompiler interne sachen zuzugreifen bzw. irgendwelche bit's zu shiften. schliesslich haben wir es hier mit einer hochsprache zu tun und keinem assembler.

ziel der hochsprachen ist es etwas leicht verständlich zu programmieren.
hochsprache und objektorientiert heisst aber auch oft nicht der performateste zu haben.

ich glaube auch das zwischen den implementierungen kein unterschied ist.
um eine schleife kommt man nicht rum denke ich.

[Amateurprofi]

@All

vielen Dank für Eure Vorschläge.
Meine Hoffnung war, daß es so etwas wir Low()/High() auch für Mengenvariablen gibt, was aber nicht der Fall zu sein scheint - da fehlt wohl was in Delphi.
Als allgemeingültige Lösung könnte ich mir dann das vorstellen:

Delphi-Quellcode:

FUNCTION MinMember(const ASet; ASize:integer):Integer;
asm
         shl   edx,3
         xor   ecx,ecx
@Loop:   bt    [eax],ecx
         jc    @End
         add   ecx,1
         sub   edx,1
         jne   @Loop
         mov   ecx,-1
@End:    mov   eax,ecx
end;

Ist für mich aber auch nicht wirklich überzeugend.

[alzaimar]

Die einzig saubere Lösung (wirklich sauber), ist die Implementierung von Blackjack (eventuell mit einer kleinen kosmetischen Korrektur):

Delphi-Quellcode:

function OrdMinElement(ASet: TAufzaehlungsMenge): Integer; // Liefert die Ordnungszahl
var 
  i: TAufzaehlungsTyp;

begin
  Result := -1; // Falls die Menge leer ist
  for i := Low(TAufzaehlungsTyp) to High(TAufzaehlungsTyp) do 
    if i in ASet then Begin
      Result := i;
      Exit;
    end;
end;

Wie gesagt, kosmetisch. Und schneller ist es auch, denn es wird nach dem ersten Element gleich zurück gesprungen.

Konsequent müsste man, um diese Funktion optimal abzubilden, eine eigene SET-Klasse schreiben, hier kann man mit Bitmustern, Arrays oder sonstwas arbeiten und diese Sonderfunktionen implementieren.

[BlackJack]

sicher dass das so geht? einmal weist du Result einen Integer zu (-1), und einmal einen TAufzaehlungsTyp (i). :gruebel:

@AmateurProfi: Sorry, aber wenn hier eine Lösung nicht allgemeingültig ist, dann deine ;)

[alzaimar]

Zitat:

Zitat von BlackJack

sicher dass das so geht? einmal weist du Result einen Integer zu (-1), und einmal einen TAufzaehlungsTyp (i). :gruebel:

Blöde Frage :zwinker:... Natürlich geht das nicht. Ich äh... :oops: wollte äh... nur Deine Aufmerksamkeit testen. :wall:

Delphi-Quellcode:

function OrdMinElement(ASet: TAufzaehlungsMenge): Integer; // Liefert die Ordnungszahl
var
  i: TAufzaehlungsTyp;

begin
  Result := -1; // Falls die Menge leer ist
  for i := Low(TAufzaehlungsTyp) to High(TAufzaehlungsTyp) do
    if i in ASet then Begin
      Result := Ord (i); // <--- Hier wars
      Exit;
    end;
end;