Récursive set union: comment cela fonctionne-t-il vraiment?

je suis actuellement en train de suivre le cours de Scala sur Coursera sur mon temps libre après le travail, dans une tentative de donner enfin un essai à la programmation fonctionnelle. Je travaille actuellement sur une tâche où nous sommes censés "calculer" l'union de deux ensembles qui contiennent un objet. Je Omets intentionnellement des détails car ce n'est pas vraiment important pour ce que j'essaie de demander ici. Ce qui est important, cependant, est que les ensembles sont définis comme des arbres binaires, avec chaque noeud contenant un élément, et deux les sous-arbres.

C'est le cas; l'exemple union dans la conférence est, comme suit:

def union(other:BTSet) :BTSet = ((left union right) union other) incl element

Question 1: très franchement, même après avoir lu la FAQ pertinente et d'autres threads de forum, Je ne comprends toujours pas comment et pourquoi cette fonction fonctionne. Il n'y a absolument aucune "action" faite ici dans la mise en œuvre de l'union à part ajouter (le incl call) l'élément au noeud de tête, il s'appelle simplement encore et encore. Je serais très reconnaissante d'une certaine explication...

Question 2: le forum du cours contient de nombreux messages indiquant que cette solution n'est pas efficace du tout, et qu'elle n'est pas assez bonne. Vu que je ne comprends pas comment ça marche pour commencer, je ne comprends pas vraiment pourquoi ce n'est pas assez bien.

veuillez noter que je ne demande en aucun cas un spoiler pour la solution d'assignation. Je suis plus que prêt à "faire le travail pour la note" mais je ne comprends tout simplement pas ce que je suis censé faire ici. Je ne crois pas que les instructions et les conseils fournis dans le cours sont adéquats pour envelopper votre tête autour des bizarreries de la programmation fonctionnelle, donc je suis heureux de tous les commentaires / réponses qui traitent comment penser correctement plutôt que comment coder à droite.

24
demandé sur posdef 2013-04-25 18:21:40
la source

6 ответов

  A
 / \  union  D
B   C

((B union C) union D) incl A
  ^^^^^^^^^......................................assume it works

(  B             )
(    \   union D ) incl A
(     C          )

(((0 union C) union D) incl B) incl A
   ^^^^^^^^^.....................................just C

