Maison Périphériques technologiques IA L'algorithme CVM révolutionnaire résout plus de 40 ans de problèmes de comptage ! Un informaticien lance une pièce de monnaie pour trouver le mot unique pour « Hamlet »

L'algorithme CVM révolutionnaire résout plus de 40 ans de problèmes de comptage ! Un informaticien lance une pièce de monnaie pour trouver le mot unique pour « Hamlet »

Jun 07, 2024 pm 03:44 PM
ai 算法 数学

Compter semble simple, mais il est très difficile à mettre en pratique.

Imaginez que vous soyez envoyé dans une forêt tropicale humide vierge pour effectuer un recensement de la faune. Chaque fois que vous voyez un animal, prenez une photo.

L'appareil photo numérique enregistre uniquement le nombre total d'animaux suivis, mais vous êtes intéressé par le nombre d'animaux uniques, mais il n'y a pas de statistiques.

Alors, quelle est la meilleure façon de mettre la main sur cet animal unique ?

À ce stade, vous devez vous dire, commencez à compter à partir de maintenant, et enfin comparez chaque nouvelle espèce de la photo à la liste.

Cependant, cette méthode de comptage courante n'est parfois pas adaptée aux informations pouvant atteindre des milliards d'entrées.

Des informaticiens de l'Institut indien de statistique, UNL, et de l'Université nationale de Singapour ont proposé un nouvel algorithme-CVM.

Il peut se rapprocher du nombre d'éléments différents dans une longue liste et n'a besoin de mémoriser qu'un petit nombre d'éléments.

Lalgorithme CVM révolutionnaire résout plus de 40 ans de problèmes de comptage ! Un informaticien lance une pièce de monnaie pour trouver le mot unique pour « Hamlet »

Adresse papier : https://arxiv.org/pdf/2301.10191

Cet algorithme convient à toute liste dans laquelle un élément apparaît à la fois, comme le texte d'un discours, les biens sur un tapis roulant, ou des voitures sur l'autoroute.

L'algorithme CVM doit son nom aux premières lettres des trois auteurs et a fait des progrès significatifs dans la résolution du « problème des différents éléments ».

Ce problème préoccupe les informaticiens depuis plus de 40 ans.

Cela nécessite un moyen efficace de surveiller un flux d'éléments (dont le nombre total peut dépasser la mémoire disponible) et d'estimer le nombre d'éléments uniques qu'il contient.

Alors, comment l'algorithme CVM résout-il le problème ?

Algorithme CVM pionnier, le secret réside dans la "randomisation"

Supposons que vous écoutiez le livre audio "Hamlet".

Ce drame compte un total de 30557 mots, combien sont différents ?

Pour trouver la réponse, vous pouvez faire une pause pendant l'écoute, écrire chaque mot par ordre alphabétique, puis sauter les mots déjà sur la liste, et enfin, simplement compter chaque mot de la liste.

Lalgorithme CVM révolutionnaire résout plus de 40 ans de problèmes de comptage ! Un informaticien lance une pièce de monnaie pour trouver le mot unique pour « Hamlet »

Cette méthode est réalisable, mais elle teste trop la « mémoire ».

Le chercheur Vinodchandran Variyam a déclaré : « Dans une situation typique de flux de données, il peut y avoir des millions d'éléments à suivre. Vous ne souhaiterez peut-être pas stocker toutes les informations.

Il s'agit d'un serveur cloud où les algorithmes peuvent fournir plus méthodes".

L'astuce est la "randomisation".

Lalgorithme CVM révolutionnaire résout plus de 40 ans de problèmes de comptage ! Un informaticien lance une pièce de monnaie pour trouver le mot unique pour « Hamlet »

Vinodchandran Variyam a aidé à inventer un algorithme CVM pour estimer le nombre d'éléments distincts dans un flux de données

Combien de mots uniques y a-t-il dans "Hamlet" ? Coin Flip Challenge

Retour à "Hamlet", en supposant que votre "mémoire effective" ne peut contenir que 100 mots.

Une fois la lecture audio commencée, vous écrivez les 100 premiers mots que vous entendez et sautez les mots répétés.

Lorsque vous avez fini d'enregistrer 100 mots, il ne vous reste plus qu'à lancer une pièce pour chaque mot –

Tête, gardez le mot. Si c'est le verso, supprimez-le.

Après ce tour préliminaire, il vous restera environ 50 mots différents.

Maintenant, vous passez à ce que l'équipe appelle le premier tour, en continuant à lire Hamlet et en ajoutant de nouveaux mots.

Si vous rencontrez à nouveau un mot qui figure déjà sur la liste, lancez à nouveau la pièce jusqu'à ce que vous ayez 100 mots dans votre tableau blanc en mémoire.

Ensuite, environ la moitié des mots sont à nouveau supprimés au hasard en fonction des résultats de 100 tirages au sort. Le premier tour se termine ici.

Ensuite, entrez dans le deuxième tour du tour 2.

