30
\$\begingroup\$

This is a simple brute force algorithm that I have programmed in C. All the program does is print out every possible combination of the given alphabet for the given length.

I would prefer suggestions on how to improve the algorithm, or decrease run-time. Any other suggestions are acceptable though.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

static const char alphabet[] =
"abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789";

static const int alphabetSize = sizeof(alphabet) - 1;

void bruteImpl(char* str, int index, int maxDepth)
{
    for (int i = 0; i < alphabetSize; ++i)
    {
        str[index] = alphabet[i];

        if (index == maxDepth - 1) printf("%s\n", str);
        else bruteImpl(str, index + 1, maxDepth);
    }
}

void bruteSequential(int maxLen)
{
    char* buf = malloc(maxLen + 1);

    for (int i = 1; i <= maxLen; ++i)
    {
        memset(buf, 0, maxLen + 1);
        bruteImpl(buf, 0, i);
    }

    free(buf);
}

int main(void)
{
    bruteSequential(3);
    return 0;
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Brute force is a category, not an algorithm. It might be useful to specify what this code is supposed to do rather than just saying it's brute force. Might save the next person to read through it a minute or two :). \$\endgroup\$ – Corbin Jan 3 '14 at 4:41
  • 1
    \$\begingroup\$ @Corbin I edited in the purpose of the code. Also Wikipedia says it is an algorithm ;) \$\endgroup\$ – syb0rg Jan 3 '14 at 4:48
  • 3
    \$\begingroup\$ Another way to think about the problem is as counting in base 62. However, that doesn't necessarily yield better code. \$\endgroup\$ – 200_success Jan 3 '14 at 21:00
  • \$\begingroup\$ just a small idea, untested. For large maxLen firstly get all possible strings for maxLen/2 and then create all combinations. This will use a lot more memory but might be faster in time. The challenge would be to determine when to use this approach and when to simply brute force as you are doing now. \$\endgroup\$ – Pinoniq May 5 '14 at 15:19
  • 2
    \$\begingroup\$ You should change the title of this thread to something more meaningful. Brute force is not an algorithm, Brute force search is (cf your reference) \$\endgroup\$ – Ivan Jun 19 '18 at 19:10
20
+50
\$\begingroup\$

I'm going to skip reviewing the OP's code, which has already been reviewed quite nicely by others. Instead I'm just going to show a much faster version and explain it.

What is the algorithm?

Basically the way the algorithm works is that a buffer is created that holds alphaLen^2 patterns, where alphaLen is the length of the alphabet. A pattern is one combination, such as "aaaaa\n". The reason that alphaLen^2 patterns are used is because the buffer is prepopulated with the last 2 letters already set to all possible combinations. So for example, the buffer initially looks like (for length 5 patterns):

"aaaaa\naaaab\naaaac\n ... aaa99\n" (62*62 patterns, 23064 bytes in length)

On every iteration, the function uses write() to output the buffer, and then increments the third to last letter. This involves writing that letter alphaLen^2 times (once per pattern). So the first iteration goes like:

"aabaa\naabab\naabac\n ... aab99\n"
   ^      ^      ^           ^
   |      |      |           |
   +------+------+-----------+----- Characters written to buffer (62*62 changes)

Whenever the third to last character wraps around, then we also need to update the fourth to last letter. If that wraps around, the fifth to last letter is also updated, etc. This continues until the first letter wraps around, at which point we are done.

How fast is it?

For all testing, I outputted to /dev/null so that my hard drive speed would not be the limiting factor. I tried the OP's program for 5 letter patterns but for me it took way too long (203 seconds). So I'll use Edward's estimate of 18 seconds for the OP's program instead. I also tested Edward's program on my machine, as well as a second program I wrote where I extended the algorithm to hardcode the last 3 characters instead of 2. I am using Cygwin gcc (32-bit) with -O4 on a Windows desktop. Here are the results:

