Discussion :

[niepoc]

Bonjour

je cherche à savoir comment fait on pour trouver dans une colonne, à partir d'une valeur donnée, la valeur la plus proche soit inferieure ou superieure

le but ecrire une fonction pour trouver dans un tableau, la ligne qui correspond à ma valeur cherchée

merci pour l'aide

[N.tox]

salut,

Déjà, ton tableaux est-il une liste de liste ? (je pense que oui mais sait-on jamais...)
Si oui, est-ce un liste de lignes ou une liste de colonnes ?

Partons du principe que c'est une liste de lignes que l'on appelle "Tab"

Un élément du tableau ligne correspond donc à "Tab[num_ligne][num_colonne]"
La longueur d'une ligne = longueur d'une des liste de Tab
longueur d'une colonne = longueur de Tab

si l'on voulait afficher chaque éléments de la deuxième ligne par exemple, on pourrait faire:

Code :

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

1
2
for idx_colonne in range(len(Tab[1])):
    print Tab[1][idx_colonne]

Ici l'élément variable est le numéro de colonne

Si maintenant on veut afficher chaques éléments de la troisième colonne par exemple, on pourrait faire:

Code :

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

1
2
for idx_ligne in range(len(Tab)):
    print Tab[idx_ligne][2]

Ici l'élément variable est le numéro de ligne

Maintenant tu devrai être en mesure de parcourir un colonne, maintenant pour savoir quelle valeur dans cette colonne, est la plus proche d'un valeur précise... tu devrais pouvoir trouver, ceci dit une fonction qui te sera utile est abs(), qui sert à obtenir la valeur absolue d'un nombre...

[panda31]

Valeurs entières, réelles, char ?
Quantité de données manipulées ?

Tu as des algo de recherche opérationnelles à ce sujet.
Tu peux utiliser un curseur sur ton tableau trié.
Ex:

Code :

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

1
2
3
4
5
 
tableau_general = [0,1,1,2,3,5,6,9,111,112,113,114]
curseur1 = 0
curseur2 = 5
curseur3 = 10

Après tu compares ta valeur à scanner par rapport à la valeur de tableau_general[curseur1], tableau_general[curseur2].
Si entre ces deux, tu scannes entre les deux. Sinon, tu regardes avec les prochains curseurs.
Tu peux ensuite faire en sorte de faire ce genre de checks dynamiquement (dichotomie et consorts)

Si non trié, ce n'est pas le même problème. Tu peux mettre en œuvre un arbre (binaire) de recherche. C'est plus une question algorithmique qu'autre chose comme tu le vois...

[niepoc]

pour info

mon tableaux fait 9 colonnes sur 600000 ligne environs, c'est un tableau de floattant (je suis désolé j'ai du mal avec liste, tableau en python, je viens de matlab)
Ce tableau ressemble à une matrice en fait

je souhaite en donnant une valeur quelconque parcourir ma colonne et trouver la valeur la plus proche

apparemment c'est un problème d'algo, il n'y a pas de fonction prédéfinie, je me penche dessus et je vous tiens au courant

merci d'avance

[eyquem]

J’ai pensé à ça:

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
from numpy import array
 
tab = array([[12.3,4.09,34.5,76.4],[23.4,26.7,113.9,46.98],[26.66,3.67,32.8,67.906],\
             [9.544,32.546,44.3214,45.67],[32.897,64.773546,24.3667,892.45],\
             [23.45,34.33,10.34,29.4],[2.45,3.0,8.23,54.0],[23.894,43.82,332.784,4.73]])
print tab,'\n'
 
 
li = list((x for x in tab[:,2]))
li.sort()
 
val = 53.4
 
if li[0]>val:  print li[0],'>',val,'\npas de valeur inferieure a',val
elif li[-1]<val:  print li[-1],'<',val,'\npas de valeur superieure a',val
else:
    a = li[0]
    for x in li:
        if x>val:
            print a,'  / val =',val,'/  ',x
            break
        a = x

