查找列表中第 K 个最大元素的程序 [英] A program that finds the Kth largest element in a list

问题描述

我正在为 kth_largest(Xs,K) 编写一个逻辑程序，该程序实现了用于查找列表 Xs 的第 k 个最大元素 K.该算法有以下步骤:

Am writing a logic program for kth_largest(Xs,K) that implements the linear algorithm for finding the kth largest element K of a list Xs. The algorithm has the following steps:

1. 将列表分成五个元素一组.
2. 有效地找到每个组的中位数，这可以用固定数量的比较.
3. 递归求中位数的中位数.
4. 根据中位数对原始列表进行分区.
5. 在适当的较小列表中递归查找第 k 个最大元素.

我该怎么做?我可以从列表中选择一个元素，但我不知道如何使用上述过程获得最大的元素.这是我从列表中选择一个元素的定义

How do I go about it? I can select an element from a list but I don't know how to get the largest using the above procedure.Here is my definition for selecting an element from a list

select(X; HasXs; OneLessXs)  
% The list OneLessXs is the result of removing
% one occurrence of X from the list HasXs.
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :-  select(X,Ys,Zs).

推荐答案

我打算加入，因为没有人尝试过答案，希望能对要编程的程序有所了解.

I'm going to jump in since no one has attempted an Answer, and hopefully shed some light on the procedure to be programmed.

我发现关于选择算法的维基百科文章对理解更大的算法非常有帮助此类快速"(最坏情况线性时间)算法的图片.

I've found the Wikipedia article on Selection algorithm to be quite helpful in understanding the bigger picture of "fast" (worst-case linear time) algorithms of this type.

但是您在问题末尾提出的问题稍微简单一些.您写道我该怎么做?我可以从列表中选择一个元素，但我不知道如何使用上述过程获得最大."(重点是我加的)

But what you asked at the end of your Question is a somewhat simpler matter. You wrote "How do i go about it? I can select an element from a list but i dont know how to get the largest using the above procedure." (emphasis added by me)

现在似乎对您是否要实现上述过程"有点困惑，这是通过连续搜索中位数来查找第 k 个最大元素的一般方法，或者您是否询问如何使用该方法简单地找到最大的元素(一种特殊情况).请注意，该配方在定位中位数或第 k 个最大元素的过程中并未特别使用寻找最大元素的步骤.

Now there seems to be a bit of confusion about whether you want to implement "the above procedure", which is a general recipe for finding a kth largest element by successive searches for medians, or whether you ask how to use that recipe to find simply the largest element (a special case). Note that the recipe doesn't specifically use a step of finding the largest element on its way to locating the median or the kth largest element.

但是您提供的代码是在删除该元素后查找列表的一个元素和该列表的其余部分，这是一个不确定的谓词，并允许通过列表的所有成员进行回溯.

But you give the code to find an element of a list and the rest of that list after removing that element, a predicate that is nondeterministic and allows backtracking through all members of the list.

寻找最大元素的任务是确定性的(至少如果所有元素都是不同的)，并且它比一般选择第 k 个最大元素(与订单统计等相关的任务)更容易.

The task of finding the largest element is deterministic (at least if all the elements are distinct), and it is an easier task than the general selection of the kth largest element (a task associated with order statistics among other things).

让我们给出一些简单的、希望明显正确的代码来查找最大元素，然后讨论一种更优化的方法.

Let's give some simple, hopefully obviously correct, code to find the largest element, and then talk about a more optimized way of doing it.

maxOfList(H,[H|T]) :-  upperBound(H,T), !.
maxOfList(X,[_|T]) :-  maxOfList(X,T).

upperBound(X,[ ]).
upperBound(X,[H|T]) :-
    X >= H,
    upperBound(X,T).

这个想法应该是可以理解的.我们查看列表的头部并询问该条目是否是列表其余部分的上限.如果是这样，那一定是最大值，我们就完成了(切割使其具有确定性).如果不是，则最大值必须出现在列表的后面，因此我们丢弃头部并继续递归搜索作为所有后续元素上限的条目.剪切在这里是必不可少的，因为我们必须在第一个这样的条目处停下来才能知道它是原始列表的最大值.

