AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Binärdarstellung einer Zahl mit einer einzigen Stringallokation

Binärdarstellung einer Zahl mit einer einzigen Stringallokation

Ein Thema von BUG · begonnen am 24. Mai 2012 · letzter Beitrag vom 26. Mai 2012
Antwort Antwort
Seite 2 von 3     12 3   
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#11

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 13:08
Mein Gedanken für die binäre Suche war, das man nicht alle Bits zweimal angucken muss. Der Aufwand für einen Schleifendurchlauf ist vielleicht etwas zu hoch.
...
Wenn ich es einsetzen müsste, würde ich wohl den Vorschlag von Amateurprofi wählen: keine Gleitkommazahlen und ohne Umwege. Aber kein pures Delphi/Pascal
Wahrscheinlich hast Du nicht genau hingesehen, aber bei meinem Code werden die Bits nur einmal angesehen (bis auf das höchste, aber das könnte man auch noch wegoptimieren).

Im Übrigen macht Amateurprofis NeededLength auch nichts wesentlich anderes, und ich bezweifele, ob ein Funktionsaufruf und langsames bsr schneller sind. Weiter kann man natürlich auch die finale Schleife rückwarts durchlaufen, hier also der kombinierte Code in Pur-Pascal:
Delphi-Quellcode:
function IntToBin(x: cardinal): string;
var
  i,n: integer;
  m: cardinal;
begin
  if x=0 then Result := '0'
  else begin
    {Teil 1: Bestimme höchstes gesetztes Bit}
    m := cardinal($80000000);
    n := 32;
    while m and x = 0 do begin
      dec(n);
      m := m shr 1;
    end;
    {Teil 2: Allokieren und Bits abarbeiten, n>0 da x<>0!}
    Setlength(Result,n);
    for i:=n downto 1 do begin
      Result[i] := Chr(Ord('0') or (x and 1));
      x := x shr 1;
    end;
  end;
end;

