Voici un problème que j'ai eu beaucoup de mal à me battre. J'ai besoin de fusionner deux séquences triées dans une séquence unique triée. Idéalement, l'algorithme doit être évalué paresseux et ne nécessite pas de mettre en cache plus d'un élément de chaque séquence. Ce n'est pas un problème terriblement difficile de résoudre et j'ai été en mesure d'ingénierie un certain nombre de solutions en F #. Malheureusement, chaque solution que j'ai proposée a un de plusieurs problèmes.
appels récursifs aux générateurs de suivi à l'aide de rendement !. Cela produit des solutions élégantes, mais la création d'une sous-séquence pour chaque article est un tueur de performance.
Code vraiment arcanique et immuable avec des interrupteurs de match profondément empilés, plusieurs blocs de code presque identiques, etc.
code qui force f # en mode purement procédural (beaucoup de valeurs mutables, etc.).
Et tous les exemples en ligne, j'ai été en mesure de trouver fondateur sur les mêmes pluies.
Est-ce que je manque quelque chose d'évident: comme si c'est vraiment simple, soit évidemment impossible? Est-ce que quelqu'un connaît une solution vraiment élégante qui est également efficace et principalement fonctionnelle? (Il ne doit pas nécessairement être purement fonctionnel.) Sinon, je peux finir par mettre en cache des sous-séquences et utiliser des listes ou des tableaux.
3 Réponses :
Utilisez le type de lazyliste dans le powerpack. Je pense que j'ai peut-être même ce code exact couché, laissez-moi regarder ...
Modifier
Pas exactement ça, mais ferme: http://cs.hubfs.net/ Forums / fil / 8136.aspx
Ok donc je suis rapidement à travers cela ( Pastebin.com/p5va4z5P ), il semble un peu salissant. Y a-t-il un bon moyen de le rendre aussi agréable que le code de liste non paresseux?
Vous n'avez pas besoin de comme gauche et comme droite , ils sont déjà appelés A et b . Il ne semblera jamais "comme gentil", f # est impatient, la paresse prend un peu de travail. Mais je pense que ce code a l'air assez agréable et je pense que @Technology va l'aimera.
Utile comme toujours et très apprécié, Brian :)
Merci, Brian et Juliette; Je pense que la lazyliste peut être ce que je cherche. J'ai copié vos exemples pour référence. Je vais aller à la recherche d'une version de la lazyliste en tant qu'exercice, puis de comparer ce que je propose.
SEQ est généralement significativement plus rapide que les listes paresseuses.
Les séquences ne correspondent pas vraiment à bien.
Heureusement l'un des avantages de F # est EM> être capable de tomber au code impératif lorsque vous en avez besoin, et je pense qu'il est toujours idiomatique de Utilisez l'état mutable en interne tant que la fonction est toujours pure aux clients consommant la fonction. Je pense que ce style est vraiment courant dans le code source F # partout où des séquences sont impliquées. P> Ce n'est pas joli, mais cela fonctionne: P> open System.Collections.Generic
let merge (a : #seq<'a>) (b : #seq<'a>) =
seq {
use a = a.GetEnumerator()
use b = b.GetEnumerator()
let aNext = ref <| a.MoveNext()
let bNext = ref <| b.MoveNext()
let inc (enumerator : IEnumerator<'a>) flag = // '
let temp = enumerator.Current
flag := enumerator.MoveNext()
temp
let incA() = inc a aNext
let incB() = inc b bNext
while !aNext || !bNext do
match !aNext, !bNext with
| true, true ->
if a.Current > b.Current then yield incB()
elif a.Current < b.Current then yield incA()
else yield incA(); yield incB()
| true, false -> yield incA()
| false, true -> yield incB()
| false, false -> ()
}
En général, mon expérience est que "si vous appelez getenumerator () , alors votre code a un bogue que vous n'avez pas encore trouvé".
Merci. Je pense que je vais essayer la lazyliste, mais c'est un exemple assez intéressant à la cachette dans mes archives de code. Sur la chose qui m'a frappé, c'est la macro "inc." Pour inverser le "sens" de l'énumération. Ceci est un modèle de conception qui semble venir souvent, même en C #.
@Brian j'ai payé le prix de getenumerator abus. Je n'utilise plus de séquences pour représenter plus de données, sauf dans mon code AI où je veux que les séquences changent de manière dynamique au lieu de recréer par exemple une liste d'événements. Ma règle générale est maintenant d'utiliser uniquement getenumerator si j'ajoute une fonction à SEQ .
Idéalement, l'algorithme doit être paresseux-évaluer ... La création d'une sous-séquence pour chaque article est un tueur de performance P>
paresseux signifie lent mais voici une solution utilisant des listes paresseuses: p>
xxx pré> Je pense par "paresseux évalué" Vous voulez dire que vous voulez que le résultat fusionné soit généré à la demande Vous pouvez également utiliser: P>
let merge xs ys = let rec gen = function | x::xs, (y::_ as ys) when x<y -> Some(x, (xs, ys)) | xs, y::ys -> Some(y, (xs, ys)) | [], x::xs | x::xs, [] -> Some(x, ([], xs)) | [], [] | [], [] -> None Seq.unfold gen (xs, ys)
Merci, Jon, je vais essayer!
Vous voudrez peut-être regarder cela pour un exemple sur l'algorithme et la convertir en F #. CODE.ACTIVESTEATECOM/RECIPES/141934-Merging-Sorded-uns a>
@James: L'algorithme n'est pas le problème, il maintient la paresse et la complexité de la commande et de l'élégance à la fois c'est la question. La réponse est
lazyliste .@James: Ce site de recette ActiveState a des trucs intéressants.
Je suis content que vous l'avez trouvé intéressant. Certaines idées intéressantes ont été effectuées dans des langues liées à F #, pour comprendre certains concepts.