Methode de comparaison et de Tri

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

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,

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:

---

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.

Citation:

---

Envoyé par prgasp77

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 :)

ArraySort pourrait t'être utile.

Citation:

---

Envoyé par kwariz

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.

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.

Citation:

---

Envoyé par kwariz

Donc ce cas ton problème est plus de trouver la permutation ...À toi de choisir l'algorithme de tri le plus adapté à ta situation et tes données.

---

En fait j'ai déjà une solution que je trouve plus simple et je n'ai pas besoin de permutation car je connais déjà les rangs de ceux que je recherche.
En effet j'ai des "candidats" et un nombre de place dispo. donc pour 10 candidats et 4 place dispo, les 4 premiers sont mes choix et ils occuperont par définition < totalcandidat dispo -1, -2 ,-3,-4).
En dehors du contexte c'est pas évident à appréhender c'est vrai.
Il s'agit en l'occurence, de Symbols sur le Forex ( paire EURUSD, GBPJPY..), qui doivent présenter certains critères pour devenir des candidats prêts à trader.
Mais quand plusieurs le sont en même temps et que la capacité financière du compte ne permet d'en prendre qu'une partie, il s'agit de choisir celui qui offre le plus de potentiel.
Voilà le code que j'ai imaginé et pour lequel je me demandais en fait , quelles étaient les solutions habituellement pratiquées, si il en existaient de plus simples.
Dernière précisions : d'une part il y a rarement plus de 10 candidats à la fois, parmis 30 symbols (i), 20 SetUps (s) et 2 sens achat-vente (t), ensuite, cet algo n'est lancé qu'une fois par heure, on est pas dans la micro-seconde.. :)

Code:

---

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

//. //>F77E.ArbitrageCandidat() // Pour reprendre l'exemple A,B,C; considérons qu'il y a 3 candidats sélectionnés pour le trading=aiNbreCandidat, et seulement 2 places disponibles=aiPlaceDispo. // CI-DESSOUS listes des Variables renseignées par fonctions précédentes //atb.CandidSetUp[i][s][t] = Boolean , si oui ou non, le Symbol du Forex [i] dans le contexte [s][t] a été validé "prêt à lancer un trade". //aiNbreCandidat = entier , nombre de candidats au trade ; //aiPlaceDispo = entier , nombre de trades possible en fonction parametres initiaux; //atd.RRCandid[i][s][t] = décimale, valeur d'un ratio risk Reward;   void F77E.ArbitrageCandidat() {//a   int ati.BestRR[][qi.SetUp][2]; ArrayResize(ati.BestRR,aqi.SB);ArrayInitialize(ati.BestRR,0); //ati.BestRR : entier, pour cumul point chaque meilleur RR   for(int i=0;i<aqi.SB;i++) //aqi.SB =nombre Symbol listé {//b for(int j=0;j<aqi.SB;j++) {//c for(int s=0;s<qi.SetUp;s++) //qi.SetUp = nombre de SetUp testé {//d for(int t=0;t<2;t++) {//e if(atb.CandidSetUp[i][s][t]==true && atb.CandidSetUp[j][s][t]=true)// chaque fois qu'un Symbol i & j sont candidats {//f if(atd.RRCandid[i][s][t]>atd.RRCandid[j][s][t] ) // si le ratio de i est supérieur à celui de j {//g ati.BestRR[i][s][t]++; //son cumul de point est incrémenté de 1 }//gz }//fz }//ez }//dz }//cz }//bz for(i=0;i<aqi.SB;i++) {//h for(s=0;s<qi.SetUp;s++) {//i for(t=0;t<2;t++) {//j for(int x=1;x<=aiPlaceDispo;x++) {//k if(ati.BestRR[i][s][t] ==aiNbreCandidat-x) {Alert("le ",x,sp,"est: ",ats.SB[i],sp,"avec: " atd.RRCandid[i][s][t]);}//sp pour space }//kz }//jz }//iz }//hz   if(Fbug==1){F04_Bug("F77E.ArbitrageCandidat");} }//az //<\_END_F77E.ArbitrageCandidat()__________________________________________________________________________________________________________________________________________________

---

Bien sûr dans le code réel, le message d'alerte est remplacé par les fonctions d'éxecution des trades "vainqueurs".

Donc , pour en finir :

