• # Compléments

    Posté par  . Évalué à 4.

    • [^] # Re: Compléments

      Posté par  . Évalué à 9. Dernière modification le 22 mai 2024 à 12:26.

      Ce n'est pas une méthode de comptage mais d'approximation :

      computer scientists have described a new way to approximate the number of distinct entries in a long list

      puis

      Hamlet has exactly 3,967 unique words. (They counted.) In experiments using a memory of 100 words, the average estimate after five runs was 3,955 words. With a memory of 1,000 words, the average improved to 3,964.

      L'algorithme n'en reste pas moins intéressant dans certains cas car simple et peu gourmand en ressources.

      • [^] # Re: Compléments

        Posté par  . Évalué à 3.

        Oui, ce qui est cohérent avec le contexte visé : celui des streaming très gros, où la mémoire ne suffit pas à contenir chaque valeur distincte déjà rencontrée.

        Mais pour le cas de tout les jours, genre dans ma base de données, je veux savoir combien de produits différents ont été vendu au client X, je m'attends pas à un chiffre approximé, et je m'attends pas non plus à 1,000,000,000 de lignes à lire.

        Par contre, si on en est à approximer, et qu'on "connaît" la nature des données, on peut aller encore plus loin et ne pas écouter l'ensemble du flux de données, non ?

        • [^] # Re: Compléments

          Posté par  . Évalué à 3.

          J'ai pas encore lu le papier (et le billet de korben, bon).

          J'avais il y a encore quelques semaines un cas où on reçoit disons des chaînes de caractères d'utilisateurs et on cherche à sortir pour chaque chaîne le nombre d'utilisateur unique qui nous l'on envoyé par jour et par mois. Comme on a 20 millions d'utilisateurs, (malheureusement) des centaines de milliers de chaînes distinctes, qu'il est demandé à ce que ce soit compté "en live" et pas de ressources infinies, il faut avoir des stratégies.

          Nous on est parti sur des hash des valeurs stockés par utilisateurs avec des hash non cryptographiques et en réduisant (un peu) la taille du hash, mais on aurait pu réduire la taille du hash quitte à générer des collisions à la marge (comme on peut faire des stats sur nos données, on peut appliquer les formules du "paradoxe" des anniversaires pour savoir à partir de quelle taille on a quelle probabilité de collision).

          Mais les donneurs d'ordre n'aiment pas trop les comportement probabilistes quand bien même on peut leur données des valeurs chiffrées.

          Je suis très curieux de si cet algo est pertinent pour le cas dont je parle.

          https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

          • [^] # Re: Compléments

            Posté par  (site web personnel) . Évalué à 2.

            Si je comprends bien votre stratégie consiste à ranger par ordre 'alphabétique' vos hash, puis à les compter ?

            Il me semble que cette stratégie soit la meilleurs si l'on peut se permettre de stocker en mémoire tout le dictionnaire des hash rencontrés. Le pré-facteur de l'approche probabiliste de l'algorithme CVM paraît sensiblement supérieur. Selon ma compréhension, cet algorithme serait pertinent pour les cas où la quantité de hash dépasserait ce qui est gérable en mémoire.

            « IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace

            • [^] # Re: Compléments

              Posté par  . Évalué à 2.

              Si je comprends bien votre stratégie consiste à ranger par ordre 'alphabétique' vos hash, puis à les compter ?

              Pas exactement, quand un device vient nous voir, on regarde si on a déjà vu passer le hash dans la plage de temps et s'il est nouveau on incrémente un compteur.

              En fait c'est dépendant de comment on organise les chose si on suit notre algo on rentre facilement les hash d'un client en mémoire.

              Si on cherchait a stocker les clients par par chaîne, ça ne rentrerait plus en mémoire. Mais s'il est très efficace ça peut être plus intéressant

              Mais j'ai pas encore pris le temps de lire.

              https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

              • [^] # Re: Compléments

                Posté par  (site web personnel) . Évalué à 2. Dernière modification le 22 mai 2024 à 19:10.

                La version de D. Knuth rend la lecture super simple. L'algorithme tient en 6 étapes (une vingtaine de lignes en Python) et ~12 lignes (vers la seconde page du document). C'est remarquable.

                « IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.