Discussion :

[pseudocode]

Je peut compter à partir de 0 ou il y a une raison au 1 ?

Non, puisqu'il faut qu'il y ait un "1" au début du nombre binaire pour servir de délimiteur.

[smyley]

Non, puisqu'il faut qu'il y ait un "1" au début du nombre binaire pour servir de délimiteur.

Non je comprends pas. Je peut pas avoir ça ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
      0
        \         
         1
      /    \
    10      11   
   /  \    /  \  
 100  110 101 111

Comme ça pour savoir dans quel bloc se trouve l'offset que je veux il suffirait de faire la division euclidienne de l'offset par la taille du block, puis de le chercher dans l'arbre binaire non ?
Avec juste ça :

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
public enum PathType
        {
            FinalPoint, /* le path se termine ici */
            Left, /* on doit continuer à gauche */
            Right /* on doit continuer à droite */
        }
 
        public virtual PathType PathType_MoveNext(ref ulong path)
        {
            if (path == 0)
                return PathType.FinalPoint;
            else
            {
                PathType result = PathType.FinalPoint;
                if ((path & 1) == 1)
                {
                    result = PathType.Right;
                }
                else
                {
                    result = PathType.Left;
                }
 
                /* et on décale */
                path = path >> 1;
 
                return result;
            }
        }

je sais où mon path commence, et où il se termine (quand path vaut 0)

[SpiceGuid]

Il reste quand même la question de parcourir l'arbre pour retrouver la liste 1, 2, 3, 4, 5, 6, 7,...

Apparemment je me serais trompé de sens, il faudrait lire les bits de gauche-à-droite au lieu de droite-à-gauche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
         1
      /    \
    10      11   
   /  \    /  \  
 100  101 110 111

Du coup pour retrouver la liste il suffirait d'un parcours en largueur.

Ou alors la solution de facilité: doubler l'arbre par une liste chaînée, après tout ça ne fais qu'un pointeur supplémentaire.

Je peut compter à partir de 0 ou il y a une raison au 1 ?

Il y a une raison incontournable:

• pour tous les noeuds sur une même ligne la longueur du chemin à la racine est la même
• cette longueur c'est le nombre de bits qui codent la clé
• par conséquent tous les noeuds qui sont sur une même ligne doivent être codés sur le même nombre de bits
• le noeud à la fin d'une ligne de niveau n doit donc être égal à 2ⁿ-1, comme ça quand on lui ajoute 1 ça incrémente le nombre de bits des clés de la ligne suivante

Non je comprends pas. Je peut pas avoir ça ?

Si ça fonctionne bien pour le cas 0 alors tu peux, ce que tu ne peux pas faire c'est ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
        0
      /    \
    1       10   
   /  \    /  \  
 11  100 101 110

Non, puisqu'il faut qu'il y ait un "1" au début du nombre binaire pour servir de délimiteur.

OUi, mais maintenant que j'ai changé de sens de lecture ça n'a plus d'importance.

[smyley]

Il reste quand même la question de parcourir l'arbre pour retrouver la liste 1, 2, 3, 4, 5, 6, 7,...

Apparemment je me serais trompé de sens, il faudrait lire les bits de gauche-à-droite au lieu de droite-à-gauche:

Bah même comme j'aurai du mal à parcourir l'arbre avec une méthode non récursive ... (comment énumérer tous les enfants d'un même niveau en ayant juste le ptr vers le gauche, le droit, et le parent ?). Pour cette histoire d'ordre j'avais pensé à ceci :

* ---- block
* 0..7 : next block (in-order) (ulong)
* 8..15 : btree left (ulong)
* 16..23 : btree right (ulong)
* 24..31 : extend 1 (ulong)
* 32..39 : extend 2 (ulong)
* 40..47 : extend 3 (ulong)
* 48..63 : data
* ---- block
* 0..63 : data
* ---- block
* 0..63 : data
* ---- block
* 0..63 : data

et pour les histoires d'extends, c'est que vu qu'un bloc fait 64 octets, en ne mettant que les données dans un bloc j'utilise 3/8 du bloc pour l'index alors qu'en improvisant une petite liste de 4 éléments j'en utilise 6/32 (ce qui, sur 24 Mo, fait une sacrée différence). Donc les blocs je les compterai en multiples de 256 - 48 (=208) octets. Pour le parent à la limite je m'en fiche dans les données, je m'arrange pour qu'à chaque fois que j'y accède je garde une liste du chemin parcouru. Vu que c'est en log, même pour 400 000 nodes je devrais pas avoir une liste plus grandes qu'une dizaine d'éléments.

Du coup pour retrouver la liste il suffirait d'un parcours en largueur.

Mais comment, sans perdre trop de temps ?

Ou alors la solution de facilité: doubler l'arbre par une liste chaînée, après tout ça ne fais qu'un pointeur supplémentaire.

Bah justement ... c'est plus rapide et c'est pas plus gros vu que je me débarrasse du pointeur vers le parent.

Il y a une raison incontournable:

• pour tous les noeuds sur une même ligne la longueur du chemin à la racine est la même
• cette longueur c'est le nombre de bits qui codent la clé
• par conséquent tous les noeuds qui sont sur une même ligne doivent être codés sur le même nombre de bits
• le noeud à la fin d'une ligne de niveau n doit donc être égal à 2ⁿ-1, comme ça quand on lui ajoute 1 ça incrémente le nombre de bits des clés de la ligne suivante

Tous mes pointeurs font 8 octets, no matter what. Et pour les niveaux, je ne vois pas tel que je conçois mon code : on parcours le path en le rétrécissant et on s'arrête quand on arrive à 0. On a pas vraiment besoin de savoir combien d'éléments on a déjà fait. Si après on veut rajouter un élément, on a la racine et le path désiré donc on crée la node et on la rajoute non ?

[SpiceGuid]

Désolé ma connection est très lente aujourd'hui et je n'ai pas réussi à lire ton message avant de poster le mien. Du coup on ne parlait pas du même arbre.
Si ça fonctionne bien pour le cas 0 alors tu peux placer ton arbre à droite si ça t'arrange.

Ce qui n'aurait aucun sens c'est un arbre comme ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
        0
      /    \
    1       10   
   /  \    /  \  
 11  100 101 110

[smyley]

Désolé ma connection est très lente aujourd'hui et je n'ai pas réussi à lire ton message avant de poster le mien. Du coup on ne parlait pas du même arbre.

Ah

Si ça fonctionne bien pour le cas 0 alors tu peux placer ton arbre à droite si ça t'arrange.

ça m'arrange ... bon bah j'y retourne (quoiqu'on ne se bat pas le ventre vide ...). Je vous dit déjà même si mon combat est loin d'être fini

[pseudocode]

Non, puisqu'il faut qu'il y ait un "1" au début du nombre binaire pour servir de délimiteur.

OUi, mais maintenant que j'ai changé de sens de lecture ça n'a plus d'importance.

Heu... si. Le "1" sert toujours de délimiteur que ce soit de "début" ou de "fin". Sinon ca voudrait dire que les "0" de début sont significatifs et qu'il y aurait donc une différence entre l'index 101 et l'index 00000101 alors qu'ils ont la meme valeur numerique.

Sinon, pour en revenir au post : quel intérêt (outre pédagogique) de développer son propre "virtual filesystem" ?

[smyley]

Heu... si. Le "1" sert toujours de délimiteur que ce soit de "début" ou de "fin". Sinon ca voudrait dire que les "0" de début sont significatifs et qu'il y aurait donc une différence entre l'index 101 et l'index 00000101 alors qu'ils ont la meme valeur numerique.

Bah
0
1
10
11
110
111
1000
..
donc pas d'ambiguïté sur le bit de départ même en comptant à partir de 0, le chemin est fini quand le nombre qu'on a entre les mains est "0".

Sinon, pour en revenir au post : quel intérêt (outre pédagogique) de développer son propre "virtual filesystem" ?

Le but de départ c'est faire fonctionner ma base de données, qui est déjà agée de 2 ans, que j'adapte pour avoir exactement ce dont j'ai besoin dans les logiciels que je fait. Cependant au fil du temps la dépendance de mes logiciels vis à vis d'elle se fait de plus en plus forte mais les nécessitées en matière de performances deviennent plus élevée (genre gérer tous mes dossiers de fonds d'écran, quand chaque dossier contient 1800 images, tout ça dans un logiciel que je suis censé "livrer" dans les semaines qui suivent ).
Mis à part les problèmes périodiques que je rencontre lorsque je veux la faire évoluer, elle est carrément plus légère et plus simple d'utilisation que devoir par exemple créer une DB MS SQL, installer le redistributable, configurer les droits, les tables, etc... Tout ça j'en ai pas besoin, je crées une clefs, qui contient les valeurs et qui se dé*erde même pour serializer les différents types que je lui passe, tout ça avec deux dlls qui font en tout 1 Mo pour environ 5-60 Mo en mémoire (en général, on tourne autour de 10 Mo pour la base de donnée). Elle peut même compresser de manière transparente les flux, les crypter, etc... mais derrière j'ai quand même besoin de stocker la structure d'une certaines manière et donc en dessous il y a plusieurs "couches" chargées d'enregistrer le fichier. Le dernier en date gardait beaucoup trop de choses en mémoire et c'est donc là que j'ai décidé de m'orienter vers une couche "file system" vu que là toute la structure reste sur le disque et on peut contrôler ce que l'on garde en mémoire, faire des caches, des optimisations, etc ...
Donc du coup, pour le stockage sur le disque je m'oriente de plus en plus vers des solutions basées sur des arbres binaires, que j'utilise actuellement pour enregistrer les clefs et la liste de leurs enfants, et que je généralise à toute la structure actuellement (même si au départ c'était pas prévu pour les chaines de blocs, c'est prometteur).

Voilà

[pseudocode]

donc pas d'ambiguïté sur le bit de départ même en comptant à partir de 0, le chemin est fini quand le nombre qu'on a entre les mains est "0".

Certes, mais dans ce cas cela ne fait plus un arbre binaire, comme on le voit sur ton schéma. Tous les chemins (sauf 0) commencent par "allez a droite".

Le but de départ c'est faire fonctionner ma base de données, qui est déjà agée de 2 ans, qui j'adapte pour avoir exactement ce dont j'ai besoin dans les logiciels que je fait. (...)

Bref, tu veux faire un système de persistance. Comme ca a déjà été dit, ca serait plus simple de faire un indexeur DB+FS : la DB pour gerer les index (recherche, ...) et le FS pour stocker les blobs (répertoires + fichiers binaires).

[smyley]

Certes, mais dans ce cas cela ne fait plus un arbre binaire, comme on le voit sur ton schéma. Tous les chemins (sauf 0) commencent par "allez a droite".

Bah oui mais sinon ce serai un calvaire de localiser le bloc qui contient l'offset 0 ... C'est toujours un arbre binaire ... pour toutes les valeurs supérieures à 0

Bref, tu veux faire un système de persistance. Comme ca a déjà été dit, ca serait plus simple de faire un indexeur DB+FS : la DB pour gerer les index (recherche, ...) et le FS pour stocker les blobs (répertoires + fichiers binaires).

ça ne répondrait pas à mes attentes : les blobs je connais pas à l'avance leur taille, il peut y avoir 10 000 blobs (10 000 fichiers ?), ça ne tient pas dans un seul fichier, ce serai extrêmement lent pour accéder aux petits blobs (vu que je charge direct une page, la lecture d'un blob de 6 Ko est plutôt rapide vu que c'est en mémoire, en tout cas plus que d'ouvrir un fichier sur le disque, lire les 6 Ko, et refermer le fichier ... en tout cas en .NET c'est affreusement lent), ça impliquerai de changer un système qui me plait et que j'utilise depuis 2 ans dans absolument tous mes projets ... bref, zvx pô

[pseudocode]

ça ne répondrait pas à mes attentes : les blobs je connais pas à l'avance leur taille, il peut y avoir 10 000 blobs (10 000 fichiers ?), ça ne tient pas dans un seul fichier, ce serai extrêmement lent pour accéder aux petits blobs (vu que je charge direct une page, la lecture d'un blob de 6 Ko est plutôt rapide vu que c'est en mémoire, en tout cas plus que d'ouvrir un fichier sur le disque, lire les 6 Ko, et refermer le fichier ... en tout cas en .NET c'est affreusement lent), ça impliquerai de changer un système qui me plait et que j'utilise depuis 2 ans dans absolument tous mes projets ... bref, zvx pô

c'est toi qui vois... Perso, je préfère utiliser DB+Cache+FS avec toutes les fonctionnalités qui vont avec (multithread, read-ahead, lazy-write, ...).

[smyley]

c'est toi qui vois... Perso, je préfère utiliser DB+Cache+FS avec toutes les fonctionnalités qui vont avec (multithread, read-ahead, lazy-write, ...).

read-ahead et lazy-write je sais faire aussi

blague à part, j'ai pas fait grand chose ces derniers jours (fêtes, dodo à 5h du mat, ...) et là j'ai une petite question :
Comme en ayant une node munie des propriétés left,right,parent, peut on obtenir, de manière itérative (mauvais souvenirs des StackOverflow) l'élément suivant du même niveau ? (ou s'il n'y en a pas, un truc qui serait bien c'est avoir le premier enfant du niveau suivant ...)

[pseudocode]

Tu veux dire cela : Queue-based level order traversal ?

[SpiceGuid]

Tu avais dis que, en plus de l'arbre, tu conservais la liste des blocs dans leur ordre d'insertion, dans ce cas c'est l'élément suivant dans cette liste, non ?

[smyley]

Tu veux dire cela : Queue-based level order traversal ?

Mais pour ça, il faut toujours partir de "root" non ? On ne peut pas partir d'un nœud ?

Tu avais dis que, en plus de l'arbre, tu conservais la liste des blocs dans leur ordre d'insertion, dans ce cas c'est l'élément suivant dans cette liste, non ?

Oui mais j'ai été bloqué des fois après m'être lancé dans du code affreux. Après un moment de réflexion sur un lit avec un cahier et un crayon, je pense que le plus efficace c'est ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
     0
       \
        1
      /    \
    10     11   
   /  \    /  \  
 100 101 110 111
  |    |  |    |
  dddddddddddddd...

A chaque fois, "d" est un bloc de données qui contient un pointeur vers le d suivant. Donc en fait, j'index une liste chainée avec un arbre binaire comme cela les performances en lecture séquentielles restent aussi bonnes que pour une simple liste chainée et le seek est rapide grâce à l'index. Mais du coup, je ne peut pas remonter à partir des données vers le bloc d'index associé. (Mais par contre je sais que pour ajouter un d, il faut que je prenne la dernière feuille de l'index et s'il est remplit de rajouter une node après cette dernière).

Sur le papier l'ajout c'est bon, la recherche c'est bon, et la suppression j'ai besoin de pouvoir énumérer les nodes par niveau car pour supprimer la node 11 vu que c'est des données il faut que je supprime tout ce qui va après 11. Donc je supprimes 11, 100, 101 et quand j'arrive à 110 c'est bon vu que son parent a été supprimé donc j'en déduit que tout ce qui suit aussi ... Coté données il suffit que je rajoute le premier d que je veux supprimer dans une liste chainée qui contient l'espace vide et c'est réglé (vu que tous les suivants vont y être aussi).

[pseudocode]

Mais pour ça, il faut toujours partir de "root" non ? On ne peut pas partir d'un nœud ?

On peut partir d'un noeud quelconque, mais on va avoir nécessairement besoin de construire la reste de la pile (=les ancêtres) à un moment. Pourquoi ne pas faire ça en récursif, ça doit prendre en gros 4 lignes ?

[smyley]

On peut partir d'un noeud quelconque, mais on va avoir nécessairement besoin de construire la reste de la pile (=les ancêtres) à un moment.

Attend, comment je fais exactement pour liste le niveau qui contient une node "a" ? je doit d'abord prendre la node, construire la liste des parents, et énumérer tous les niveaux jusqu'à trouver la node pour ensuite continuer l'énumération ? (faut me comprendre, je suis pas réveillé depuis longtemps ...).

Pourquoi ne pas faire ça en récursif, ça doit prendre en gros 4 lignes ?

J'ai un mauvais souvenir ... le nombre de récursion faites dans ce cas est proportionnel à quoi ? (vu que au bout d'un moment sur certaines récursions j'avais un gros StackOverflowException qui crash tout le programme sans rien demander et sans rien dire ...)

[pseudocode]

je doit d'abord prendre la node, construire la liste des parents, et énumérer tous les niveaux jusqu'à trouver la node pour ensuite continuer l'énumération ? (faut me comprendre, je suis pas réveillé depuis longtemps ...).

Oui, ca c'est la methode brutale. On peut optimiser en stockant avec l'arbre un pointeur sur le 1er node de chaque niveau, car pour l'iteration "level order" on a juste besoin de connaitre la liste des parents immédiats (= au niveau n-1)

J'ai un mauvais souvenir ... le nombre de récursion faites dans ce cas est proportionnel à quoi ? (vu que au bout d'un moment sur certaines récursions j'avais un gros StackOverflowException qui crash tout le programme sans rien demander et sans rien dire ...)

Hmm ? Au pire, la récursion est égale a la hauteur de l'arbre, donc O(Log2(n)). A moins d'avoir un très très gros arbre, je ne vois d'où vient le StackOverflowException ?

[smyley]

Oui, ca c'est la methode brutale. On peut optimiser en stockant avec l'arbre un pointeur sur le 1er node de chaque niveau, car pour l'iteration "level order" on a juste besoin de connaitre la liste des parents immédiats (= au niveau n-1)

Je vais essayer de faire le "Queue-based level order traversal" (faudrait déjà que je comprenne). Mais bon, après manger

Hmm ? Au pire, la récursion est égale a la hauteur de l'arbre, donc O(Log2(n)). A moins d'avoir un très très gros arbre, je ne vois d'où vient le StackOverflowException ?

C'était pas pour le même problème.

[SpiceGuid]

C'est quoi ton problème exactement, tu veux pouvoir retirer des blocs ?

Si oui, alors la solution de loin la plus simple c'est de marquer le noeud comme "libre" de façon à pouvoir le recycler en "occupé".
Mais ça ne va peut être pas avec ton application.

À mon avis tu ne devrais rien coder avant d'être certain d'avoir pensé à tout (et surtout à toutes les complications/limitations possibles).