Time (secs)  Length   Program
-----------  ------   -------
    18.0       5      syb0rg
     9.6       5      Edward
     0.4       5      JS1 (2 characters)
     0.4       5      JS1 (3 characters)

   665.0       6      Edward
    26.0       6      JS1 (2 characters)
    24.2       6      JS1 (3 characters)

  1513.7       7      JS1 (3 characters)

As you can see, this algorithm is very fast.

The code

Both programs are available here on GitHub. I'll show the 2 character variation below:

static void generate(int maxlen)
{
    int   alphaLen = strlen(alphabet);
    int   len      = 0;
    char *buffer   = malloc((maxlen + 1) * alphaLen * alphaLen);
    int  *letters  = malloc(maxlen * sizeof(int));

    if (buffer == NULL || letters == NULL) {
        fprintf(stderr, "Not enough memory.\n");
        exit(1);
    }

    // This for loop generates all 1 letter patterns, then 2 letters, etc,
    // up to the given maxlen.
    for (len=1;len<=maxlen;len++) {
        // The stride is one larger than len because each line has a '\n'.
        int i;
        int stride = len+1;
        int bufLen = stride * alphaLen * alphaLen;

        if (len == 1) {
            // Special case.  The main algorithm hardcodes the last two
            // letters, so this case needs to be handled separately.
            int j = 0;
            bufLen = (len + 1) * alphaLen;
            for (i=0;i<alphaLen;i++) {
                buffer[j++] = alphabet[i];
                buffer[j++] = '\n';
            }
            write(STDOUT_FILENO, buffer, bufLen);
            continue;
        }

        // Initialize buffer to contain all first letters.
        memset(buffer, alphabet[0], bufLen);

        // Now in buffer, write all the last 2 letters and newlines, which
        // will after this not change during the main algorithm.
        {
            // Let0 is the 2nd to last letter.  Let1 is the last letter.
            int let0 = 0;
            int let1 = 0;
            for (i=len-2;i<bufLen;i+=stride) {
                buffer[i]   = alphabet[let0];
                buffer[i+1] = alphabet[let1++];
                buffer[i+2] = '\n';
                if (let1 == alphaLen) {
                    let1 = 0;
                    let0++;
                    if (let0 == alphaLen)
                        let0 = 0;
                }
            }
        }

        // Write the first sequence out.
        write(STDOUT_FILENO, buffer, bufLen);

        // Special case for length 2, we're already done.
        if (len == 2)
            continue;

        // Set all the letters to 0.
        for (i=0;i<len;i++)
            letters[i] = 0;

        // Now on each iteration, increment the the third to last letter.
        i = len-3;
        do {
            char c;
            int  j;

            // Increment this letter.
            letters[i]++;

            // Handle wraparound.
            if (letters[i] >= alphaLen)
                letters[i] = 0;

            // Set this letter in the proper places in the buffer.
            c = alphabet[letters[i]];
            for (j=i;j<bufLen;j+=stride)
                buffer[j] = c;

            if (letters[i] != 0) {
                // No wraparound, so we finally finished incrementing.
                // Write out this set.  Reset i back to third to last letter.
                write(STDOUT_FILENO, buffer, bufLen);
                i = len - 3;
                continue;
            }

            // The letter wrapped around ("carried").  Set up to increment
            // the next letter on the left.
            i--;
            // If we carried past last letter, we're done with this
            // whole length.
            if (i < 0)
                break;
        } while(1);
    }

    // Clean up.
    free(letters);
    free(buffer);
}
\$\endgroup\$
  • \$\begingroup\$ Could you include some tests in there dealing with more character permutations? Some algorithms perform well with smaller sets of data than larger sets, so I'm curious as to how this will do \$\endgroup\$ – syb0rg Dec 21 '14 at 18:13
  • \$\begingroup\$ @syb0rg Do you mean more characters in the alphabet or longer length pattern? Tell me how long of an alphabet and/or what pattern length you want me to test, and I'll test it. \$\endgroup\$ – JS1 Dec 21 '14 at 21:15
  • \$\begingroup\$ A longer length pattern please. I'm quite certain your code will still perform well compared to others, but I'm still curious. \$\endgroup\$ – syb0rg Dec 21 '14 at 22:49
  • 1
    \$\begingroup\$ @syb0rg I added a length 7 time. Note that this is generating over 28 terabytes of data. The time was as expected, around 62x the length 6 time. I'm not going to run it for length 8 because it would take over a day to run. \$\endgroup\$ – JS1 Dec 22 '14 at 2:45
  • \$\begingroup\$ +1 - nice job! I confirmed the accuracy with the other two algorithms and also noted that even when I bump up the buffer size in my version to similar size, this algorithm is significantly faster (0.5 s vs. 9.1 s on my machine). \$\endgroup\$ – Edward Dec 26 '14 at 13:07
