Liste in `num`Teile splitten

[frabron]

Hi,

Ich benutze folgende Funktion, um eine Liste `l` in `num` Teile zu splitten. Das ganze funktioniert wohl wie erwartet, allerdings finde ich die `for` Schleife nicht besonders effizient. Allerdings ergab eine Suche in den üblichen Verdächtigen (itertools usw.) mir keine Idee, wie man das anders machen könnte. Alle Rezepte, die ich fand, erzeugten `x` neue Listen mit einer festen Anzahl an Elementen, wo dann u.U. noch aufgefüllt wurde, wie bei itertools.izip_longest. Aber vielleicht hat ja jemand hier noch eine Idee, wie man das ganze schöner schreiben kann.

Code: Alles auswählen

def chunks(l, num):
    """split a list into num parts. On last turn add all remaining elements"""
    step = len(l) // num

    for i in xrange(num):
        start = step * i
        end = step * (i+1)
        if i == num - 1:
            chunk = l[start::]
        else:
            chunk = l[start:end]
        yield chunk

for chunk in chunks(range(1, 23), 4):
    print chunk

Code: Alles auswählen

> python chunks.py
[1, 2, 3, 4, 5]
[6, 7, 8, 9, 10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20, 21, 22]

Also! Code Golf ist eröffnet

[sma]

Code: Alles auswählen

def chunks(l, num):
    num = (len(l) + num - 1) // num
    while l: yield l[:num]; l = l[num:]

for chunk in chunks(range(1, 23), 4):
     print chunk

gibt:

Code: Alles auswählen

[1, 2, 3, 4, 5, 6]
[7, 8, 9, 10, 11, 12]
[13, 14, 15, 16, 17, 18]
[19, 20, 21, 22]

was ich für das richtigere Ergebnis halte.

Nicht sorgfältig gelesen habend, dachte ich ursprünglich, dies wäre die korrekte Anwort:

Code: Alles auswählen

def chunks(l, num):
    while l: yield l[:num]; l = l[num:]

Daher sieht mein Code so aus, wie er aussieht.

Stefan

[nomnom]

Mein Code (scheint kürzer als Frabrons zu sein und korrekte Ergebnisse zu liefern; trotzdem hässlich):

Code: Alles auswählen

def chunks(l, num):
    step = len(l) // num
    for i in xrange(num+1):
        res = l[i*step:i*step+step]
        if len(l[i*step+step:]) < num:
            yield res + l[i*step+step:]
            break
        yield res

Edit: Neue Version:

Code: Alles auswählen

def chunks(l, num):
    step = len(l) // num
    for i in xrange(num):
        r, n = l[i*step:i*step+step], l[i*step+step:]
        yield r + (n if len(n) < num else [])

Ich denke mal, Smas Vierzeiler (wenn er sich an PEP8 halten würde) dürfte der eleganteste Ansatz sein, außerdem der kürzeste.

[Hyperion]

Wenn die Ergänzung um leere Elemente erlaubt ist, oder aber das letzte Element länger sein darf, dann empfiehlt sich auch der Ansatz aus der Doku zu `izip / zip`:

Code: Alles auswählen

zip(*[iter(s)]*n)

Wobei man die Länge `n` natürlich vorher noch a la sma berechnen muss.

[frabron]

Leere Elemente wollte ich eigentlich nicht in der Liste haben. Eigentliches Ziel war es, eine Liste von Dateien aufzuteilen, um die Dateien per threading zügiger bearbeiten zu können, also statt eine nach der anderen halt mehrere auf einmal.
Das Problem ist komplexer, als ich ursprünglich angenommen habe, deshalb auch mein Beitrag hier. Im Konzept dachte ich noch, teilst du die (Datei)Liste halt auf vier Threads auf, ohne die Komplexität dahinter zu erkennen

Smas Lösung ist in der Tat verführerisch, allerdings wird da ja die Liste verändert, da weiss ich noch nicht, ob mir das für meinen Anwendungsfall gefällt. Aber davon habe ich ja auch im Ursprungspost nix erwähnt. Aber definitiv elegant imo ...

Code: Alles auswählen

r, n = l[i*step:i*step+step], l[i*step+step:]

erzeugt doch, wenn ich das richtig sehe, immer zwei Listen, wobei doch in den meisten Fällen die Liste `n` nicht benötigt wird, oder? Ich weiss, hier geht es nicht im Gigabyte große Listen, aber ich finde es doch ein wenig verschwenderisch, nix für ungut

Was die zip/iter Lösung angeht, die habe ich, wie erwähnt auch schon so ähnlich gefunden, ich finde sie aber schwer verständlich, zumindest schwerer als smas Lösung. Ausserdem bekomme ich damit keine richtige Lösung hin. Entweder sind es zu wenig Ergebnislisten, oder aber nicht alle Elemente verteilt.

Code: Alles auswählen

