PHP, limites du in_array()

  • Auteur de la discussion mdj de normandie
  • Date de début

mdj de normandie

Grand Maître
#1
Salut a tous !

Je bosse sur un "petit" projet perso depuis quelque mois,
je ne rentre pas dans les détails technique et complexe (les plus malins d'entre vous comprendrons de quoi sa parle)
et passe directement au problème

j'ai un tableaux (json chargé en PHP) qui contient un certain nombre de hash sha1
(20 millions au moment ou je vous parle, oui c'est beaucoup et sa continue de monter, et oui j’arrive a le charger dans 16go de ram, j'ai même encore de la marge)
chaque hash correspond a un ensemble de données (que je vais appeler ici "situation")
mon programme explore les évolutions possible d'une situation vers un ensemble d'autres situations (générant de nouvelles entré sha1)
mais certaines situations aboutissent au même hash

un personnage partant d'un point 0 fait un pas en avant et un pas chassé a droite, il arrive au point 1,
il retourne au point 0 et fait un pas chassé a droite et un pas un avant, il arrive aussi au point 1,
les situations d'arrivé sont les mêmes.
dans mon programme c'est un peu ce qu'il se passe

donc lors du calcul d'une situation si son résultat (hash) est déjà connu (dans la liste) alors on l'ignore, si non on l'ajoute a la liste *.
vous imaginez bien que vu le nombre de hash il y a un tableau qui sert de buffer et qui est ajouté a la liste définitive tout les 100 000 nouveaux hash trouvé ...

donc évidement pour savoir si un hash été connu j’utilisais un simple :
PHP:
if(in_array($new_hash, $hash_connus)){...}
mais voila depuis que j'ai passé les 10M de hash dans la liste la fonction in_array() ... galère (mais galère a un point !...)

donc j'ai trouvé une solution (j'ai besoin de vous juste pour l'optimiser)
cette solution m'est venu en tournant la tête vers mes encyclopédies,
comme quoi le support papier a encore une utilité... comment sa "ok boomer" ?
les hash c'est des chaines de caractères, il peuvent donc être comparer a des mots.
ma liste de hash connues si je la passe dans la fonction sort() je la récupère dans l'ordre alphabétique et obtiens donc un "dictionnaire".
et quand je reçois un nouveau hash (mot) et que je veux voir si il existe dans mon dictionnaire, comment je procède ?
je ne vous ferait pas l'affront d'expliquer comment chercher un mots dans un dictionnaire ;) mais une rapide recherches sur les fonctions :
array_chunk() et strcmp() et me voila avec le code suivant (et qui fonctionne !) :


PHP:
private function main(){
    //...
    sort($hash_connus)
    $hash_connus=array_chunk($hash_connus, 100000) //c'est ici que ma question arrive !
    //...
    if($this->in_dictionary($hash, $hash_connus)){
        //...
    }
}

private function in_dictionary($word, &$dictionary) { //passer la liste par référence me fait gagner de la mémoire
    foreach ($dictionary as $section) {
        if (strcmp($word, $section[0]) >= 0 and strcmp($word, $section[count($section) - 1]) <= 0) {
            return in_array($word, $section);
        }
    }
    return false;
}
et ma question porte sur la taille des chunk : une taille trop élevé et je retombe dans les chutes de performance de in_array(), une taille trop petite et c'est le foreach ($dictionary as $section) qui fait trop de tours...

donc d'après vous quel es la taille optimal des chunk ?

cette taille doit elle être proportionnel a la liste des hash connus ?
si oui dans quel proportion ?


Quelques questions que vous pouvez vous poser :
- Pourquoi je ne passe pas par une base de donnée SQL ? lors que toutes les données seront généré et exploitable elle seront mise en base donnée sur un serveur de prod, mais en dev il est plus simple pour moi de manipuler, transférer et faire des backup de fichiers plutôt que de faire une migration de base de donnée qui fera certainement plus d'une centaine de GO .

- Pourquoi sha1 ? purement arbitraire, j'aurais pu prendre n'importe quel autre méthode de hash du même calibre voir qui génère des clés plus courtes.

- Pourquoi PHP ? c'est le langage avec le quel je suis le plus a l'aise, et je peux lancer un serveur (php -S) pour exécuter certaines taches de façons asynchrone sur d'autres thread ...

- la Chloroquine, pour ou cont... non je déconne ! :D
 
Dernière édition:

mdj de normandie

Grand Maître
#2
bon j'ai fait tourner une simulation, semblerais que le plus performant (sur le proco que j'ai) c'est entre 1 000 et 10 000 de taille de chunk (mais sa reste acceptable a 100 000)
j’aurai aimé poussé la taille du dico a 100 000 000 mais j'ai fait un out of memory sur ma machine test (et l'autre est occupé)
Je laisse le tableau de résultat au cas ou ...
stat dico.jpg
 
Vous devez vous inscrire ou vous connecter pour répondre ici.
Staff en ligne
  • job31
    Admin tout frippé
  • vince1053
    Modérateur
  • Storos
    Modérateur cochon
  • AccroPC2
    Fou du PC
Membres en ligne
  • job31
  • SergioVE
  • vince1053
  • BorisAlpha
  • Storos
  • Lau0417
  • ImTim
  • dartyduck
  • longaripa
  • AccroPC2
Derniers messages publiés
Statistiques globales
Discussions
871 066
Messages
8 131 223
Membres
1 581 593
Dernier membre
Noemie1104
Partager cette page
Haut