Seite 1 von 3
Columnizer (jetzt: shcol)
Verfasst: Mittwoch 4. Juli 2012, 18:53
von snafu
Meine neueste Projektidee ist ein Tool, mit dem sich `ls`-ähnliche Ausgaben (z.B. in Verbindung mit `os.listdir()`) erzeugen lassen kann. Es geht also darum, eine Liste mit Zeichenketten so zu formatieren, dass auch bei mehrzeiliger Ausgabe keine Verschiebung der Spalten stattfindet. Ihr wisst ja selber, wie `ls` vorgeht: Solange die Elemente nebeneinander in eine Zeile passen, dann werden sie einfach nur in gleichem Abstand voneinander ausgegeben. Sobald aber die Zeile überschritten wird und ein Umbruch stattfinden muss, stehen aufeinander folgende Elemente nicht mehr nebeneinander, sondern untereinander. Auch erfolgt die Verteilung auf die Spalten möglichst gleichmäßig, damit alle Zeilen möglichst bis zum Ende gefüllt werden können und man in der letzten Zeile nicht noch Riesenraum nach rechts hat.
Als ersten Schritt, um die Aufgabe zu lösen, probiere ich, die unterschiedlichen Spaltenbreiten und Anzahl der Spalten zu ermitteln, wobei die Spaltenzahl sich ja ganz einfach aus der Anzahl der Breitenangaben ergibt. Ein bißchen Code zum Ermitteln dieser Breitenangaben habe ich schon:
Code: Alles auswählen
def get_column_widths(items, spacing=2, max_line_width=80):
column_widths = []
filled_width = 0
column_index = 0
for item in items:
item_width = len(item)
if item_width > max_line_width:
# Item would fill more than the whole line length
raise ValueError('Item width too long for line')
if column_index == len(column_widths):
# Current index after last column
if (filled_width + item_width) <= max_line_width:
# New column for item will fit in line
# => Add new column
# XXX: Setting zero-length is needed to see
# the offset in following code (ugly!)
column_widths.append(0)
else:
# New column would be too large for line
# => Fallback to first column
column_index = 0
offset = item_width - column_widths[column_index]
if offset > 0:
# Item wider than column => Enlarge column
column_widths[column_index] += offset
# Enlarge total length with respect to spacing
filled_width += offset + spacing
# Increase index used for next iteration
column_index += 1
return column_widths
Das ergibt beim Testen:
Code: Alles auswählen
>>> import columnizer
>>> columnizer.get_column_widths([76 * 'x', 2 * 'x', 78 * 'x'])
[78, 2]
...was soweit auch korrekt ist, da die letzte Länge von 78 ja die vormalige 76er-Spalte verbreitert.
Am Code muss aber noch viel gemacht werden. So klappt folgendes noch nicht wie gewünscht:
Code: Alles auswählen
>>> columnizer.get_column_widths([50 * 'x', 25 * 'x', 60 * 'x'])
[60, 25]
Hier hätte die Funktion natürlich beachten müssen, dass nach dem Verbreitern der Zeile eine zu hohe Gesamtgröße besteht (nämlich inklusive Abstand 87 statt 80). Aber dafür steht er ja auch im Ideen-Forum und nicht im Projekte-Forum.
Und abgesehen davon macht die Funktion natürlich nicht das, was man von `ls` erwarten würde, da sie nämlich nach dem Zeilenumbruch das 3. Element unter das 1. Element gesetzt hat (60 in die 50er-Spalte). Eigentlich müsste da erstmal die 25er-Länge drunter rutschen. Wie gesagt: Alles noch im Anfangsstadium.

