1

2

une recherche binaire/dichotomique? (->wikipedo)

3

Folco (./1) :
Ma question : que ferait un vrai programmeur expérimenté ?


Recherche binaire dans une table triée http://en.wikipedia.org/wiki/Binary_search (plus simple) et/ou table de hashage. http://en.wikipedia.org/wiki/Hash_function (plus compliqué)

4

Après faut voir si ça vaut le coup de se casser la tête à optimiser ça, tu auras probablement des hotspots plus critiques dans ton code... vu que ta liste d'instruction va être relativement courte et que chaque instruction n'utilise que quelques caractères, utiliser une table de hashage pour ça, ce serait comme écraser une puce avec une enclume, une recherche binaire suffira amplement AMHA.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

5

6

Folco (./5) :
En fait, j'ai très peur du résultat en vitesse, je ne suis pas aussi bon optimiseur que certains, loin s'en faut.
Bah, les TI 68K sont au moins aussi puissantes que les micro-ordinateurs des années 80, et puis tu codes en assembleur, tu devrais arriver à un résultat décent je crois smile
Folco (./5) :
+ de 110
Je considère pas ça comme une "grosse" table (même sur TI), d'autant plus que la recherche binaire est proportionnelle au logarithme du nombre d'éléments. Si je ne me pas planté, tu t'en tires avec 7 comparaisons de chaînes dans le pire des cas. Et jusqu'à 8 caractères, une comparaison de chaînes se réduit à 2 comparaisons d'entiers 32 bits, au pire. Ça fait donc 14 comparaisons dans le pire des cas.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

7

Pareil, moi je ferais une recherche dichotomique si c'est pas critique en vitesse (c'est ce que fait GTC), mais si je voulais vraiment optimiser j'utiliserais une fonction de hash parfaite ^^

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

8

9

10

C'est pour faire quoi? c'est sur pc ou sur TI?
Tout ce qui passe pas par le port 80, c'est de la triche.

11

12

Folco (./9) :
Ouep, mais rien ne dit que les chaines soient bien alignées, donc faut d'abord le faire etc...
Ah ouais pardon, j'avais oublié l'histoire de l'alignement sur 68K... je suis dans ma phase "assembleur x86" en ce moment ^^
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

13

attention Sur un x86, les accès non alignés sont permis, mais sur la plupart des x86 récents, ils rament!
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

14

