Bitmuster "rückwärts" dekrementieren

[dede67]

Moin!
Ich habe eine Zahl, die ich als Bitmuster betrachte.
Und die möchte ich jetzt dekrementieren - allerdings mit umgedrehten Wertigkeiten der Bits.
Also ganz links das Bit 0.

Ich habs mal hingepfuscht, indem ich die Zahl nach String wandel, dann einen "reverse" mache, zurück nach Zahl, -1, wieder String, wieder reverse und dann wieder nach Zahl.
Das geht - gefällt mir so aber überhaupt nicht.

Hier der Programmcode:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def highbit_dec(val, bits):
  bm="0"*bits + bin(val)[2:]  # Zahl -> String
  bm2=bm[len(bm)-bits:]       # Ausrichten
  rbm=bm2[::-1]               # Reverse
  v2=eval("0b"+rbm)-1         # String -> Zahl und -1
  v3="0"*bits+bin(v2)[2:]     # Zahl -> String
  v4=v3[len(v3)-bits:]        # Ausrichten
  v5=v4[::-1]                 # Reverse
  return(eval("0b"+v5))       # String -> Zahl

def binprint(val, bits):
  b="0"*bits+bin(n)[2:]
  return(b[len(b)-bits:])

n=15
print binprint(n, 4), n
for i in range(15):
  n=highbit_dec(n, 4)
  print binprint(n, 4), n

Liefert wie gewünscht:
1111 15
0111 7
1011 11
0011 3
1101 13
0101 5
1001 9
0001 1
1110 14
0110 6
1010 10
0010 2
1100 12
0100 4
1000 8
0000 0

Ich habe irgendwie wohl gerade eine Sperre im Kopp....und finde keinen Ansatz für eine elegantere Umsetzung von highbit_dec()... :K
Hat hier Jemand eine Idee, wie ich das hübscher und ohne den Umweg über Strings bauen kann?

Vielen Dank im voraus,
Detlev

[BlackJack]

@dede67: Bitte ganz schnell `eval()` vergessen. Es gibt die `int()`-Funktion, die kann man ganz wunderbar zum Umwandeln von Zeichenketten mit Ziffern zu Zahlen verwenden. Auch für andere Basen als 10.

Dann ist das alles nicht besonders schön lesbar mit nur zwei Leerzeichen einrückung, komischen, nichtssagenden, nummerierten Namen, und keinen Leerzeichen um Zuweisungen und Operatoren. Das ist doch kein BASIC auf 8-Bit-Rechnern, wo man Speicherplatz sparen muss und wo Leerzeichen vom Interpeter zur Laufzeit überlesen werden müssen und damit Rechenzeit kosten.

Statt des `highbit_dec()` reicht doch völlig eine „mirror”-Funktion und dann zählt man von 15 bis 0 runter und spiegelt die Bits vor der Ausgabe. Die Funktion wäre auch bei Deinem Ansatz schon interessant, denn den „mirror”-Code hast Du zweimal in Deinem Code stehen.

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8


def int_to_bin(value, width):
    return '{0:0{1}b}'.format(value, width)


def mirror_bits(value, width):
    return int(int_to_bin(value, width)[::-1], 2)


def main():
    width = 4
    for i in reversed(xrange(2**width)):
        value = mirror_bits(i, width)
        print int_to_bin(value, width), value


if __name__ == '__main__':
    main()

Das ist jetzt hübscher, IMHO zumindest, aber nicht ohne Zeichenketten. Das finde ich letztlich aber gar nicht so schlimm, denn wenn man hier mit den Zahlen auf Bitebene arbeiten würde, wäre es komplexer und wahrscheinlich auch sehr viel langsamer. In C hätte ich mich auf Bitoperationen eingelassen, in Assembler wären Bitschiebereien erst recht meine erste Wahl gewesen, aber in Python gewinnt man dadurch nichts.

Was ist denn der Anwendungsfall?

[dede67]

