Liste triée perturbant une recherche dichotomique

**jlb91600** · 01/12/2016, 13h20

Bonjour,

Pour faire simple, proposant une extraction d'informations techniques issue d'une base de données Oracle, je mets en tableau des informations de caractéristique technique d'un équipement.
Les concepteurs du logiciel de GMAO ont utilisés des astuces pour permettre d'optimiser les informations stockées.
Chaque équipement dispose d'une classe et d'une sous classe renseignée ou non, sur chaque classe nous définissons des propriétés pour identifier une caractéristique technique.
Seule les propriétés renseignées individuellement sont stockées. Par contre une sous classe hérite des propriétés de la classe, de ce fait une valeur associée à la propriété de la sous classe est affiché pour tous les équipements tout en étant stockée une seule fois - gain non négligeable.

Lors de l'utilisation du programme Excel, selon les critères de sélection d'équipement, j'interroge la base Oracle sur plusieurs tables et effectue une mise en forme tabulaire des données.
Pour extraire les données de propriétés techniques, je concatene le code de la propriété, le code de la classe, le code de l'équipement ou le code de la sous-classe, en regard de la valeur stockée.
Soit : "propriété classe équipement" ou "propriété classe sous-classe"

Une recherche dichotomique permet de trouver rapidement les informations, sauf quand il y a une aberration dans le tri !

Ci-dessous une partie de la liste (il y a plus de 43000 lignes) :
IDCNTRGLGREQFA-GR-000001246 ==> IDCNTRGL GR EQFA-GR-000001246 propriété classe équipement
IDCNTRGLGREQFA-GR-000001247
IDCNTRGLGREQFA-GR-000001248
IDCNTRGLGRGR-BLINDALU ==> IDCNTRGL GR GR-BLINDALU propriété classe sous-classe
IDCNTRGLGRGR-CAPALDI
IDCNTRGLGRGR-FIRAC/MEMC
IDCNTRGLGRGR-MEMC
IDCNTRGLGRGR-S-CLEMESSY
IDCNTRGLGRGR-S-CLEMESSY-V2
IDCNTRGLGRGR-SEFALU
IDCNTRGLGRGR-S-FIRAC-V2
IDCNTRGLGRGR-S-SOTRALINOX ==> donnée recherchée
IDCNTRGLGRGR-VERBOOM
IDCNTRGLGSEQFA-GS-000000000
IDCNTRGLGSEQFA-GS-000000001
IDCNTRGLGSEQFA-GS-000000002

Pour la sous classe GR-S-SOTRALINOX la réponse est "non-renseigné" or la ligne existe !
Donc pourquoi un tri EXCEL ou SQL insère IDCNTRGLGRGR-SEFALU entre s-c et s-f ? quel est l'importance du signe moins par rapport aux lettres ?

Pour contrer ce problème, lorsque l'écart de recherche est inférieur à 10, je teste chaque ligne entre les bornes et trouve la bonne occurence !

Si vous avez une explication rationnelle ou si je n'ai pas été assez clair, j'attends vos avis.
Cordialement Jean-Luc

**halaster08** · 01/12/2016, 13h41

Bonjour,

On dirait qu'il ignore le "-".
on a bien se entre sc et sf.
j'ai fait un test en rajoutant un sd et un s-d, les deux vont s'insérer entre s-c et se.

edit: on remplaçant "-" par "_" là le tri se fait bien.

**jlb91600** · 01/12/2016, 14h11

Oui en changeant le caractère, mais ce sont des codes utilisés dans la GMAO et le souligné ne se voit pas forcément dans des champs encadrés.

Mais c'est bien la même conclusion, le signe moins n'est pas interprété lors d'un tri, CQFD.

**halaster08** · 01/12/2016, 14h32

Il y a d'autres caractères que tu peux utilisé si le "_" ne se voit pas bien, ex: "/"
Tiens le double "-" (donc "--") marche bien avec le tri ...

**boisgontierjacques** · 01/12/2016, 20h44

Bonsoir,

Une autre façon d'accéder rapidement aux infos consisterait à utiliser l'objet Dictionary (qui utilise en interne le hash-code).

Boisgontier
http://boisgontierjacques.free.fr

**eriiic** · 02/12/2016, 00h06

Bonjour,

Pour confirmer :

Excel trie les données dans l'ordre suivant*:
0 1 2 3 4 5 6 7 8 9 (espace) ! " # $ % & ( ) * , . / : ; ? @ [ \ ] ^ _ ` { | } ~ + < = > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Les apostrophes (') et les tirets (-) sont ignorés, à une exception près : si deux chaînes de texte sont identiques à l'exception d'un trait d'union, le texte comportant le trait d'union est trié en dernier.

