Werte aus zwei Listen aufsteigend sortieren und mit Quelle ausgeben.

[Daikoku]

Hallo,

ich habe zwei Listen, welche jeweils Integers in der Range von 1 bis max. 899 enthalten können.
Ich möchte die Werte aus beiden Listen, aufsteigend sortiert, mit der jeweiligen Quellenangabe ausgeben.
Ich habe mir nachstehende Lösung überlegt und würde gerne wissen, ob diese so brauchbar ist,
oder ein anderer Lösungsansatz hier vielleicht sinnvoller wäre. Vielen Dank.

Ich benutze Python 3.5.2 unter Windows Windows-7-6.1.7601-SP1.

Code: Alles auswählen

def remove_the_first_item(list):
    try:
        removed = list.pop(0)
    except:
        removed = 999  # end of list
    return removed, list

def smallest_element(list1, list2):
    a, list1 = remove_the_first_item(list1)
    b, list2 = remove_the_first_item(list2)
    while True:
        if a < b:
            yield '{} aus Liste 1'.format(a)
            a, list1 = remove_the_first_item(list1)
        else:
            if a == 999 and b == 999: break   # Ende
            yield '{} aus Liste 2'.format(b)
            b, list2 = remove_the_first_item(list2)

def smallest_element_wrapper(values_from_smallest_element):
    for value in values_from_smallest_element:
        yield value

# Nach der Verarbeitung müssen beide Listen im Original erhalten bleiben.
# Die Listen sind hier bewusst vorsortiert.
x = [10,20,40,70,84,85,91,95,120]
y = [15,20,39,72,83,90]

wrap = smallest_element_wrapper(smallest_element(x[:],y[:]))
for c, i in enumerate(wrap, start=1):
    print('{0:2.0f}. {1}'.format(c,i))

# ******************************************************************************
# Ausgabe:
#   1. 10 aus Liste 1
#   2. 15 aus Liste 2
#   3. 20 aus Liste 2
#   4. 20 aus Liste 1
#   5. 39 aus Liste 2
#   6. 40 aus Liste 1
#   7. 70 aus Liste 1
#   8. 72 aus Liste 2
#   9. 83 aus Liste 2
# 10. 84 aus Liste 1
# 11. 85 aus Liste 1
# 12. 90 aus Liste 2
# 13. 91 aus Liste 1
# 14. 95 aus Liste 1
# 15. 120 aus Liste 1

[Sirius3]

@Daikoku: Verwende niemals ein nacktes except, weil das wirklich jeden Fehler abfängt. Du willst in remove_the_first_item eigentlich nur einen IndexError abfangen. Nenne Variablen nicht wie häufig verwendete eingebaute Funktionen (list). list wird verändert, sollte also irgendwo fett im Doc-String stehen. Eigentlich würde ich die Funktion ganz weg lassen und einfach nur »a = list1.pop(0) if list1 else 999« schreiben. Wobei 999 ein schlechter Wert ist, um anzuzeigen, dass eine Liste fertig ist. Statt mit pop arbeitet man am besten mit Iteratoren »iter(list1)« und »next« (dann macht man sich auch nicht die Listen kaputt). Dass für beide Listen quasi der selbe Code dasteht ist auch nicht schön, vor allem, wenn man das auf drei oder mehr Listen erweitern will. Da würde man am besten die Listen in eine Liste stecken.
Den Sinn von »smallest_element_wrapper« verstehe ich nicht.

Als Zwischenschritt kommt das dabei raus:

Code: Alles auswählen

def smallest_element(list1, list2):
    iter1 = iter(list1)
    iter2 = iter(list2)
    a = next(iter1, None)
    b = next(iter2, None)
    while a is not None or b is not None:
        if b is None or a < b:
            yield '{} aus Liste 1'.format(a)
            a = next(iter1, None)
        else:
            yield '{} aus Liste 2'.format(b)
            b = next(iter2, None)

x = [10,20,40,70,84,85,91,95,120]
y = [15,20,39,72,83,90]
 
wrap = smallest_element(x, y)
for c, i in enumerate(wrap, start=1):
    print('{0:2.0f}. {1}'.format(c,i))

Alternativ helfen Funktionen aus itertools:

Code: Alles auswählen

from itertools import chain, repeat
x = [10,20,40,70,84,85,91,95,120]
y = [15,20,39,72,83,90]

wrap = sorted(chain(zip(x, repeat(1)), zip(y, repeat(2))))
for index, (value, list_nr) in enumerate(wrap, 1):
    print('{:2d}. {} aus Liste {}'.format(index, value, list_nr))

