1

これは、最近私が直面した楽しい小さな課題です。以下に私の答えを示しますが、よりエレガントで効率的なソリューションがあるかどうかを知りたいです。

私に提示された要件の説明:

  1. 文字列は英数字です (以下のテスト データセットを参照)
  2. 文字列は自然にソートする必要があります（説明については、この質問を参照してください）
  3. 英字は数字の前にソートする必要があります (つまり、'100' の前に 'abc' を配置します)。
  4. アルファベット文字の大文字のインスタンスは、小文字のインスタンスの前にソートする必要があります (つまり、'ABc'、'Abc'、'abc')

テスト データセットは次のとおりです。

test_cases = [
    # (unsorted list, sorted list)
    (list('bca'), ['a', 'b', 'c']),
    (list('CbA'), ['A', 'b', 'C']),
    (list('r0B9a'), ['a', 'B', 'r', '0', '9']),
    (['a2', '1a', '10a', 'a1', 'a100'], ['a1', 'a2', 'a100', '1a', '10a']),
    (['GAM', 'alp2', 'ALP11', '1', 'alp100', 'alp10', '100', 'alp1', '2'],
        ['alp1', 'alp2', 'alp10', 'ALP11', 'alp100', 'GAM', '1', '2', '100']),
    (list('ra0b9A'), ['A', 'a', 'b', 'r', '0', '9']),
    (['Abc', 'abc', 'ABc'], ['ABc', 'Abc', 'abc']),
]

ボーナス テスト ケース

これは、選択した回答が現在失敗しているという以下の Janne Karila のコメントに触発されています (ただし、私の場合は実際には問題になりません)。

(['0A', '00a', 'a', 'A', 'A0', '00A', '0', 'a0', '00', '0a'],
        ['A', 'a', 'A0', 'a0', '0', '00', '0A', '00A', '0a', '00a'])
4

3 に答える 3

6 
re_natural = re.compile('[0-9]+|[^0-9]+')

def natural_key(s):
    return [(1, int(c)) if c.isdigit() else (0, c.lower()) for c in re_natural.findall(s)] + [s]

for case in test_cases:
    print case[1]
    print sorted(case[0], key=natural_key)

['a', 'b', 'c']
['a', 'b', 'c']
['A', 'b', 'C']
['A', 'b', 'C']
['a', 'B', 'r', '0', '9']
['a', 'B', 'r', '0', '9']
['a1', 'a2', 'a100', '1a', '10a']
['a1', 'a2', 'a100', '1a', '10a']
['alp1', 'alp2', 'alp10', 'ALP11', 'alp100', 'GAM', '1', '2', '100']
['alp1', 'alp2', 'alp10', 'ALP11', 'alp100', 'GAM', '1', '2', '100']
['A', 'a', 'b', 'r', '0', '9']
['A', 'a', 'b', 'r', '0', '9']
['ABc', 'Abc', 'abc']
['ABc', 'Abc', 'abc']

編集：私はこの質問を再検討し、ボーナスケースを処理できるかどうかを確認することにしました。キーのタイブレーカー部分をより洗練する必要があります。目的の結果と一致させるには、数値部分の前にキーのアルファ部分を考慮する必要があります。また、キーの自然なセクションとタイブレーカーの間にマーカーを追加して、短いキーが常に長いキーの前に来るようにしました。

def natural_key2(s):
    parts = re_natural.findall(s)
    natural = [(1, int(c)) if c.isdigit() else (0, c.lower()) for c in parts]
    ties_alpha = [c for c in parts if not c.isdigit()]
    ties_numeric = [c for c in parts if c.isdigit()]
    return natural + [(-1,)] + ties_alpha + ties_numeric

これにより、上記のテストケースで同じ結果が生成され、さらにボーナスケースで必要な出力が生成されます。

['A', 'a', 'A0', 'a0', '0', '00', '0A', '00A', '0a', '00a']
于 2012-08-29T19:33:00.977 に答える
2

ボーナステストでも機能するものを次に示します。

def mykey(s):
    lst = re.findall(r'(\d+)|(\D+)', s)
    return [(0,a.lower()) if a else (1,int(n)) for n, a in lst]\
        + [a for n, a in lst if a]\
        + [len(n) for n, a in lst if n]

def mysort(lst):
    return sorted(lst, key=mykey)

このタイプのパターンでは、re.findall は文字列をタプルのリストに分割します。

>>> re.findall(r'(\d+)|(\D+)', 'ab12cd')
[('', 'ab'), ('12', ''), ('', 'cd')]
于 2012-08-30T16:11:12.603 に答える
0

この関数は、現時点ではパフォーマンスについて主張していません。

def alpha_before_numeric_natural_sensitive(unsorted_list):
    """presorting the list should work because python stable sorts; see:
    http://wiki.python.org/moin/HowTo/Sorting/#Sort_Stability_and_Complex_Sorts"""
    presorted_list = sorted(unsorted_list)
    return alpha_before_numeric_natural(presorted_list)

def alpha_before_numeric_natural(unsorted_list):
    """splice each string into tuple like so:
    'abc100def' -> ('a', 'b', 'c', 100, 'd', 'e', 'f') ->
    (ord('a'), ord('b'), ord('c'), ord('z') + 1 + 100, ...) then compare
    each tuple"""
    re_p = "([0-9]+|[A-za-z])"
    ordify = lambda s: ord('z') + 1 + int(s) if s.isdigit() else ord(s.lower())
    str_to_ord_tuple = lambda key: [ordify(c) for c in re.split(re_p, key) if c]
    return sorted(unsorted_list, key=str_to_ord_tuple)

これは、この自然な並べ替えソリューションと私が書いたこの関数によって提供される洞察に基づいています。

def alpha_before_numeric(unsorted_list):
    ord_shift = lambda c: c.isdigit() and chr(ord('z') + int(c.lower()) + 1) or c.lower()
    adjust_word = lambda word: "".join([ord_shift(c) for c in list(word)])

    def cmp_(a, b):
        return cmp(adjust_word(a), adjust_word(b))

    return sorted(unsorted_list, cmp_)

さまざまな機能を比較する完全なテスト スクリプトについては、http://klenwell.com/is/Pastebin20120829を参照してください。

于 2012-08-29T18:11:27.343 に答える