current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 10 down vote favorite
2

This is a simple brute force algorithm I have in C. All the program does it 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;
}
share|improve this question
    
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 :). –  Corbin Jan 3 at 4:41
    
@Corbin I edited in the purpose of the code. Also Wikipedia says it is an algorithm ;) –  syb0rg Jan 3 at 4:48
1  
Another way to think about the problem is as counting in base 62. However, that doesn't necessarily yield better code. –  200_success♦ Jan 3 at 21:00
    
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. –  Pinoniq May 5 at 15:19
add comment

3 Answers

up vote 10 down vote accepted

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.

share|improve this answer
add comment
up vote 6 down vote

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.

share|improve this answer
2  
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. –  syb0rg Jan 4 at 20:18
add comment
up vote 3 down vote

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

share|improve this answer
    
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. –  rolfl♦ Jan 3 at 13:26
    
@rolfl no because he creates shorter strings as well, so in that case 200_success' answer is correct –  ratchet freak Jan 3 at 14:15
1  
Fair point, but, you can move it outside the recursion at least, and call it just maxLen times, instead of gazillions! –  rolfl♦ Jan 3 at 14:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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