Memory Efficient Recursion

Question

Hi,

I have written an application in C# that generates all the words that can be existed in the combination of alphabets, numbers and few special characters.

The problem is that it isn't memory efficient as it is adapting Recursion and also some collection like List.

Is there any way I can make it to run in limited memory environment?

Umair

Answer 1

Convert it to an iterative function.

Answer 2

Well, you obviously cannot store the intermediate results in memory (unless you've got some sort of absurd computer at your disposal); you will have to write the results to disk.

The recursion depth isn't a result of the number of considered characters - its determined by what the maximum string length you're willing to consider.

For instance, my install of python 2.6.2 has it's default recursion limit set to 1000. Arguable, I should be able to generate all possible 1-1000 length strings given a character set within this limitation (now, I think the recursion limit applies to total stack depth, so the actual limit may be less than 1000).

Edit (added python sample): The following python snippet will produce what you're asking for (limiting itself to the given runtime stack limits):

from string import ascii_lowercase

def generate(base="", charset=ascii_lowercase):
    for c in charset:
        next = base + c
        yield next
        try:
            for s in generate(next, charset):
                yield s
        except:
            continue

for s in generate():
    print s

One could produce essentially the same in C# by try/catching on StackOverflowException. As I'm typing this update, the script is running, chewing up one of my cores. However, memory usage is constant at less than 7MB. Now, I'm only print to stdout since I'm not interested in capturing the result, but I think it proves the point above. ;)

Addendum to the example: Interesting note: Looking closer at running processes, python is actually I/O bound with the above example. It's only using 7% of my CPU, while the rest of the core is bound rending the results in my command window. Minimizing the window allows python to climb to 40% of total CPU usage, this is on a 2 core machine.

Answer 3

Unfortunately C# compiler does not perform tail call optimization, which is something that you want to happen in this case. CLR supports it, kinda, but you shouldn't rely on it.

Perhaps left of field, but maybe you can write the recursive part of your program in F#? This way you can leverage guaranteed tail call optimization and reuse bits of your C# code. Whilst a steep learning curve, F# is a more suitable language for these combinatorial tasks.

Answer 4

One more consideration: When you concatenate or use some other method to generate a string in C#, it occupies its own memory and may stick around for a while. If you are generating millions of strings, you are likely to notice some performance drag.

If you don't need to keep your many strings around, I would see if there's away to avoid generating the strings. For example, maybe you have a character array that you keep updating as you move through the character combinations, and if you're outputting them to a file, you would output them one character at a time so you don't have to build the string.

Answer 5

Well...I am not sure whom with I go amongst you but I got the solution. I am using more than one process one that is interacting with user and other for finding the words combination. The other process finds 5000 words, save them and quit. Communication is being achieved through WCF. This looks pretty fine as when process quits = frees memory.