Discussion :

[ScannerTahiti]

Bonjour,
J'ose à peine poster ici, tant mes connaissances autodidactes sont très spécifiques et je devrais lire vos réponses avec un lexique..
Je code dans un dérivé de C# ( mql4 orientation financière). Je code un prog depuis presque un an qui doit faire dans les 7000 lignes ajd, et je commence à être plus à l'aise.

J'avais besoin de faire des tris dans les listes et j'ai imaginé le moyen ci-après.
Je le trouve efficace mais il me parait simple alors je souhaiterais comparer avec ce qui existe déjà si possible.

Ma question, : "quels autres moyens existent pour vous ?".

- Dans mon cas, au plus une trentaine de données maximum seront à comparer pour chaque blocs.

exemple :

- prenons trois candidats A,B,C. disons que A>B; A>C; C > B.
- chaque fois que l'un est supérieur à l'autre, j'incrémente son compteur de 1.

if A>A; A=+1 else A=+0 >> donc A=+0
if A>B; A=+1 else A=+0 >> A=0+1
if A>C; A=+1 else A=+0 >> A=0+1+1 >>> A=2

if B>A; B=+1 else B=+0 >> B=+0
if B>B; B=+1 else B=+0 >> B=+0+0
if B>C; B=+1 else B=+0 >> B=+0+0+0 >>> B=0

if C>A; C=+1 else C=+0 >> C=+0
if C>B; C=+1 else C=+0 >> C=+0+1
if C>C; C=+1 else C=+0 >> C=+0+1+0 >>> C=1

Ceci étant fait avec une boucle For.
Pour trouver le 1er, nous savons que cela correspond au TotalCandidat-1

(Totalcandidat-1) = ici 2 donc A est 1er
(Totalcandidat-2) = ici 1 donc C est 2eme
(Totalcandidat-max) = ici 0 donc B est 3eme et dernier.


Je suis sûr que c'est simplissime pour la plupart d'entre vous et je m'en excuse,
je cherche juste à connaître ce qui existe avant car en réalité, dans ce que j'ai pu voir des codes dans les forum de trading,
je n'ai jamais trouvé d'exemple de tri pour arbitrage..c'est assez lapidaire..

Bref, merci d'avance pour ceux qui m'ont lu jusque là et vraiment désolé si cela vous pourrait élémentaire..

Daniel

[prgasp77]

Bonjour,

le tri est un exercice classique d'algorithmie, si bien que de beaux algos tout fait existent déjà, et que de belles implémentations pullulent sur le net. Il existe des tris à la fois plus simple et plus efficaces que le tiens. Dans ton cas, tu compares deux à deux chacun de tes éléments, puis tu fais une recherche ; c'est vraiment très lent.

Pour un petit nombre d'éléments (30 est petit, jusqu'à cent on va dire que c'est petit), je conseille le tri par insertion. Si tu devais dépasser la centaine, un tri rapide serait conseillé (en réalité, le pivot est 16, mais tout de même, pour de petits nombres le tri par insertion est plus simple, surtout pour un débutant).

Le principe du tri par insertion est qu'il est facile d'insérer un élément dans une liste déjà triée. Donc on insère le premier élément dans une liste vide, puis le second dans une liste triée d'un élément, puis le troisième dans une liste triée de deux éléments ...

Plus d'info sur Wikipedia ou les Numerical Recipies.

Edit : la bibliothèque standard de ton machin dérivé de C# n'a pas un conteneur (liste, vecteur, ...) qui se trie toute seule ?

Cdlt,

[kwariz]

Bonjour,

l'algorithme que tu décris est un peu maladroit dans sa formulation en ce sens que dans une ligne comme if A>B; A=+1 else A=+0 >> A=0+1 le A avant le ; n'est pas le même que celui utilisé après, et on comprend que tu cherche à incrémenter un compteur asscocié à A.
Cependant ta démarche reste claire.
La première étape est qu'à chaque cellule d'un tableau A à trier on associe une cellule d'autre tableau C de même longueur qui va, pour un indice i, contenir le nombre d'éléments de A qui sont strictement plus grand.
Dans la seconde étape tu construis le tableau trié T à partir de C en trouvant les cellules de A ayant le plus de nombre de cellule à valeur supérieure.

Si on formalise sous une autre forme on pourrait obtenir un algorithme comme :

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
procedure Tahitri( input A: array ; output T: array )
local var
  C: array[ 1 .. A.length ]
