Déterminer le nombre manquant dans le flux de données

14

Nous recevons un flux de n1 nombres différents par paire de l'ensemble {1,,n} .

Comment puis-je déterminer le nombre manquant avec un algorithme qui lit le flux une fois et utilise une mémoire de seulement O(log2n) bits?

Queue
la source

Réponses:

7

Vous savez , et parce queS=n(n+1)i=1ni=n(n+1)2 pourraient être codés enO(log(n))bits cela peut être fait dans lamémoireO(logn)et dans un chemin (il suffit de trouverS-currentSum, c'est le nombre manquant).S=n(n+1)2O(log(n))O(logn)ScurrentSum

Mais ce problème pourrait être résolu dans le cas général (pour constant ): nous avons k nombres manquants, découvrez-les tous. Dans ce cas, au lieu de calculer simplement la somme de y i , calculez la somme de la puissance j'st de x i pour tous les 1 j k (j'ai supposé que x i est des nombres manquants et y i est des nombres en entrée):kkyixi1jkxiyi

i=1kxi=S1,i=1kxi2=S2,i=1kxik=Sk (1)

Rappelez -vous que vous pouvez calculer simplement, car S 1 = S - y i , S 2 = i 2 - y 2 i , ...S1,...SkS1=SyiS2=i2yi2

Maintenant, pour trouver les nombres manquants, vous devez résoudre pour trouver tous les x i .(1)xi

Vous pouvez calculer:

, P 2 = x ix j , ..., P k = x i ( 2 ) .P1=xiP2=xixjPk=xi (2)

Pour cela rappelez-vous que , P 2 = S 2 1 - S 2P1=S1 , ...P2=S12S22

Mais est des coefficients de P = ( x - x 1 ) ( x - x 2 ) ( x - x k ) mais P pourrait être factorisé de manière unique, de sorte que vous pouvez trouver les nombres manquants.PiP=(xx1)(xx2)(xxk)P

Ce ne sont pas mes pensées; lisez ceci .

Raphael
la source
1
Je ne comprends pas (2). Peut-être que si vous ajoutiez les détails des sommes? Est-ce que manquez Σ ? Pk
Raphael
@Raphael, est l'identité de Newton, je pense que si vous regardez ma page wiki référencée, vous pouvez avoir l'idée du calcul, chaque P i pourrait être calculé par les Ps , S j précédents , rappelez-vous la formule simple: 2 x 1x 2 = ( x 1 + x 2 ) 2 - ( x 2 1 + x 2 2 ) , vous pouvez appliquer une approche similaire à tous les pouvoirs. Aussi, comme je l'ai écrit P iPiPiPSj2x1x2=(x1+x2)2(x12+x22)Piest le sigma de quelque chose, mais n'a pas de Σ , car il n'y en a qu'un Π . PkΣΠ
Quoi qu'il en soit, les réponses doivent être autonomes dans une mesure raisonnable. Vous donnez des formules, alors pourquoi ne pas les compléter?
Raphael
11

Du commentaire ci-dessus:

Avant de traiter le flux, bits, dans lequel vous écrivez x : = n i = 1 b i n ( i ) ( b i n ( i ) est la représentation binaire de i et est point par point exclusif- ou). Naïvement, cela prend du temps O ( n ) .log2nx:=i=1nbin(i)bin(i)iO(n)

jx:=xbin(j)k be the single number from {1,...n} that is not included in the stream. After having read the whole stream, we have

x=(i=1nbin(i))(ikbin(i))=bin(k)ik(bin(i)bin(i))=bin(k),
yielding the desired result.

Hence, we used O(logn) space, and have an overall runtime of O(n).

HdM
la source
3
may I suggest an easy optimization that makes this a true streaming single-pass algorithm: at time step i, xor x with bin(i) and with the input bin(j) that has arrived on the stream. this has the added benefit that you can make it work even if n is not known ahead of time: just start with a single bit allocated for x and "grow" the allocated space as necessary.
Sasho Nikolov
0

La solution de HdM fonctionne. Je l'ai codé en C ++ pour le tester. Je ne peux pas limiter le valueàO(Journal2n) bits, mais je suis sûr que vous pouvez facilement montrer comment seul ce nombre de bits est réellement défini.

Pour ceux qui veulent du pseudo code, en utilisant un simple plier fonctionnement exclusif ou ():

Disparu=plier(,{1,,N}Flux d'entrée)

Preuve ondulée à la main: A never requires more bits than its input, so it follows that no intermediate result in the above requires more than the maximum bits of the input (so O(log2n) bits). is commutative, and xx=0, thus if you expand the above and pair off all data present in the stream you'll be left only with a single un-matched value, the missing number.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

void find_missing( int const * stream, int len );

int main( int argc, char ** argv )
{
    if( argc < 2 )
    {
        cerr << "Syntax: " << argv[0] << " N" << endl;
        return 1;
    }
    int n = atoi( argv[1] );

    //construct sequence
    vector<int> seq;
    for( int i=1; i <= n; ++i )
        seq.push_back( i );

    //remove a number and remember it
    srand( unsigned(time(0)) );
    int remove = (rand() % n) + 1;
    seq.erase( seq.begin() + (remove - 1) );
    cout << "Removed: " << remove << endl;

    //give the stream a random order
    std::random_shuffle( seq.begin(), seq.end() );

    find_missing( &seq[0], int(seq.size()) );
}

//HdM's solution
void find_missing( int const * stream, int len )
{
    //create initial value of n sequence xor'ed (n == len+1)
    int value = 0;
    for( int i=0; i < (len+1); ++i )
        value = value ^ (i+1);

    //xor all items in stream
    for( int i=0; i < len; ++i, ++stream )
        value = value ^ *stream;

    //what's left is the missing number
    cout << "Found: " << value << endl;
}
edA-qa mort-ora-y
la source
3
Please post readable (pseudo) code of only the algorithm instead (skip main). Also, a correctness proof/argument at some level should be included.
Raphael
4
@edA-qamort-ora-y Your answer assumes that the reader knows C++. To someone who is not familiar with this language, there is nothing to see: both finding the relevant passage and understanding what it's doing are a challenge. Readable pseudocode would make this a better answer. The C++ is not really useful on a computer science site.
Gilles 'SO- stop being evil'
3
If my answer proves not to be useful people don't need to vote for it.
edA-qa mort-ora-y
2
+1 for actually taking the time to write C++ code and test it out. Unfortunately as others pointed out, it's not SO. Still you put effort into this !
Julien Lebot
9
I don't get the point of this answer: you take someone else's solution, which is very simple and obviously very efficient, and "test" it. Why is testing necessary? This is like testing your computer adds numbers correctly. And there is nothing nontrivial abt your code either.
Sasho Nikolov