Re: Columnizer
Verfasst: Sonntag 15. Juli 2012, 11:37
von snafu
Ich bin etwas weiter gekommen:
https://gist.github.com/3116202
"Hauptfunktion" ist `columnize()`. Sie erwartet mindestens eine Liste von Strings, für die sie eine spaltenmäßige Formatierung vornehmen soll. Optional kann als zweites Argument der Spaltenabstand angegeben werden (Standard: 2), sowie als drittes Argument die Länge einer Zeile (Standard: 80).
Bitte erwartet aber keine Wunder. Die Einteilung der Spalten ist bis jetzt sehr naiv programmiert und daher noch arg verbuggt. Zum Testen empfehle ich `os.listdir()`-Ausgaben. Falls es mal komisch aussehen sollte (was momentan noch sehr häufig sein wird), dann kann man das Terminalfenster durchaus vergrößern, um ein bißchen näher an der eigentlich gedachten Ausgabe zu sein...
Achja, und die Verteilung der Items geschieht nach wie vor noch zeilenmäßig, statt zeilenmäßig. Da werde ich mir auch noch was für ausdenken müssen.
Re: Columnizer
Verfasst: Montag 19. November 2012, 16:46
von snafu
Der Algorithmus zum Ermitteln der Spaltenbreiten dürfte jetzt ausgereift sein:
Code: Alles auswählen
from collections import namedtuple
from itertools import count
LineSpec = namedtuple('LineSpec', ['spacing', 'column_widths'])
def get_line_spec(items, spacing=2, max_width=80):
for max_lines in count(1):
column_widths = []
current_line = 1
for item in items:
item_width = len(item)
if item_width > max_width:
raise ValueError('item width exceeds max_width')
if not column_widths or current_line > max_lines:
# append column
column_widths.append(item_width)
current_line = 2
else:
# put item into current column
column_widths[-1] = max(column_widths[-1], item_width)
current_line += 1
total_spacing = spacing * (len(column_widths) - 1)
line_width = sum(column_widths) + total_spacing
if line_width > max_width:
# restart with max_lines increased by 1
# (next iteration in outer loop)
break
else:
return LineSpec(spacing, column_widths)
Ich gehe Trial-and-Error mäßig vor und mache eine spaltenbezogene Anordnung. Es wird also zuerst versucht, alles in eine Zeile zu packen. Wenn dies fehlschlägt, wird von vorne begonnen und diesmal mit 2 Zeilen gearbeitet. Das erste und das zweite Item kämen also in die erste Spalte, das dritte und das vierte Item in die zweite Spalte usw. Schlägt auch dies fehl, wird wieder von vorn begonnen - diesmal mit 3 Zeilen. Das Spiel geht solange, bis eine passende Konfiguration gefunden wurde und die geb ich dann zurück. Hinsichtlich der tatsächlichen Ausgabe mittels String-Formatting werde ich noch die passende Funktion schreiben. Dachte nur, dass vielleicht jemand bei dem bisherigen Teil der Aufgabe drübergucken möchte oder anderweitig interessiert ist...
Re: Columnizer
Verfasst: Montag 19. November 2012, 17:06
von EyDu
Schau dir doch mal Dynamische Programmierung an.
Re: Columnizer
Verfasst: Montag 19. November 2012, 23:25
von snafu
EyDu hat geschrieben:Schau dir doch mal Dynamische Programmierung an.
Spielst du darauf an, das Problem in Teilprobleme zu zerlegen und sich damit Iterationsschritte zu sparen? Wie könnte man das denn hier angehen? Ich habe in den letzten Monaten immer wieder mal überlegt, ob es einen Algorithmus gibt, der nach einem Durchlauf, wo zunächst die Längen "eingesammelt" werden, anschließend die nötige Anordnung der Elemente ermittelt, damit es von den Spalten her optimal passt. Mir ist dazu aber leider nichts besseres eingefallen.

