PureBasic

Un prototype de fouille ultra rapide pour trouver une valeur dans un tableau déja trié. Il semble y aavoir un bogue s'il y a plusieurs occurences d'une même valeur.

A+
Guimauve

EDITION :

Je viens de mettre à jour le code avec une suggestion donné sur le forum anglais. Moi j'ai toujours eu un temps de fouille égale à 0. Faut dire que le tableau n'est pas très grand.

Code : Tout sélectionner

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Nom du projet : Prototype de fouille Dichotomique
; Fichier : Code Expérimental
; Version : 0.0.0
; Programmation : En progression
; Programmé par : Guimauve
; Date : 25-08-2005
; Mise à jour : 25-08-2005
; Codé pour PureBasic V3.94
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; PRINCIPE DE FONCTIONNEMENT :
;
; On regarde l'element du milieu. S'il est trop petit,
; On recommence dans la partie de droite restante, sinon
; On recommence dans la partie de gauche restante.
; Ainsi, l'espace de recherche diminue de moitié a chaque
; fois.
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<<<<<< ! ! ! TRÈS TRÈS TRÈS IMPORTANT ! ! ! <<<<<<<<<<
;
; LE TABLEAU SUR LEQUEL LA FOUILLE EST EFFECTUÉE DOIT ÊTRE
; TRIÉ AVANT DE COMMENCER LA FOUILLE. SI NON LA FOUILLE NE
; FONCTIONNE PAS CORRECTEMENT.
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

#Nb_Element = 10
#Max_Random = 5000

Dim Tableau.l(#Nb_Element)


Procedure.l DichotomicSearch(ValeurRecherchee.l)
  
  Position.l = -1
  
  Debut.l = 0
  Fin.l = #Nb_Element ; La grandeur du tableau
  
  While Debut <= Fin
    
    ; On trouve le milieu de l'espace de recherche. 
    Milieu = (Debut + Fin+1) >> 1
    
    ; On conserve la moitie de droite ou de gauche de l'espace de
    ; recherche
    If ValeurRecherchee < Tableau(Milieu)
      Fin = Milieu - 1
      
    ElseIf ValeurRecherchee > Tableau(Milieu)
      Debut = Milieu + 1
      
      ;Si c'est égal, nous avons trouvé et on retourne la position du milieu    
    Else    
      Debut = Fin + 1
      Position = Milieu                
      
    EndIf 
    
  Wend
  
  ProcedureReturn Position
EndProcedure 

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; On met en place des valeurs aléatoire entre 0 et #Max_Random dans le tableau

For index = 0 To #Nb_Element
  Tableau(index) = Random(#Max_Random)
Next 

; On trie le tableau pour que les plus petites valeurs se retrouve au début
SortArray(Tableau(),0)

Debug "On affiche le tableau"
For index = 0 To #Nb_Element
  Debug Tableau(index)
Next 

Debug "On commence à Fouiller dans le tableau"

; on passe toute les valeurs de 0 à #Max_Random pour voir si elle se trouve dans le tableau

For index = 0 To #Max_Random
  
  StartTime = ElapsedMilliseconds() 
  Position = DichotomicSearch(index)
  ElapsedTime = ElapsedMilliseconds()-StartTime
  ; Debug "Temps de Fouille : " + Str(ElapsedTime)

  
  If Position <> -1
    Debug Str(index) + " trouvé à la position : " + Str(Position)
    Debug "La valeur dans le tableau à cet index " + Str(Position) + " : " + Str(Tableau(Position))
    Debug "Temps de Fouille : " + Str(ElapsedTime)
  EndIf 
  
Next

Pourquoi travailler avec des réels (la fonction Round) alors que des entiers iraient encore plus vite ? ca reste optimisable tout ca mais c'est un bon début ^^

Dri

Je sais, c'est un exemple qui provient de MATLAB et dans cet environnement de programmation, le type des variables à de l'importance seulement si on veut lire et écrire un fichier ou si l'on fait un fprintf() sur l'écran.

Exemple en PB si on déclare des variables comme suit :

nombre_de_mot
nom_de_fichier
maximum

Ces 3 variables vont être de type entier 32 bits (Long). Et bien dans MATLAB ça peut-être de n'importe quel type. Ce sont les commandes qui suivent qui vont déterminer le type des variables. L'interpréteur va décider lui-même du bon type de variable à utiliser. C'est plus facile selon certain, selon mon point de vue
C'EST HORRIBLE COMME MÉTHODE DE FAIRE !!! ON N'A PAS LE CONTRÔLE SUR CE QUE L'ON FAIT !

J'en ai presque des boutons à savoir que vais devoir encore programmer dans cet environnement.

C'est un prototype et je n'ai pas eu le temps de le pousser à fond. Dans PB il y a des commandes de triage Ultra performante basé sur l'algorythme FlashSort mais aucune pour fouiller rapidement. c'est pour cette raison que j'ai fait passer cette fonction de MATLAB vers PB.

Voilà !

Ce que j'aimerais bien voir ce sont des fonctions de recheche qui fonctionnent de la même manière que les commandes Sort de PB.

Exemple :

SortStructuredList(ListName(), Options, OffsetDuChamp, Type [, Debut, Fin])

DichotomicSearchStructuredList(ListName(), Options, OffsetDuChamp, Type [, Debut, Fin])

Je pourrais peut-être faire une suggestion à Fred pour PB V4.0

A+
Guimauve

Oué c'est toujours ca les langages interprêtés... faut pas aller chercher loin (javascript c'est pareil)

Quand aux fonctions de recherche pour PB4, c'est pas con ca ^^

Dri