(lien d'origine plus valide, désolé)
eric

**unparia** · 02/12/2016, 07h09

Bonjour à tous

Pas grand chose à voir avec Excel en soi ou l'informatique (quel que soit le langage de développement), mais tout à voir avec l'application de la norme AFNOR NF Z44-001 (que le tri soit ou non fait par l'informatique)
https://fr.geneawiki.com/index.php/L...NOR_NF_Z44-001

EDIT : en traitement informatique, il eût bien entendu été plus facile d'ignorer cette norme, puisque le code du signe "-" est inférieur à celui de tous les caractères alphanumériques habituellement utilisés, mais c'eût été quelque peu "prétentieux" d'adapter le reste à l'informatique et non l'informatique au reste.

**jlb91600** · 02/12/2016, 07h51

Bonjour à tous,

Merci pour ces réponses, qui m'éclaire sur la norme régissant l'ordre de tri et inhibant l'apostrophe et le signe moins ou tiret !

De quel Objet Dictionnary s'agit-il ?

Les codes créés en GMAO sont non modifiables, il faut que je fasse avec ! Donc autre solution utiliser un "REMPLACER" afin d'inhiber le caractère "-" dans la liste et le contrôle. A voir.

Jean-Luc

**unparia** · 02/12/2016, 07h56

De quel Objet Dictionnary s'agit-il ?

Aucune importance. Laisse tomber cette idée car même lui appliquera la même norme.

Ah oui : je comprends maintenant. Il t'a été proposé pour vérifier une existence en lieu et place d'un tri.
L'objet Dictionnary peut d'ailleurs être remplacé par une simple collection.

Mais "transporter" ainsi (que ce soit vers un dictionnaire ou une collection) des enregistrements d'une base de données (puisque tu précises qu'ils sont dans Oracle) est lourd lourd ...

**jlb91600** · 02/12/2016, 08h17

Ok.

J'ai contourné le problème d'une façon, mes utilisateurs ont l'intégralité des informations en tableau ce qui leur simplifient l'analyse.

J'étudirai d'autres solutions d'optimisation pour les temps de réponse et la bonne adéquation du tri.

Merci.

Invité · 02/12/2016, 08h27

Bonjour,
Le problème c'est que ta base de données oracle est très certainement configurer en utf8 ou autre chose!

Si tu interface pour plus de commodité tes table via Access tu complique la chose.

Note qu'il existe des instructions par requête qui modifie les paramètres de configuration d'oracle pendant toutes la durée de ta connexion!

Ça fait plus de 15 ans que je n'ai pas fait joujou avec oracle mais en son temps je les ai utiliser!

qu'est ce qui justifié une recherche dichotomique et pas un Find excel ou une requête sql {drive Excel} sur ton fichier?

même esprit que le dictionnaire!

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
49
50
51
Enum ConstAdo    adSmallInt = 2
     adInteger = 3
     adSingle = 4
     adDate = 7
     adBoolean = 11
     adDecimal = 14
     adNumeric = 131
     adVarChar = 200
End Enum
Enum ConsAdoCon
    adOpenKeyset = 1
    adLockPessimistic = 2
    adUseClient = 3
    adFldMayBeNull = 64
End Enum
Sub test()
Set rstADO = CreateObject("ADODB.Recordset")
With rstADO
   ' .Fields.Append "EmployeeID", adInteger, , adFldKeyColumn
    .Fields.Append "Ligne", adInteger, , adFldMayBeNull
    .Fields.Append "FirstName", adVarChar, 10, adFldMayBeNull
    '.Fields.Append "LastName", adVarChar, 20, adFldMayBeNull
    '.Fields.Append "Email", adVarChar, 64, adFldMayBeNull
    '.Fields.Append "Include", adInteger, , adFldMayBeNull
    '.Fields.Append "Selected", adBoolean, , adFldMayBeNull
 
 
    .CursorType = adOpenKeyset
    .CursorLocation = adUseClient
    .LockType = adLockPessimistic
    .Open
End With
For i = 10 To 20
    rstADO.AddNew
    rstADO("Ligne") = i
    rstADO("FirstName") = "Robert"
     rstADO.Update
Next
For i = 21 To 31
    rstADO.AddNew
    rstADO("Ligne") = i
    rstADO("FirstName") = "Lucien"
     rstADO.Update
Next
  rstADO.Sort = "FirstName DESC"
  rstADO.Filter = "FirstName='Robert'"
  While rstADO.EOF = False
    Cells(rstADO("Ligne"), "A") = rstADO("FirstName")
    rstADO.MoveNext
  Wend
End Sub

**boisgontierjacques** · 02/12/2016, 10h47

Bonjour,

>L'objet Dictionnary peut d'ailleurs être remplacé par une simple collection.

La rapidité de Dictionary n'est pas comparable à la lenteur Collection

Boisgontier

Invité · 02/12/2016, 10h54

ma proposition permet de trier ainsi que de filtrer ça remplace avantageusement, enfin il me semble (pas vérifié), une recherche dichotomique!

**unparia** · 02/12/2016, 12h04

Bonjour boisgontierjacques

La rapidité de Dictionary n'est pas comparable à la lenteur Collection

Tu en es certain ? As-tu vérifié (chronométré) par de petits tests ?

Invité · 02/12/2016, 12h33

soit on utilise une collection pour charge les valeur d'une liste et j'en vois pas l'intérêt!

Code :

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

1
2
3
4
5
Sub subCollection()
Dim r As New Collection
r.Add "z"
r.Add "a"
End Sub

soit pour dédoublonner mais il faut gérer le on error!

Code :

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

1
2
3
4
5
Sub subCollection()
Dim r As New Collection
r.Add "z","z"
r.Add "a","a"
End Sub

mais pour ce qui nous préoccupe?????

pour moi tout réside dans la mauvaise qualité des données récupérée dans oracle!

il faut corriger au plus haut niveau possible!

**unparia** · 02/12/2016, 13h11

Et que fait, selon vous, en arrière plan, l'objet dictionnary pour éviter les doublons, sinon gérer (en arrière plan) le "on error" ?
L'objet Dictionnary n'est jamais rien d'autre qu'une collection assortie de fonctions de confort gérant ce que l'on peut gérer directement dans une collection.
Il n'apporte rien en matière de vitesse d'exécution. C'est même souvent le contraire. Il apporte par contre (et là, c'est certain) une lourdeur ajoutée.