Comme au premier tour, nous allons augmenter la difficulté d'un mot - lorsque vous rencontrez un mot répété, lancez à nouveau la pièce.

La condition est que si c'est une queue, supprimez-la comme avant. Mais si c’est face, lancez à nouveau la pièce. Le mot n'est conservé que lorsqu'il apparaît face pour la deuxième fois.

Une fois le tableau blanc mémoire plein, terminez le tour, puis supprimez à nouveau environ la moitié des mots en fonction des résultats de 100 lancers.

Au tour 3, vous devez lancer une pièce de monnaie trois fois de suite pour tenir un mot.

Au quatrième tour, gardez un mot au recto quatre fois de suite, et ainsi de suite.

Enfin, au kième tour, vous écouterez l'intégralité de la pièce "Hamlet".

Le but de cet exercice est de s'assurer que chaque mot a la même probabilité d'occurrence : 1/2 (k).

Supposons qu'à la fin de l'audio Hamlet, vous ayez 61 mots dans votre liste et qu'il vous ait fallu six tours pour la terminer.

Vous pouvez estimer le nombre de mots différents en divisant 61 par probabilité 1/2 (6) - le résultat final de ce jeu est 3904.

La précision de l'algorithme est proportionnelle à la quantité de mémoire

Les chercheurs Chakraborty, Variyam et Meel ont prouvé mathématiquement que la précision de l'algorithme CVM est proportionnelle à la quantité de mémoire.

Et Hamlet possède 3967 mots uniques. (Par méthode de comptage ordinaire)

Dans l'expérience utilisant une mémoire de 100 mots, l'estimation moyenne des 5 séries de résultats expérimentaux est de 3955 mots.

Avec 1000 mots en mémoire, la capacité moyenne de mémoire est passée à 3964.

Variyam a déclaré : « Si (la mémoire) est suffisamment grande pour accueillir tous les mots, alors nous pouvons atteindre une précision de 100 %. »

William Kuszmau de l'Université Harvard a déclaré : "C'est un excellent exemple de la façon dont même pour des problèmes très fondamentaux et largement étudiés, il peut parfois y avoir des solutions simples mais pas évidentes à découvrir."

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Article chaud

<🎜>: Grow A Garden - Guide de mutation complet
3 Il y a quelques semaines By DDD
<🎜>: Bubble Gum Simulator Infinity - Comment obtenir et utiliser les clés royales
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Système de fusion, expliqué
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers of the Witch Tree - Comment déverrouiller le grappin
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Tutoriel Java
1666
14
Tutoriel PHP
1273
29
Tutoriel C#
1253
24
Comment utiliser la bibliothèque Chrono en C? Comment utiliser la bibliothèque Chrono en C? Apr 28, 2025 pm 10:18 PM

L'utilisation de la bibliothèque Chrono en C peut vous permettre de contrôler plus précisément les intervalles de temps et de temps. Explorons le charme de cette bibliothèque. La bibliothèque Chrono de C fait partie de la bibliothèque standard, qui fournit une façon moderne de gérer les intervalles de temps et de temps. Pour les programmeurs qui ont souffert de temps et ctime, Chrono est sans aucun doute une aubaine. Il améliore non seulement la lisibilité et la maintenabilité du code, mais offre également une précision et une flexibilité plus élevées. Commençons par les bases. La bibliothèque Chrono comprend principalement les composants clés suivants: std :: chrono :: system_clock: représente l'horloge système, utilisée pour obtenir l'heure actuelle. std :: chron

Comment gérer un écran DPI élevé en C? Comment gérer un écran DPI élevé en C? Apr 28, 2025 pm 09:57 PM

La gestion de l'affichage DPI élevé en C peut être réalisée via les étapes suivantes: 1) Comprendre le DPI et la mise à l'échelle, utiliser l'API du système d'exploitation pour obtenir des informations DPI et ajuster la sortie graphique; 2) Gérer la compatibilité multiplateforme, utilisez des bibliothèques graphiques multiplateformes telles que SDL ou QT; 3) Effectuer une optimisation des performances, améliorer les performances par le cache, l'accélération matérielle et le réglage dynamique du niveau de détails; 4) Résoudre des problèmes communs, tels que le texte flou et les éléments d'interface, sont trop petits et résolvent en appliquant correctement la mise à l'échelle DPI.

Comment comprendre les opérations DMA en C? Comment comprendre les opérations DMA en C? Apr 28, 2025 pm 10:09 PM

DMA IN C fait référence à DirectMemoryAccess, une technologie d'accès à la mémoire directe, permettant aux périphériques matériels de transmettre directement les données à la mémoire sans intervention CPU. 1) L'opération DMA dépend fortement des dispositifs matériels et des pilotes, et la méthode d'implémentation varie d'un système à l'autre. 2) L'accès direct à la mémoire peut apporter des risques de sécurité et l'exactitude et la sécurité du code doivent être assurées. 3) Le DMA peut améliorer les performances, mais une mauvaise utilisation peut entraîner une dégradation des performances du système. Grâce à la pratique et à l'apprentissage, nous pouvons maîtriser les compétences de l'utilisation du DMA et maximiser son efficacité dans des scénarios tels que la transmission de données à grande vitesse et le traitement du signal en temps réel.