Re: Columnizer
Verfasst: Montag 19. November 2012, 23:36
von EyDu
Nein, ich spiele darauf an, dass man solche Probleme recht gut mit
Dynamischer Programmierung lösen kann. Das ist zugegebenermaßen für Nicht-Informatiker eine schwere Kost, aber du kannst es dir ja mal anschauen.
Re: Columnizer
Verfasst: Montag 19. November 2012, 23:47
von snafu
Ich weiß in etwa, was dynamische Programmierung ist. Verstehe aber trotzdem nicht, worauf du hinaus willst.
Re: Columnizer
Verfasst: Samstag 19. Januar 2013, 00:50
von snafu
Habe mich nochmal drangesetzt. "Dynamische Programmierung" ist es leider nicht geworden. Dafür bin ich entweder zu unerfahren oder es gibt tatsächlich keinen dazu passenden Algorithmus dazu...
Habe jedenfalls das Ermitteln der Spaltenbreiten nochmal umgeschrieben. Die Elemente für die jeweilige Spalte werden jetzt quasi als Chunks in einem Rutsch geholt. Ich setze hier `islice()` ein, um die fortwährende Generierung von temporären Listen zu vermeiden, da mein Vorgehen eben immer noch Trial&Error-mäßig ist. Ein paar Details zum Ablauf habe ich als Kommentar in den Quellcode geschrieben (wobei der Kommentar noch nicht ganz so ist, wie ich es eigentlich beschreiben möchte).
Bei nächster Gelegenheit werde ich dann auch nochmal eine Funktion schreiben, welche die tatsächliche Formatierung vornimmt. Allein mit den Spaltenbreiten ist das ganze ja doch noch arg theoretischer Natur...
https://gist.github.com/4569688
Re: Columnizer
Verfasst: Freitag 15. Februar 2013, 13:01
von snafu
Habe nun - wie angekündigt - eine vollständig funktionsfähige Version gebastelt:
http://pastebin.com/1zw9eFRm
Unter Python2 gibt es noch Probleme mit Umlauten (bzw nicht ASCII-Zeichen) in Bezug auf die Längenermittlung und der Algo zur Ermittlung der Spaltenbreiten geht sehr viele überflüssige Iterationen durch. Dies macht sich selbst bei einem Test mit `columnize(os.listdir('/usr/bin'))` (also recht vielen Elementen) zwar kaum bemerkbar, ist aber natürlich trotzdem unschön. Denn man muss natürlich keinesfalls jedes Mal alle Elemente durchlaufen, um zu erkennen, dass man über das Fassungsvermögen für die jeweilige Zeilenanzahl hinausgekommen ist. Ich wollte allerdings zuviel Komplexität innerhalb von `get_line_properties()` vermeiden. Wahrscheinlich mache ich aus dieser Funktion auch noch eine Klasse, vornehmlich als Namensraum für Hilfsfunktionen (bzw -methoden). Auch mit dem Konzept der dynamischen Programmierung habe ich mich weiter vertraut gemacht (lese gerade "Diskrete Strukturen, Bd. 1" von Angelika Steger, wo dies auf ein paar Seiten erklärt wird) und werde mal versuchen, es sinnvoll in meinen Code einzubauen...
Re: Columnizer
Verfasst: Montag 18. Februar 2013, 15:35
von snafu
Die weitere Entwicklung findet jetzt im neu erstellten
Github-Repo statt. Außer ein paar sehr kleinen Modifikationen habe ich das zuletzt gepostete Skript nur noch um eine (stupide) Testfunktion erweitert.
Das nächste Ziel wird jetzt die schon genannte Anwendung dynamischer Programmierung (also Vermeidung von Mehrfachberechnungen der gleichen Sache), sowie das Ausmerzen von Darstellungsfehlern sein - und das Schreiben vernünftiger Testfälle (hihi). Insbesondere in Bezug auf Punkt 1 stellen sich gewisse Fragen bezüglich Design und Herangehensweise (wobei ich schon ein paar Ideen habe) und somit werde ich wohl erstmal wieder ein bißchen in mich gehen, bevor ich etwas neues hochlade...

Re: Columnizer
Verfasst: Donnerstag 28. Februar 2013, 23:45
von snafu
Habe zwischenzeitlich
columnize entdeckt, was die gleichen Ziele verfolgt wie mein Projekt. Inzwischen habe ich das Projekt übrigens in `shcol` umbenannt.
Nach dem
letzten Commit (welchen ich vor einigen Minuten gepusht hab) verhält sich ein `shcol.columnize()` genau so wie ein `columnize.columnize()` mit den Default-Einstellungen, nur mit dem Unterschied dass mein Algo für große Mengen an Items eine deutlich bessere Laufzeit hat. So brauchte mein Rechner mit `os.listdir('/usr/bin')` als Eingabe (1939 Dateinamen) ca 1,3 Sekunden für *einen* Durchlauf mit `columnize`, während `shcol` die selbe Menge in durchschnittlich 0,085 Sekunden schaffte.
Zudem ist bei `columnize` sämtlicher Code innerhalb einer einzigen Funktion implementiert. Ich hingegen habe den Code objektorientiert in zwei Klassen mit diversen Methoden gesplittet, zwecks besser Test- und Wartbarkeit (wobei sich an der API wohl noch einiges ändern wird).
Ich werde den Code jetzt allmählich vorbereiten für's erste Release (v.a. vernünftige Doku und Tests schreiben).
Re: Columnizer (jetzt: shcol)
Verfasst: Mittwoch 18. September 2013, 13:52
von snafu
So, alle Klassen, Methoden und die Funktion auf Modulebene sind nun brav dokumentiert. Es kam Funktionalität für eine sortierte Ausgabe der übergebenen Strings dazu und es wurden noch intern einige Änderungen am Code vorgenommen. Außerdem findet man jetzt eine grobe Beschreibung der gedachten Anwendung des Moduls auf der zugehörigen
Github-Seite.
Ich mache mich jetzt noch an ordentliche automatisierte Tests (die hab ich ignoranterweise bisher nicht geschrieben) und werde danach das Projekt endlich mal auf PyPI hochladen....
PS: Weiß jemand, wie man die ins dortige README-File eingefügten Python-Shell Ausgaben mit Syntaxhervorhebung anzeigen lassen kann?
Re: Columnizer (jetzt: shcol)
Verfasst: Mittwoch 18. September 2013, 16:37
von derdon
snafu hat geschrieben:PS: Weiß jemand, wie man die ins dortige README-File eingefügten Python-Shell Ausgaben mit Syntaxhervorhebung anzeigen lassen kann?
Jup, siehe
https://help.github.com/articles/github ... ghlighting.
Re: Columnizer (jetzt: shcol)
Verfasst: Mittwoch 18. September 2013, 18:00
von snafu
Wenn ich so vorgehe, wie im von dir verlinkten Ruby-Beispiel (s. Rohtext meiner aktuellen
README), dann ist die Darstellung des Codes komplett kaputt (Zeilenumbrüche werden nicht mehr erkannt und Syntax-Hervorhebungen gibt es nach wie vor nicht). Was mache ich falsch?
EDIT: Hat sich erledigt. Man sollte für Markdown halt auch nicht `.rst`, sondern stattdessen die Endung `.md` nehmen...
Re: Columnizer (jetzt: shcol)
Verfasst: Dienstag 5. November 2013, 02:01
von snafu
Habe soeben das Release 0.1 auf PyPi hochgeladen:
https://pypi.python.org/pypi/shcol
Die nächste Version wird sehr wahrscheinlich auch von der Kommandozeile aus aufrufbar sein und z.B. die Terminalbreite selbst erkennen können. Aber dies vermutlich nicht vor 2014.

