Konsekutive Bereiche pythonisch summieren

Question

Ich habe eine Funktion sumranges(), die alle Bereiche aufeinanderfolgender Zahlen in einem Tupel-Tupel summiert. Zur Veranschaulichung:

def sumranges(nums): 
    return sum([sum([1 for j in range(len(nums[i])) if 
        nums[i][j] == 0 or 
        nums[i][j - 1] + 1 != nums[i][j]]) for 
       i in range(len(nums))]) 

>>> nums = ((1, 2, 3, 4), (1, 5, 6), (19, 20, 24, 29, 400)) 
>>> print sumranges(nums) 
7 

Wie Sie sehen können, ist es, die Anzahl der Bereiche von aufeinander folgenden Stellen innerhalb des Tupel zurückgibt, das heißt: len ((1, 2, 3, 4), (1), (5, 6), (19, 20), (24), (29), (400)) = 7. Die Tupel sind immer geordnet.

Mein Problem ist, dass mein sumranges() ist schrecklich. Ich hasse es, es anzuschauen. Ich wiederhole gerade das Tupel und jedes Sub-Tupel, gebe eine 1 zu, wenn die Zahl nicht (1 + vorherige Zahl) ist, und addiere die Summe. Ich habe das Gefühl, dass mir ein viel einfacherer Weg fehlt, um mein erklärtes Ziel zu erreichen. Kennt jemand eine mehr pythische Art, dies zu tun?

Edit: Ich habe alle bis jetzt gegebenen Antworten bewertet. Danke an euch alle für eure Antworten.

Das Benchmarking-Code ist wie folgt, eine Stichprobengröße von 100 K mit:

from time import time 
from random import randrange 
nums = [sorted(list(set(randrange(1, 10) for i in range(10)))) for 
     j in range(100000)] 

for func in sumranges, alex, matt, redglyph, ephemient, ferdinand: 
    start = time() 
    result = func(nums) 
    end = time() 
    print ', '.join([func.__name__, str(result), str(end - start) + ' s']) 

Ergebnisse sind wie folgt. Die tatsächliche Antwort zu verifizieren gezeigt, dass alle Funktionen, die richtige Antwort zurück:

sumranges, 250281, 0.54171204567 s 
alex, 250281, 0.531121015549 s 
matt, 250281, 0.843333005905 s 
redglyph, 250281, 0.366822004318 s 
ephemient, 250281, 0.805964946747 s 
ferdinand, 250281, 0.405596971512 s 

RedGlyph nicht Kante in Bezug auf Geschwindigkeit, aber die einfachste Antwort ist wahrscheinlich Ferdinands, und wahrscheinlich gewinnt für die meisten pythonic.

Answer 1

Mein 2 Cent:

>>> sum(len(set(x - i for i, x in enumerate(t))) for t in nums) 
7 

Es ist im Grunde die gleiche Idee wie in Alex' post descriped, sondern ein set statt itertools.groupby Verwendung in einem kürzeren Ausdruck führt. Da set s in C implementiert sind und len() eines Satzes in konstanter Zeit läuft, sollte dies auch ziemlich schnell sein.

Answer 2

Betrachten:

>>> nums = ((1, 2, 3, 4), (1, 5, 6), (19, 20, 24, 29, 400)) 
>>> flat = [[(x - i) for i, x in enumerate(tu)] for tu in nums] 
>>> print flat 
[[1, 1, 1, 1], [1, 4, 4], [19, 19, 22, 26, 396]] 
>>> import itertools 
>>> print sum(1 for tu in flat for _ in itertools.groupby(tu)) 
7 
>>> 

wir „glätten“, die von Interesse „Rampen Erhöhung“ durch den Index aus dem Wert subtrahiert wird, um sie in aufeinanderfolgenden „runs“ identischen Werten drehen; dann identifizieren wir uns und konnten das "rennen" mit dem wertvollen itertools.groupby. Dies scheint eine ziemlich elegante (und schnelle) Lösung für Ihr Problem zu sein.

Answer 3

Dies könnte wahrscheinlich in einer kompakteren Form zusammengestellt werden, aber ich denke, Klarheit leiden würde:

def pairs(seq): 
    for i in range(1,len(seq)): 
     yield (seq[i-1], seq[i]) 

def isadjacent(pair): 
    return pair[0]+1 == pair[1] 

def sumrange(seq): 
    return 1 + sum([1 for pair in pairs(seq) if not isadjacent(pair)]) 

def sumranges(nums): 
    return sum([sumrange(seq) for seq in nums]) 


nums = ((1, 2, 3, 4), (1, 5, 6), (19, 20, 24, 29, 400)) 
print sumranges(nums) # prints 7 

Answer 4

Sie könnten wahrscheinlich das besser tun, wenn Sie ein IntervalSet class haben, denn dann würden Sie durch Ihre Bereiche scannen Erstellen Sie Ihr IntervalSet und verwenden Sie dann nur die Anzahl der gesetzten Mitglieder.

Einige Aufgaben eignen sich nicht immer für sauberen Code, insbesondere wenn Sie den Code für die Leistung schreiben müssen.

Answer 5

Nur etwas näher an den ursprünglichen Code zu erhalten:

def sumranges(nums): 
    return sum((1 for i in nums 
        for j, v in enumerate(i) 
        if j == 0 or v != i[j-1] + 1)) 

Die Idee dabei war:

• vermeiden Zwischenlisten bauen, sondern einen Generator stattdessen verwenden, wird es einige Ressourcen sparen
• Vermeiden Sie die Verwendung von Indizes, wenn Sie bereits ein Unterelement (i und v oben) ausgewählt haben.

Die restlichen sum() ist immer noch notwendig mit meinem Beispiel.

Answer 6

Es gibt eine Formel dafür, die Summe der ersten n Zahlen, 1+ 2+ ... + n = n (n + 1)/2. Wenn Sie dann die Summe von i-j haben wollen, dann ist es (j (j + 1)/2) - (i (i + 1)/2), das ist sicher einfacher, aber Sie können das ausarbeiten. Es könnte nicht pythonisch sein, aber es ist das, was ich benutzen würde.

Answer 7

Hier ist mein Versuch:

def ranges(ls): 
    for l in ls: 
     consec = False 
     for (a,b) in zip(l, l[1:]+(None,)): 
      if b == a+1: 
       consec = True 
      if b is not None and b != a+1: 
       consec = False 
      if consec: 
       yield 1 

''' 
>>> nums = ((1, 2, 3, 4), (1, 5, 6), (19, 20, 24, 29, 400)) 
>>> print sum(ranges(nums)) 
7 
''' 

Es schaut auf die Zahlen paarweise, zu überprüfen, ob sie ein aufeinanderfolgendes Paar sind (es sei denn, es auf dem letzten Element der Liste ist). Jedes Mal, wenn es ein fortlaufendes Paar von Zahlen gibt, ergibt es 1.