All,
I am writing a generic peg board (solitaire) solver. There is some CS theory that I haven't researched yet, so for now this is brute force. The issue I am facing is balancing speed and memory since this is a generic solver and can't be optimized for a specific case.

The current method I intend to use starts out requiring only very little memory, peaks half way through the solution, and then tapers off. It looks a little bit like this:

my $old_work = get_initial_work(); # hash reference
my $new_work = {};
while (%$old_work) {
    for my $item (keys %$old_work) {
        my $job = delete $old_work->{$item};
        for (new_work($job)) {
            $new_work{$item . $_} = $_;
        }
    }
    ($new_work, $old_work) = ({}, $new_work);
}
[download]

While I can easily determine the upper boundary memory requirement for any board, I can't know for sure how close to that boundary the code will actually get. One way to approach this would be to allow the user indicate the maximum amount of memory they are willing to spend and if the upper boundary exceeds that amount - resort to BerkeleyDB. This is an "all or none" approach.

I can improve upon this a bit because I can calculate the upper boundary memory requirement for each pass through the work process. I can switch between in-memory and BerkeleyDB as soon as I know I might exceed the user-defined threshold and then revert as soon as I know that I won't. This is a "per-pass" approach and is the strategy I plan on using at the moment.

What I would like to do however is make the switch only if I actually do approach the limit. So I would need to know the memory consumed by ($old_work + $new_work) and have a way of switching to BerkeleyDB. For now I am knowingly ignoring lots of details such as Perl not necessarily freeing memory to the OS. What I am interested in knowing is:

• Is there a sane way of determining memory consumption of a running program from within that program?
• Will Devel::Size tell me how much memory just $old_work and $new_work are using?
• Is there a smart way to load all they key/val pairs of an existing hash ref into a BerkeleyDB when it is initialized?

The reason I would like to do this is that many board configurations are likely impossible due to the constraints of the game. Only valid configurations are visited so the actual memory consumption may never approach the upper boundary and keeping things in memory will certainly be faster. Thanks in advance for your time and consideration in this matter.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.