Python sort and sorted - リストのリストはどのようにして正確にソートされていますか？

Question

要素がリストであるリストをソートするために、Pythonで使用される正確なルールは何ですか？これは 'key'または 'cmp'として表現できますか ？問題は、 の2種類があります.の長さがで、値がの位置がであることが原因です。

sorted([ 
    [ 0, 1, 2, 3 ], # 1st line: longer list 
    [ 0, 1 ],  # 2nd line: shorter list 
    [ 0, 2 ]   # 3rd line: suspected last 
]) 

第2行目が最初の行よりも前にソートされると考えるのは安全でしょうか？ 3行目が常に最後にソートされると想定するのは安全でしょうか？

注：安定性についてではなく、です。！上記の特定のケースは、前述のように のように動作します。しかし、そこにあるルールは、 と一般的に考えられますか？ここでPythonが適用する正確なルールは何ですか？次のように定義Lexicographical Order（Ashniwiのおかげで）に依存

：、より短い配列が 通常、十分な「空白」で終わりにパディングされ、異なる長さの配列を比較するために

（特殊記号 ことAのすべての要素よりも小さく扱われます）。異なる長さの シーケンスを比較するこの方法は、常に辞書で使用されます。しかしながら、コンビナトリアルにおいて、別の慣例が頻繁に使用され、より短い配列は常により長い配列よりも小さい。 。 この辞書形式の変種は、ショートレックス オーダーと呼ばれることがあります。

Pythonで 'ショートカットオーダー'を使用していますか？その仮定の証明はどこにありますか？ 実際の例を超えていますか？

Answer 1

docsから引用：特に

は、タプルとリストは、対応する要素を比較 によって辞書編集比較されます。これは、等価を比較するには、 すべての要素が等しいかどうかを比較しなければならず、2つのシーケンスが同じタイプの で同じ長さでなければならないことを意味します。

Lexicographical comparison between built-in collections works as follows：2つのコレクションのため

• 等しい比較し、それらが同じタイプである必要があり、同じ長さを有し、対応する要素の各対は[1,2] == (1,2)が偽である（例えば、等しい比較する必要がありますタイプが同じではないため）。
• 順序比較をサポートするコレクションは、最初の等しくない要素と同じ順序になります（たとえば、[1,2,x] <= [1,2,y]の値はx <= yと同じです）。対応する要素が存在しない場合は、最初に短いコレクションが順序付けされます（たとえば、[1,2] < [1,2,3]がtrue）。リストのために行われ、基本的な比較は、この機能を使って表現することができる

：

def cmp(list_1, list_2): 
    length_1 = len(list_1) 
    length_2 = len(list_2) 
    min_length = min(length_1, length_2) 

    # Compare individual items till there's a different item found 
    for i in xrange(min_length): 
     if list_1[i] > list_2[i]: 
      return 1 
     elif list_1[i] < list_2[i]: 
      return -1 

    # All items were same so far, let's compare sizes. 
    if length_1 > length_2: 
     return 1 
    elif length_1 < length_2: 
     return -1 
    elif length_1 == length_2: 
     return 0 

デモ：

>>> lst = [[ 0, 1, 2, 3 ], [ 0, 1 ], [ 0, 2 ]] 
>>> print sorted(lst) == sorted(lst, cmp=cmp) 
True 

関連CPython code for reference：

/* Search for the first index where items are different */ 
for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) { 
    int k = PyObject_RichCompareBool(vl->ob_item[i], 
            wl->ob_item[i], Py_EQ); 
    if (k < 0) 
     return NULL; 
    if (!k) 
     break; 
} 

if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) { 
    /* No more items to compare -- compare sizes */ 
    Py_ssize_t vs = Py_SIZE(vl); 
    Py_ssize_t ws = Py_SIZE(wl); 
    int cmp; 
    PyObject *res; 
    switch (op) { 
    case Py_LT: cmp = vs < ws; break; 
    case Py_LE: cmp = vs <= ws; break; 
    case Py_EQ: cmp = vs == ws; break; 
    case Py_NE: cmp = vs != ws; break; 
    case Py_GT: cmp = vs > ws; break; 
    case Py_GE: cmp = vs >= ws; break; 
    default: return NULL; /* cannot happen */ 
    } 
    if (cmp) 
     res = Py_True; 
    else 
     res = Py_False; 
    Py_INCREF(res); 
    return res; 
} 

Answer 2

デフォルトでは、sortedは、比較される項目の__lt__メソッドを使用します。比較可能な要素を持つリストは、Pythonのドキュメントに基づいて辞書的に比較されます。したがって、言語は、短い文字列で長い文字列の前にソートされることを保証します。