Seite 1 von 1

Gemeinsamen Anfang einer Liste finden...

Verfasst: Dienstag 10. Juli 2007, 15:46
von jens
Für http://www.python-forum.de/post-72855.html#72855 benötige ich eine Funktion, die den gemeinsamen Anfang einer Liste feststellt.

Meine Aktuelle Variante, macht das rekursiv, es sieht so aus:

Code: Alles auswählen

def get_basename(filelist, basename=""):
    """
    Liefert die gemeinsame Basis aller Dateinamen zurück

    >>> get_basename(["abc1.txt", "abc2.txt", "abc3.txt"])
    'abc'
    >>> get_basename(["1.txt", "2.txt", "3.txt"])
    ''
    """
    first_fn = filelist[0]
    pos = len(basename)

    # nächsten Buchstaben einfügen
    new_basename = basename + first_fn[pos]

    for fn in filelist:
        if not fn.startswith(new_basename):
            # Eine Datei fängt nicht so an -> Basis gefunden
            return basename

    return get_basename(filelist, new_basename)
Wie geht's besser/schneller? (Obwohl es erstmal schnell genug für mich ist)

Verfasst: Dienstag 10. Juli 2007, 16:04
von Zap
Ich hatte irgendwie das Gefühl so eine Funktion schonmal als build-in
gesehen zu haben. Und so ist es auch :o

Code: Alles auswählen

>>> l = [ i for i in os.listdir(".") if i.endswith(".txt") ]
>>> l
['test.txt', 'test1.txt', 'test2.txt', 'test3.txt', 'test4.txt', 'test_neu.txt']
>>> os.path.commonprefix(l)
'test'
>>>
Oder habe ich was übersehen ?

Verfasst: Dienstag 10. Juli 2007, 16:21
von jens
Damit hab ich nicht gerechnet... Ist ja super, dann nutzte ich das ;)

Verfasst: Dienstag 10. Juli 2007, 19:36
von Joghurt
jens hat geschrieben:Wie geht's besser/schneller?
Ich hätte es übrigens so gelöst(und anscheinend macht es commonprefix im Prinzip genauso)

Code: Alles auswählen

def common_prefix(names):
    sorted_names = sorted(names)
    first = sorted_names[0]
    last = sorted_names[-1]
    i = 0
    try:
        while first[i] == last[i]:
            i += 1
    except IndexError:
        pass
    return first[:i]
Andere Vorschläge?

Verfasst: Dienstag 10. Juli 2007, 20:55
von Zap
ähnlich...
Ich geh davon aus das min/max schneller ist als ein sort auf strings.
Auch wenns 2 mal aufgerufen wird.

Code: Alles auswählen

def commonprefix(m):
    "Given a list of pathnames, returns the longest common leading component"
    if not m: return ''
    s1 = min(m)
    s2 = max(m)
    n = min(len(s1), len(s2))
    for i in xrange(n):
        if s1[i] != s2[i]:
            return s1[:i]
    return s1[:n]

Verfasst: Mittwoch 11. Juli 2007, 12:48
von birkenfeld
Zap hat geschrieben:ähnlich...
Ich geh davon aus das min/max schneller ist als ein sort auf strings.
Warum?

Verfasst: Mittwoch 11. Juli 2007, 16:08
von BlackJack
Zumindest in O-Notation ist es O(n) gegen O(n·log(n)). Müsste man also messen ob's grundsätzlich einen Unterschied macht bzw. ab welchem n die `min()`/`max()`-Variante gegenüber dem Sortieren im Vorteil ist.