Sujet Précédent Sujet Suivant

[Concour] 5

cs_dragon Messages postés 2336 Date d'inscription samedi 14 juillet 2001 Statut Membre Dernière intervention 5 mai 2009 - 25 août 2004 à 18:05
cs_dragon Messages postés 2336 Date d'inscription samedi 14 juillet 2001 Statut Membre Dernière intervention 5 mai 2009 - 26 août 2004 à 14:24
faut mélanger puis trier le plus rapidement possible ceci
en plus, faut donner le temps écouler dans un msgbox à la fin pour combien de temps après le mélange et combien de temps après le trie

dim tableau(0 to 1000000) as long
dim i as integer
for i = 0 to 1000000
tableau(i) = i
next i
-------------------------------------------------
Dragon alias aussi Waxime mais bon, pas le gout de refaire un nouveau profil lol
-------------------------------------------------

13 réponses

Réponse 1 / 13
jrivet Messages postés 7392 Date d'inscription mercredi 23 avril 2003 Statut Membre Dernière intervention 6 avril 2012 60
25 août 2004 à 18:11
tu pourrai preciser un peu plus STP, car j comprend pas bien ce que tu veux ;)

Pour le temps ecouler je dirai:

dim a
a = GetTickCount
(le reste)
msgbox ("Le temps ecoule: " & gettickcount() - a & " ms")

J attend ta precision
;)

A+

:big)
0
Réponse 2 / 13
Zigarn Messages postés 106 Date d'inscription mardi 13 juillet 2004 Statut Membre Dernière intervention 26 janvier 2005
25 août 2004 à 18:19
pour le mélange : 
dim a as integer
dim b as integer
dim k as long
randomize
for i = 1 to 1000000
a = Int((1000000 * Rnd) + 1)
b = Int((1000000 * Rnd) + 1)
k = tableau(a)
tableau(a) = tableau(b)
tableau(b) = k
next i

+ un calcul de temps et ensuite un petit quicksort dont j'ai plus l'algo en tête et je dois y aller ...
A demain.

-------------------------------------------------
Débutant ... mais pas pour longtemps !
0
Réponse 3 / 13
cs_dragon Messages postés 2336 Date d'inscription samedi 14 juillet 2001 Statut Membre Dernière intervention 5 mai 2009 6
25 août 2004 à 19:09
bon oki, je recommence la question

faut mélanger ceci
dim tableau(0 to 1000000) as long
dim i as long
for i = 0 to 1000000
tableau(i) = i
next i

attention, faut mélanger ce tableau là, pas insérer de nouvelle donnée

ensuite, faut prendre le tableau mélanger puis le remettre en ordre
-------------------------------------------------
Dragon alias aussi Waxime mais bon, pas le gout de refaire un nouveau profil lol
-------------------------------------------------
0
Réponse 4 / 13
cs_CanisLupus Messages postés 3757 Date d'inscription mardi 23 septembre 2003 Statut Membre Dernière intervention 13 mars 2006 21
25 août 2004 à 22:03
Ben vala, après diner g toujours les idées + claires donc je te proposes ce code pas pompé nulle part, à part l'algo de tri que g adapté d'une vieille source en C : 

Private Sub Form_Load()
Dim tableau(0 To 1000000) As Long
Dim i As Long
Dim t0 As Date, t1 As Date, t2 As Date
Dim a As Long, b As Long, k As Long

' Remplisage du tableau d'origineFor i 0 To 1000000: tableau(i) i: Next

t0 = Time

' Foutage de bordel dans le tableau
Randomize Time

For i = LBound(tableau) To UBound(tableau)
a = Int(((UBound(tableau) - LBound(tableau) + 1) * Rnd) + LBound(tableau))
b = Int(((UBound(tableau) - LBound(tableau) + 1) * Rnd) + LBound(tableau))
k = tableau(a)
tableau(a) = tableau(b)
tableau(b) = k
Next i