Hallo BlackJack,
danke für die Antwort.
Meine Routine war, wie geschrieben, zusammengepfuscht - daher auch die sinnlosen Variablennamen.
Normalerweise verwende ich durchaus lange und lesbare Namen

Deine Routine erfüllt leider nicht den Zweck, den ich brauche.
Bei dir kommen die Zahlen ja schon in der richtigen Reihenfolge an.
Was ich brauche ist:
- Eine Zahl wie z.B. 15 (1111) ist gegeben, dann rufe ich eine Routine auf, um davon die Zahl 7 (0111) geliefert zu bekommen.
- Oder eben bei 7 eine 11 und bei 11 eine 3 u.s.w.

Der Einsatzzweck ist ein Progrämmchen, das die Dateien in meinen "Download-Ordnern" so zusammenstellt bzw. auswählt, dass ich damit eine BlueRay randvoll füllen kann. Klappt auch schon sehr gut. Obwohl die Dateien alle im dreistelligen MB-Bereich liegen, komme ich nach ein paar Sekunden Volllast auf einem Core auf unter 10KB Restkapazität (meinem Abbruchkriterium) - bei 24GB Gesamtkapazität.
Der Algorithmus sieht vor, die Dateien nach Größe zu sortieren, dann solange die großen Dateien zuzufügen, bis die jeweils nächst-kleinere Datei nicht mehr auf den Datenträger passt. Hier wird dann die Liste der Dateien getrennt. Der "obere" Teil (mit den kleineren Dateien) wird mehr oder weniger intelligent als Bitmuster hochgezählt (bei einer 1 wird die Datei zur Summe dazugerechnet, bei einer 0 nicht). Wenn dabei aber keine akzeptable Lösung herauskommt, wird der untere Teil (mit den großen Dateien) als Bitmuster heruntergezählt und dann der obere Teil wieder durchlaufen.
Der untere Teil wird "rückwärts" bzw. mit meiner verbesserungswürdigen Routine verändert/durchlaufen.

Sieht dann (nach 6 Sekunden) z.B. so aus:

Code: Alles auswählen

dede@c2q:~> fillBD.py dry
Kapazität auf dem Ziel: 23776 MB
Dateien: 41
---------------------- -XXXXXXXXXXXXXXXXXX   1 GB
---------------------X -XXXXXXXXXXXXXXXXXX  78 MB
XXX----------------X-- X---XXXXXXXXXXXXXXX  13 MB
XXX----------------X-- -X-X-XXXXXXXXXXXXXX   9 MB
XXX----------------X-- --XXXX-XXXXXXXXXXXX   5 MB
--XXXX------------X--- --XX-X-XXXXXXXXXXXX   1 MB
-----XXXXXX------X---- ---X---XXXXXXXXXXXX 168 KB
----XXXX-------X------ XXX--X-XX-XXXXXXXXX  48 KB
----XXXX-------X------ XX-X-XX-X-XXXXXXXXX  24 KB
---XXXXXXXXX-------X-- --XXX-X-----XXXXXXX   8 KB

Wobei die X'e die Dateien kennzeichnen, die zusammen die rechts angezeigte Restkapazität ergeben.

Sicherlich ließe sich mein Algorithmus irgendwie so umbauen, dass ich auf diese unsägliche Routine verzichten könnte.
Aber ich habe jetzt schon so lange mit Rucksack- und 0/1-Teilsummen-Algorithmen rumgewurschtelt....und das war alles viel zu langsam....und jetzt habe ich keine Lust mehr auf tiefergehene Algorithmus-Änderungen (abgesehen von dieser einen hässlichen Funktion)....weil es jetzt schnell und korrekt arbeitet.

Wenn das Tool hinreichend getestet ist und mir Programmcode-technisch nicht völlig peinlich sein muß, werde ich es hier ablegen:
http://dede67.bplaced.net/PhythonScript ... Seite.html
(gerne auch mit Namensnennung im Header von Demjenigen, der mit eine hübschere highbit_dec() sponsert)

Detlev

[BlackJack]

