Python - Reduzieren Zeitverbrauch

Question

I wurde Code für this problem Schreiben:

ein Array mit N Elementen A angegeben. Finde die Gesamtzahl der Paare (i, j), so dass j < i und Aj = Ai.

Dies ist mein Code:

raw_input() 

l = list(map(int, raw_input().split())) 

count = 0 

for a in range(len(l)): 
    count = count + l[a+1:].count(l[a]) 

print(count) 

Aber leider ist der Code eine Menge Zeit. Haben Sie Vorschläge, wie ich den Zeitaufwand reduzieren könnte? Ich meine, wie reduziere ich die Zeit in der for Schleife verbraucht. Ich finde, dass die Methode list.count viel Zeit braucht, also haben Sie irgendwelche Ideen, durch die ich es ersetzen könnte.

Answer 1

Dies ist wahrscheinlich schneller, weil die Verwendung Generator und Schneiden:

l = [1, 2, 1, 3] 

count = 0 
for idx, value in enumerate(l): 
    count += sum(1 for v in l[:idx] if v == value) 

print(count) 
assert count == 1 

Answer 2

Micro-Optimierungen in Ihrem Python-Code werden Ihre aktuelle O nicht reduzieren (n^2) Komplexität um einen signifikanten Betrag. Ich würde vorschlagen, Implementierungen zu betrachten, die eine geringere Komplexität ergeben. Dieser Link wird Ihnen helfen find total number of (i,j) pairs in array such that i<j and a[i]>a[j]

Answer 3

Sie können es beschleunigen, indem Sie eine schnellere Möglichkeit zur Überprüfung der Mitgliedschaft als .count() verwenden. Zum Beispiel ist ein dict Lookup extrem schnell:

from collections import defaultdict 

raw_input() 

l = list(map(int, raw_input().split())) 

keys = defaultdict(list) 

for i, v in enumerate(l): 
    keys[v].append(i) 

for value, keys in keys.items(): 
    print("Value %d appears at indices %s." % (k, ", ".join(keys))) 

Dann brauchen Sie nur die Anzahl der Paare zu zählen.

Answer 4

Ich bekam endlich die Antwort. Es hat den Zeitaufwand auf einen sehr geringen Betrag reduziert. Entschuldigung für Störungen verursacht.

raw_input() 

l = list(map(int, raw_input().split())) 

dictionary = {} 

for value in l: 
    if value in dictionary: 
     dictionary[value] += 1 
    else: 
     dictionary[value] = 0 

def sum_till_n(iterable): 
    return [x*(x+1)/2 for x in iterable] 

print(sum(sum_till_n(dictionary.values()))) 

Ich hoffe, Sie verstehen, was der Code tut. Ich habe das Problem mathematisch betrachtet. Das Wörterbuch dictionary speichert die Nummer value nach der ersten value. Die sum_till_n Funktion ist eine Funktion, die die Summe der Zahlen bis n findet. Wie für n=3 gibt es 1+2+3 zurück.

Answer 5

Nehmen wir uns eine Minute das Problem und nicht Ihre Implementierung!

Die Aufgabe ist:

ein Array mit N Elementen A angegeben. Finde die Gesamtzahl der Paare (i, j) , so dass j < i und Aj = Ai.

Das ist das gleiche wie alle Duplikate in Ihrem Array zu finden!

Das Auffinden aller Duplikate ist eine sehr häufige Aufgabe.

Eine Lösung kann ich schnell denken:

• Art Array von Tupeln (Wert, Index) (O (N) = N * log (N))
• Querungs das Array einmal in Folge zu finden Duplikate

Hier ein Beispiel ist, wie die resultierenden Daten aussehen würde:

input = [2.0, 1.0, 3.0, 1.0] 
# create and sort tuples (I will leave this task to you) 
sorted_tuples = [(1.0, 1), (1.0, 3), (2.0, 0), (3.0, 2)] 
# find consecutive duplicates (I will leave this task to you) 
solution = [(3, 1)]