[Daikoku]

@Sirius3: Vielen Dank für Deine Ausführungen.
Die eingebaute Funktion list zu überschreiben war nicht gewollt, hatte ich übersehen.
Das nackte except hatte ich der Einfachheit halber gewählt, da die Listen hardcoded sind und evtl. Fehler für mich vorhersehbar.
Werde in der Zukunft ein paar Zeilen Code mehr schreiben, damit dies zu keinen Irritationen führt. Danke für den Hinweis.
Auch habe ich vergessen den Code aufzuräumen, sodass smallest_element_wrapper natürlich völlig überflüssig geworden ist.

Ich werde mit Deiner Lösung "from itertools import chain, repeat" jetzt erst einmal weiterarbeiten.
Vielen Dank für all Deine Hinweise.

[Daikoku]

ich möchte noch einmal auf die einzelnen Ausführungen von Sirius3 zurück kommen.

Code: Alles auswählen

def smallest_element(liste1, liste2):
    iter1 = iter(liste1)
    iter2 = iter(liste2)
    a = next(iter1, None)
    b = next(iter2, None)
    while a is not None or b is not None:
        if b is None or a is not None and a < b:
            yield '{} aus Liste 1'.format(a)
            a = next(iter1, None)
        else:
            yield '{} aus Liste 2'.format(b)
            b = next(iter2, None)

x = [10,20,40,70,120]
y = [15,20,39,72,83,90,120]

# Lösung 1
wrap = smallest_element(x,y)
for index, value in enumerate(wrap, start=1):
    print('{:2d}. {}'.format(index, value))

# Lösung 2
wrap = sorted(chain(zip(x, repeat(1)), zip(y, repeat(2))))
for index, (value, list_nr) in enumerate(wrap, 1):
    print('{:2d}. {} aus Liste {}'.format(index, value, list_nr))

Beide Lösungen führen zu dem gleichen Ergebnis.
Die Lösung 2 ist hier für mich die geeignetere Lösung und dies nicht nur, weil diese wesentlich kompakter, sondern vor allem, weil diese nur die Hälfte der CPU-Zeit benötigt wie Lösung 1. Nochmals vielen Dank @Sirius3, Deine Lösung ist genial.

Eine kurze Erläuterung zu Lösung 2:

Die Funktion zip(x, repeat(1)) erzeugt aus der Liste x ein iterierbares Objekt, welches dann über Tupel iteriert werden kann.
Die Funktion repeat(1) gibt nur das Objekt selber zurück, in diesem Fall also 1.

Zum Beispiel würde die Funktion list(zip(x, repeat(1))) eine neue Liste [(10, 1), (20, 1), (40, 1), (70, 1), (120, 1)] erzeugen.
Analog hierzu, würde die Funktion list(zip(y, repeat(2))) ebenfalls eine neue Liste [(15, 2), (20, 2), (39, 2), (72, 2), (83, 2), (90, 2), (120, 2)] erzeugen.

Die Funktion chain verkettet beide Listen wieder zu einer einzigen.
Die Funktion list(chain([(10, 1), (20, 1), (40, 1), (70, 1), (120, 1)], [(15, 2), (20, 2), (39, 2), (72, 2), (83, 2), (90, 2), (120, 2)])) erzeugt
eine neue Liste [(10, 1), (20, 1), (40, 1), (70, 1), (120, 1), (15, 2), (20, 2), (39, 2), (72, 2), (83, 2), (90, 2), (120, 2)].

Diese neue Liste, muss dann nur noch mit sorted in die gewünschte Reihenfolge gebracht werden und schon war die Aufgabe gelöst.
Genial einfach, wenn man die richtigen Werkzeuge zur Hand hat.

[snafu]

Das Sortieren kann man auch noch direkter vornehmen:

Code: Alles auswählen

sorted([(item, 1) for item in x] + [(item, 2) for item in y])

Ist aber etwas langsamer und verbraucht mehr Speicher (kommt ja immer auf die echten Daten an).

[Sirius3]

@snafu: die chain-Variante kann man einfach auf beliebig viele Listen erweitern:

Code: Alles auswählen

lists = [x, y]
wrap = sorted(chain.from_iterable(zip(n, repeat(m)) for m, n in enumerate(lists, 1)))

[Daikoku]

@snafu, vielen Danke für Deine Lösung.

Unabhängig von der Flexibilität der jeweiligen Lösung, hier einmal die Performance:

Code: Alles auswählen

import cProfile
import os
import sys
import platform

from itertools import chain, repeat


