Wie ändert man diesen Python-Code (wenn nötig), um ihn effizienter zu machen?

Question

Sie erhalten also eine ganze Zahl n, die der Anzahl loser Socken entspricht, die Sie haben. Sie erhalten dann eine Liste von Socken mit Nummern, die ihrem Tag/ihrer Farbe entsprechen.

zum Beispiel des Probeneingang:

9 
10 20 20 10 10 30 50 10 20 

ausgeben würde:

3 

Die Paare in diesem Fall wären: (10,10), (20,20), (10,10) weil jede einzelne Socke einmal verwendet werden kann nur.

Ich war in der Lage, eine Lösung für das Problem zu finden, indem Sie ein Paar finden und jedes Tag zu -1 markieren, um eine Socke zu bezeichnen, die bereits in einem Paar befindet. Meine erste Lösung schien ineffizient zu sein, weil die Schleifen durch Werte iterierten, die auch die -1 enthielten, so dass ich break and continue nutzte, was ich letzte Woche im Kurs gelernt habe.

Dies ist meine letzte Lösung:

import sys 


n = int(input().strip()) 
c = [int(c_temp) for c_temp in input().strip().split(' ')] 

matching = 0 
pairFound = True 

while pairFound: 
    pairFound = False 
    for i in range(len(c)): 
     if c[i] == -1: 
      continue 
     for j in range(i+1,len(c)): 
      if c[j] == -1: 
       continue 
      if c[i] == c[j] and c[i] != -1 and c[j] != -1: 
       pairFound=True 
       matching = matching + 1 
       c[i]=-1 
       c[j]=-1 
      if c[i] == -1: 
       break 
print(matching) 

Wie effizient den Code ich geschrieben habe?

Ich bin nicht wirklich auf der Suche nach einer alternativen Lösung, ich bin mehr interessiert an einer Möglichkeit, dies zu optimieren, um meinen bestehenden Code besser zu machen.

Danke Jungs.

Answer 1

Ihr Ansatz ist ganz in Ordnung aus konzeptioneller Perspektive für jemanden, der die ersten Schritte in der Programmierung macht:

• Die gute Sache ist, dass Sie nur nehmen Sie die nachfolgende Liste für jedes Element aus Ihrem erste for Schleife in Rechnung und nicht über die gesamte Liste iterieren.

• Das Schlimme ist, was Sie wahrscheinlich denken lässt, dass dies verbessert werden kann, dass Sie Socken, denen ein Paar zugewiesen wurde, markieren, anstatt sie aus der Liste zu entfernen. Wenn Sie sie entfernen, verkürzt sich die Liste und die Berechnungsschritte, die zum Beenden der Aufgabe erforderlich sind, werden reduziert. Es ist jedoch eine schlechte Idee, Elemente aus einer Liste zu entfernen, während man darüber iteriert, also brauchen Sie hier etwas anderes.

• Zusätzlich können Sie die umgebende while-Schleife weglassen, da die erste for Schleife sowieso endet, sobald das Ende der Sockensequenz erreicht ist. Achten Sie auf IndexError s beim Zugriff auf die nachfolgende Liste, wenn Sie das Ende erreicht haben.

Ich bezweifle, dass Sie Rekursion in der Klasse noch bedeckt, aber dies wäre ein effizienter Ansatz von Iterieren über ändernden Listen und zugleich sammelt Gegenstände, die nicht zu einem Paar zugeordnet werden können (dh einsam Socken).

Rekursion ist über eine Funktion von selbst anrufen:

Lassen socks Ihre Eingabeliste sein. Sie können es in seine head (das erste Element) und rest (alle anderen Elemente) teilen.

socks = [10, 20, 10, 40] 
head = socks[0] # Here, head will be 10 
rest = socks[1:] # Here, rest will be [20, 10, 40] 

Für den ersten Schritt müssen Sie für ein Element in rest suchen, die zu Ihrem head gleich ist. Einmal gefunden, können Sie es von rest entfernen, da es nicht mehr als einmal kombiniert werden kann:

for i, s in enumerate(rest): 
    if s == head: 
     match = rest.pop(i) 
     break 

nun nach diesem Schritt, wissen Sie, dass Sie ein Paar gefunden haben, bestehend aus den Elementen head und match. Und Ihre rest Liste hat sich verändert: Sie haben das passende Teil entfernt:

[20, 40] 

Sie können diese Schritte wiederholen, bis die rest Liste der Länge ist <= 1, so würden wir einen weiteren Lauf hier brauchen, wo head20 sein würde und rest wäre [40]. Iterieren über rest würde kein Paar ergeben und wir sollten es so wie es ist zurückgeben.

Sobald Ihre Iteration den Punkt erreicht hat, an dem die Länge rest<= 1 ist, können Sie beenden, da Sie wissen, dass Sie alle Paare gefunden haben müssen.

In Code, könnte dies wie folgt aussehen:

import random 

def seek_pair(lst): 
    if len(lst) <= 1: 
     # Nothing to do if we cannot split list into head and rest 
     return lst 

    # Split list into head and rest 
    head, rest = lst[0], lst[1:] 

    # Iterate over rest and try to find a match 
    match = None 
    for i, s in enumerate(rest): 
     if s == head: 
      # We have found an element that equals our head 
      # Remove it from the list and store it in variable 'match' 
      match = rest.pop(i) 
      # Break the loop as we have found a match 
      break 

    if match: 
     # If there was a match in the 'rest' list, we can print it 
     print('Pair: ({:d}, {:d})'.format(head, match)) 
     # And call the method 'seek_pair()' on the resulting 'rest' 
     # Note that here, the matching element has already been 
     # removed from the list 'rest'. 
     return seek_pair(rest) # RECURSION 
    else: 
     # If no match was found, we still need to search the 'rest' 
     # list for other matches. 
     # And, since 'head' did not match any other element, we append 
     # it to the beginning of our result list, which will hold all 
     # elements without matches (i.e. lonely socks). 
     return [head] + seek_pair(rest) # RECURSION 

if __name__ == '__main__': 
    # Randomly generate an input list of desired length 
    n = 9 
    socks = [random.randint(1, 9) * 10 for _ in range(n)] 

    # Print the list 
    print('Socks: {:s}'.format(', '.join([str(s) for s in socks]))) 
    # Call the function on the entire list and obtain its result, 
    # that should contain all lonely socks. 
    rest = seek_pair(socks) 
    # Print lonely socks 
    print('Rest: {:s}'.format(', '.join([str(s) for s in rest]))) 

Der Ausgang dieser Code sieht wie folgt aus:

Socks: 30, 10, 30, 40, 30, 50, 40, 60, 70 
Pair: (30, 30) 
Pair: (40, 40) 
Rest: 10, 30, 50, 60, 70 

Answer 2

Ihr Code ist nicht übermäßig effizient, da seine Laufzeit proportional zum Quadrat der Anzahl der Elemente (z. B. Socken) ist. Sie können eine lineare Laufzeit erreichen, indem Sie einfach die Elemente zählen und die Summe von (Anzahl_Elemente // 2) erhalten. Wenn ich wirklich an Laufzeit interessiert bin, würde ich empfehlen, Counter-Klasse aus Modul-Sammlungen zu verwenden.

Answer 3

Meine Lösung Verwendung von collections.Counter

>>> import collections 
>>> c = [10, 20, 20, 10, 10, 30, 50, 10, 20] 
>>> sum([int(i/2) for i in collections.Counter(c).values()]) 
>>> 3 

machen

Wenn Sie die Details des wiederholten Paares erhalten möchten, verwenden Sie den unten stehenden Code.Es zeigen wir 4 Vorkommen von 10, 3 occurenc e von 20 und so weiter ist die meisten auftreten, um

>>> import collections 
>>> c = [10, 20, 20, 10, 10, 30, 50, 10, 20] 
>>> collections.Counter(c).most_common() 
>>> [(10, 4), (20, 3), (50, 1), (30, 1)]