Get Element in Liste mit der niedrigsten Anzahl von *

Question

Ich habe eine Liste und ich möchte das Element finden, das die niedrigste Anzahl von '*' hat.

mylist = ['12*3','12345**6','11234'] 

So ist die Antwort in diesem kleinen Test '11234'

Dies funktioniert ist, aber langsam (ich arbeite mit massiven genomischen Daten:

sorted(mylist, key = lambda x: x.count('*'))[0] 

Dies ist weniger eloquent, aber Werke :

values = map(lambda x: x.count('*'), mylist) 
print mylist[values.index(min(values))] 

gibt es eine bessere Art und Weise ich ein Schwartzian trans zu tun versuchte? Bildung aber kann es nicht herausfinden.

Answer 1

Sie können min mit key Parameter verwenden:

>>> mylist = ['12*3','12345**6','11234'] 
>>> min(mylist, key=lambda x: x.count('*')) 
'11234' 

key ist eine Funktion, die für jedes Element auf dem iterable genannt wird, wie in sorted der Bestellung auf die gleiche Weise zu spezifizieren.

Above Ansatz führt zu O (n) Zeitkomplexität, wo als Sortierung ist O (n log n).

Update: Wenn die Saiten wirklich lang sind, dann können Sie das Auftreten von * in einer Schleife zählen und die Zeichenfolge so schnell verwerfen als Zählung der gleiche wie Strom minimal ist. Sie könnten auch die Suche beenden, wenn der String mit 0 Vorkommen gefunden wird:

def find(l): 
    min_item = None 
    min_val = float('inf') 

    for x in l: 
     current = 0 
     for c in x: 
      current += (c == '*') 
      if current >= min_val: 
       break 
     else: 
      # Found new minimum, update 
      min_item = x 
      min_val = current 

     # Can't get lower than 0 
     if min_val == 0: 
      break 

    return min_item 

print(find(['12*3','11234', '12345**6', '1'])) # '11234' 

Answer 2

Sie die Leistung weiter verbessern kann durch die separate Funktion für key statt lambda als Lambda-Funktionen zu schaffen langsam sind. Zum Beispiel als:

def get_asterisk_count(my_string): 
    return my_string.count('*') 

mylist = ['12*3','12345**6','11234'] 
min(mylist, key=get_asterisk_count) 

Im Folgenden sind die timeit Statistik:

• Mit lambda Funktion: 1,25 usec

  mquadri$ python -m "timeit" -s "mylist = ['12*3','12345**6','11234']" "min(mylist, key=lambda x: x.count('*'))" 
  1000000 loops, best of 3: 1.25 usec per loop 
  

• Verwendung separater Funktion: 1,19 usec

  mquadri$ python -m "timeit" -s "mylist = ['12*3','12345**6','11234']" "def get_asterisk_count(my_string): return my_string.count('*')" "min(mylist, key=get_asterisk_count)" 
  1000000 loops, best of 3: 1.19 usec per loop