Toujours se méfier ce ces "outils de confort", qu'il s'agisse de FSO, d'objet Dictiopnnary, etc ...

Invité · 02/12/2016, 13h24

Envoyé par unparia

Et que fait, selon vous, en arrière plan, l'objet dictionnary pour éviter les doublons, sinon gérer (en arrière plan) le "on error" ?
L'objet Dictionnary n'est jamais rien d'autre qu'une collection assortie de fonctions de confort gérant ce que l'on peut gérer directement dans une collection.
Il n'apporte rien en matière de vitesse d'exécution. C'est même souvent le contraire. Il apporte par contre (et là, c'est certain) une lourdeur ajoutée.

Toujours se méfier ce ces "outils de confort", qu'il s'agisse de FSO, d'objet Dictiopnnary, etc ...

je suis d'accord avec ça et c'est pour cela que je n'objecte pas sur l’utilisation du dictionnaire entre une gestion implicite et une gestion explicite si l’alourdissement n'est pas flagrant! mais là je parle sans preuve que je ne vais pas rechercher!

je n'en dirais pas tant de FSO car là pour le coup Marc me l'a démontré mais je t'accorde l'avantage! pour m'a part, j'utiles très souvent des collection, c'est surtout Patrick qui m'a fait découvre les dictionnaires en vba, que j'utilises de longue date en .net, et j'ai trouvé bien pratique sans pour autant faire d'étude comparative!

pour mois le problème avant tout c'est une mauvaise extraction oracle, Utf8??? après le mode de traitement me semble secondaire même si je pense qu'il ne faudra pas l'éluder!

**boisgontierjacques** · 02/12/2016, 18h24

Voici un test qui montre que Dictionary est 12 fois plus rapide que Collection

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
 
Sub DicoSansDoublons()
  t = Timer()
  Set mondico = CreateObject("Scripting.Dictionary")
  n = 60000
  For i = 1 To n
    temp = Int(Rnd * n)
    mondico(temp) = ""
  Next i
  [a2].Resize(mondico.Count) = Application.Transpose(mondico.keys)
  MsgBox Timer() - t ' 0,6 sec
End Sub
 
Sub CollectionSansDoublons()
   Dim t, i As Long, n As Long, temp As Long
   t = Timer()
   Dim Maliste As New Collection
   On Error Resume Next
   n = 60000
   For i = 1 To n
     temp = Int(Rnd * n)
     Maliste.Add Item:=temp, Key:=CStr(temp)
   Next i
   On Error GoTo 0
   Dim a()
   ReDim a(1 To n)
   For i = 1 To Maliste.Count
     a(i) = Maliste(i)
   Next i
   [a2].Resize(Maliste.Count) = Application.Transpose(a)
   MsgBox Timer() - t ' 8 sec
