[T] Tableau dynamique à partir d'un tableau statique

Partagez vos scripts, et vos applications AutoIt.
Règles du forum
.
Répondre
Avatar du membre
Tlem
Site Admin
Site Admin
Messages : 11773
Enregistré le : ven. 20 juil. 2007 21:00
Localisation : Bordeaux
Status : Hors ligne

[T] Tableau dynamique à partir d'un tableau statique

#1

Message par Tlem »

Message transféré de l'ancien forum.
Auteur : ClemTB
Date : 04/07/2007


Citation :

l'intérêt est très théorique mais ce script peut se révéler utile dans l'implémentation d'une pile ou d'un tas.

Je vais mettre la version améliorée pour l'insertion ici. Il utilise la librairie math include dans la version de base de AutoIt donc devrai pas y avoir de problème (au pire suffit de ré-écrire la fonction _Min($n1,$n2) ...
Par contre pour la librairie array ... si vous lavez pas tant pis :p

J'ai des temps assez correctes (90ms pour insérer 1000 éléments, temps d'accès maximum vu 0,06ms et temps pour vider min pour vider le tableau 47ms) vu grâce à la fonction de test


Code : Tout sélectionner

#include-once
#include
#include
;************************************************************************
;* Auteur: ClemTB
;* Date: 04/07/2007
;* Pays:France
;*
;* Description:
;* Script contenant le minimum vital pour implémenter
;* un tableau dynamique a partir d'un tableau statique.
;*
;* Fonctions disponibles:
;* getListe($position) :retrouve un élément O(n)
;* addElement($element) :ajoute un élément en début de chaîne O(1)
;* deleteElement($position) :supprime un élément dans la liste O(n)
;*
;* Commentaire:
;* Je l'ai commenté du mieux que je pouvait.
;*
;*************************************************************************
;tableau de contenu 10000 enregistrements ca devrait suffire non?
Global $__Listechainee_maxEnregistrements = 1000
Global $__Listechainee_tableContenu[$__Listechainee_maxEnregistrements]
;tableau de pointeurs
Global $__Listechainee_tablePointeurs[$__Listechainee_maxEnregistrements]
Global $__Listechainee_nbEnregistrement = 0
Global $__Listechainee_debut = 0
Global $__Listechainee_minInsertion = 0

