Find parse tree for sentence blows up my computer!

[watdahel]

struct Derivation {
public:
vector< string > parse_tree;
vector< string > tree_list;
};

queue< Derivation > fringe;




This is a parsing project I'm working on. Basically, given a sentence, find a parse tree using a bottom-up algorithm. Initially, a sentence is tokenized and put into the tree_list member of a Derivation object. This object is then put into the fringe. Another function pops the objects from the fringe and expands that "node," if possible, according to grammar, by creating new Derivation objects each containing possible derivation of the previous string and these new objects are placed in the fringe for further expansion later on.

My problem is with sentences with four or more words in it. It runs indefinitely until the program crashes. I have 512MB of memory and I monitored the consumption and the program quickly eats it all up and starts using the harddisk. A few moments later the program crashes. I'm pretty sure it's related to this memory problem.

Now, the fringe grows to contain nearly 100,000 Derivation objects when the program crashes. Do vectors occupy that much memory? Would using a string array use less memory? What can I do? Perhaps this is a losing battle for my current 512 MB memory?

 

[agnitrate]

lol i doubt it is a memory problem.

did you ever think your program has an infinite loop or some other massive error causing it to do this?

-silver

 

[mugs]

Originally posted by: agnitrate
did you ever think your program has an infinite loop or some other massive error causing it to do this?

 

[AFB]

This would never happen in Java



















































😉😛 j/k


Like he said, you probably have an infinite loop or something.

 

[watdahel]

It does sound like my program has errors but it works for some 4 words sentence and everything less than 4. The partial parse tree produced is accurate but never finishes because of the memory. Once it starts using virtual memory it pretty much slows down.

 

[mugs]

Originally posted by: erwin1978
It does sound like my program has errors but it works for some 4 words sentence and everything less than 4. The partial parse tree produced is accurate but never finishes because of the memory. Once it starts using virtual memory it pretty much slows down.

Post your code if you can't figure it out.

 

[watdahel]

#include <iostream>
#include <string>
#include <queue>
#include <vector>


struct Derivation2
{
vector< string > parse_tree;
vector< string > tree_list;
};

int main()
{

...

queue< Derivation2 > array2;

Derivation2 d2;
for( int x = 0; x < 80000 ; x++ ) {
d2.parse_tree.push_back( "hello" );
d2.tree_list.push_back( "hello" );
array2.push( d2 );
}




...
}




Can anyone explain why declaring d2 outside the for-loop uses more memory than when I declared it inside the for-loop?