@dede67: Na dann wähle als Startzahl für die Schleife halt zum Beispiel ``mirror_bits(7, 4)`` ( + 1).

Edit: Blöde Frage: Wenn Du die Teilliste mit den grossen Dateien *einmal* umdrehst, dann müsstest Du doch auch da einfach einen *normalen* Zähler verwenden können der runtergezählt wird, oder ist es jetzt für mich einfach zu spät zum nachdenken?

[dede67]

Hallo BlackJack,
die Schleife in der ersten Anfrage war nur ein Demonstartor für die Routine. Die gibts so nicht im Programm.

Zu deinem "Edit":
Möglicherweise könnte ich die untere Liste drehen.
Derzeit liegen die Dateinamen und Dateigrößen allerdings einer "großen" Gesamtliste.
Die beiden einzelnen Bitmuster gelten für jeweils einen Teil der Gesamtliste.
Ich werde mal darüber nachdenken.....obwohl.....lesbarer oder verständlicher würde das Programm dadurch aber sicher nicht.

Ich geh jetzt zu Bett
Detlev

[BlackJack]

@dede67: Wenn ich das jetzt richtig verstanden habe brauchst Du die Bits nur um auf Elemente einer grossen Liste zuzugreifen, beziehungsweise um aus einem iterierbaren Objekt mit Indizes die auszuwählen die dann auch tatsächlich zum Ergebnis gehören? Also so etwas wie das hier (ungetestet):

Code: Alles auswählen

def select_by_bitmap(sequence, bitmap, width, reverse=False):
    if bitmap:
        offset = len(sequence) - width if reverse else 0
        indices = xrange(width)
        if reverse:
            indices = reversed(indices)
        for i in indices:
            if bitmap & 2**i:
                yield sequence[i + offset]

Das wählt aus den `width` ersten Elementen von `paths` die mit einem gesetzten Bit in `bitmask` aus beziehungsweise wenn `reverse` wahr ist dann aus den `width` letzten Elementen die mit einem gesetzten Bit, allerdings von hinten aus betrachtet also mit gespiegelter Bitmaske.

[dede67]

Moin BlackJack,
ich habe mal deine nächtliche Idee umgesetzt und die relevante Teil-Liste gedreht, um sie jetzt standardmäßig durchlaufen zu können.
Das ging leicht:

Code: Alles auswählen

# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# Hier wird die zur rechten Bitmap gehörende Liste bzgl. Reihenfolge
# invertiert. Auf diese Weise wirkt ein Decrement auf die rechte Bitmap
# zuerst auf die kleineren Dateien.
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
files4=files3[0:j][::-1] + files3[j:]

An Position j ist die Liste logisch getrennt.

Und nun bekomme ich z.B. sowas:

Code: Alles auswählen

dede@c2q:~> fillBD.py dry
Kapazität auf dem Ziel: 23776 MB
Dateien: 38   Gesamtgröße: 37905 MB
------------------ XXXXXXXXXXXXXXXXXXXX 905 MB
------------X----- XXXXXXXXXXXXXXXXXXXX  17 MB
----------------XX XXXXXXXXXXXXXXXXXXX- 704 KB
X--------XXXXXXXXX XXXXXXXXXXX--------X 408 KB
----X----XXXXXXXXX XXXXXXXXX-X-----XX-- 280 KB
--------XXXXXXXXXX XXXXXXXXX-----XX-X-- 184 KB
--X-------XXXXXXXX XXXXXXXX-X-X-XX-X--- 128 KB
--------XXXXXXXXXX XXXXXXXX-X--XXX----- 104 KB
--X-------XXXXXXXX XXXXXXXX--XXX----XX-  32 KB
Abbruch! Laufzeit >=10 Sekunden und <100KB Restkapazität.

Summe Dateigrößen: 24931418112
Datenträger      : 24931450880
Restkapazität    : 32768

Und der df liefert für den Zieldatenträger nach dem copy dann auch brav die 32KB Restkapazität
Problem gelöst....wenn auch durch einen Workaround.

Detlev