Qu'est-ce que la programmation du système d'exploitation en temps réel en C? Qu'est-ce que la programmation du système d'exploitation en temps réel en C? Apr 28, 2025 pm 10:15 PM

C fonctionne bien dans la programmation du système d'exploitation en temps réel (RTOS), offrant une efficacité d'exécution efficace et une gestion du temps précise. 1) C répond aux besoins des RTO grâce à un fonctionnement direct des ressources matérielles et à une gestion efficace de la mémoire. 2) En utilisant des fonctionnalités orientées objet, C peut concevoir un système de planification de tâches flexible. 3) C prend en charge un traitement efficace d'interruption, mais l'allocation de mémoire dynamique et le traitement des exceptions doivent être évités pour assurer le temps réel. 4) La programmation des modèles et les fonctions en ligne aident à l'optimisation des performances. 5) Dans les applications pratiques, C peut être utilisé pour implémenter un système de journalisation efficace.

Étapes pour ajouter et supprimer les champs aux tables MySQL Étapes pour ajouter et supprimer les champs aux tables MySQL Apr 29, 2025 pm 04:15 PM

Dans MySQL, ajoutez des champs en utilisant alterTableTable_namEaddColumnNew_Columnvarchar (255) AfterExist_Column, supprimez les champs en utilisant alterTableTable_NamedRopColumnColumn_to_drop. Lorsque vous ajoutez des champs, vous devez spécifier un emplacement pour optimiser les performances de la requête et la structure des données; Avant de supprimer les champs, vous devez confirmer que l'opération est irréversible; La modification de la structure de la table à l'aide du DDL en ligne, des données de sauvegarde, de l'environnement de test et des périodes de faible charge est l'optimisation des performances et les meilleures pratiques.

Comment mesurer les performances du fil en C? Comment mesurer les performances du fil en C? Apr 28, 2025 pm 10:21 PM

La mesure des performances du thread en C peut utiliser les outils de synchronisation, les outils d'analyse des performances et les minuteries personnalisées dans la bibliothèque standard. 1. Utilisez la bibliothèque pour mesurer le temps d'exécution. 2. Utilisez le GPROF pour l'analyse des performances. Les étapes incluent l'ajout de l'option -pg pendant la compilation, l'exécution du programme pour générer un fichier gmon.out et la génération d'un rapport de performances. 3. Utilisez le module Callgrind de Valgrind pour effectuer une analyse plus détaillée. Les étapes incluent l'exécution du programme pour générer le fichier callgrind.out et la visualisation des résultats à l'aide de Kcachegrind. 4. Les minuteries personnalisées peuvent mesurer de manière flexible le temps d'exécution d'un segment de code spécifique. Ces méthodes aident à bien comprendre les performances du thread et à optimiser le code.

Classement d'échange quantitatif 2025 Top 10 des recommandations pour les applications de trading quantitatif de la monnaie numérique Classement d'échange quantitatif 2025 Top 10 des recommandations pour les applications de trading quantitatif de la monnaie numérique Apr 30, 2025 pm 07:24 PM

Les outils de quantification intégrés de l'échange comprennent: 1. Binance: fournit un module quantitatif à terme Binance Futures, des frais de manutention faible et prend en charge les transactions assistées par l'IA. 2. OKX (OUYI): prend en charge la gestion multi-comptes et le routage des ordres intelligents, et fournit un contrôle des risques au niveau institutionnel. Les plates-formes de stratégie quantitative indépendantes comprennent: 3. 3Commas: générateur de stratégie de glisser-déposer, adapté à l'arbitrage de la couverture multiplateforme. 4. Quadancy: Bibliothèque de stratégie d'algorithme de niveau professionnel, soutenant les seuils de risque personnalisés. 5. Pionex: stratégie prédéfinie intégrée, frais de transaction bas. Les outils de domaine vertical incluent: 6. CryptoPper: plate-forme quantitative basée sur le cloud, prenant en charge 150 indicateurs techniques. 7. Bitsgap:

Top 10 des plates-formes de trading de devises numériques: 10 premiers échanges de devises numériques sûrs et fiables Top 10 des plates-formes de trading de devises numériques: 10 premiers échanges de devises numériques sûrs et fiables Apr 30, 2025 pm 04:30 PM

Les 10 principales plates-formes de trading de devises virtuelles numériques sont: 1. Binance, 2. Okx, 3. Coinbase, 4. Kraken, 5. Huobi Global, 6. Bitfinex, 7. Kucoin, 8. Gemini, 9. Bitstamp, 10. Bittrex. Ces plateformes offrent toutes une haute sécurité et une variété d'options de trading, adaptées à différents besoins des utilisateurs.

See all articles