Columnizer (jetzt: shcol)

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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. :mrgreen:

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. :)
Zuletzt geändert von snafu am Samstag 16. März 2013, 19:33, insgesamt 1-mal geändert.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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...
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Schau dir doch mal Dynamische Programmierung an.
Das Leben ist wie ein Tennisball.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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. :(
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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.
Das Leben ist wie ein Tennisball.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Ich weiß in etwa, was dynamische Programmierung ist. Verstehe aber trotzdem nicht, worauf du hinaus willst.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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...
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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... ;)
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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).
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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?
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

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.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

derdon hat geschrieben:
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.
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...
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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. ;)
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

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
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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. :)
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

mutetella hat geschrieben:

Code: Alles auswählen

    '''
    ...
    Thanks to 'BlackJack' from 'python-forum.de' for this
    peace of code...! '''
Codefrieden? :)
Das Leben ist wie ein Tennisball.
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

Was bedeutet 'Codefrieden'?
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
Benutzeravatar
/me
User
Beiträge: 3554
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

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? :shock:
Antworten