Je reçois un flux de nombres non ordonné. Y a-t-il une structure de données que je peux détenir afin de savoir si un nombre existe déjà dans le flux sans contenir une collection des nombres que j'ai reçus du flux (c'est un flux infini)?Identifier un nouveau numéro dans un flux non ordonné
Non, il n'est pas possible d'éviter de conserver tous les nombres précédemment vus.
A cet effet, une table de hachage est probablement la plus appropriée.
Il se peut que des économies (marginales) soient possibles par compression ou en profitant de certaines propriétés des données, mais vous ne nous en avez pas beaucoup parlé.
il est littéralement un flux de nombres. Je me demandais simplement s'il y a un genre de métadonnées/calculs que je peux sauvegarder sur le flux qui me permettra de savoir si le numéro est nouveau. si oui alors mettre à jour les calculs – igx
Créez un flux de bits, lorsque vous voyez un nombre à ce bit et le retournez. De cette façon, vous pouvez vous souvenir des nombres en utilisant moins d'espace. Donc, si les numéros à mémoriser sont de 32 bits de long. L'espace total requis pour stocker le flux binaire serait de 2^32 bits ou 536,870912 mégaoctets et une heure constante pour accéder au flux binaire.
Si les nombres sont grands, vous pouvez les hacher à nouveau sur 32 bits.
ce n'est pas ce que je cherchais car il consomme beaucoup de mémoire même peut-être plus que ce qu'il devrait (par exemple si j'ai 4 numéros répétés). mais c'est une bonne solution +1 – igx
Est-ce un flux infini de nombres d'une gamme ou d'un ensemble fini? Par exemple. un flux de seulement 0, 1, 2, 3 ou 4. – Yunnosch
En fait, il est flux de hashcodes donc il est très large gamme – igx
Et il serait bien sûr typique pour les hachages de ne pas avoir de relation utile comme par exemple. monotone ascendant ... – Yunnosch