Posté par nico4nicolas .
É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.
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 ?
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.
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.
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
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.
# Compléments
Posté par Letho . Évalué à 4.
L'article détaillé en anglais : https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/
La note de Donald Knuth : https://www-cs-faculty.stanford.edu/~knuth/papers/cvm-note.pdf
[^] # Re: Compléments
Posté par nico4nicolas . Évalué à 9. Dernière modification le 22 mai 2024 à 12:26.
Ce n'est pas une méthode de comptage mais d'approximation :
puis
L'algorithme n'en reste pas moins intéressant dans certains cas car simple et peu gourmand en ressources.
[^] # Re: Compléments
Posté par Dring . É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 barmic 🦦 . É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 ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (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 barmic 🦦 . Évalué à 2.
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 ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (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.