(((C union D) incl B) incl A
   ^^^^^^^^^.....................................expand

((((0 union 0) union D) incl C) incl B) incl A
    ^^^^^^^^^....................................just 0

(((0 union D) incl C) incl B) incl A
   ^^^^^^^^^.....................................just D

((D incl C) incl B) incl A
^^^^^^^^^^^^^^^^^^^^^^^^^^.......................all incl now

il suffit de l'écrire, étape par étape. Maintenant, vous voyez que l'union se réduit à un tas de déclarations incl appliquées à l'argument de droite.

23
répondu Rex Kerr 2013-04-25 19:15:27
la source

j'en déduis que incl insère un élément dans un ensemble existant? Si oui, c'est là que le vrai travail se passe.

La définition de l'union est l'ensemble qui inclut tout ce qui en soit d'entrée de jeu. Étant donné deux ensembles stockés sous forme d'arbres binaires, si vous prenez les unions du premier ensemble avec les branches du deuxième, le seul élément dans l'un ou l'autre qui pourrait être absent du résultat est l'élément au noeud racine du deuxième arbre, donc si vous insérez cet élément vous avez le l'union de tous entrée de jeux.

c'est juste une façon très inefficace d'insérer chaque élément des deux ensembles dans un nouvel ensemble qui commence vide. Les doublons sont probablement éliminés par incl, donc le résultat est l'union des deux entrées.


peut-être que cela aiderait à ignorer la structure de l'arbre pour le moment; ce n'est pas vraiment important pour l'algorithme essentiel. Disons que nous avons des ensembles mathématiques abstraits. Étant donné un ensemble d'entrées avec des éléments inconnus, nous pouvons faire deux les choses les choses:

  • Ajouter un élément (qui ne fait rien si l'élément est déjà présent)
  • vérifiez si l'ensemble n'est pas vide et, si c'est le cas, décomposez-le en un seul élément et deux sous-ensembles disjoints.

pour prendre l'union de deux ensembles {1,2} et {2,3}, nous commençons par décomposer le premier ensemble en l'élément 1 et les sous-ensembles {} et {2}. Nous récursive de l'union, {}, {2}, et {2,3} en utilisant le même processus, puis insérez-1 dans le résultat.

à chaque étape, le problème est réduit d'une opération syndicale à deux opérations syndicales sur des entrées plus petites; un algorithme standard de diviser pour mieux régner. Lorsque l'on atteint l'union d'un ensemble unique et d'un ensemble vide, l'union est triviale, puis remontée dans la chaîne.

la structure de l'arbre est juste utilisée pour permettre l'analyse de cas/décomposition en ensembles plus petits, et pour rendre l'insertion plus efficace. La même chose pourrait être faite en utilisant d'autres données structures, telles que des listes qui sont divisées en deux pour la décomposition et avec l'insertion fait par un contrôle exhaustif pour l'unicité. Prendre le syndicat efficacement nécessite un algorithme qui est un peu plus intelligent, et tire profit de la structure utilisée pour stocker les éléments.

4
répondu C. A. McCann 2013-04-25 19:29:19
la source

donc basé sur toutes les réponses ci-dessus, je pense que le vrai cheval de travail est incl et la récursivité de l'appel de union est juste pour passer à travers tous les éléments de décors.

j'ai proposé la mise en œuvre suivante de l'union, est-ce mieux?

def union(other:BTSet) :BTSet = right union (left union (other incl element))
3
répondu Y.G. 2016-06-20 02:03:57
la source
  2
 / \  union  4
1   3

((1 union 3) union 4) incl 2
  ^^^^^^^^^......................................assume it works

(((E union E) union 3 incl 1) union 4) incl 2
   ^^^^^^^^^.....................................still E

(E union E) union 3 incl 1 = E union 3 incl 1 = 3 incl 1

le sous-groupe suivant doit être 3 incl1

(  3             ) 
(    \   union D ) incl 2
(      1         )


(((1 union E) union 4) incl 3) incl 2
   ^^^^^^^^^.......................................expand

(((( (E union E) union E) incl 1) union 4) incl 3) incl 2
      ^^^^^^^^^^^^^^^^^^^^^^^^^^..................still 1

((1 union 4) incl 3) incl 2
   ^^^^^^^^......................................continue

((((E union E) union 4) incl 1) incl 3) incl 2
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^..........expand 1 union 4

((4 incl 1) incl 3) incl 2
  ^^^^^^^^^^^^^^^^^^^^^^^^^............Final union result 

Merci @Rex Kerr sort les marches. Je substitue la deuxième étape avec l'étape d'exécution réelle, qui peut donner une description plus claire de La Scala union fonction.

2
répondu chapter09 2014-05-12 22:42:11
la source

vous ne pouvez pas comprendre les algorithmes récursifs à moins de regarder le cas de base. En fait, souvent, la clé de la compréhension réside dans la compréhension du scénario de base d'abord. Puisque le cas de base n'est pas montré (probablement parce que vous n'avez pas remarqué il y a un en premier lieu) il n'y a aucune compréhension possible.

1
répondu Ingo 2013-10-01 03:26:35
la source

je fais le même cours, et la mise en œuvre ci-dessus de union a s'avèrent être extrêmement inefficace.

j'ai trouvé la solution non-fonctionnelle suivante pour créer une union d'ensembles d'arbres binaires, qui est beaucoup plus efficace:

def union(that: BTSet): BTSet = {
  var result:BTSet = this
  that.foreach(element => result = result.incl(element))
  result
}
-3
répondu Ilya Kogan 2014-11-21 23:49:24
la source