Un programme qui trouve le Kème élément le plus grand dans une liste

Question

J'écris un programme logique pour kth_largest (Xs, K) qui implémente l'algorithme linéaire pour trouver le kième élément le plus grand k d'une liste Xs . L'algorithme comporte les étapes suivantes:

1. Divisez la liste en groupes de cinq éléments.
2. Trouver efficacement la médiane de chacun des groupes, ce qui peut être fait avec un nombre fixe de comparaisons .
3. Récursivement trouver la médiane des médianes.
4. Partitionnez la liste originale en fonction de la médiane des médianes.
5. Trouvez de façon récursive le kième élément le plus grand dans la liste plus petite appropriée.

Comment procéder? Je peux sélectionner un élément dans une liste, mais je ne sais pas comment obtenir le plus grand utilisent ce qui précède procedure.Here est ma définition pour la sélection d'un élément dans une liste

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). 

Answer 1

Je vais sauter depuis personne n'a tenté de répondre et, espérons-le, a fait la lumière sur la procédure à programmer.

J'ai trouvé l'article de Wikipedia sur Selection algorithm très utile pour comprendre l'image plus grande des algorithmes "rapides" (le temps le plus défavorable) de ce type.

Mais ce que vous avez demandé à la fin de votre question est un peu plus simple. Vous avez écrit "Comment puis-je y aller? Je peux sélectionner un élément d'une liste, mais je ne sais pas comment obtenir le plus grand en utilisant la procédure ci-dessus." (Je souligne par moi)

Maintenant il semble y avoir un peu de confusion quant à savoir si vous voulez mettre en œuvre "la procédure ci-dessus", qui est une recette générale pour trouver un kth plus grand élément par des recherches successives de médianes, ou si vous demandez comment utiliser cette recette pour trouver simplement l'élément le plus grand (un cas particulier). Notez que la recette n'utilise pas spécifiquement une étape de trouver l'élément le plus grand sur son chemin pour localiser la médiane ou le kème élément le plus grand.

Mais vous donnez le code pour trouver un élément d'une liste et le reste de cette liste après avoir supprimé cet élément, un prédicat qui n'est pas déterministe et permet le retour en arrière à travers tous les membres de la liste. La tâche de trouver l'élément le plus grand est déterministe (au moins si tous les éléments sont distincts), et c'est une tâche plus facile que la sélection générale du kième élément le plus grand (une tâche associée à des statistiques d'ordre entre autres) . Donnons un code simple, heureusement correct, pour trouver l'élément le plus grand, puis parlons d'une façon plus optimisée de le faire.

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

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

L'idée devrait être compréhensible. Nous regardons la tête de la liste et demandons si cette entrée est une limite supérieure pour le reste de la liste. Si oui, cela doit être la valeur maximale et nous avons fini (la coupe le rend déterministe). Si ce n'est pas le cas, la valeur maximale doit apparaître plus tard dans la liste, donc nous rejetons la tête et poursuivons récursivement la recherche d'une entrée qui est une limite supérieure de tous les éléments suivants. La coupe est essentielle ici, car il faut s'arrêter à la première entrée pour savoir que c'est un maximum de la liste originale.

Nous avons utilisé un prédicat auxiliaire upperBound/2, ce qui n'est pas inhabituel, mais la complexité globale de cette implémentation est la plus quadratique de la liste. Il y a donc place à amélioration! Permettez-moi de faire une pause ici pour être sûr que je ne vais pas complètement hors-piste en essayant de répondre à votre question. Après tout, vous avez peut-être voulu demander comment utiliser "la procédure ci-dessus" pour trouver le plus grand élément, et donc ce que je décris peut être trop spécialisé. Cependant, il peut être utile de comprendre l'habileté des algorithmes de sélection généraux pour comprendre l'optimisation subtile du cas simple, en trouvant un élément plus grand.

Ajouté:

Intuitivement, nous pouvons réduire le nombre de comparaisons nécessaires dans le pire des cas en passant par la liste et de garder une trace de la plus grande valeur trouvée « si loin ». Dans un langage procédural, nous pouvons facilement accomplir cela en réattribuant la valeur d'une variable, mais Prolog ne nous permet pas de le faire directement.

Au lieu d'une manière Prolog de le faire est d'introduire un argument supplémentaire et définissent le prédicat maxOfList/2 par un appel à un prédicat auxiliaire avec trois arguments:

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

L'argument supplémentaire dans maxOfListAux/3 peut alors être utilisé pour suivre la plus grande valeur « jusqu'à présent » comme suit:

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

Ici, le premier argument de maxOfListAux représente la réponse finale à le plus grand élément de la liste, mais nous ne connaissons pas cette réponse jusqu'à ce que nous aient vidé la liste. Donc, la première clause ici "finalise" la réponse quand cela arrive, unifiant le premier argument avec le deuxième argument (la plus grande valeur "jusqu'à présent") juste au bout de la liste a atteint la fin. La seconde clause pour maxOfListAux laisse le premier argument non lié et "met à jour" le second argument en conséquence car l'élément suivant de la liste dépasse ou non la valeur la plus grande précédente.

Il est pas strictement nécessaire d'utiliser un prédicat auxiliaire dans ce cas, parce que nous aurions pu garder une trace de la plus grande valeur trouvée en utilisant la tête de la liste au lieu d'un argument supplémentaire:

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