String Sortierung basierend auf einigen Format

Question

Ich habe eine Zeichenfolge, die basierend auf der sort_fmt sortiert werden muss. Bsp .: Wenn der String 'abdcdfs' & ist, ist die sort_fmt 'dacg'. Nach der Sortierung sollte die Ausgabe 'ddacfbs' sein. Wie Sie sehen, gibt es möglicherweise Zeichen in der Eingabezeichenfolge, die in der Reihenfolge nicht enthalten sind und umgekehrt. Die Zeichen der Eingabezeichenfolge, die in der Bestellzeichenfolge nicht vorhanden sind, sollten in beliebiger Reihenfolge am Ende der Ausgabezeichenfolge stehen.

Hier ist was ich geschrieben habe. Es funktioniert, es ist O (n * m) algo. Ich frage mich, gibt es bessere & kürzere Möglichkeiten, dies zu tun? Vielleicht itertools verwenden?

def sort_str(s, sort_fmt): 
    sorted_str = '' 
    str_hash = dict() 

    # O(n) 
    for ch in s: 
     if ch in str_hash: 
      str_hash[ch] += 1 
     else: 
      str_hash[ch] = 1 

    # O(m) + O(1) where m<=n 
    for ch in sort_fmt: 
     if ch in str_hash: 
      cnt = str_hash[ch] 
      sorted_str += cnt * ch 

    # O(n) 
    for ch in s: 
     if ch not in sort_fmt: 
      sorted_str += ch 
    return sorted_str 


if __name__ == '__main__': 
    print sort_str('abdcdfs', 'dacg') 

Answer 1

Sie versuchen, counting sort zu implementieren, die in der Tat O (n) unter bestimmten Bedingungen ist. Jedoch Ihre Implementierung hat zwei Fehler in der Nähe von dem Ende, das dazu führen, dass die tatsächliche Zeit, die Komplexität der Implementierung O (n + n * m):

for ch in s: 
    if ch not in sort_fmt: # <--- "in" requires a linear search. O(n*m) 
     sorted_str += ch # <--- Ouch! Concatenation! O(n^2) 

• Sie bauen das Ergebnis in einer ineffizienten Weise weil Sie Verkettung in einer Schleife verwenden.
• Die Verwendung von in für einen String ist linear in der Länge des Strings, und Sie tun dies in einer Schleife.

Versuchen Sie es stattdessen. Es erfordert Python 2.7 oder höher wegen der Verwendung von collections.Counter, aber die Counter kann leicht mit einem defaultdict für ältere Versionen von Python ersetzt werden):

from collections import Counter 

def sort_str(s, sort_fmt): 
    counter = Counter(s) 
    d = set(sort_fmt) 
    result = ''.join(c * counter[c] for c in sort_fmt) 
    result += ''.join(c for c in s if c not in d) 
    return result 

if __name__ == '__main__': 
    print sort_str('abdcdfs', 'dacg') 

Hier ist ein prägnanter Weise das gewünschte Ergebnis, wenn Sie zu erhalten fallen die Anforderung, dass es sollte O (n) sein:

>>> d = dict((v,k) for (k,v) in enumerate('dacg')) 
>>> sorted('abdcdfs', key = lambda c:d.get(c, len(d))) 
['d', 'd', 'a', 'c', 'b', 'f', 's'] 

Answer 2

ich über die Komplexität der sortierten nicht sicher bin. Dies funktioniert

def sort_str(s, frmt): 
    l = len(frmt) 
    return sorted(s, key = lambda x: frmt.index(x) if x in frmt else l)