les inconvénients de l'opérateur (::) en F#

L'opérateur :: en F#, toujours ajoute des éléments à la liste. Est-il un opérateur qui s'ajoute à la liste? Je suppose que l'utilisation d'opérateur @

[1; 2; 3] @ [4]

serait moins efficace, que d'ajouter un élément.

InformationsquelleAutor Max | 2010-03-20
  1. 44

    Comme les autres ont dit, il n'existe pas d'opérateur, car il ne serait pas beaucoup de sens. En fait, je pense que c'est une bonne chose, car il est plus facile à réaliser que l'opération ne sera pas efficace. Dans la pratique, vous ne devriez pas avoir besoin de l'opérateur, il est généralement une meilleure façon d'écrire la même chose.

    Scénario typique: je pense que le scénario typique où vous pourriez penser que vous avez besoin pour ajouter des éléments à la fin est si commun qu'il peut être utile de le décrire.

    Ajoutant des éléments à la fin semble nécessaire lorsque vous êtes en train de rédiger une queue-une version récursive de la fonction à l'aide de la accumulateur paramètre. Par exemple, un (inefficace) de la mise en œuvre de filter fonction pour les listes ressemblerait à ceci:

    let filter f l = 
  let rec filterUtil acc l =
    match l with 
    | [] -> acc
    | x::xs when f x -> filterUtil (acc @ [x]) xs
    | x::xs -> filterUtil acc xs
  filterUtil [] l

    Dans chaque étape, nous avons besoin d'ajouter un élément à l'accumulateur (qui contient les éléments à être retournées comme résultat). Ce code peut être facilement modifié pour utiliser la :: opérateur au lieu d'ajouter des éléments à la fin de la acc liste:

    let filter f l = 
  let rec filterUtil acc l =
    match l with 
    | [] -> List.rev acc                        //(1)
    | x::xs when f x -> filterUtil (x::acc) xs  //(2)
    | x::xs -> filterUtil acc xs
  filterUtil [] l

    Dans (2), nous sommes maintenant en ajoutant des éléments à l'avant de l'accumulateur et lorsque la fonction est sur le point de retourner le résultat, nous avons inversé la liste (1), qui est beaucoup plus efficace que d'ajouter des éléments un par un.

    • Il y a sûrement un moyen de le faire ce w/o la nécessité d'inverser le tableau à la fin?
    • Si vous vouliez faire cela sans revenir à la liste, vous pouvez utiliser l'application décrite par Norman Ramsey ou l'utilisation d'une mutation (en F#, vous devez définir mutable liste). En utilisant le standard de type liste, il n'y a aucun moyen de le faire.
    • Pourriez-vous expliquer pourquoi l'inversion est "beaucoup plus efficace que d'ajouter des éléments un par un"?
    • Parce qu'un non vide individuellement liée liste est un constructeur, avec une valeur (de la tête), et un pointeur vers une autre liste chaînée (la queue). Pour obtenir le dernier élément dans une liste que vous n'avez pas consulté avant, vous avez à suivre que de nombreux pointeurs, comme le nombre d'éléments dans la liste. Ajoutant à l'avant signifie simplement la construction d'une nouvelle liste avec l'élément que vous souhaitez ajouter, et un pointeur vers l'ancienne liste. Ajouter du texte à la fin d'une liste exige que soit la mutation de la dernière constructeur dans la liste, ou en créant une nouvelle liste où vous copiez tous les éléments de l'ancienne liste.
    • Vous a expliqué pourquoi l'ajout à la fin est mauvaise (que je connaissais déjà), mais vous n'avez pas d'expliquer pourquoi l'inversion est "beaucoup plus efficace". Je soupçonne que le list type en F# est une liste doublement chaînée, donc l'inversion de l'opération, c'est juste pour mettre à jour certains indicateurs internes.
    • Pourriez-vous expliquer pourquoi l'inversion d'une liste est plus efficace?
    • Je suis tout juste de mettre en F#, mais je crois que c'est parce que si vous ajoutez à une liste immuable, il aura besoin de marcher toute la liste à chaque fois qu'il 'ajoute' un élément à la fin et crée une nouvelle liste. En ajoutant à l'avant de la liste, vous avez toujours un pointeur vers le début de la liste, puis d'inverser la liste, vous avez seulement besoin de marcher toute la liste 1 fois.

    InformationsquelleAutor Tomas Petricek
  2. 27

    Listes de F# sont liée individuellement et immuable. Cela signifie consing sur le front de l'est O(1) (créer un élément et l'ont point à une liste existante), alors que snocing sur le dos est en O(N) (comme l'ensemble de la liste doivent être répliqués; vous ne pouvez pas changer la finale pointeur, vous devez créer une nouvelle liste).

    Si vous avez besoin d'ajouter un élément à l'arrière", puis, par exemple,

    l @ [42]

    est la façon de le faire, mais c'est une odeur de code.

    • snoc ? Et suggérez-vous de l'ajout à une liste est une mauvaise idée ? Dans ce cas, comment voulez-vous créer une liste de manière incrémentielle ?
    • Agnew, vous de le construire à l'avant, puis de la Liste.rev lorsque vous avez terminé (voir Tomas de la réponse). Malheureusement, je ne suis pas assez intelligent pour vous dire combien, O()'s qu'il rend.
    • qui fait sens et est ce que je fais en Scala. Thx.
    • Agnew: c'est un jeu de mots: "snoc" == "cons".reverse
    • Ainsi, la construction de la liste exige d'abord l'un des inconvénients de chaque élément, et l'opération inverse n'est une fois de plus de cette liste, une fois de plus, faire l'un des inconvénients de chaque élément. Cela signifie qu'il y a 2n contre les opérations nécessaires à la construction d'une liste de longueur n, de telle manière. Toutefois, en big-O notation le facteur constant de 2 n'est pas pertinent ici, donc, la tâche de la construction d'une liste d'une telle manière est O(n).
    • 1@[42] ne compile pas. peut-être 1::[42] est ce que vous recherchez?

    InformationsquelleAutor Brian
  3. 12

    Le coût de l'ajout de deux listes standard est proportionnelle à la longueur de la liste sur la gauche. En particulier, le coût de

    xs @ [x]

    est proportionnelle à la longueur de xs—il est pas un coût constant.

    Si vous voulez une liste-comme l'abstraction avec une constante de temps append, vous pouvez utiliser de John Hughes est fonction de la représentation, je vais l'appeler hlist. Je vais essayer d'utiliser la syntaxe d'OCaml, qui, je l'espère, est assez proche de F#:

    type 'a hlist = 'a list -> 'a list   (* a John Hughes list *)