Code :

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

1
2
3
4
5
6
7
8
9
10
[[  12.3         4.09       34.5        76.4     ]
 [  23.4        26.7       113.9        46.98    ]
 [  26.66        3.67       32.8        67.906   ]
 [   9.544      32.546      44.3214     45.67    ]
 [  32.897      64.773546   24.3667    892.45    ]
 [  23.45       34.33       10.34       29.4     ]
 [   2.45        3.          8.23       54.      ]
 [  23.894      43.82      332.784       4.73    ]] 
 
44.3214   / val = 53.4 /   113.9

Je n’aime pas trop la fabrication d’un objet liste quand il y a 600 000 lignes mais on y est obligé si on veut pouvoir faire un sort().

Le sort() classe sur place, tandis qu’un sorted() crée une liste supplémentaire à la liste d’origine, d’après ce que j’ai compris dans la doc.

Je ne vois pas comment créer un itérateur à partir de tab[:,2] et en ayant un classement quelque part.

Il doit y avoir des tonnes de solutions qui ont été proposées sur ce problème depuis des lustres, il faut chercher s’il y a mieux.

[panda31]

Bonjour,

Je reste sur un arbre de recherche. C'est un peu fastidieux à mettre en œuvre mais c'est efficace.
Si tu ne connais pas cette structure, un petit memo:
Tu pars du premier élément. Si la valeur suivante est plus grande, elle devient successeur "à droite", sinon successeur "à gauche"

Code :

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

1
2
3
4
5
6
7
8
9
 
Pour la liste (4,3,5,2,2.5):
                                              4
                                             / \
                                            3   5
                                          /       
                                         2
                                           \
                                             2.5

Tu peux facilement ensuite selon ton implémentation savoir si tu es plus grand ou plus petit. Si tes colonnes ne bougent pas trop, pour l'ordonnancement c'est bien pratique. Cherche sur le web, il y a pas mal d'implémentations toutes faîtes. Souvent on recherche une valeur exacte mais tu peux raffiner grâce à cette structure vu que tes bornes sont aussi tes éléments.

Si tu as besoin d'aide pour implémenter cela, n'hésite pas.

Je partirais sur une base objet:

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
 
class ABR:
   def __init__(self,...):
      ...
 
   def insere(self, element):
      """ insère un élément dans l'arbre """
      ...
 
   def contientSup(self, element):
      """ 
      retourne la valeur de l'élément si trouvé, sinon l'élément le plus proche supérieur 
      """
 
   def contientInf(self, element):
      """
      retourne la valeur de l'élément si trouvé, sinon l'élément le plus proche inférieur
      """

A combiner avec une classe Noeud ou Node selon le choix de la langue.
J'ai trouvé cela aussi : lien
Hope it helps !

[niepoc]

merci pour ces réponses

je suis preneur pour une aide sur l'arbre de recherche

je vais essayer l'idée de eyquem aussi, de toute façon ça va m'aider à maitriser le langage

merci d'avance

[eyquem]

Il y a quelque chose qui est flou dans ta question.

Tu as écrit

trouver dans une colonne, à partir d'une valeur donnée, la valeur la plus proche soit inferieure ou superieure

Donc je me suis dit: il cherche la valeur la plus proche dans UNE colonne, et il indiquera d’une manière ou d’une autre LA colonne dans laquelle la recherche doit être faite.
Dans mon exemple, j’ai pris la colonne 2 (la troisième) au hasard.

Mais panda a écrit

Si tes colonnes ne bougent pas trop, ...

ce qui me perturbe un peu parce que je ne comprends pas ce que ça veut dire,
et en relisant ta question je vois

le but ecrire une fonction pour trouver DANS UN TABLEAU, la ligne qui......

et j’en viens à me demander si tu cherches la plus proche valeur dans tout le tableau ou dans une colonne seulement.

[panda31]