;test
test()
Func test()
    $begin = TimerInit()
    getListe(0) ;retourne une erreur dans la Console
    ConsoleWrite("temp:" & TimerDiff($begin) & @CRLF)
    getListe(1) ;retourne une erreur dans la Console
    $begin = TimerInit()
    deleteElement(0) ;retourne une erreur dans la Console
    ConsoleWrite("temp:" & TimerDiff($begin) & @CRLF)
    deleteElement(1) ;retourne une erreur dans la Console
    deleteElement(2) ;retourne une erreur dans la Console

    $begin = TimerInit()
    addElement("premier élément inséré") ;insère un premier élément
    ConsoleWrite("temp insertion du premier element:" & TimerDiff($begin) & @CRLF)
    ConsoleWrite("premier élément:" & getListe(0) & Chr(13)) ;devrait afficher la première valeur
    $begin = TimerInit()
    deleteElement(0) ;supprime le premier élément
    ConsoleWrite("temp suppression du premier element:" & TimerDiff($begin) & @CRLF)
    ConsoleWrite("null ? -> " & getListe(0) & Chr(13)) ;retourne une erreur dans la Console et affiche 0(=NON)
    ;la boucle insère des éléments dans tout le tableau et devrait générer une erreur pour le dernier élément
    $begin = TimerInit()
    For $i = 0 To $__Listechainee_maxEnregistrements
        If Mod($i, 100) = 0 Then ConsoleWrite("insertion n°" & $i & Chr(13))
        addElement("element inseré N°" & $i)
    Next
    ConsoleWrite("temp d'insertion de tous les éléments:" & TimerDiff($begin) & @CRLF)
    ;lit tous les éléments (devrait les afficher dans l'ordre décroissant)
    For $i = 0 To $__Listechainee_maxEnregistrements - 1
        If Mod($i, 100) = 0 Then ConsoleWrite("lecture n°" & $i & " -> " & getListe($i) & Chr(13))
    Next

    $begin = TimerInit()
    deleteElement(0) ;supprime le premier élément
    ConsoleWrite("temp suppression tableau plein:" & TimerDiff($begin) & @CRLF)

    ;devrait afficher $__Listechainee_maxEnregistrements-2
    $begin = TimerInit()
    ConsoleWrite("lecture n°0 -> " & getListe(0) & Chr(13))
    ConsoleWrite("temps d'access au premier élément tableau plein:" & TimerDiff($begin) & @CRLF)

    ;ajoute un élément en début
    $begin = TimerInit()
    addElement("Re ajout")
    ConsoleWrite("temp insertion tableau plein:" & TimerDiff($begin) & @CRLF)

    ;devrait afficher "Re ajout"
    ConsoleWrite("lecture n°0 -> " & getListe(0) & Chr(13))

    ;devrait afficher "élément inséré N°0"
    $begin = TimerInit()
    ConsoleWrite("lecture n°0 -> " & getListe($__Listechainee_maxEnregistrements - 1) & Chr(13))
    ConsoleWrite("temps de lecture du dernier élément avec tableau plein:" & TimerDiff($begin) & @CRLF)

    ;supprime le dernier élément
    $begin = TimerInit()
    deleteElement($__Listechainee_maxEnregistrements - 1)
    ConsoleWrite("temps de suppression du dernier élément avec tableau plein:" & TimerDiff($begin) & @CRLF)

    ;vidage du tableau par le premier élément, génère une erreur pour le dernier élément
    $begin = TimerInit()
    For $i = 0 To $__Listechainee_maxEnregistrements - 1
        If Mod($i, 100) = 0 Then ConsoleWrite("suppression n°" & $i & Chr(13))
        deleteElement(0)
    Next
    ConsoleWrite("temps de vidage du tableau : " & TimerDiff($begin) & @CRLF)

EndFunc   ;==>test

;fonction d'accès
Func getListe($position)
    ;position en dehors du tableau = erreur
    If $position >= $__Listechainee_nbEnregistrement Or $position < 0 Then
        Return __ListeChaineeErreur(1, "Position en dehors du tableau")
    EndIf
    ;init du parcours
    $parcoursPointeur = $__Listechainee_debut
    $parcoursPosition = 0
    ;parcours du tableau jusqu'à la valeur que l'on cherche
    While $parcoursPosition < $position
        $parcoursPointeur = $__Listechainee_tablePointeurs[$parcoursPointeur]
        $parcoursPosition += 1
    WEnd
    Return $__Listechainee_tableContenu[$parcoursPointeur]
EndFunc   ;==>getListe

;fonction d'écriture
Func addElement($element)
    ;si le tableau est plein on plante
    If $__Listechainee_maxEnregistrements < $__Listechainee_nbEnregistrement Then
        Return __ListeChaineeErreur(2, "Tableau plein")
    EndIf

    If $element = "" Then
        Return __ListeChaineeErreur(2, "Ajout d'un élément interdit")
    EndIf

    ;init du parcours
    $parcoursPosition = $__Listechainee_minInsertion
    ;parcours du tableau jusqu'à la fin ou jusqu'à ce qu'on tombe sur un élément vide
    While $parcoursPosition < $__Listechainee_maxEnregistrements And (Not $__Listechainee_tableContenu[$parcoursPosition] = "")
        $parcoursPosition += 1
    WEnd
    ;si on est arrivés a la fin du tableau ... ben erreur.. mais ça devrait pas arriver normalement
    If $parcoursPosition >= $__Listechainee_maxEnregistrements Then
        Return __ListeChaineeErreur(2, "Tableau plein")
    EndIf
    ;sinon on est tombé sur un élément vide !! super on insère notre maillon 1
    ;enregistrement de l'élément
    $__Listechainee_tableContenu[$parcoursPosition] = $element
    ;mise en place du chainage
    $__Listechainee_tablePointeurs[$parcoursPosition] = $__Listechainee_debut
    ;initialisation du debut
    $__Listechainee_debut = $parcoursPosition
    ;positionnement de l'element le plus loin (non fragmenté)
    $__Listechainee_minInsertion = $parcoursPosition
    ;incrément du décompte
    $__Listechainee_nbEnregistrement += 1
    Return 1
EndFunc   ;==>addElement

;suppression d'un élément
Func deleteElement($position)
    ;position en dehors du tableau = erreur
    If $position > $__Listechainee_nbEnregistrement Or $position < 0 Or $__Listechainee_nbEnregistrement = 0 Then
        Return __ListeChaineeErreur(3, "Position en dehors du tableau")
    EndIf

    If $position = 0 Then
        $__Listechainee_tableContenu[$__Listechainee_debut] = ""
        $__Listechainee_debut = $__Listechainee_tablePointeurs[$__Listechainee_debut]
        $__Listechainee_nbEnregistrement -= 1
        $__Listechainee_minInsertion = 0
        Return 1
    EndIf

    ;init du parcours
    $parcoursPointeur = $__Listechainee_debut
    $parcoursPosition = 0
    ;parcours du tableau jusqu'à la valeur qu'on cherche
    While $parcoursPosition + 1 < $position
        $parcoursPointeur = $__Listechainee_tablePointeurs[$parcoursPointeur]
        $parcoursPosition += 1
    WEnd

    ;decalage
    $__Listechainee_tableContenu[$parcoursPointeur] = ""
    $__Listechainee_tablePointeurs[$parcoursPointeur] = $__Listechainee_tablePointeurs[$__Listechainee_tablePointeurs[$parcoursPointeur]]
    $__Listechainee_nbEnregistrement -= 1
    $__Listechainee_minInsertion = _Min($parcoursPointeur, $__Listechainee_minInsertion)
    Return 1
EndFunc   ;==>deleteElement

;centralisation des erreurs
Func __ListeChaineeErreur($IDFuncError, $message)
    ;aucun traitement pour l'instant
    ConsoleWrite($message & Chr(10) & Chr(13))
    Return 0
EndFunc   ;==>__ListeChaineeErreur
Répondre