Python Liste

[xme11]

Hallo,

Ich hoffe dass ich hier richtig bin, bin neu hier.
Ich habe ein paar FRagen bzgl einer Listen-Erstellung in Python:

1. Wie kann man bestimmte Werte aus einer Liste heraussuchen? z.B( Alle Quadratzahlen zählen & die Summe der Quadratzahlen finden)

2. Was ist der Python- Code für Merge- & Bubblesort falls man eine Liste von Zahlen sortieren soll?

3. Bzgl der Laufzeit, wie kann man herausfinden wie viele Zahlen mehrfach vorhanden sind?


Danke im Voraus

MfG,
xME11

[Sirius3]

@xme11: das hört sich stark nach Hausaufgabe an. Was für ein Tutorial hast Du schon durchgearbeitet? Was weißt Du schon über Listen?

[BlackJack]

@xme11: Ad 1.: Man könnte eine Schleife über die Elemente schreiben und bei jedem Element prüfen ob es eine Quadratzahl ist und falls ja, Zähler und Summe aktualisieren.

Ad 2.: Listen haben eine `sort()`-Methode die den Timsort-Algorithmus verwendet. Kein Grund so etwas wie Mergesort oder Bubblesort selber in Python zu programmieren. Falls man eine neue, sortierte Liste erstellen möchte, gibt es die `sorted()`-Funktion.

Ad 3.: Man könnte die vorhandenen Zahlen zählen, also nicht die gesamtanzahl, sondern wie oft jede vorkommt die vorkommt, und dann schauen welche davon mehr als einmal gezählt wurde. `collections.Counter` kann dabei sehr nützlich sein. Was „Bzgl der Laufzeit“ in der Frage soll, habe ich nicht verstanden.

[beertonic]

1. Das ist änlich wie in anderen Sprachen, aber in Python kannst du direkt über die werte iterieren(ohne index) also

Code: Alles auswählen

for wert in liste:
		if wert == Quadratzahl:
			zähle

wenn du willst kannst du das mit sum() in eine Zeile quetschen:

Code: Alles auswählen

anzahlquadratzahlen = sum(1 for wert in liste if wert**(1/2.) %1 == 0)

2. Du kannst die Standardfunktion sorted() verwenden, die ist aber ziemlich langsam. Ansonsten muss du mal hier gucken http://interactivepython.org/courselib/ ... ctree.html
und selbst eine Funktion schreiben.

3. Was haben die mehrfach Nennungen mit der Laufzeit zu tun?
https://wiki.python.org/moin/TimeComplexity

[nezzcarth]

2. Du kannst die Standardfunktion sorted() verwenden, die ist aber ziemlich langsam.

Worauf stützt sich diese Aussage? Ich würde sagen, dass ein selbst in Python implementierter Standard-Algorithmus vermutlich wesentlich ineffizienter sein wird, als der in Python verwendete Timsort.

[BlackJack]

@beertonic: `sorted()` ist langsam? Auf jeden Fall dürften Merge- oder Bubblesort in Python implementiert, zumindest in CPython langsamer sein. Sehr wahrscheinlich *deutlich* langsamer.

[beertonic]

Ziemlich langsam ist vielleicht übertrieben, aber wenn die Liste lang genug ist werden die Laufzeitunterschiede deutlich. sorted() erstellt eine neue Liste was Zeit kostet.
.sort() manipuliert die vorhandene Liste deswegen ist es schneller.

edit: timsort ist bestcase O(n) das wusste ich nicht

[Sirius3]

@beertonic: Du kannst sicher Deine Behauptung mit einem Beispiel belegen?

[beertonic]

Code: Alles auswählen

import time
import random
test_list1=random.sample(range(1000000),1000000)
test_list2=random.sample(range(1000000),1000000)

s=time.time()
test_list1.sort()
print(time.time()-s)

s=time.time()
test_list2=sorted(test_list2)
print(time.time()-s)

Code: Alles auswählen

0.7350404262542725
0.7730495929718018

[Sirius3]

@beertonic: es ist ziemlich witzlos, eine bereits sortierte Liste nocheinmal zu sortieren. Da bleibt natürlich nur die Zeit des Kopierens der Liste bei sorted und fast nichts bei sort übrig.

Edit: da Sortieren mit O(n*log(n)) geht und kopieren mit O(n), sinkt der Unterschied von sort zu sorted mit steigendem n wie 1/log(n). Ob man bei n=100000 den deutlichen Unterschied von (experimentell ermittelten) 4% noch merkt, sei dem geneigten Leser überlassen.

[beertonic]

@sirius: Stimmt, so wars auch nicht gedacht. Aber jetzt macht es Sinn.

edit: Ist der Unterschied nicht immer O(n)?

[nezzcarth]

Ich komme mit etwas anderem "Versuchsaufbau" auf etwas andere Werte. Wahrscheinlich findet man für jede Position eine Variante, die diese unterstützt

Code: Alles auswählen

import time
import random
from copy import copy
from statistics import mean, stdev


result = {'first': [], 'second': [], 'third': []}
for _ in range(1000):
    first = random.sample(range(100000), random.randint(500, 50000))
    second, third = copy(first), copy(first)
    # Inplace
    t1 = time.time()
    first.sort()
    t2 = time.time()
    result['first'].append(t2 - t1)
    # Neu + Zuweisung
    t1 = time.time()
    tmp = sorted(second)
    t2 = time.time()
    result['second'].append(t2 - t1)
    # Neu ohne Zuweisung
    t1 = time.time()
    sorted(third)
    t2 = time.time()
    result['third'].append(t2 - t1)
    
for key, value in sorted(result.items()):
    print(key, mean(value), stdev(value))


###
first 0.010389111757278443 0.006631446143784157
second 0.010644254446029663 0.006716690760591668
third 0.010373297452926636 0.006851655273388946

Das interessanteste an der ganzen Sache wäre für mich eigentlich, wie man so etwas sinnvoll d.h. belastbar misst.

[Sirius3]

@nezzcarth: anhand Deiner Standardabweichung merkst Du ja, dass die Unterscheide nicht signifikant sind. Statt die Zeit für jeweils einen Sortiervorgang zu nehmen, nimmt man die Zeit für viele, wiederholt das entsprechend oft und hat dann eine relativ genau Zeitmessung. Davon zieht man dann noch die Zeit des NoP-Vorgangs ab.

[beertonic]

Habe es noch ein paar mal durchlaufen lassen der Unterschied variiert von 0,1% bis 9,5%.