Pour moi c'est un détail. Il veut sans doute implémenter cela pour chaque colonne d'un tableau. Je suppose qu'on ne cherche que dans une colonne à la fois.

[niepoc]

1. le but est de rechercher dans une colonne précise la valeur la plus proche, et d'isoler toutes les lignes où cette valeur se trouve, dans un tableau.

Puis recommencer sur ce nouveau tableau sur une autre colonne pour enfin isoler une seule ligne.

Je recherche en fait toutes les latitudes dans mon 1. et ensuite j'isole dans 2. la ligne qui correspond à mes coordonnées données au hasard.

Et aprés, j'obtiens toutes les infos souhaitées selon les coordonnées dans le reste de ma ligne

merci pour l'aide

[N.tox]

Le concept suivant devrait fonctionner, par contre il faudra peut-être adapter la fonction colonne à Numpy (je ne m'en suis jamais servi...):

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
def colonne(idx_col, tab):
    for idx_row in xrange(len(tab)):
        yield (idx_row, idx_col, tab[idx_row][idx_col])
 
def nearest_in(val,colonne_gen):
    nearest=None
    no_equal=True
    for row,col,val_el in colonne_gen:
        diff=abs(val-val_el)
        if not diff: no_equal=False
        if no_equal:
            if (nearest and diff<nearest[-1][-1]) or (not nearest):
                nearest=[(row,col,val_el,diff)]
            elif (nearest and diff==nearest[-1][-1]):
                nearest+=[(row,col,val_el,diff)]
        else:
            if not diff:
                yield (row,col,val_el,diff)
    if no_equal:
        for x in nearest:
            yield x

Exemple d'utilisation :

Code :

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

1
2
3
4
5
tab=[range(16)[y:y+4] for y in range(0,len(range(16)),4)]
for x in tab:
    print x
 
for x in nearest_in(3, colonne(1,tab)): print x

Résultats

Code :

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

1
2
3
4
5
6
[ 0,  1,  2,  3]
[ 4,  5,  6,  7]
[ 8,  9, 10, 11]
[12, 13, 14, 15]
(0, 1, 1, 2)
(1, 1, 5, 2)

Edit : la même chose mais en supposé plus rapide (clock et timit ne fonctionne pas chez moi, ne demandez pas pourquoi...) :

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def colonne(idx_col, tab):
    for idx_row in xrange(len(tab)):
        yield (idx_row, idx_col, tab[idx_row][idx_col])
 
def nearest_in(val,colonne_gen):
    first_sup=None
    first_inf=None
    no_equal=True
    for row,col,val_el in colonne_gen:
        if no_equal:
            if val_el < val:
                if ( (first_inf and val_el>first_inf[-1][-1]) or (not first_inf) ):
                    first_inf=((row,col,val_el),)
                elif (first_inf) and (val_el==first_inf[-1][-1]):
                    first_inf+=((row,col,val_el),)
            elif val_el > val:
                if  ( (first_sup and val_el<first_sup[-1][-1]) or (not first_sup) ):
                    first_sup=((row,col,val_el),)
                elif (first_sup) and (val_el==first_sup[-1][-1]):
                    first_sup+=((row,col,val_el),)
            elif val_el==val:
                no_equal=False
                yield (row,col,val_el,0)
        else:
            if val_el==val:
                yield (row,col,val_el,0)
 
    diff_inf=abs(val-first_inf[-1][-1]) if first_inf else None
    diff_sup=abs(val-first_sup[-1][-1]) if first_sup else None
    if first_inf and first_sup:
        if diff_inf == diff_sup:
            winners=(first_inf,first_sup)
            diff=diff_inf
        elif diff_inf < diff_sup:
            winners=(first_inf,)
            diff=diff_inf
        else:
            winners=(first_sup,)
            diff=diff_sup
        for liste in winners:
            for element in liste:
                yield element+(diff,)
    elif not first_inf:
        for element in first_sup:
            yield element+(diff_sup,)
    else:
        for element in first_inf:
            yield element+(diff_inf,)