Geändert von gammatester (24. Mai 2012 um 13:11 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.659 Beiträge
 
FreePascal / Lazarus
 
#12

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 13:10
wie wäre es hiermit?

Delphi-Quellcode:
fuction GetLengthofBinString(z:longword):integer;
  i : integer;
begin
  result:=0;
  for i:=0 to 31 do
    if (z and (1 shl i))<>0 then result:=i+1;
end;
Gruß
K-H
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#13

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 13:15
Damit wird ja schon allein zur Längenbestimmung jedes Bits angesehen!
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#14

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 13:48
Wahrscheinlich hast Du nicht genau hingesehen, aber bei meinem Code werden die Bits nur einmal angesehen (bis auf das höchste, aber das könnte man auch noch wegoptimieren).
Stimmt, hast recht

Im Übrigen macht Amateurprofis NeededLength auch nichts wesentlich anderes,
Wie gesagt, die machen alle das gleiche.

und ich bezweifele, ob ein Funktionsaufruf und langsames bsr schneller sind.
Bei kleinen Zahlen könnte es schneller sein.
Bei großen Zahlen muss der Code ja auch alle Bits durchgehen (siehe oben).
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.504 Beiträge
 
Delphi 11 Alexandria
 
#15

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 13:52
Damit wird ja schon allein zur Längenbestimmung jedes Bits angesehen!

Wobei BSR auch nicht so toll sein soll.
Zumindestens für 32 Bit war es so (64 weiß ich nicht), aber da gab es letzes Jahr einen Thread dazu, wo ich dieses BSR verwendete.


Delphi-Quellcode:
function GetLengthofBinString(z: LongWord): LongInt; inline:

function GetLengthOfBinString(Value: LongWord): LongInt;
begin
  Result := 32;
  while (Result >= 0) and (LongInt(Value) >= 0) do begin
    Dec(Result);
    Value := Value shl 1;
  end;
end;
Mit etwas Glück macht der Compiler daraus einen Code, welcher nur 2 Register belegt und komplett innerhalb der Register arbeitet.

Oder man nutzt eben doch Assembler.



klar, man könnte jetzt noch über eine Bitmaske mehrere Bits prüfen.
z.B. jedes Byte einzeln, aber ob das immer was bringt?

Delphi-Quellcode:
function GetLengthOfBinString(Value: LongWord): LongInt;
begin
  if Value = 0 then
    Exit(0);
  Result := 32;
  if Value and $FFFF0000 = 0 then begin
    Result := 16;
    Value := Value shl 16;
  end;
  while (Result >= 0) and (LongInt(Value) >= 0) do begin
    Dec(Result);
    Value := Value shl 1;
  end;
end;

//oder

function GetLengthOfBinString(LongWord: LongWord): LongInt;
begin
  if Value = 0 then
    Exit(0);
  Result := 32;
  while (Result >= 0) and (Value and $FF000000 = 0) do begin
    Dec(Result, 8);
    Value := Value shl 8;
  end;
  while (Result >= 0) and (LongInt(Value) >= 0) do begin
    Dec(Result);
    Value := Value shl 1;
  end;
end;
Die Pascal-Variante hätte den Vorteil derPlattformunabhängigkeit und sie könnte man auch für 64 Bit anpassen.
32 = SizeOf(NativeInt) * 8
LongInt = NativeInt
LongWord = LongWord
$FF000000 = ($FF shl (SizeOf(NativeInt) - 1) * 8)
usw.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list

Geändert von himitsu (24. Mai 2012 um 14:04 Uhr)
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#16

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 14:04
Also ich wäre schwer dafür, für die Bitlänge eine Lookuptabelle zu nehmen. Das könnte noch schneller sein. Gut, der Speicherverbrauch ist suboptimal, aber darum geht es hier nichtm, denn die Aufgabenstellung besagt:
1. Jedes Bit nur einmal anschauen (wegen der bit abrasion, is klar) und
2. soll der String soll auch nur 1x alloziiert werden. Vermutlich das schädlich für den Speicher, ich tippe auf memory rotting, wegen dem fehlenden garbage collector
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.504 Beiträge
 
Delphi 11 Alexandria
 
#17

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 14:06
Wegen Speicher ... macht es doch so wie IntToStr oder Format?

ein array[0..31] of Char als Puffer auf'm Stack,
dann einmal die Zeichen berechnen und den Puffer befüllen,
gleichzeitig werden die Bits automatisch gezählt
und zum Schluß ein SetString, wo nur einmal Speicher allociert wird.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#18

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 14:20
Spielverderber.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#19

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 14:21
ein array[0..31] of Char als Puffer auf'm Stack,
dann einmal die Zeichen berechnen und den Puffer befüllen,
gleichzeitig werden die Bits automatisch gezählt
und zum Schluß ein SetString, wo nur einmal Speicher allociert wird.
Guck mal in den ersten Beitrag

So daneben lag ich mit der binären Suche für das wohl trotzdem nicht:
Zitat von http://coding.derkeiler.com/Archive/Assembler/comp.lang.asm.x86/2005-04/msg00283.html:
K7 - microcoded binary-search, runs in constant 7-8 cycles
Das blr so langsam sein kann, hatte ich nicht vermutet.
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
963 Beiträge
 
Delphi XE2 Professional
 
#20

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 23:00
Im Übrigen macht Amateurprofis NeededLength auch nichts wesentlich anderes, und ich bezweifele, ob ein Funktionsaufruf und langsames bsr schneller sind.
Hallo gammatester,

vielleicht solltest du nicht nur bezweifeln sondern prüfen.

Ich habe mal mit den Werten 0, 2^0..31 getestet.

Die nachstehende Tabelle zeigt von links nach rechts folgende Daten

1) Der Wert der umgewandelt wurde.
2) CPU-Ticks für deine IntToBin.
3) CPU-Ticks für meine IntToBin.
4) CPU-Ticks für deine Ermittlung der benötigten Länge.
5) CPU-Ticks für meine Ermittlung der benötigten Länge.

Mein zusätzlicher Funktionsaufruf und das so langsame "bsr" ist im (Vergleich zu deiner Methode) genau so schnell bis 7 Mal so schnell.

Code:
         0 238 110 /   50  50
         1 568 110 /  374  50
         2 484 136 /  358  50
         4 484 152 /  340  50
         8 492 178 /  330  50
        16 494 204 /  322  50
        32 500 220 /  306  50
        64 518 238 /  288  50
       128 520 264 /  280  50
       256 534 288 /  262  50
       512 544 314 /  246  50
      1024 552 340 /  238  50
      2048 568 356 /  228  50
      4096 578 382 /  212  50
      8192 586 408 /  204  50
     16384 594 432 /  188  52
     32768 604 450 /  170  50
     65536 612 476 /  162  50
    131072 630 502 /  144  50
    262144 706 526 /  136  50
    524288 714 612 /  128  50
   1048576 730 630 /  110  50
   2097152 730 670 /  102  50
   4194304 748 680 /   92  50
   8388608 756 714 /   84  50
  16777216 782 730 /   84  50
  33554432 782 748 /   68  50
  67108864 792 774 /   68  50
 134217728 808 798 /   60  50
 268435456 824 826 /   58  50
 536870912 840 850 /   58  50
1073741824 858 866 /   50  58
2147483648 892 884 /   50  50
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:23 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf