python natuurlijke vergelijking tussen strings?

Heeft Python een snelle functie voor het doen van een natuurlijke soort tussen twee strings? Niet noodzakelijkerwijs sorteren, alleen een vergelijkingsfunctie die 0, -1 of 1 retourneert, afhankelijk van wat in natuurlijke volgorde of hetzelfde is.

EDIT: de voorgestelde functie is correct maar is veel te traag. Hoe kan dit snel worden gedaan in Python?

NOTE This is not a duplicate of the post many people suggest -- since these other threads do not address the efficiency issue. The current solutions work and are correct, but make a regular expression call for each line, which is prohibitively expensive. I would like a solution that is efficient and can be used to make millions of comparisons.

0
Het is geen duplicaat, aangezien deze andere threads het efficiënte probleem niet aanpakken. De huidige oplossingen maken een reguliere expressie-oproep voor elke regel, die onbetaalbaar is
toegevoegd de auteur user248237dfsf, de bron
Definieer "natuurlijke volgorde".
toegevoegd de auteur dan04, de bron
toegevoegd de auteur mac, de bron
@ user248237 - (1) Een bewerking moet de duidelijkheid van een vraag verbeteren, en niet van aard veranderen. Je begon te vragen naar de functie en dan veranderde in een vraag over snelheid. (2) Regex is echt snel [in verhouding tot de hoeveelheid werk die ze doen]. (3) Comparatiefuncties zoals cmp zijn snel omdat ze op bitniveau met elkaar vergelijken. Alles wat een 'menselijke logica' vereist, wordt veruit langzamer.
toegevoegd de auteur mac, de bron

3 antwoord

cmp is the built-in function to do just that.

>>> a = 'hello'
>>> b = 'world'
>>> cmp(a, b)
-1

EDIT: with "natural sort" do you refer to sorting numbers as humans would do? If this is the case, than this is a possible recipe.

5
toegevoegd
Is dit identiek aan het sorteren van -V van Unix?
toegevoegd de auteur user248237dfsf, de bron
@ user248237 - Nee. Zie mijn bewerkingen als dat het gedrag is waarnaar u op zoek bent (ik heb de code niet rechtstreeks geplakt, want er is een lange draad van interessante observatie op de ActiveState-website).
toegevoegd de auteur mac, de bron

Adapted from the answer to this question: Does Python have a built in function for string natural sort?

import re

def nat_cmp(a, b):
    convert = lambda text: int(text) if text.isdigit() else text.lower()
    alphanum_key = lambda key: [ convert(c) for c in re.split('([0-9]+)', key) ]

    return cmp(alphanum_key(a), alphanum_key(b))

print nat_cmp('foo10z', 'foo100z')
print cmp('foo10z', 'foo100z')  # <- notice the builtin yields a different result

uitgangen:

-1
1

Bijwerken

Getimed (met de voorbeeldinvoer) met ipython:

In [1]: %timeit nat_cmp('foo10z', 'foo100z')
100000 loops, best of 3: 11.6 us per loop

Update 2

Over prestaties gesproken ... ik weet niet zeker of u begrijpt hoe snel de re lib eigenlijk is, vergeleken met pure python-code. Om te demonstreren heb ik de sleutelfunctie (het gedeelte met re ) genomen en het meerdere keren herschreven in pure python en hun snelheden vergeleken met het, veel eenvoudiger, gebruik van re.split .

import re
from itertools import groupby

def regex_key(key):
    """Traditional, regular-expression-based nat-sort key."""
    convert = lambda text: int(text) if text.isdigit() else text.lower()
    return [convert(c) for c in re.split('([0-9]+)', key)]

def fast_key(value):
    """Attempt #1 to go faster than 'slow' 're' library."""
    result = []
    for is_int, chunk in groupby(value.lower(), str.isdigit):
        if is_int:
            result.append(int(''.join(chunk)))
        else:
            result.append(tuple(chunk))
    return result

def faster_key(value):
    """Attempt #2.  'Low-level' python."""
    start_idx = 0
    is_num = None
    result = []
    for idx, c in enumerate(value.lower()):
        now_is_num = c.isdigit()
        if is_num is not None and now_is_num != is_num:
            buf = value[start_idx:idx]
            result.append(int(buf) if is_num else buf)
            start_idx = idx
            is_num = None
        is_num = now_is_num
    buf = value[start_idx:]
    result.append(int(buf) if is_num else buf)
    return result

Vervolgens voer ik deze uit tegen een eenvoudige benchmark:

from datetime import datetime

def benchmark(fn):
    print "Benching %s (run 1000 times)" % fn.__name__

    start = datetime.now()
    for x in xrange(1000):
        # run key function on something approx 100 chars long
        fn('asdf1234sdfg234jhd88123j2134 - 123d34123djfsk'*2)
    print "\t%s" % (datetime.now() - start)

benchmark(regex_key)
benchmark(fast_key)
benchmark(faster_key)

Dit zijn de resultaten:

Benching regex_key (run 1000 times)
    0:00:00.025908
Benching fast_key (run 1000 times)
    0:00:00.065567
Benching faster_key (run 1000 times)
    0:00:00.042654

Nu weet ik zeker dat er dingen zijn die ik zou kunnen doen om mijn key-func-implementaties sneller te maken, maar tenzij ik iets groots mis, zal het moeilijk zijn om zo snel te worden als de re.split code (met pure python, dat wil zeggen).

5
toegevoegd
Eigenlijk is deze functie ongelooflijk langzaam - ik moet er miljoenen vergelijkingen mee maken. Is htere een manier om het te versnellen?
toegevoegd de auteur user248237dfsf, de bron
@AdamWagner Ik vergelijk de volgorde van 50-100 miljoen reeksen met elkaar. Elke reeks is ongeveer 100 tekens lang
toegevoegd de auteur user248237dfsf, de bron
@AdamWagner Ik wil ook de oproep om te "re" vermijden omdat het miljoenen keren wordt gedaan en dat is erg inefficiënt
toegevoegd de auteur user248237dfsf, de bron
@AdamWagner Ik denk dat Python dit kan doen als het eenvoudige bewerkingen zijn zoals het splitsen van strings, etc. maar het evalueren van een reguliere expressie elke keer dat het gewoon erg onhandig/traag lijkt. De re-bibliotheek is over het algemeen langzaam.
toegevoegd de auteur user248237dfsf, de bron
Merk op dat dit niet werkt in Python 3.x.
toegevoegd de auteur dan04, de bron
U kunt int niet langer vergelijken met str . Ook is cmp verwijderd.
toegevoegd de auteur dan04, de bron
Dank u meneer..
toegevoegd de auteur Adam Wagner, de bron
Kun je me een voorbeeld geven van wat je vergelijkt en wat je als traag beschouwt?
toegevoegd de auteur Adam Wagner, de bron
Welke snelheden zie je? Ik heb dit tegen snaren ongeveer 100 tekens lang getest en ik krijg een gemiddelde looptijd van 65us. Ik begrijp dat je met grote hoeveelheden gegevens werkt, maar als je prestatie-eisen zo groot zijn, kun je misschien iets anders dan python bekijken. Dat gezegd hebbende, zou dit (als ik mijn wiskunde goed heb gedaan) meer dan 10.000 vergelijkingen per seconde opleveren.
toegevoegd de auteur Adam Wagner, de bron
Welke snelheden krijg je/verwacht je?
toegevoegd de auteur Adam Wagner, de bron

Hiermee kun je een lijst met strings natuurlijk sorteren:

import re

unsorted_list = ["a1", "a2", "a11", "b1", "b2", "b11"]

def natural_key(s):
    return [ int(c) if c.isdigit() else c for c in re.split(r'(\d+)', s) ]

sorted_list = sorted(unsorted_list, key = lambda x : natural_key(x))

print sorted_list

This will return -1, 0 or 1, depending on if x > y

def natural_key(x, y):
     x = [int(c) if c.isdigit() else c for c in re.split(r'(\d+)', x)]
     y = [int(c) if c.isdigit() else c for c in re.split(r'(\d+)', y)]
     if x == y:
          return 0
     elif x > y:
          return 1
     else:
          return -1

Dit werkt in python 2.X en 3.X

2
toegevoegd