Fonctions de Hash

Je ne me souviens plus bien quelle était la fonction de Hash utilisée dans ma HashTable mais je devrais bouquiner l'article suivant :

Un petit bout de code pour tester une fonction de hash qui minimise les collisions pour des adresses mémoires stockées dans une hash table. Avec cet exemple j'ai un taux d'occupation de ~1.4 pour 60000 pointeurs stockés, ce qui est très appréciable.

function    hash($n)
{
    $a = (($n >> 24) & 0xF) << 7;
    $b = (($n >> 16) & 0x3F) << 6;
    $c = (($n >> 8) & 0xFF) << 1;
    $d = $n & 0xFF;
    $d *= $d;
    return ($a+$b+$c+$d) & 0xFFFF;
}

$Counts = array();
$p = 0x81000000;        //Adresse mémoire de départ pour l'affectation des new...
for($i=0; $i<60000; $i++)       {
    $Hash = hash($p + $i*32 + rand(0, 24));
    if (!isset($Counts[$Hash]))     $Counts[$Hash] = 0;
    $Counts[$Hash]++;
}

$Total = 0;
foreach($Counts as $Index=>$Count)      $Total += $Count;
echo "Moyenne d'occupation (".count($Counts)." cellules occupées) : ".($Total / count($Counts))."<br/>\n\";

La fonction de hash adaptative

Si je veux stocker des pointeurs mémoires dans une hashtable (en table de correspondance ID<-->Pointeurs) j'aurais intérêt à analyser les pointeurs successivement renvoyés par new et à rendre la fonction de hash adaptative : elle se modifierait en fonction des adresses fournies par new. Une analyse des bits les plus fréquemment changeant ou fixes et hop !

Tout part d'une constatation évidente sur la construction d'un cube à partir de deux simples points 1D :

(-1), (1)

Pour passer à un carré (2D) et enfin au cube (3D) il suffit de réaliser deux produits tensoriel avec le vecteur (-1, 1) :

(-1, -1) (1, -1)
(-1, 1) (1, 1)

(-1, -1, -1) (1, -1, -1)
(-1, 1, -1) (1, 1, -1)
(-1, -1, 1) (1, -1, 1)
(-1, 1, 1) (1, 1, 1)

Et en suivant la même logique on arrive à un objet à 16 points 4D, un hypercube :

(-1, -1, -1, -1) (1, -1, -1, -1)
(-1, 1, -1, -1) (1, 1, -1, -1)
(-1, -1, 1, -1) (1, -1, 1, -1)
(-1, 1, 1, -1) (1, 1, 1, -1)
(-1, -1, -1, 1) (1, -1, -1, 1)
(-1, 1, -1, 1) (1, 1, -1, 1)
(-1, -1, 1, 1) (1, -1, 1, 1)
(-1, 1, 1, 1) (1, 1, 1, 1)

Le but est maintenant de trouver comment projeter ces 16 points 4D en 3 dimensions pour le rendre sur un simple écran.

Programmation LUA

Expressions régulières

Une compilation de conseils et d'exemples sur les expressions régulières. Histoire de ne pas avoir de multiples sources de renseignements pour des choses simples et qui reviennent souvent. �videmment, ces regex d'exemples et ces conseils sont initialement tirés de ce site pour montrer qu'ils sont utilisables directement.

global  $TabWidth, $Tabs, $TabLengths;
    $Tabs = array();    $TabLengths = array();
    for($j=0; $j<=$TabWidth; $j++)      $TabLengths[$j] = strlen($Tabs[$j] = $j ? ($Tabs[$j-1])."&nbsp;" : "");
    $Ln = strlen($snip);
    $Computed = 0;
    foreach(array(true, false) as $ComputeWidth)        {
        $PosInLine = 0;
        $i = 0;
        while ($i<$Ln)      {
            $c = $snip[$i++];
            if ($c == "\n")         $PosInLine = -1;
            if ($c != "\t")     {   $PosInLine++;   continue;   }
            //On étend les tabs
            $RealWidth = $TabWidth - $PosInLine%$TabWidth;
            $Offset = $TabLengths[$RealWidth] - 1;
            if (!$ComputeWidth)     {
                $snip = substr($snip, 0, $i-1).$Tabs[$RealWidth].substr($snip, $i);
                $Ln += $Offset;         $i += $Offset;
            }   else    $Computed += $Offset;
            $PosInLine += $RealWidth;
            if ($ComputeWidth)      $Computed++;
        }
    }

Une expression régulière tirée d'un commentaire de la doc PHP de preg_grep.

/((?:(?!BADWORD).)*)/s

Programmation X11