The idea should be understandable. We look at the head of the list and ask if that entry is an upper bound for the rest of the list. If so, that must be the maximum value and we're done (the cut makes it deterministic). If not, then the maximum value must occur later in the list, so we discard the head and continue recursively searching for an entry that is an upper bound of all the subsequent elements. The cut is essential here, because we must stop at the first such entry in order to know it is a maximum of the original list.

我们使用了辅助谓词 upperBound/2，这并不罕见，但该实现的整体复杂性是最坏情况下列表长度的二次方.所以还有改进的空间！

We've used an auxiliary predicate upperBound/2, which is not unusual, but the overall complexity of this implementation is worst-case quadratic in the length of the list. So there is room for improvement!

让我在这里暂停一下，以确保我在尝试解决您的问题时不会完全偏离轨道.毕竟您可能想问如何使用上述过程"来找到 kth 最大的元素，所以我所描述的可能过于专业化.然而，它可能有助于理解一般选择算法的聪明之处，以了解简单情况下的微妙优化，即找到最大元素.

Let me pause here to be sure I'm not going totally off-track in trying to address your question. After all you may have meant to ask how to use "the above procedure" to find the kth largest element, and so what I'm describing may be overly specialized. However it may help to understand the cleverness of the general selection algorithms to understand the subtle optimization of the simple case, finding a largest element.

添加:

直觉上，我们可以减少最坏情况下所需的比较次数通过浏览列表并跟踪找到的最大值所以far".在过程语言中，我们可以通过重新分配轻松实现这一点变量的值，但 Prolog 不允许我们直接这样做.

Intuitively we can reduce the number of comparisons needed in the worst case by going through the list and keeping track of the largest value found "so far". In a procedural language we can easily accomplish this by reassigning the value of a variable, but Prolog doesn't allow us to do that directly.

相反，Prolog 这样做的方法是引入一个额外的参数和通过调用辅助谓词定义谓词 ma​​xOfList/2三个参数:

Instead a Prolog way of doing this is to introduce an extra argument and define the predicate maxOfList/2 by a call to an auxiliary predicate with three arguments:

maxOfList(X,[H|T]) :- maxOfListAux(X,H,T).

然后可以使用 ma​​xOfListAux/3 中的额外参数来跟踪到目前为止"的最大值如下:

The extra argument in maxOfListAux/3 can then be used to track the largest value "so far" as follows:

maxOfListAux(X,X,[ ]).
maxOfListAux(Z,X,[H|T]) :-
    ( X >= H  -> Y = X ; Y = H ),
    maxOfListAux(Z,Y,T).

这里 maxOfListAux 的第一个参数代表最终答案列表中最大的元素，但直到我们知道答案已清空列表.所以这里的第一条敲定"了答案发生这种情况时，将第一个参数与第二个参数统一(到目前为止"的最大值)就在列表尾部到达时结束.

Here the first argument of maxOfListAux represents the final answer as to the largest element of the list, but we don't know that answer until we have emptied the list. So the first clause here "finalizes" the answer when that happens, unifying the first argument with the second argument (the largest value "so far") just when the tail of the list has reached the end.

maxOfListAux 的第二个子句使第一个参数未绑定并且相应地更新"第二个参数作为列表的下一个元素是否超过前一个最大值.

The second clause for maxOfListAux leaves the first argument unbound and "updates" the second argument accordingly as the next element of the list exceeds the previous largest value or not.

在这种情况下，使用辅助谓词并不是绝对必要的，因为我们可能已经跟踪了通过使用找到的最大值列表的头部而不是额外的参数:

It isn't strictly necessary to use an auxiliary predicate in this case, because we might have kept track of the largest value found by using the head of the list instead of an extra argument:

maxOfList(X,[X]) :- !.
maxOfList(X,[H1,H2|T]) :-
    ( H1 >= H2  -> Y = H1 ; Y = H2 ),
    maxOfList(X,[Y|T]).

这篇关于查找列表中第 K 个最大元素的程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！