t1 = Time

' Tri du tableau
TriSeparation tableau, LBound(tableau), UBound(tableau)

t2 = Time
MsgBox "Temps mélange " & Format((t1 - t0), "hh:mm:ss") & vbCrLf & "Temps tri " & Format((t2 - t1), "hh:mm:ss")

End Sub

' Ca, ca s'appelle du tri par séparation (si quelqu'un a mieux...)
Sub TriSeparation(tbl, deb As Long, fin As Long)
Dim a As Long, b As Long, pivot As Long
    pivot tbl(deb): a deb: b = fin
  
  Do While a < b
    
    Do While tbl(b) > pivot: b = b - 1: Loop
    
    If a <> b Then
      tbl(a) = tbl(b)
      tbl(b) = pivot
      a = a + 1
    End If
    
    Do While tbl(a) < pivot: a = a + 1: Loop
    
    If a <> b Then
      tbl(b) = tbl(a)
      tbl(a) = pivot
      b = b - 1
    End If
    
  Loop
  
  If deb < a - 1 Then TriSeparation tbl, deb, a - 1
  If fin > a + 1 Then TriSeparation tbl, a + 1, fin
  
End Sub


G testé sur une machine équipée d'un Celeron 700 MHZ/256Mo de RAM, sous Win98 SE avec VB6.0.

Temps d'exec :En debug : mélange 3s, tri 33s (en moyenne)En compilé : mélange 2s, tri 18s (en moyenne)

je précise que le test a été fait avec 1 session Explorer + 2 session IE + 1 session VB6 + Outlook dans la barre de tâches et 2/3 autres trucs mais qui ne bouffent pas de mémoire.

Cordialement, CanisLupus

Tous les glands ne deviennent pas des chênes mais tous les chênes ont été des glands
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 13
cs_dragon Messages postés 2336 Date d'inscription samedi 14 juillet 2001 Statut Membre Dernière intervention 5 mai 2009 6
25 août 2004 à 22:14
Excellent, tout ceux qui posterons, je teste sur mon ordi avec rien d'ouvert dessus

HP d530 SFF(DJ698S)
Intel(R) Pentium
(R) 4 CPU 2.40Hz
AT/AT Compatible
261,616 Ko de RAM

carte graphique
Nvidia Dualview
Nvidia Quadro NVS

ton score est de
temp mélange = 00:00:01
temp tri = 00:00:11
temp total = 00:00:12

c'est juste domage qu'on peut pas avoir les mili-secondes
-------------------------------------------------
Dragon alias aussi Waxime mais bon, pas le gout de refaire un nouveau profil lol
-------------------------------------------------
0
Réponse 6 / 13
cs_dragon Messages postés 2336 Date d'inscription samedi 14 juillet 2001 Statut Membre Dernière intervention 5 mai 2009 6
25 août 2004 à 22:26
avec des mini modification de ton code, j'ai pus sauvé 1 seconde pendant le mélange

temp mélange = 00:00:00
temp tri = 00:00:11
temp total = 00:00:11 

Private Sub Form_Load()
    Dim tableau(0 To 1000000) As Long
    Dim i As Long
    Dim t0 As Date, t1 As Date, t2 As Date
    Dim a As Long, b As Long, k As Long
    Dim rndTemp As Long
    
    ' Remplisage du tableau d'origine    For i 0 To 1000000: tableau(i) i: Next
    
    t0 = Now
    
    ' Foutage de bordel dans le tableau
    Randomize
    
    For i = 0 To 1000000
        rndTemp = Int(Rnd * 1000000)
        k = tableau(i)
        tableau(i) = tableau(rndTemp)
        tableau(rndTemp) = k
    Next i
    
    t1 = Now
    
    ' Tri du tableau
    TriSeparation tableau, 0, 1000000
    
    t2 = Now
        MsgBox "Temps mélange " & Format((t1 - t0), "hh:mm:ss") & vbCrLf & "Temps tri " & Format((t2 - t1), "hh:mm:ss") & vbCrLf & "Temps total = " & Format((t2 - t0), "hh:mm:ss")

End Sub

' Ca, ca s'appelle du tri par séparation (si quelqu'un a mieux...)
Sub TriSeparation(tbl, deb As Long, fin As Long)
    Dim a As Long, b As Long, pivot As Long
        pivot tbl(deb): a deb: b = fin
    
    Do While a < b
        Do While tbl(b) > pivot: b = b - 1: Loop
        
            If a <> b Then
                tbl(a) = tbl(b)
                tbl(b) = pivot
                a = a + 1
            End If
        Do While tbl(a) < pivot: a = a + 1: Loop
        If a <> b Then
            tbl(b) = tbl(a)
            tbl(a) = pivot
            b = b - 1
        End If
    Loop
    
    If deb < a - 1 Then TriSeparation tbl, deb, a - 1
    If fin > a + 1 Then TriSeparation tbl, a + 1, fin
End Sub


Qui sera le suivant ??? il reste encore pliens d'algo, surtout de tri
Le tri que tu as fait, c'est un QuickSort non ??? me souviens pus, trop loin dans ma mémoire les sort de malade lol
-------------------------------------------------
Dragon alias aussi Waxime mais bon, pas le gout de refaire un nouveau profil lol
-------------------------------------------------
0
Réponse 7 / 13
cs_CanisLupus Messages postés 3757 Date d'inscription mardi 23 septembre 2003 Statut Membre Dernière intervention 13 mars 2006 21
25 août 2004 à 23:02
Ben, pour ce qui est des algo de tri de tableaux, je me suis arrêté à celui-là car, en C en tous cas, il m'a parut le plus rapide avec une perf à peu près égale de n * log(n). On appelle ça aussi (improprement) le tri rapide (ou QuickSort) qui est trop inégal en perf et peut atteindre n^2 au pire (comme le tri séquentiel).
Maintenant, c qu'une adaptation en vb6. Il y a sans doute mieux. Certains langages (autres que C) ont des fonctions de tri de tableaux prédéfinies comme asort. En .NET, je ne sais pas encore.

Avec VB6, g même pensé à des trucs de malades, mais bon faut tester, comme me servir d'une table access avec un order by en SQL, et à des controles genre listbox en utilisant leur méthode sort, .... g pas trouvé mieux que ma soluce.

J'attends avec impatience une solution + rapide que celle que g proposé.

Pour les millisecondes, g essayé gettickcount et ça ralenti plutôt qu'autre chose.

Quoique, un tableau dimensionné à 1000001 d'éléments est-ce bien raisonnable ? Lol !

Cordialement, CanisLupus

Tous les glands ne deviennent pas des chênes mais tous les chênes ont été des glands
0
Réponse 8 / 13
cs_CanisLupus Messages postés 3757 Date d'inscription mardi 23 septembre 2003 Statut Membre Dernière intervention 13 mars 2006 21
25 août 2004 à 23:08
D'autre part, je suis ok avec ta "mini modif" à condition que le tableau commence par 0. Sinon, problème.

Cordialement, CanisLupus

Tous les glands ne deviennent pas des chênes mais tous les chênes ont été des glands
0
Réponse 9 / 13
cs_dragon Messages postés 2336 Date d'inscription samedi 14 juillet 2001 Statut Membre Dernière intervention 5 mai 2009 6
25 août 2004 à 23:25
moi qui a fait la question, pas pour rien j,ai parti de 0, masi en .Net, on par toujours à 0

pour la grandeur de tableau, c,est pour une autre concour, sauf ce coup ci, avec 11 item :-P

le résultat serait totallement différent, puisque certain tri sont très rapide, masi quand il y a beaucoup d,item et d'autre rapide, seulement qu'en il y en a pas beaucoup
-------------------------------------------------
Dragon alias aussi Waxime mais bon, pas le gout de refaire un nouveau profil lol
-------------------------------------------------
0
Réponse 10 / 13
Zigarn Messages postés 106 Date d'inscription mardi 13 juillet 2004 Statut Membre Dernière intervention 26 janvier 2005
26 août 2004 à 12:23
Voilà quelques algos de tri, mais ils seront toujours moins performants que le tri rapide qui est celui avec la complexité moyenne la plus petite possible. 

Sub TriBulle(Tableau() As Long)
  Dim i, n, k As Long
  Dim ok As Boolean
  
  n = UBound(Tableau)
  
  Do
    ok = True
    For i = 1 To n - 1
      If (Tableau(i - 1) > Tableau(i)) Then
        ok = False
        k = Tableau(i)
        Tableau(i) = Tableau(i - 1)
        Tableau(i - 1) = k
      End If
    Next i
  Loop While (Not ok)

End Sub

Sub TriSelection(Tableau() As Long)

  Dim i, j, n, k As Long

  n = UBound(Tableau)

  For i = 0 To n - 2
    For j = i + 1 To n - 1
      If (Tableau(j) < Tableau(i)) Then
        k = Tableau(i)
        Tableau(i) = Tableau(j)
        Tableau(j) = k
      End If
    Next j
  Next i

End Sub

Sub TriInsertion(Tableau() As Long)

  Dim Pivot, i, n, Val As Long
  
  n = UBound(Tableau)
  
  For Pivot = 1 To n - 1
    i = Pivot - 1
    Val = Tableau(Pivot)
    Do While (i >= 0 And Tableau(i) > Val)
      Tableau(i + 1) = Tableau(i)
      i = i - 1
      If (i < 0) Then Exit Do
    Loop
    Tableau(i + 1) = Val
  Next Pivot

End Sub


-------------------------------------------------
Débutant ... mais pas pour longtemps !
0
Réponse 11 / 13
Zigarn Messages postés 106 Date d'inscription mardi 13 juillet 2004 Statut Membre Dernière intervention 26 janvier 2005
26 août 2004 à 12:29
Pour le mélange, on peut peut-être aussi faire : 
n = UBound(Tableau)
For i = 0 To Int(n/2)
a = Int(n * Rnd)
b = Int(n * Rnd)
k = tableau(a)
tableau(a) = tableau(b)
tableau(b) = k
Next i

Statistiquement tous les éléments ont été déplacé au moins une fois.
-------------------------------------------------
Débutant ... mais pas pour longtemps !
0
Réponse 12 / 13
Zigarn Messages postés 106 Date d'inscription mardi 13 juillet 2004 Statut Membre Dernière intervention 26 janvier 2005
26 août 2004 à 12:47
Au fait, pour avoir des tests de comparaison corrects, il faudrait faire les tris sur le même tableau mélangé !

-------------------------------------------------
Débutant ... mais pas pour longtemps !
0
Réponse 13 / 13
cs_dragon Messages postés 2336 Date d'inscription samedi 14 juillet 2001 Statut Membre Dernière intervention 5 mai 2009 6
26 août 2004 à 14:24
le but du concour, est de mélanger et de replacer le plus rapidement possible. Donc je te l'accord qu'un même tableau serait le mieux, mais puisqu'il faut mélanger dans la question
-------------------------------------------------
Dragon alias aussi Waxime mais bon, pas le gout de refaire un nouveau profil lol
-------------------------------------------------
0

Discussions similaires

pour le tierce quarte quinte
hyga -
13jean1 -

1 réponse
Les systèmes réducteurs
cs_cantador -
ATitus -

43 réponses
Organiser le desordre
TTMan -
Mindiell -

11 réponses
boucles imbriquées
cs_oolivierr -
Vb Lover -

10 réponses
STEP 5 - S5
xpmich -
chtitkoala59 -

5 réponses
Rejoignez-nous