let empty : 'a hlist = let id xs = xs in id
let append xs ys = fun tail -> xs (ys tail)
let singleton x = fun tail -> x :: tail
let cons x xs = append (singleton x) xs
let snoc xs x = append xs (singleton x)
let to_list : 'a hlist -> 'a list = fun xs -> xs []

    L'idée est que vous représentez une liste fonctionnellement comme une fonction de "le reste des éléments" à "la liste finale". Cela fonctionne de la créer si vous allez mettre en place l'ensemble de la liste avant que vous regardez l'un quelconque des éléments. Sinon, vous allez avoir à traiter avec le linéaire des coûts d'ajouter ou d'en utiliser une autre structure de données entièrement.

    • Je peux sentir quelque chose de drôle.. je pense que c'est mon cerveau de fusion 🙂
    InformationsquelleAutor Norman Ramsey
  4. 5

    Je suppose qu'à l'aide de @ opérateur [...] serait moins efficace, que d'ajouter un élément.

    Si elle l'est, ce sera un effet négligeable. À la fois l'ajout d'un seul élément et de la concaténation d'une liste à la fin sont O(n) opérations. Comme une question de fait, je ne peux pas penser à une seule chose que @ a à faire, qui d'un seul élément ajout de la fonction ne serait pas.

    • Avant d'ajouter une liste avec un opérateur @ on a besoin de créer une liste d'un élément.
    • Comment voulez-vous mettre en œuvre un ajout d'une fonction qui n'a pas créé un seul élément de la liste contenant l'élément ajouté? Après tout, la queue de la queue de la queue de [1,2,3,4] est [4]. Et vous ne pouvez pas construire une liste sans la construction de sa queue.
    • Pourquoi le downvote?
    • Rappelez-vous ce que cela signifie d'avoir une liste: Cela signifie que vous avez a :: b :: c :: d :: []. Pour ajouter un nouvel élément à la fin, vous avez à construire a :: b :: c :: d :: e :: []. Et comme cela a été illustré précédemment, e :: [] est la même chose que [e]. D'autre part, d'ajouter un élément à une liste, c'est juste e :: original_list.
    • -1 : comme l'a souligné Brian, puisque F# les listes sont liée individuellement, en ajoutant à la fin est un O(N^2) où N est la longueur de la liste. Cela peut devenir très importante pour les grandes listes. Beaucoup mieux à ajouter lorsque vous générez la liste, puis la Liste.rev moment de retourner le résultat final, qui est en O(N).
    • Ajoutant à une liste est pas O(N^2). Ajout de N fois est O(N^2). Ajoutant à une liste une fois n'est O(N) qui est la même que la concaténation d'une liste de longueur 1 à la fin de la liste. Oui, les préfixant est plus rapide (car il est O(1)), mais ce n'était PAS la question. La question était de savoir si la concaténation d'un seul élément de la liste à la fin a été plus lent que l'ajout d'un seul élément. Qui elle ne l'est pas.
    • Je corrige la position des mains, et j'ai essayé de supprimer le downvote (ne peut pas car il est trop vieux). Cependant, la réponse peut être trompeur pour certains. L'ajout d'un seul élément, UN TEMPS, ne sera pas très cher: O(N), où N est l'original de la taille de la liste. MAIS, les listes sont généralement construit de manière itérative en N opérations et donc de coût O(N^2), où N est le nombre d'éléments à mettre dans la liste.
    • Aussi, je ne suis pas clair sur la différence entre "ajouter" et de "concaténation" un seul élément; ne sont-ils pas synonymes?
    • O(N) est certainement lent pour ajouter un élément à la liste. Et oui concattenating un élément de liste et en ajoutant un élément sont les mêmes sematically. La question était de savoir si une fonction qui savait que c'était seulement l'ajout d'un seul élément serait plus rapide que l'utilisation @ avec un seul élément de la liste. Qui elle ne l'est pas.
    • Qui semble que ce serait un énorme surveillance de la MS de la partie, si c'est la façon dont c'est fait. Tout en F#, étant immuable, vous devez créer/copier une toute nouvelle liste afin d'avoir deux listes concaténés, à la fin d'un ancien. Mais plutôt un moyen facile de le faire en O(n) au lieu de O(N^2) serait de construire la queue-list d'abord, puis la tête de la liste, vous pouvez rejoindre la tête de la queue avec la queue de la tête, tout en O(n) (désolé pour la confusion de la formulation).
    • Pas une surveillance par MS, mais plutôt de compatibilité avec OCaml; autant que je sache, tous les ML à base de langages de définir des listes comme individuellement liée (comme Haskell). Concernant les performances, la solution générale est de renverser votre liste, ajouter de multiples éléments à la tête, puis d'inverser de nouveau la liste, ce qui rend pour un ordre de O(N) opérations. Voir la réponse de Brian.
    • Ils sont liée individuellement, oui. C'était l'implicite raison de ma nécessitant de faire la queue de la liste avant de la tête de liste (la tête de liste serait tout simplement être construit de la tête-la tête la première, comme d'habitude, puis liés à déjà construit queue de liste à l'aide de la tête de la queue de l'élément lorsqu'il est enfin construit).

    InformationsquelleAutor sepp2k
  5. 3

    Peut-être vous voulez utiliser une autre structure de données. Nous avons une double-fini les files d'attente (ou court "Deques") dans fsharpx. Vous pouvez en lire plus sur eux à la http://jackfoxy.com/double-ended-queues-for-fsharp

    InformationsquelleAutor forki23
  6. 1

    L'efficacité (ou l'absence) vient d'itérer sur la liste pour trouver l'élément final. Si la déclaration d'une nouvelle liste avec [4] va être négligeable pour tous, mais le plus trivial des scénarios.

    InformationsquelleAutor Brian Agnew
  7. 0

    Essayez d'utiliser un double-clos de la file d'attente au lieu de la liste. J'ai récemment ajouté 4 versions de deques (Okasaki de l'orthographe) à FSharpx.De base (Disponibles via NuGet. Le code Source à FSharpx.De base.Structures de données). Voir mon article sur l'utilisation de dequeus Double-fini les files d'attente pour F#

    Je l'ai suggéré à l'équipe F# l'opérateur cons, ::, et de la configuration active discriminateur être mis à disposition pour d'autres structures de données avec une tête/queue de signature.Trois

    InformationsquelleAutor Jack Fox