def do_cprofile(func):
    def profiled_func(*args, **kwargs):
        profile = cProfile.Profile()
        try:
            profile.enable()
            result = func(*args, **kwargs)
            profile.disable()
            return result
        finally:
            profile.print_stats()
    return profiled_func

def smallest_element(liste1, liste2):
    iter1 = iter(liste1)
    iter2 = iter(liste2)
    a = next(iter1, None)
    b = next(iter2, None)
    while a is not None or b is not None:
        if b is None  or  a is not None and a < b:
            yield '{} aus Liste 1'.format(a)
            a = next(iter1, None)
        else:
            yield '{} aus Liste 2'.format(b)
            b = next(iter2, None)

# Lösung 1
@do_cprofile
def loesung_1(x,y,z):
    print('-' * 80)
    print('   Ergebnis zu Lösung 1:\n')
    for _ in range(z):
        wrap = smallest_element(x,y)
        for index, value in enumerate(wrap, start=1):
            pass
            #print('{:2d}. {}'.format(index, value))

# Lösung 2
@do_cprofile
def loesung_2(x,y,z):
    print('-' * 80)
    print('   Ergebnis zu Lösung 2:\n')
    for _ in range(z):
        wrap = sorted(chain(zip(x, repeat(1)), zip(y, repeat(2))))
        for index, (value, list_nr) in enumerate(wrap, 1):
            pass
            #print('{:2d}. {} aus Liste {}'.format(index, value, list_nr))

# Lösung 3
@do_cprofile
def loesung_3(x,y,z):
    print('-' * 80)
    print('   Ergebnis zu Lösung 3:\n')
    for _ in range(z):
        wrap = sorted([(item, 1) for item in x] + [(item, 2) for item in y])
        for index, (value, list_nr) in enumerate(wrap, 1):
            pass
            #print('{:2d}. {} aus Liste {}'.format(index, value, list_nr))


if __name__ == '__main__':
    print('*' *80)
    print('- {}'.format(os.path.realpath(__file__)))
    print('- {}'.format(sys.executable))
    print('- Python  : {} Build: {} vom {}'.format(
                platform.python_version(),
                platform.python_build()[0],
                platform.python_build()[1]))
    print('- Compiler: {}'.format(platform.python_compiler()))
    print('- OS      : {} - {} ({})'.format(
                sys.platform,
                platform.platform(terse=True),
                platform.platform(aliased=True)))
    print('- CPU     : {}'.format(platform.processor()))

    x = [10, 20, 40, 70, 120]
    y = [15, 20, 39, 72, 83, 90, 120]
    z = 100000  # Duration

    loesung_1(x,y,z)
    loesung_2(x,y,z)
    loesung_3(x,y,z)

Hier mein Ergebnis:

[codebox=text file=Unbenannt.txt]
********************************************************************************
- C:\Entwicklung\myDev\sophia\test_08.py
- C:\Entwicklung\python3\python.exe
- Python : 3.5.2 Build: v3.5.2:4def2a2901a5 vom Jun 25 2016 22:18:55
- Compiler: MSC v.1900 64 bit (AMD64)
- OS : win32 - Windows-7 (Windows-7-6.1.7601-SP1)
- CPU : Intel64 Family 6 Model 23 Stepping 10, GenuineIntel
--------------------------------------------------------------------------------
Ergebnis zu Lösung 1:

4100004 function calls in 9.684 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1300000 4.665 0.000 8.064 0.000 test_08.py:38(smallest_element)
1 1.621 1.621 9.684 9.684 test_08.py:52(loesung_1)
200000 0.197 0.000 0.197 0.000 {built-in method builtins.iter}
1400000 1.333 0.000 1.333 0.000 {built-in method builtins.next}
2 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1200000 1.869 0.000 1.869 0.000 {method 'format' of 'str' objects}


--------------------------------------------------------------------------------
Ergebnis zu Lösung 2:

100004 function calls in 0.851 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.380 0.380 0.851 0.851 test_08.py:63(loesung_2)
2 0.000 0.000 0.000 0.000 {built-in method builtins.print}
100000 0.472 0.000 0.472 0.000 {built-in method builtins.sorted}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}


--------------------------------------------------------------------------------
Ergebnis zu Lösung 3:

200004 function calls in 1.244 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.634 0.634 1.427 1.427 test_08.py:74(loesung_3)
100000 0.182 0.000 0.182 0.000 test_08.py:79(<listcomp>)
2 0.000 0.000 0.000 0.000 {built-in method builtins.print}
100000 0.429 0.000 0.429 0.000 {built-in method builtins.sorted}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
[/code]