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
Python Liste
@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.
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.
1. Das ist änlich wie in anderen Sprachen, aber in Python kannst du direkt über die werte iterieren(ohne index) also
wenn du willst kannst du das mit sum() in eine Zeile quetschen:
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
Code: Alles auswählen
for wert in liste:
if wert == Quadratzahl:
zähle
Code: Alles auswählen
anzahlquadratzahlen = sum(1 for wert in liste if wert**(1/2.) %1 == 0)
und selbst eine Funktion schreiben.
3. Was haben die mehrfach Nennungen mit der Laufzeit zu tun?
https://wiki.python.org/moin/TimeComplexity
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.beertonic hat geschrieben: 2. Du kannst die Standardfunktion sorted() verwenden, die ist aber ziemlich langsam.
Zuletzt geändert von nezzcarth am Dienstag 9. Mai 2017, 17:58, insgesamt 1-mal geändert.
@beertonic: `sorted()` ist langsam? Auf jeden Fall dürften Merge- oder Bubblesort in Python implementiert, zumindest in CPython langsamer sein. Sehr wahrscheinlich *deutlich* langsamer.
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
.sort() manipuliert die vorhandene Liste deswegen ist es schneller.
edit: timsort ist bestcase O(n) das wusste ich nicht
Zuletzt geändert von beertonic am Dienstag 9. Mai 2017, 18:40, insgesamt 1-mal geändert.
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
Zuletzt geändert von beertonic am Dienstag 9. Mai 2017, 19:29, insgesamt 1-mal geändert.
@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.
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.
Ich komme mit etwas anderem "Versuchsaufbau" auf etwas andere Werte. Wahrscheinlich findet man für jede Position eine Variante, die diese unterstützt
Das interessanteste an der ganzen Sache wäre für mich eigentlich, wie man so etwas sinnvoll d.h. belastbar misst.
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
@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.