17 janvier 2009

Recherche rapide - table de hachage - exemple simple

Voiçi un petit programme simple de double table de hachage: hashtable2.c  , il permet d'entrer des nom dans une table et de les retrouver.
Posté par InPhilly à 05:19 - - Commentaires [0] - Permalien [#]

16 janvier 2009

Reduire les collisions: Double et triple table de hachage

Optimiser la méthode: Si la probabilité P est d'avoir une collision à une adresse donnée, alors la probabilité d'avoir une autre collision à la même adresse est de PxP en supposant que les deux événements soient indépendants. En supposant que la probabilité d'une collision est de 10%, une deuxième collision aurait une probabilité de 0.1x0.1=1% et une troisième collision, une probabilité de 0.1x0.1x0.1=0.1% Donc en multipliant la table de hachage, il devrait être possible de limiter fortement la recherche linéaire. Le petit... [Lire la suite]
Posté par InPhilly à 02:11 - - Commentaires [0] - Permalien [#]
15 janvier 2009

Table de hachage - Limiter les collisions - Programme de test

Limiter les collisions: Le risque de collision est d'autant plus important que la table d'indexation est remplie.  En supposant que la fonction de hachage soit parfaite: les clés sont uniformément réparties. Alors la probabilité de collision est égale au taux de remplissage de la table d'index. Une table d'indexation remplie à 10% donnera 10% de risque de collision. Dimensionnement de la table d'index: Supposons que l'on ne veuille pas plus de 10% de collision; alors la table d'index devra pouvoir contenir 10 fois plus... [Lire la suite]
Posté par InPhilly à 00:01 - - Commentaires [0] - Permalien [#]
13 janvier 2009

ilog10 et ilog2 sans math.h

Voici comment calculer le logarithme d'un entier (integer) simplement et sans passer par la librairie mathématique: Le code source à télécharger: Logarithmes.c #include <stdlib.h>#include <stdio.h> /*retourne la puissance de 2 immediatement inferieureCe n'est pas la plus 'smart' des methodes, mais elle estfacile a comprendre. Max 32 interations en 32bits*/unsigned ilog2(unsigned x) {unsigned n;  n=-1;  while (x > 0) {    n++;    x=x>>1;  }  return n;} /*retourne... [Lire la suite]
Posté par InPhilly à 13:33 - - Commentaires [0] - Permalien [#]
12 janvier 2009

Table de hachage - indexation rapide

Une table de hachage est particulièrement interessante pour retrouver rapidement un enregistrement à partir d'une clé, la méthode est d'autant plus interessante que le nombre d'enregistrement est important. Wikipedia explique clairement la méthode employée. Comme je n'ai pas trouvé d'exemples simples pour expérimenter la méthode, alors je les ai créés. Premier exemple très simple (60 lignes), le code source: hashtableCe petit programme ne gère pas les collisions, mais permet de comprendre le principe de base. #include... [Lire la suite]
Posté par InPhilly à 04:57 - - Commentaires [0] - Permalien [#]
11 janvier 2009

Le calcul sur les entiers est-il plus rapide que sur les réels ?

Pour répondre à la question: Est-ce que les calculs simples (addition, soustraction, multiplication et division) sont plus rapides sur les entiers (integers) que sur les flottants (floats) ? J'ai écrit un petit programme en c speed.c  , il faudra le compiler avec gcc sans optimisation: gcc -o speed speed.cpuis lancer le programme 'speed' Le programme mesure successivement sur un entier long, un flottant simple et un flottant double le temps d'exécution d'une boucle de 1million d'itération. Il y a 8 boucles: a) une... [Lire la suite]
Posté par InPhilly à 03:45 - - Commentaires [0] - Permalien [#]

02 janvier 2009

Le message: "Running with --rebuild-tree is required"

Que faire si au Linux vous dit "Filesystem seems to have fatal corruptions... Running with --rebuild-tree is required" ? Ce message est apparu après une mise à jour de Ubuntu 7.10 vers Ubuntu 8.04 au redémarrage de l'ordinateur. Je n'en connais pas vraiment la cause, mais j'ai la solution pour réparer:  Attention elle s'applique à une partition formatée reiserfs. - Redémarrer l'ordinateur sur un live-cd (j'ai choisi Xubutuntu 8.10 mais peu importe).- Donner un mot de passe au 'root'  (aller dans... [Lire la suite]
Posté par InPhilly à 07:13 - - Commentaires [0] - Permalien [#]
01 janvier 2009

Quelques liens utiles pour découvrir Genie

Je corrige un oubli, si vous souhaitez plus d'info sur Genie, voici les liens: Découvrir les bases du langage: http://live.gnome.org/Genie Le journal de Jamie Mc Cracken (Developpeur de Genie): http://jamiemcc.livejournal.com/12009.html L'analyse de Barry Kauler (Developpeur de Puppylinux): http://puppylinux.com/genie/
Posté par InPhilly à 12:51 - - Commentaires [0] - Permalien [#]
31 décembre 2008

Vala évolue rapidement

Il suffit de jetter un coup d'oeil sur les 'releases' http://live.gnome.org/Vala/Release pour constater que Vala évolue vite. Aussitôt que j'aurai un peu plus de temps, j'écrirais un petit traducteur C# vers Vala pour faciliter le portage des applications développées en C#.
Posté par InPhilly à 17:47 - - Commentaires [0] - Permalien [#]
31 décembre 2008

Genie: Un langage de programmation simple et performant

Genie est un peu le cousin de Vala, il partage le même compilateur Valac et passe donc par l'intermédiaire du c qui est directement compilé en executable par gcc.  Genie comme Vala s'appuit sur les puissantes bibliothèques de Gnome GLib et GTK+ pour produire son code. L'avantage de Genie est d'offir une syntaxe plus épurée que Vala et qui s'apparente un peu à Python à cause de l'indentation qui est imposée. En terme de performance, il faut s'attendre à des résultats équivalents à Vala, c'est à dire au C + GLib et bien sûr... [Lire la suite]
Posté par InPhilly à 02:49 - - Commentaires [4] - Permalien [#]