- voyez-vous un système plus sobre, rapide ou solide ?
- sinon, y voyez vous des failles ?

Merci en tous cas , c'est sympa de trouver des professionnels qui nous renvoient pas jouer au billes.. :ccool:

J'ai appris que vous avez pléthore de soleil ces jours-ci, donc pas la peine que je vous en envoie de chez moi 8-)

Bonjour Messieursss ,

J'ai travaillé sur vos posts ( très lent à bosser, ça mouline dans mon sommeil..),

@prgasp77
j'ai regardé sur wiki le tri par insertion (et du coup j'ai découvert un peu les autres). Ce qu'il y a de sûr c'est que ce n'est pas plus simple.
Par contre, vous n'aviez pas connaissance de mes exacts besoins, donc je comprend vos conseils à ce niveau.
En réalité, si j'ai effectivement "30 concurrents", dans la grande majorité, moins de 10 d'entre eux sont sélectionnés pour être candidats, et enfin, seulement les 2 ou 3 premiers seront choisis, voire seulement le 1er (plus simple auquel cas), donc c'est pourquoi je n'ai pas besoin de mouliner la liste qu'une fois et que je connais d'emblée la ref tableau de chacun.

D'ailleurs je vais ajouter peut-être un if d'abord du style :
"si besoin 1 seul vainqueur" alors "max (liste);
comme ça devrait arriver la moitié du temps, ça sortirait tout de suite...

En disant cela , cela me fait penser à une autre façon, je me dis que dans mon cas, avec seulement 1 à 4 vainqueur max, je pourrais peut-être procéder par élimination en n'utilisant que la fonction Max dans le style :
1er= max(liste); 2eme=max(list-1er) ; 3eme=max(list-1er-2eme) ....
Merci pour les wiki, je n'y avais même pas penser, mais bon, j'ai du mal avec leur codif :(

@kwariz : Alors même chose que pour PrgGasp, d'une part je n'ai pas besoin de retravailler sur la totalité de la liste triée (pour ce qui est de la rapidité ) et cette incrémentation me donne la ref Array de chacun des candidats triés du coup. le dernier étant à la [0] et le dernier à la [total candidat-1] etc.. donc tout travail sur une seconde liste est inutile, enfin je pense, je n'ai pas encore testé :(
Par contre, je vais modifier en appliquant vos conseils pour optimiser et supprimer les comparaisons inutiles (...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é) .

Pour en finir, avec un dernier conseil, ne pensez-vous pas que l'idée que je viens d'avoir ici, en travaillant avec l'exclusion du maxi de listes successives dégraissées, ne serait pas plus concise en raison des faibles volumes ?

Avec mes remerciements

Bonjour,

je ne vois pas bien l'intérêt d'utiliser ton algorithme sachant qu'il semble déjà exister un algorithme de tri natif :
http://docs.mql4.com/array/ArraySort

Tu es en train de commettre une erreur classique des débutants en programmation. Il s'agit de l'anti-pattern "réinventer la roue carrée". Je t'invite à lire cette page :
http://fr.wikipedia.org/wiki/Antipattern

Cela t'amène à proposer des solutions extrêmement contre-productives comme utiliser la fonction max sur des successions de sous-tableaux. Je ne pense pas qu'il existe pire solution.

Pour battre les algorithmes de tri classiques, il faut coder en dur des arbres de décision pour des tailles de tableaux fixes. C'est à la fois beaucoup plus efficace et beaucoup plus clair que ta solution. Mais tenter de battre les algorithmes de tri sur des tableaux de petites tailles n'a pas grand intérêt car le nombre de fois qu'il faille trier de si petits tableaux pour que le gain devienne significatif par rapport aux autres instructions de ton programme me paraît irréaliste.

ArraySort() natif :
Pas bon dans mon cas, parce que les positions relatives, référence des Arrays, changent avec le tri, hors A doit rester data[0], B data[1] et C data[2] puisqu'elles connues dans cet ordre tout le long.



Ah Ah, j'ai regardé le wiki et en fait ça me fait plaisir car durant cet année, j'ai pratiquement commis une bonne partie des erreurs décrites, mais je me suis repris sur la plupart, en réécrivant, simplifiant , nettoyant..

Je vais bien les relire car on peut induire pas mal de choses de ces anti-patern..
merci