Bien sûr (c'est même marqué dans la doc constructeur), mais c'est pas limité au x86 récents, ni aux x86 tout court d'ailleurs. À cause de l'organisation des bus et des caches, il est toujours recommandé d'aligner les données.

(Cependant, quand on ne peut pas le faire, j'avais déjà testé : apparemment au niveau perf ça reste plus intéressant de faire des accès 32 bits non alignés que de les décomposer en accès plus petits)
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

15

normal, quand tu fais un accès non aligné, il fait en hard ce que tu fais en soft avec des accès multiples.

16

Oui, c'est ce que je m'étais dit aussi, mais sur les procs "modernes" tu as parfois des surprises vu la complexité des sous-systèmes et leurs interactions.
(par ex. j'avais optimisé une routine assembleur de 2 façons différentes, et constaté que l'une était plus rapide que l'autre sur P3, mais plus lente sur Athlon...
de la même façon, certaines instructions de calcul sont devenues tellement rapides qu'utiliser des tables précalc peut devenir un inconvénient, même quand elles tiennent dans le cache)
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

17

ah oui c'est un vrai casse tête, les cycles nécessaires aux instructions sont différents sur chaque modèle smile

18

Pour les recherche dans des dictionnaires il existe les arbres binaire avec un jolie nom (mais je m'en souvient plus)... c'est pas mal quand le nombre de mots est élevé devant la taille de l'alphabet: (pour de très grand dictionnaire on part sur des tables de hachage)

à chaque noeud tu as une lettre si la lettre est bonne tu passe a la suivante et tu vas sur le fils droit sinon tu continue sur le fils gauche et tu signal chaque fin de mots ainsi codé par un point

exemple avec le dictionnaire: add abc mul mult


a->b->c->.
|  |->d->d->.
|->m->u->l->.
            |->t->.


mais dans ton cas la taille du dictionnaire est du même ordre de grandeur que ton alphabet... donc cette algo ne donnera pas forcement de bon résultat.

Dans ton cas une table (sous forme de tableau ici) de hashage puis recherche dichotomique peut être plus intéressant la plus part des mots fait quatre lettres donc un hachage sur 32 bit peut très bien être l'identité...

Le cas général c'est une table avec les hachages qui référence plusieur tables avec les résultat qui corresponde au hachage.( ces sous-tables peuvent être un tableau classé, abre,nouvelle table de hachage,...)

En optimisant un peut pour le 68k descendre à 16 bits peut être sympa.... 4 caractères dans un alphabet de taille 26 ça doit pouvoir se faire sans les collisions: plusieures clé (ici les mots de ton dictionnaire) qui donne un même hachage et ça évite les cas particulier(sous table) à traiter après.


si tu appels H ta fonction de Hachage
si tu prend un cas simple: on dit que H(x1 x2 x3 x4) renvoie x1. on obtient:
(tu as une colision avec abcd / add et mul mult)

a->abcd->add
m->mult->mult

donc un cout: en une recherche dicotomique: log(26) comparaison/saut
puis recherhe linaire qui vaut 4² comparaison/saut

si tu prend H(x1,x2,x3,x4)=x1+26*x2+26²*x3+...
tu obtiens le resultat en une seul recherche dichotomique: peu (pas?)de collision.

le cout est globalement en log(264) mais ton hachages te coutes 4 multiliplications/additions....

Mais globalement le principe est là à toi de voir ce qu'il vaut mieux choisir pour avoir le meilleur cout (et celui en développement aussi)



[URL=http://perso.ffwill.homelinux.com/TI89.html]Assembleur TI-89 en Ti-basic [/URL]

19

la longueur des chaines est variable, donc il faudra la stocker.

je pense que t'as pris la meilleure voie martial, stocker une liste par lettre me semble le plus rapide, surtout que tu codes en asm et pas en C.

ça revient à une "table de hachage" non équilibrée. la plus longue sous-liste a combien d'opcodes?

NB: pour aller encore plus vite tu peux facilement faire une recherche dichotomique sur la 2e lettre de l'opcode

ie

etape 1 utiliser une table d'offset pour trouver direct la première entrée pour la première lettre
etape 2 utiliser une recherche dichotomique (comme dans un agenda) sur la 2e lettre
etape 3 scanner ce qui reste smile

c'est à mon avis
-le plus simple, et le moins casse tête
-le plus compact, t'as juste besoin d'une table d'offset en plus de la liste des opcodes (mysql et oracle font pas mieux trioui)
-pas du tout dégueu en performances

Bonne explication: http://www.asp-php.net/tutorial/divers/dichotomie.php

20

squalyl (./19) :
je pense que t'as pris la meilleure voie martial, stocker une liste par lettre me semble le plus rapide, surtout que tu codes en asm et pas en C.

Je crois qu'un hash serait plus efficace, là il va se retrouver avec plein d'entrées vides qui prennent de la mémoire sans accélérer beaucoup pour autant.

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

21

ça fait 26 .dword hein grin

mais de toute j'ai aucun doute que ce topic va finir en bataille hash ou pas hehe

22

Sa solution de départ me paraît vraiment pas mal. Les instructions ASM sont courtes. Faire une table de saut pour les deux premières lettres ne prendrait que 6,5 ko et serait très rapide (passées les deux premières lettres d'une instruction, il ne reste vraiment plus beaucoup de possibilités à parcourir avec une recherche linéaire).

Pour la première lettre, la table prendrait 'z'-'A'=122-65 = 57 octets.
Pour la seconde lettre, la table prendrait 57x(57x4) = 12,7 ko.


On peut descendre à 6,5 ko en faisant une table de sauts relatifs. Ce n'est rien, même si l'assembleur est amené à fonctionner sur TI (en ROM évidemment, grâce à PedROM). Tu aurais un truc simple et rapide.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

23

y'a pas tant d'entrées (110), un index des premières lettres suffit largement, moi j'estime ça à 26*4 = 104 octets, car on se fiche des majuscules pour les opcodes asm.

24

Oui mais on perd du temps à changer la casse.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

25

genre grin

sachant que
0x41<=majuscule<=0x5a
0x61<=minuscule<=0x7a,

0x41 = 0b0100 0001
il suffit de tester le bit 6 et de le mettre à zéro si il est à un grin

et même, un and avec 0x1011 1110 = 0xbe suffit à passer tout le monde en uppercase et un or avec 0x40 suffit à passer tout le monde en lowercase grin

26

OK ! Je ne savais pas. Ma solution (qui est celle de Martial) passe donc à 1,3 ko smile
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

27

on va te lui faire un de ces trucs aux petits oignons à force tripo

28

29

Folco (./28) :
J'ai pensé à un truc, je vais peut-être lire un longword comme un bourrin, et intercepter l'adress error pour lire byte+word+byte au cas où ^^

Address Error ne peut pas être intercepté de manière fiable, c'est une non-continuable exception.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

30

Folco : En relatif il n'y a non seulement aucun relogement, mais il n'y a pas non-plus d'espace occupé en RAM, grâce à PedROM wink
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.