6
\$\begingroup\$

I'm trying to compute de Bruijn sequences for alphabets which have a number of characters which is a power of two. So the sequence must contain every possible subsequence of length \$N\$ from \$0\$ to \$2^n\$ as a sequence of consecutive characters exactly once.

I need to use only 2 digits (0 and 1) with a length \$N \le 20\$ so \$B(2, N)\$.

The idea is quite simple, I have implemented it but I have time restriction 0.5 sec and from \$N=16\$ to \$N=20\$ I will get Time Limit Exceeded (I didn't submit the code yet because that programming contest web evaluator is not working at the moment). Using my computer I get for \$N=15\$ somewhere between \$0.2\$ to \$0.3\$ seconds but for \$N=16\$ I get \$1.180\$ seconds which is not good at all.

Prefer Ones rule: Write \$n\$ zeros. Then, always write a one unless it would cause the repetition of an \$n\$-length string; otherwise, write a zero.

This is my code without libraries declaration:

int construct(int n, string ans){
    int number=0, poz=0;
    for(int i=ans.length()-n; i<ans.length(); ++i, ++poz)
        if(ans[i]=='1')
            number ^= (1<<poz);
    return number;
}

int main ()
{
    int n, aux, usedN=1; // usedN counts the combinations 
                         // I created in my sequence (till 2^n)
    fin>>n;
    aux=n;

    bool used[(1<<n)+1];
    string ans;
    memset(used, 0, sizeof(used));
    used[0]=1; // that's why I have usedN = 1

    while(aux--)
        ans.push_back('0');

    while(usedN!=(1<<n)) {   
        ans.push_back('1'); // first I try with an '1'

        int number=construct(n, ans); // I construct as a number
                                      // the new combination created
                                      // of length N
                                      // with the last added digit, the
                                      // '1' in this case to check if I already 
                                      // have it in my de Bruijn sequence (in ans)
        if(used[number]==1) {
            ans.pop_back();
            ans.push_back('0');
            used[construct(n, ans)]=1;
        } else
            used[number]=1;

        ++usedN;
    }

    cout<<ans.length()<<'\n'<<ans;
    return 0;
}

I'm mostly looking for optimizations so that my running time gets considerably slower, but feedback on all other aspects of my code would be great too!

\$\endgroup\$
  • \$\begingroup\$ There's no need to have the review request in the title. Things like optimization are also already implied on this site. \$\endgroup\$ – Jamal Jan 9 '16 at 15:18
2
\$\begingroup\$

The 'prefer-1' algorithm works by having a current word, shifting out the first bit and then appending a new bit.

Such a current word - which essentially represents the tail of the sequence constructed thus far - could be housed in a machine word (word-sized variable or register) for lengths up to 32 or 64 bits. The new bit that you decide on during each iteration can then be converted to text and appended to the answer, which would obviously have been initialised to the textual representation of the all-0 word before the loop.

Your implementation does not keep such a current word. Instead you reconstruct the current word at each step from the textual representation of the sequence, by looking at its tail.

If you remove this inefficiency then your code ought to be fast enough to beat the generous timeout.

Also, your code can benefit from a bit of refactoring - moving the code for constructing the sequence out of main() into its own function - and from a thorough spring cleaning.

E.g. the expression (1<<n) does not change during the computation but you recompute for every iteration of the outer loop. usedN looks ugly and is not very informative; what about words_found? Or change things around to

for (unsigned words_to_find = 1u << n - n; words_to_find--; )
{
   ...
}

This must work since you find exactly one new word during each iteration. The term is (1 << n) - n because n characters have already been appended to the output sequence; other loop structures are possible but then the loop logic would have to be adapted.

Try to change your code so that it reads more like a description of what you're doing. Including asserts can help clarify things both for you and the reader, and it can help finding mistakes early.

For example, the 'prefer 1' algorithm implies that if the new word with a 1 already exists, then swapping the 1 for a 0 must result in word that does not exist yet. Assuming the current new word to be housed in a variable current_word:

if (used[current_word])
   current_word &= ~1u;  // change the new bit to zero

assert(not used[current_word]);
used[current_word] = true;

ans.push_back('0' + (current_word & 1u));

Or, if you enjoy terse code:

current_word ^= used[current_word];
...

But then you need to be careful about only writing strict 1 (i.e. true) into the array. Other non-zero values would also evaluate to true in conditions but they would completely mess up the terse code.

For an example that uses an integer working variable I'm appending a simple, straightforward Delphi rendition of the code (since I need to learn Delphi ATM). It clocks about 50 ms for n = 20, and a C++ version should be even faster. The code can be made significantly faster still for higher n, by using a packed bitmap and preallocating the result string (i.e. calling reserve() in C++).

function DeBruijn_sequence (n: Cardinal): string;
var
   seen: array of Boolean;
   bits: Cardinal;
   mask: Cardinal;
   i: Cardinal;
   w: Cardinal;
begin
   bits := 1 shl n;
   mask := bits - 1;
   assert(bits <> 0);
   SetLength(seen, bits);
   result := StringOfChar('0', n);
   w := 0;
   for i := n + 1 to bits do begin
      seen[w] := true;
      w := ((w shl 1) or 1) and mask;
      if seen[w] then begin
         w := w and not 1;
         assert(not seen[w]);
      end;
      result := result + Char(Byte('0') + (w and 1));
   end;
end;
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.