Python排序和排序-列表列表如何精确排序?

弗兰克·雷恩·谢弗

在Python中用于对列表进行排序的精确规则是什么?可以将其表示为“键”或“ cmp”功能吗?问题来自以下事实:要考虑两件事:长度位置上的

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

是否可以安全地假设第二行将在第一行之前排序?是否可以安全地假设第三行将始终排在最后?

注意,这与稳定性无关上面的特定情况的行为如上所述。但是,规则可以认为是一般性的吗?python在这里适用的确切规则是什么?

依靠以下定义“字典顺序”(感谢阿什尼维):

为了比较不同长度的序列,通常在结尾处用足够的“空白”填充较短的序列(特殊符号被视为小于A的每个元素)。在字典中始终使用这种比较不同长度序列的方式。但是,在组合语言中,经常使用另一种约定,即较短的序列始终小于较长的序列。词典顺序的这种变体有时称为shortlex顺序。

Python是否使用' shortlex order '。除了实际例子之外,该假设的证据在哪里?

阿什维尼乔杜里(Ashwini Chaudhary)

引用文档

特别是,通过比较相应的元素按词典顺序对元组和列表进行比较。这意味着要比较相等,每个元素必须比较相等,并且两个序列必须是相同类型且长度相同。

内置集合之间的词典比较如下

  • 为了使两个集合比较相等,它们必须具有相同的类型,具有相同的长度,并且每对对应的元素必须比较相等(例如,[1,2] == (1,2)由于类型不同,因此为false)。
  • 支持顺序比较的集合的排序与其第一个不相等元素相同(例如,[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代码供参考

/* 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;
}

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章