Re: Columnizer (jetzt: shcol)
Verfasst: Dienstag 5. November 2013, 18:46
von mutetella
snafu hat geschrieben:... die Terminalbreite selbst erkennen ...
Auf der Suche nach einer Möglichkeit, die Terminalgröße ohne `curses`, `stty` oder abenteuerlichem Auslesen von `env`-Variablen zu bekommen und das vielleicht auch noch in einer Console ohne X bin ich zwar sehr bald auf `ioctl` gestoßen, konnte das aber mangels C Kenntnis nicht umsetzen.
BlackJack hat mir dann geholfen, herausgekommen ist das:
Code: Alles auswählen
from ctypes import c_ushort, sizeof, Structure
from termios import TIOCGWINSZ
from fcntl import ioctl
import sys
class WinSize(Structure):
'''To get the terminal size information via the UNIX systemcall
'ioctl()'. This is needed cause the control sequence '\033[18t'
only work proper in xterm-like terminals but not without running
X-Server.
The 'WinSize.from_file()'-method returns the result of 'ioctl()'
and is wrapped by 'window_size()'. Use this function instead.
Thanks to 'BlackJack' from 'python-forum.de' for this
peace of code...! '''
_fields_ = [
('rows', c_ushort),
('columns', c_ushort),
('x_pixels', c_ushort), # Unused.
('y_pixels', c_ushort), # Unused.
]
@classmethod
def from_file(cls, tty_file):
result = ioctl(tty_file, TIOCGWINSZ, '\0' * sizeof(cls))
return cls.from_buffer_copy(result)
def window_size():
'''window_size() -> (rows, columns) '''
size = WinSize.from_file(sys.stdout)
return size.rows, size.columns
Vielleicht wird's Dir ja mal 'ne Hilfe sein.
mutetella
Re: Columnizer (jetzt: shcol)
Verfasst: Mittwoch 6. November 2013, 00:32
von snafu
Joa, man findet ja überall im Netz entsprechende Schnipsel zu dem Thema. Da hätte ich mich dann eben eingearbeitet. Ich glaube, ein aktuelles Python (3.3) hat sogar schon Funktionalität zum Ermitteln der Terminalmaße eingebaut. Aber trotzdem danke für's Posten. Das ist auf jeden Fall ein guter Start.

Re: Columnizer (jetzt: shcol)
Verfasst: Mittwoch 6. November 2013, 01:36
von EyDu
mutetella hat geschrieben:Code: Alles auswählen
'''
...
Thanks to 'BlackJack' from 'python-forum.de' for this
peace of code...! '''
Codefrieden?

Re: Columnizer (jetzt: shcol)
Verfasst: Mittwoch 6. November 2013, 07:55
von mutetella
Was bedeutet 'Codefrieden'?
Re: Columnizer (jetzt: shcol)
Verfasst: Mittwoch 6. November 2013, 08:27
von /me
mutetella hat geschrieben:Was bedeutet 'Codefrieden'?
Na du hat doch "peace of code" geschrieben. Da peace
Frieden heißt, halte ich das für eine angemessene Übersetzung.
Vielleicht meintest du ja
piece, also
Stück. Oder solltest du
piss gemeint haben?