End Sub

Comparaison d'une recherche dans un Dictionnaire , une Collection et une recherche dichotomique

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Sub RechercheDico()
  t = Timer()
  Set mondico = CreateObject("scripting.dictionary")
  a = [A1:b60000]
  For i = 1 To 60000
    mondico(a(i, 1)) = a(i, 2)
  Next i
  For j = 1 To 60000 Step 2  ' 30000 recherches
    x = "Nom" & Trim(Str(j))
    y = mondico(x)
   Next j
   MsgBox Timer() - t   ' 0,90 sec
End Sub

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Sub RechercheCollection()
  t = Timer()
  Dim MaListe As New Collection
  a = [A1:b60000]
  For i = 1 To 60000
    MaListe.Add Item:=a(i, 2), Key:=a(i, 1)
  Next i
  For j = 1 To 60000 Step 2  ' 30000 recherches
    x = "Nom" & Trim(Str(j))
    y = MaListe(x)
  Next j
  MsgBox Timer() - t  '1,70s
End Sub

Si la table est déjà triée, 30.000 recherches: 1,2 s

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
 
Sub RechDichotomique()
 t = Timer()
 a = [A1:B60000]
 'Call tri(a, 1, UBound(a), 2, 1)
 N = 60000
 For j = 1 To 60000 Step 2  ' 30000 recherches
  cherche = "Nom" & Format(j, "00000")
  Inf = 1: Sup = N
  Do
    If Inf > Sup Then Position = -1: Exit Do
    Milieu = Int((Inf + Sup) / 2)
    If cherche < a(Milieu, 1) Then
       Sup = Milieu - 1
    Else
       If cherche > a(Milieu, 1) Then
         Inf = Milieu + 1
       Else
         Position = Milieu: Exit Do
       End If
     End If
  Loop
  If Position <> -1 Then
    y = a(Position, 2)
  Else
    Stop
  End If
 Next j
 MsgBox Timer() - t
End Sub

Boisgontier
http://boisgontierjacques.free.fr

**unparia** · 02/12/2016, 18h59

T'aurais pas comme un peu l'impression, ami boisgontierjacques, de mélanger quelque peu les choses ?
Une chose est de créer sans doublons, l'autre est l'utilisation des résultats !
Restons purs, si tu veux bien. Il ne s'agit ici QUE de créer une liste d'éléments sans doublons.
Regarde :

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
Dim t As Double, mondico As Object, maliste As New Collection, temp As String, i As Long
 t = Timer()
  Set mondico = CreateObject("Scripting.Dictionary")
  n = 60000
  For i = 1 To n
    temp = Int(Rnd * n)
    mondico(temp) = ""
  Next i
  MsgBox Timer() - t
 
 
   t = Timer()
   'Dim maliste As New Collection
   On Error Resume Next
   n = 60000
   For i = 1 To n
     temp = Int(Rnd * n)
     maliste.Add "", temp
   Next i
   On Error GoTo 0
   MsgBox Timer() - t

histoire sans paroles nécessaires

EDIT : et plus tu augmenteras la valeur de n (le nombre de boucles), plis la différence sautera aux yeux (et de manière plus que simplement proportionnelle).
Amitiés

EDIT 2 : passe donc n à 1 000 000 (je veux éviter de te faire trop souffrir avec le dico et une attente très très très longue et donc ne pas aller plus "haut" ) et tu comprendras bien vite

(je viens de faire le test avec 1 000 000 : la collection est .... 46 fois plus rapide que le dico).
Je ne suis pas maso et ne vais pas immobiliser ma machine avec une boucle de 5 000 000 ((par exemple).

**Marc-L** · 02/12/2016, 20h20

Salut !

résultat du test d'unparia sous Excel 2003 + Seven + processeur i5 2.5GHz :

Pour 60 000 :
Dict = 0,188s
Coll = 0,313s

Pour 1 000 000 :
Dict = 49,313s
Coll = 7,414s (là la collection est ~ 7 fois plus rapide)

J'utilise les deux, c'est selon les contraintes (demande expresse de rester au maximum en "pur" VBA, MAC/PC) …

_________________________________________________________________________________________________________

Je suis Paris, Nice, Bruxelles, Charlie, …

Liste triée perturbant une recherche dichotomique

Macros et VBA Excel

Discussions similaires

Partager

Partager