在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 '。除了实际例子之外,该假设的证据在哪里?
引用文档:
特别是,通过比较相应的元素按词典顺序对元组和列表进行比较。这意味着要比较相等,每个元素必须比较相等,并且两个序列必须是相同类型且长度相同。
[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] 删除。
我来说两句