`predsort / 3'的可能行为 [英] Possible behaviors of `predsort/3`
问题描述
这是对回答关于对某个术语的特定参数排序的问题,而不为 keysort
创建新列表(如果我理解原始问题正确)。
假设我们想要 predsort / 3
2 :如果我理解正确,这意味着调用它:
? - predsort ,List,Sorted)。
现在我们想使用 predsort / 3
按 msort / 2
实现排序(另请参见问题)。一种方法是定义一个不能统一 Delta $的比较谓词
Pred(-Delta,+ A,+ B)
c $ c> =
当元素实际上相等时:
mcompare(Delta,A,B): -
compare(Delta0,A,B),
(Delta0 ==(=)
- Δ b; Delta = Delta0
)。
? - predsort(mcompare,List,Sorted)。
问题:确实很简单地排序而不删除重复项,因为 msort / 2
有吗?它似乎应该这样。
继续:我们想按照术语中第n个参数的标准顺序对arity> n进行排序。干净的方法是:
sort_argn(N,List,Sorted): -
map_list_to_pairs (N),List,Pairs),
keysort(Pairs,Sorted_pairs),
pairs_values(Sorted_pairs,Sorted)。
如果我们想使用 predsort / 3
为了实现相同的效果,我们可以尝试使用如下的比较谓词:
compare_argn(N,Delta,A,B) : -
arg(N,A,AN),
arg(N,B,BN),
比较(Delta,AN-A,BN-B)。
按第二个参数排序:
? - predsort(compare_argn(2),List,Sorted)。
但是,这不像 sort_argn / 3
上面使用 keysort / 2
。它将删除重复项,如果两个项的第二个参数相等,则它将根据原始完整期的标准顺序对复合词进行排序:
? - predsort(compare_argn(2),[f(b,2),f(a,1),f(a,1),f(a,2)
Sorted = [f(a,1),f(a,2),f(b,2)]。
?- sort_argn(2,[f(b,2),f(a,1),f(a,1),f(a,2)
Sorted = [f(a,1),f(a,1),f(b,2),f(a,2)]。
对传递给比较谓词
Pred(Delta,A,B)
的和
B
A
在原始列表中的 B
之前。我们可以定义比较:
compare_argn_stable(N,Delta,A,B): -
arg A,AN),
arg(N,B,BN),
(Delta0,AN,BN),
(Delta0 ==(=)
- =(<)
; Delta = Delta0
)。
此时,当且仅当 $ c> A 和 B
始终以与原始列表中相同的顺序传递到比较谓词,这应该与 sort_argn / 3
上面:
? - predsort(compare_argn_stable ,List,Sorted)。
现在当然, compare_argn_stable / 4
当两个键相等时,将与
keysort
示例iff predsort / 3
相同才保持原始顺序
> 问题是否有涵盖 predsort / 3
这一方面的标准?
因为没有人回答,因为我现在很确定:
是的,你可以使用 predsort / 3
以模拟任何其他排序。
- 稳定性取决于
predsort / 3
(见问题)的实现 -
predsort / 3
本身不是任何标准的一部分(据我所知) - ,您的Prolog实现提供
msort / 2
或keysort / 2
,远远高于predsort / 3
在很少的情况下,列表元素的大小大于我们排序的列表的长度,这个小舞:
list_to_keyval_pairs用户必要的
keysort(Pairs,Sorted_pairs),
pairs_values(Sorted_pairs,Sorted)
$ b b
(参见这里)其实更贵(慢于)使用 predsort(keycmp,List,Sorted)
与用户定义的 keycmp / 3
即使这样,使用等价键的结果顺序不仅取决于 keycmp / 3
的(用户)定义,还取决于 predsort / 3
。
换句话说,使用 predsort / 3
是一个坏主意。
This is a followup to an answer to a question about sorting on a particular argument of a term, without creating a new list for a keysort
(if I understood the original question correctly).
Say we wanted predsort/3
to behave exactly as sort/2
: if I understand correctly, this would mean calling it as:
?- predsort(compare, List, Sorted).
Now say that we wanted to use predsort/3
to sort as implemented by msort/2
(see also this question). One way to do it would be to define a comparison predicate Pred(-Delta, +A, +B)
that does not unify Delta
with =
when the elements are actually equal:
mcompare(Delta, A, B) :-
compare(Delta0, A, B),
( Delta0 == (=)
-> Delta = (<)
; Delta = Delta0
).
?- predsort(mcompare, List, Sorted).
Question: does that really simply sort without removing duplicates, as msort/2
does? It seems like it should.
Moving on: say we wanted to sort terms with arity > n, on the standard order of the nth argument in the term. The clean way to do it would be:
sort_argn(N, List, Sorted) :-
map_list_to_pairs(arg(N), List, Pairs),
keysort(Pairs, Sorted_pairs),
pairs_values(Sorted_pairs, Sorted).
If we wanted to use predsort/3
to achieve the same effect, we could try using a comparison predicate as follows:
compare_argn(N, Delta, A, B) :-
arg(N, A, AN),
arg(N, B, BN),
compare(Delta, AN-A, BN-B).
And to sort on the second argument:
?- predsort(compare_argn(2), List, Sorted).
However, this is not the same as sort_argn/3
above that uses keysort/2
. It will remove duplicates, and it will order compound terms according to the standard order of the original full term if the second arguments of two terms happen to be equal:
?- predsort(compare_argn(2), [f(b,2), f(a,1), f(a,1), f(a,2)], Sorted).
Sorted = [f(a, 1), f(a, 2), f(b, 2)].
?- sort_argn(2, [f(b,2), f(a,1), f(a,1), f(a,2)], Sorted).
Sorted = [f(a, 1), f(a, 1), f(b, 2), f(a, 2)].
Making the assumption that for every pair of A
and B
passed to the comparison predicate Pred(Delta, A, B)
, A
comes before B
in the original list. Can we define a comparison:
compare_argn_stable(N, Delta, A, B) :-
arg(N, A, AN),
arg(N, B, BN),
compare(Delta0, AN, BN),
( Delta0 == (=)
-> Delta = (<)
; Delta = Delta0
).
At this point, if and only if any two elements A
and B
are always passed to the comparison predicate in the same order as they were in the original list, this should behave identically to sort_argn/3
above:
?- predsort(compare_argn_stable(N), List, Sorted).
Now of course it is important that compare_argn_stable/4
unifies Delta
with <
when the two "keys" are equal. Furthermore, the behavior is implementation dependent, and only identical to the keysort
example iff predsort/3
keeps the original order of elements when passing them to the comparison predicate.
Question Is that correct?
Question Is there any standard that covers this aspect of predsort/3
?
Since no one has answered, and since I am quite certain about it now:
Yes, you could use predsort/3
to emulate any of the other sorts. The question describes in some detail how.
However: this is a bad idea for several reasons.
- The "stability" depends on the implementation of
predsort/3
(see the question) - The
predsort/3
itself is not part of any standard (as far as I can tell) - The chances are, your Prolog implementation provides an
msort/2
orkeysort/2
that is far more efficient thanpredsort/3
There might be rare cases where the size of the elements of the list is much bigger than the length of the list we are sorting, and this little dance:
list_to_keyval_pairs(List, Pairs), % defined by the user as necessary
keysort(Pairs, Sorted_pairs),
pairs_values(Sorted_pairs, Sorted)
(see here) is actually more expensive (slower) than using predsort(keycmp, List, Sorted)
, with keycmp/3
defined by the user. Even then, the order of results with equivalent keys depends not only on the (user) definition of keycmp/3
, but also on the implementation of predsort/3
.
In other words, a "stable" sort with predsort/3
is a bad idea.
这篇关于`predsort / 3'的可能行为的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!