>>> l = range(20)
>>> n = 3
>>> zip(*[iter(l)] * ((len(l) + n - 1) // n))
[(0, 1, 2, 3, 4, 5, 6), (7, 8, 9, 10, 11, 12, 13)]
>>> zip(*[iter(l)] * ((len(l) + n) // n))
[(0, 1, 2, 3, 4, 5, 6), (7, 8, 9, 10, 11, 12, 13)]
>>> zip(*[iter(l)] * ((len(l)) // n))
[(0, 1, 2, 3, 4, 5), (6, 7, 8, 9, 10, 11), (12, 13, 14, 15, 16, 17)]
>>> 
>>> (len(l) + n - 1) // n
7
>>> (len(l) + n) // n
7
>>> (len(l)) // n
6
>>> 

:K fehlt irgendwie noch die Verteilung des Rests auf die letzte Liste

Echt nicht so einfach, wie anfangs gedacht

[sparrow]

Wenn es um die Aufteilung von Arbeitsdaten auf Threads geht: Warum nimmst du dir nicht eine Warteschlange aus der sich jeder fertige Thread bei Bedarf neue Arbeit holt?

Ich weiß nicht was genau deine Threads machen, aber wenn die Bearbeitung von den Dateien unterschiedlich lange dauern kann es dir so passieren, dass Thread 1 fertig ist (seine 4 Dateien konnten schneller abgearbeitet werden) und nichts mehr zu tun hat, während in der Liste für Thread 2 noch zwei Dateien darauf warten abgearbeitet zu werden.

[frabron]

Ja, das wäre wohl passiert, das ein Thread vor dem anderen fertig geworden wäre - Konditional deshalb, weil ich feststellen musste, dass Teile der Bearbeitungs - Kommandos leider nicht Thread-safe sind. Deshalb ist das Thema für mich nur noch von allgemeinem Interesse, was nicht abwertend gemeint ist.
Das Thema Warteschlange und Threads werde ich mir mal ansehen. Meine Erfahrung mit Threads ist offensichtlich nicht berauschend

[nomnom]

Code: Alles auswählen

r, n = l[i*step:i*step+step], l[i*step+step:]

erzeugt doch, wenn ich das richtig sehe, immer zwei Listen, wobei doch in den meisten Fällen die Liste `n` nicht benötigt wird, oder?

Code: Alles auswählen

def chunks(l, num):
    step, rest = divmod(len(l), num)
    for i in xrange(num):
        r = l[i*step:i*step+step]
        yield r + (i + 1 == num and rest and l[i*step+step:] or [])

[sma]

Smas Lösung ist in der Tat verführerisch, allerdings wird da ja die Liste verändert,

Smas Lösung verändert die Liste nicht.

Stefan

[frabron]

Hm, sorry, aber passiert das nicht in dieser Zeile?

Code: Alles auswählen

while l: yield l[:num]; l = l[num:]

Wenn doch an l die liste gebunden ist, überschreibst du doch hier

Code: Alles auswählen

 l = l[num:]

die Liste mit dem Restbestand von sich selber, oder? Musst du ja auch, sonst while'd es ja eine Weile
Ich versuche das mal nachzuvollziehen, aber ich bin da jetzt doch ein wenig überrascht ... aber grundsätzlich bist du der versierte von uns beiden, deshalb will ich da gar nicht widersprechen

[EyDu]

Nein, die Liste wird hier nicht überschrieben. Wenn du eine Zuweisung machst, dann wir dein Objekt an einen Namen gebunden. Im Prinzip zeigt der Name l also nur auf eine Liste. Wenn du l nun eine andere Liste zuweist, dann zeigt l eben wo anders hin. Der alte Wert ist davon nicht betroffen. Du darfst dir eine Variable also nicht als einen Speicherbereich vorstellen, so wie es in C beispielsweise der Fall ist.

[frabron]

Von Speicherbereichen verstehe ich auch nix
Ich habe in letzter Zeit wohl zuviel mit Javascript gearbeitet, wo zumindest Objekte als Referenz an die Funktion übergeben werden und dann auch innerhalb der Funktion verändert werden können. Das selbe Muster hatte ich auch hier in diesem Falle angenommen, fälschlicherweise.

[Hyperion]

Mach es Dir vielleicht einmal an einem kleinen Beispiel klar:

Code: Alles auswählen

In [9]: l = [1, 2, 3]

In [10]: def change(l):
   ....:     l = l[1:]
   ....:     print(l)
   ....:     

In [11]: l = [1, 2, 3]

In [12]: change(l)
[2, 3]

In [13]: l
Out[13]: [1, 2, 3]

Wie Du siehst "simuliere" ich smas Chunking in `change`. Das Objekt, welches *in* der Funktion zunächst an `l` gebunden ist, ist das Listenobjekt, welches außerhalb von `change` ebenfalls an den Namen `l` gebunden ist. In der Liste binde ich nun das Ergebnis einer Slicing-Operation an den lokalen Namen `l`. Wie erwartet wird die verkürzte Liste ausgegeben. Nach Abarbeiten der Funktion sehen wir aber, dass das ursprüngliche Listenobjekt eben nicht verändert wurde, sondern weiterhin gleich geblieben ist.

In diesem Teil hier `l[1:]` ist `l` noch an das gobale Listenobjekt gebunden, durch die Zuweisung `l = ` wird das *Ergebnis* der Operation nun an `l` gebunden und die "Referenz" auf die äußere Liste ist in der Funktion "verloren".

Slicing erzeugt eben ein neues Objekt und verändert ein bestehendes nicht.

Das wäre ja auch ein wenig wirr bzw. inkonsistent, denn man kann Slicing ja auch auf Immutable Sequence Types, etwa Strings, anwenden:

Code: Alles auswählen

In [26]: s = "Python"

In [27]: s[2:4]
Out[27]: 'th'

In [28]: s
Out[28]: 'Python'

Das könnte zu schlimmen Bugs führen, wenn Slicing je nach Objekttyp ein unterschiedliches Verhalten hätte...

Anders sieht es z.B. hier aus, wo wir tatsächlich das Objekt ändern:

Code: Alles auswählen

In [14]: def real_change(l):
   ....:     l.pop()
   ....:     print(l)
   ....:     

In [16]: l
Out[16]: [1, 2, 3]

In [17]: real_change(l)
[1, 2]

In [18]: l
Out[18]: [1, 2]

[frabron]

Danke, ich hatte das schon mit einem eigenen Schnippsel soweit nachvollzogen, aber dein Beispiel macht das nochmals deutlicher (aus dem vim kopiert, deshalb die Zeilennummern).

Code: Alles auswählen

   5 def mod(a):
   6     a = 5
  14 a = 1
  15 mod(a)
  16 print a

gibt immer noch '1' aus, wie zu erwarten. Ich hatte in der Tat übersehen, dass durch `l = l[1:]` ein neue Liste an `l` gebunden wird, und nicht die alte überschrieben.

In Javascript funktioniert das leider nicht so:

Code: Alles auswählen

    <script type="text/javascript">
        function mod_var(a) {
            var b = a;
            b[0] = 5;
        }

        var a = [1,2,3];
        mod_var(a);
        alert(a);
    </script>

daher meine "Verwirrung".

Edith:
Das stimmt natürlich auch wieder nicht. Ich habe ja keine Kopie der Liste angelegt, mittels `a.slice()` bekommt man das selbe Verhalten hin ...

[Hyperion]

Vorsicht! *Das* funktioniert in Python genauso:

Code: Alles auswählen

In [34]: def mod_var(a):
   ....:     b = a
   ....:     b[0] = 5
   ....:     

In [35]: l = [1, 2, 3]

In [36]: mod_var(l)

In [37]: l
Out[37]: [5, 2, 3]

`=` kopiert eben nicht ein Objekt, sondern bindet es lediglich an einen anderen Namen! Das `b` in `mod_var` wird an *dasselbe* Objekt gebunden, an das auch `a` gebunden ist.

Das kannst Du auch mittels `is` überprüfen:

Code: Alles auswählen

In [39]: a = [1, 2, 3]

In [40]: b = a

In [41]: b is a
Out[41]: True

Um es noch einmal auf den Punkt zu bringen - und genau das wollte ich ja oben schon erklären:
Wenn Du ein Objekt an eine Funktion übergibst, dann ist das *keine* Kopie, sondern dasselbe Objekt! Dieses kannst Du *in* der Funktion auch manipulieren, je nach den Möglichkeiten eines Typs. Das Zuweisen an einen Namen bindet nur ein Objekt an diesen - dabei ist es egal, welches Objekt das ist. Es passiert bei der Zuweisung keine Magie. Man muss sich da genau angucken, was auf der linken Seite von `=` passiert

Beim Slicing wird halt ein *neues* Objekt erzeugt, daher wird das bei smas Ausdruck an den selben Namen gebunden - die alte Bindung wird damit aufgelöst. Hier wird einfach dasselbe Objekt an einen anderen Namen gebunden.

[Nuby]

Nein, die Liste wird hier nicht überschrieben. Wenn du eine Zuweisung machst, dann wir dein Objekt an einen Namen gebunden. Im Prinzip zeigt der Name l also nur auf eine Liste. Wenn du l nun eine andere Liste zuweist, dann zeigt l eben wo anders hin. Der alte Wert ist davon nicht betroffen. Du darfst dir eine Variable also nicht als einen Speicherbereich vorstellen, so wie es in C beispielsweise der Fall ist.

Und was passiert dann mit dem Objekt, zu dem kein Verweis mehr führt? Sollte man das Objekt anschließend löschen? Was ist mit den sonstigen Verweisen, die auf das "alte" Objekt verweisen?

[BlackJack]

@Nuby: Wenn kein Verweis mehr auf ein Objekt existiert wird es von der automatischen Speicherbereinigung (englisch „garbage collection”) sehr wahrscheinlich irgend wann freigegeben.

Wie willst Du ein Objekt löschen wenn Du keinen Verweis mehr darauf hast?