begin
  // La première phase construction du tableau C, on le suppose remplit de 0 au départ
  // pour chaque i on aura C[i]=nombre de valeur dans A qui sont strictement plus 
  // grandes que A[i]
  for i=1 to A.length do // i est l'indice de la cellule pour laquelle on compte le nombre
                          // de valeurs strictement supérieures
    for j=1 to A.length do // j parcours A pour trouver ces valeurs
      if A[j]>A[i] then
        C[i] = C[i] + 1;
      end if
    end for
  end for
 
  // Seconde étape : on utilise les valeurs de C pour construire T le tableau trié
  // Ici je modifie ton idée d'algorithme pour l'adapter à des tableaux pouvant contenir
  // des valeurs non uniques
  i=1 // i sera l'indice de la prochaine cellule de T a être remplie
  for rang=A.length downto 1 do // toutes les valeurs possibles de rang
    for j=1 to A.length do // pour parcourir  C
      if C[j]=rang then 
        T[i]=A[j]
        i = i+1
      end if
    end for
  end for
 
  // Ici T est la version triée du tableau A
end

Dans la faune des algorithmes de tris on distingue plusieurs catégories. Ceux qui à un moment donné comparent les éléments du tableau entre eux et ceux qui ne le font pas. Le tien compare dans la première partie les éléments de A entre eux (ligne 11), mais pas du tout dans la seconde.
Pour rester un peu cohérent nous allons essayer de comparer l'efficacité de ton algorithme avec les algorithmes classiques de tri par comparaisons. Nous allons estimer le nombre de comparaisons entre éléments dans la première partie plus le nombre de comparaisons dans la seconde en fonction de la taille du tableau à trier. On va noter n=A.length pour simplifier l'écriture.

La première partie contient deux boucles chacune allant de 1 à A.length, la longueur du tableau. Il y aura donc n² comparaisons. Pour la même raison il y a aussi n² comparaisons dans la seconde partie.
Dans le jargon on parle d'un algorithme de tri en O(n²). En général ces algorithmes n'offrent pas de bonne performances pour de grands tableau (cf post de prgasp77). Ton algorithme à une complexité similaire au tri par sélection (celui qu'on utilise naturellement pour trier des cartes).

On peut évidemment lui apporter de petites modifications, comme par exemple dans la première phase en ne parcourant dans la seconde boucle que les éléments situé après celui d'indice i en testant aussi le cas inférieur. Dans la seconde phase on peut s'arrêter dès que i vaut A.length (signe qu'on a tout traité). Mais cela ne change pas le comportement global de l'algorithme. On pourra remarquer que ton algorithme est stable aussi.

Néanmoins, si tu n'as jamais qu'à arbitrer 3 valeurs comme dans ton exemple, ton algorithme donnera de bons résultats en le mettant un peu à plat ... il battra sans sourciller quicksort, mergesort et les autres grosses pointures.

Comme te le conseille prgasp, wikipedia donne un bon aperçu des différents tris existant, même si personnellement je lui préfère sa version en anglais.

[ScannerTahiti]

Bonjour,
Dans ton cas, tu compares deux à deux chacun de tes éléments, puis tu fais une recherche ; c'est vraiment très lent...

Edit : la bibliothèque standard de ton machin dérivé de C# n'a pas un conteneur (liste, vecteur, ...) qui se trie toute seule ?

Cdlt,

Hé, Merci d'avoir répondu,

Alors côté biblio, non ; ni liste, ni vecteur, ni même possibilité directe ( à ma connaissance) de pouvoir faire des chaines listées ( http://docs.mql4.com/)
par contre , ce programme Russe pour le Forex est le N°1 Mondial .

Ensuite pour la lenteur, étant donné que je mets ça en Array, après la boucle For, je retrouve directement la position de chacun puisque c'est leur référence, donc ça va vite.

Je vais chercher effectivement cette méthode par insertion, si cela ne nécessite pas de listes chaînées par contre.

merci en tous cas

[kwariz]

ArraySort pourrait t'être utile.

[ScannerTahiti]

ArraySort pourrait t'être utile.

Malheureusement non parce que les positions relatives, référence des Arrays, changent avec, hors A doit rester data[0], B data[1] et C data[2] puisqu'elles connues dans cet ordre tout le long.

Merci, je regarde ton dernier post et les wikipedia.

[kwariz]

Donc ce cas ton problème est plus de trouver la permutation qui appliquée à ton tableau donne un tableau trié.
Pour l'obtenir c'est relativement simple. Si ton tableau contenant les données est nommé data, et que la permutation cherchée est un tableau nommé P (de même taille que data) alors:

• tu commences par initialiser P[i]=i
• tu tries avec n'importe quel algorithme de tri en changeant :
  
  • les comparaisons data[i] > data[j] en data[ P[i] ] > data[ P[j] ] => on n'accède aux données uniquement via la permutation
  • les modifications swap(data[i], data[j]) en swap(P[i], P[j]) => on modifie la permutation et jamais le tableau initial
• Après ça, P[i] va contenir l'indice qu'aurait data[i] dans un tableau trié.

À toi de choisir l'algorithme de tri le plus adapté à ta situation et tes données.