15
\$\begingroup\$

In this program, bruteImpl is a tight loop. I wouldn't bother optimizing anything else, even if it would save some time, because most of time will be wasted running bruteImpl anyway. Running memset one time won't save your time, as it's ran... length times. However, with length set to 5, bruteImpl is called... 15264777 times. This is definitely something worth optimizing.

The biggest limitation in performance is printf in my opinion. Console output is usually somewhat slow. If I remove printf, and instead make small loop counter, I get 2 seconds for length set to 5 (I added global count variable to force the loop to do anything, increased every time you would use puts).

The other problem is recursion that cannot be removed by compiler. However, in this case recursion appears to be needed (iterative algorithm that doesn't use the stack suggested by @200_success is 9 times slower than yours), so it's not worth removing it (you would have to simulate stack structure anyway). Recursion is slower than iteration in many algorithms, but sometimes it's just needed.

Also, the biggest problem is actually using the variables (it's not problem with your algorithm, just something worth mentioning). Practically doing anything involving values from your algorithm is slower. For example, I tried to add memcmp and strcmp in place of puts. memcmp makes your algorithm 6 times slower, and strcmp makes your algorithm 10 times slower. Your algorithm is already fast enough, if memcmp is already rather slow. Sometimes optimizing is just not worth it - compilers already do that really well.

\$\endgroup\$
  • 3
    \$\begingroup\$ I like all the points you made, but adding some code examples to show what you mean would really make this answer rock. I get what you are saying though, so +1. \$\endgroup\$ – syb0rg Jan 4 '14 at 20:18
14
\$\begingroup\$

I would say that this is pretty much impeccable as a recursive solution.

In bruteSequential(), I would rename i to len for clarity. As a slightly hackish optimization, you could move the memset() call before the for-loop, since you know that the output string lengths will never decrease. You could then combine it with the malloc() for

char* buf = calloc(maxLen + 1, sizeof(char));

As a helper function, bruteImpl() should be declared static.

\$\endgroup\$
11
\$\begingroup\$

There are some things I've seen that may help you improve your code.

Prefer iterations to recursion

Recursive functions are often a good way to approach a programming task, but there is a tradeoff in terms of memory and time. Specifically, one can often reduce or eliminate the computational cost of a function call and reduce or eliminate the memory overhead as well by converting from a recursive to an interative function.

Use pointers rather than indexing

Code that uses indexing often has the benefit that it's easy to read and understand:

for (int i = 0; i < alphabetSize; ++i) {
    str[index] = alphabet[i];
    // ...

However, code is often faster to use pointers instead. So for example, that code might be rendered like this:

for (const char *a = alphabet; *a; ++a) {
    str[index] = *a;
    // ...

It's likely that one could obtain even more time savings by converting the left hand side to use pointers as well.

Use the lowest level I/O that's practical

Using library functions like printf is convenient, but they aren't necessarily the most efficient. Something like printf("%s\n", str); has to go through the memory of str looking for the terminating NUL character which might not be needed if you already know the length.

Reduce I/O if practical

The usual bottleneck in programs like this is the input/output part. When you can replace I/O with memory access instead, it may lead to time savings. However, the underlying operating system might buffer I/O already, so the only way to check for sure is to measure it.

Putting it all together

Here's what I came up with as an alternative implementation that uses all of these suggestions:

// create a large buffer
static const int BUFFLEN=1024*100;

void brute2(int maxLen)
{
    char* indices = malloc(maxLen + 1);
    char* terminal = indices+maxLen;
    char *printbuff = malloc(BUFFLEN);
    char *pbend = &printbuff[BUFFLEN-1];
    char *b = printbuff;
    *pbend = '\0';
    ++indices[0];
    char *p;

    while (*terminal == 0) {
        // print value
        for (p = indices; *p; ++p)
            ;
        for (--p ; p >= indices; --p) {
            *b++ = alphabet[*p-1];
            if (b == pbend) {
                fwrite(printbuff, 1, b-printbuff, stdout);
                b = printbuff;
            }
        }
        *b++ = '\n';
        if (b == pbend) {
            fwrite(printbuff, 1, b-printbuff, stdout);
            b = printbuff;
        }
        // increment values
        int carry = 1;
        for (++p ; carry; ++p) {
            if ((*p += carry) > alphabetSize) {
                *p = 1;
                carry = 1;
            } else {
                carry = 0;
            }
        }
    }
    fwrite(printbuff, 1, b-printbuff, stdout);

    free(indices);
    free(printbuff);
}

Results

I modified your original driver program as follows:

int main(int argc, char *argv[])
{
    if (argc != 3) {
        puts("Usage: brute iterations old|new\n");
        return 1;
    }
    int iterations = atoi(argv[1]);
    if (argv[2][0] == 'o')
        bruteSequential(iterations);
    else
        brute2(iterations);
}

This allowed me to time various combinations. For example, on my computer, calculating all of the 5-character combinations took 55 seconds with this version and over 65 seconds for the original. Redirecting the output to /dev/null eliminates the overhead of actual disk I/O (5.2 gigabytes in this case) and reveals that the new version takes about 8.9 s on my machine, and the original version takes 18 seconds or about twice as long.

\$\endgroup\$
  • \$\begingroup\$ A modern optimising compiler will optimise iterating over an array with an index into iterating directly via pointers instead \$\endgroup\$ – Mark K Cowan Feb 20 '17 at 9:18
  • \$\begingroup\$ @MarkKCowan: I think you'll find that the compiler produces different code. When making the suggestion, I also timed the results and found that the use of pointers consistently provides a speed advantage. Other compilers and machines may produce different results; measuring is the way to find out which produces faster code. \$\endgroup\$ – Edward Feb 20 '17 at 13:33
  • \$\begingroup\$ It depends on the compiler of course, I'm using GCC v6.3.1 and checking the assembly it produces rather than benchmarking \$\endgroup\$ – Mark K Cowan Feb 20 '17 at 14:13
7
\$\begingroup\$

you don't need the memset in the for of bruteSequential you just need to add a '\0' to the end when max depth has been reached:

void bruteImpl(char* str, int index, int maxDepth)
{
    for (int i = 0; i < alphabetSize; ++i)
    {
        str[index] = alphabet[i];

        if (index == maxDepth - 1) 
            printf("%s\n", str);
        else bruteImpl(str, index + 1, maxDepth);
    }
}

void bruteSequential(int maxLen)
{
    char* buf = malloc(maxLen + 1);

    for (int i = 1; i <= maxLen; ++i)
    {
        buf[i]='\0';
        bruteImpl(buf, 0, i);
    }

    free(buf);
}

frankly you don't even need that as a simple buf[i]='\0'; in the for of bruteSequential will suffice, but that may over simplify it

\$\endgroup\$
  • \$\begingroup\$ You don't need to put the str[maxDepth]='\0'; in the loops either. You can move it out to after the malloc since it only needs to run once. \$\endgroup\$ – rolfl Jan 3 '14 at 13:26
  • \$\begingroup\$ @rolfl no because he creates shorter strings as well, so in that case 200_success' answer is correct \$\endgroup\$ – ratchet freak Jan 3 '14 at 14:15
  • 2
    \$\begingroup\$ Fair point, but, you can move it outside the recursion at least, and call it just maxLen times, instead of gazillions! \$\endgroup\$ – rolfl Jan 3 '14 at 14:25

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.