Discussion :

[rambc]

Bonjour,
j'ai le fichier XML incomplet suivant :

Code :

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
<number="1" depth="0">
    <number="2" depth="1">
        <number="4" depth="2">
            <number="8" depth="3">
                ...               
            </number>
        </number>
        <number="3" depth="2">
            <number="5" depth="3">
                ...  
            </number>
            <number="6" depth="3">
                ...  
            </number>
        </number>
    </number>
</number>

Ce fichier représente l'arbre incomplet suivant :

Code :

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

1
2
3
4
5
6
7
8
9
           1
           |
           2         ----> Doubles or Sums of the precedings numbers
          / \
         3   4       ----> Doubles or Sums of the precedings numbers
        / \   \
       /   \   \
      5     6   8
... etc

Je veux utiliser des fichiers XML afin de ne pas être limité en mémoire.

Je voudrais à partir du fichier XML faire trois choses le plus rapidement possible, quitte à faire appel à des bibliothèques extérieures comme lxml (c'est même sûr qu'il faudra faire cela) :

1. Savoir si un nombre N apparait en tant que valeur de number.
2. Si un nombre N apparait dans le fichier XML, j'aimerais récupérer le chemin qui permet d'y accéder. Par exemple, pour 8, j'aimerais récupérer [1,2,4], et pour 3 avoir [1,2]. J'aimerais aussi récupérer sa profondeur depth indiquée dans mon fichier XML,mais je pense inutile d'utiliser ce depth.
3. Une dernière chose, j'aimerais aussi, afin de construire mon fichier XML, ajouter des noeuds là où il y a des points de suspension.

Toute info. est la bienvenue.

[rambc]

Je pense avoir un début de réponse ici. Je "zieuterais" cela tout à l'heure après le vélo.

[wiztricks]

Je veux utiliser des fichiers XML afin de ne pas être limité en mémoire.

Je ne comprends pas la relation entre XML et moins de limitation mémoire.

[*] Une dernière chose, j'aimerais aussi, afin de construire mon fichier XML, ajouter des noeuds là où il y a des points de suspension.[/LIST]
Toute info. est la bienvenue.

Je vais peut être dire une bétise mais la forme:
<number=value depth=n>
ne me paraît pas très correcte. il serait peut être plus juste d'avoir
<number value=value depth=n/>
Ce qui est un nœud sans fils.

Pour le reste... XML est populaire pour sérialiser des données qu'on va échanger entre applications. Prendre des outils tels que lxml pour les analyser est très bien mais si vos traitements ne peuvent se faire en lisant le XML pas à pas (i.e. SAX) il va falloir le charger en mémoire et l'attaquer avec du DOM.
Et comme vous voulez interroger la structure en mémoire, je ne vois pas trop comment faire ça sans tout charger.
Quitte à tout charger et à parcourir la chose avec des requêtes à inventer pourquoi ne pas désérialiser l'engin dans une base de donnée?
Cela permet de ne pas se poser de questions "côté mémoire" et côté query ou autre fonctionnalité on dispose d'un engin un peu plus performant.
Mais ce n'est peut être pas ce que vous voulez.
- W

[rambc]

Je ne comprends pas la relation entre XML et moins de limitation mémoire.

Je crée mon fichier XML pour une velur donnée, si elle a déjà été traité j'utilise le fichier XML, sinon j'ajoute les nouveaux noeuds nécessaires pour obtenir cette nouvelle valeur.

Je vais peut être dire une bétise mais la forme:
<number=value depth=n>
ne me paraît pas très correcte. il serait peut être plus juste d'avoir
<number value=value depth=n/>
Ce qui est un nœud sans fils.

Bonnes remarques...

Et comme vous voulez interroger la structure en mémoire, je ne vois pas trop comment faire ça sans tout charger.
Quitte à tout charger et à parcourir la chose avec des requêtes à inventer pourquoi ne pas désérialiser l'engin dans une base de donnée?
Cela permet de ne pas se poser de questions "côté mémoire" et côté query ou autre fonctionnalité on dispose d'un engin un peu plus performant.
Mais ce n'est peut être pas ce que vous voulez.

Seul souci, mon niveau de connaissance équivaut au zéro absolu de la gestion de BDD.

Je vais quand même essayer à titre d'essai mon idée. Faut juste que je trouve du temps donc ce ne seras sûrement pas avant la fin de la semaine prochaine.

[miawaw]

Bonjour.

Pour ne pas avoir à construire d'arbre je récupère dans les données number et depth. Ensuite, en parcourant 'intelligemment' la liste des depths, je trouve le chemin qui conduit à n'importe quel nombre.

Code :

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
31
32
#!/usr/bin/env python
 
import re
 
def trouve_chemin(number):
    fname = "xmlfile.xml"
    xmltext = open(fname, 'r').read()
    reg = re.compile(r'<number="(\d+)" depth="(\d+)">', re.DOTALL)
    m = reg.findall(xmltext)
 
    if m:
        numbers, depths = zip(*map(lambda (x,y): (int(x),int(y)), m))
        I = numbers.index(number)
        depth = depths[I]
        chemin = []
 
        while depth > 0:
            depth -= 1
            depths = depths[:I]
            c = depths[I-1::-1] # 3 3 2 3 2 1 0
            I = I - 1 - c.index(depth)
            chemin.append(numbers[I])
        chemin = chemin[::-1]
        print "chemin pour %2d:" % number, chemin
 
    else:
        print "No match for %d." % number
 
 
 
for n in [1,2,3,4,5,6,8]:
    trouve_chemin(n)

les resultats:

Code :

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

1
2
3
4
5
6
7
chemin pour  1: []
chemin pour  2: [1]
chemin pour  3: [1, 2]
chemin pour  4: [1, 2]
chemin pour  5: [1, 2, 3]
chemin pour  6: [1, 2, 3]
chemin pour  8: [1, 2, 4]

Bonne soirée.

EDIT: Illustration:
Les listes 'numbers' et 'depths' construites (d'apres l'exemple) sont:

Code :

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

1
2
numbers= [1, 2, 4, 8, 3, 5, 6]
depths = [0, 1, 2, 3, 2, 3, 3]

En image, on voit que que vaut la variable I lors de chaque itération de la boucle while:

Code :

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

1
2
3
4
5
6
recherche: 6
numbers:     1    2    4    8    3    5    6
iteration 0:                               x   (avant le while)
iteration 1:                     x
iteration 2:      x
iteration 3: x

on a construit le chemin [1,2,3].

[rambc]

Merci pour la réponse précédente.

Voici ce que j'ai fait pour la lecture :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import xml.etree.ElementTree as etree
tree = etree.parse('memoryTree.xml')
root = tree.getroot()
 
def findNumber(node, number):
    for child in node:
        if(child.attrib['value']==number):
            return [number]
 
        test = findNumber(child, number)
        if test:
            return [child.attrib['value']] + test
 
print(findNumber(root, str(12)))

J'obtiens :

Code :

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

['1', '2', '3', '6', '12']

Le fichier XML memoryTree.xml est le suivant :

Code :

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
<?xml version="1.0" encoding="ISO-8859-1" standalone="no" ?>
<knuth>
    <number value="1">
        <number value="2">
            <number value="4">
                <number value="8">
                </number>
            </number>
            <number value="3">
                <number value="5">
                </number>
                <number value="6">
                    <number value="9">
                    </number>
                    <number value="12">
                    </number>
                </number>
            </number>
        </number>
    </number>
</knuth>

Quand je trouverais 5 min, je m'attaquerais à la création du fichier XML avec les règles imposées.