Duncan Murdoch wrote:
Maximilian Kofler wrote:
Duncan Murdoch <murdoch.duncan <at> gmail.com> writes:
I doubt if that was the error message. More likely you saw
Error: evaluation nested too deeply: infinite recursion /
options(expressions=)?
Exactly this was the error message I recieved
This isn't a case of the source being nested to deeply, but rather of the
evaluation being nested too deeply.
This happens in recursive algorithms when R runs out of
stack space, around 5000 calls deep. Is it likely in your dataset that
a recursion depth of 5000 is reasonable? In most cases this indicates a
programming error that leads to an infinite recursion, but there are
probably cases where a depth like that is reasonable.
I don't think that it is a programming error, because I succeyyfully
calculated subgraph isomirphism with the algorithm, but with
smaller input graphs.
The programming error might be in the design, not the implementation.
For example, you can sum a vector like this:
I've taken a look at your original functions, and I can't spot cases as
obvious as the one below, so there isn't going to be a quick fix for
this. Here are my suggestions:
- Name your functions meaningfully. You named them refine1 to refine9,
so it's not at all obvious what they are trying to do.
- Use nested functions. You are passing lots of arguments in every
function call, e.g.
refine1 <- function(M, A, B, p_A, p_B, FAIL, elim, i, j, k, sc, h, lst, x){
#print("refine 1")
# elim marks if there was eliminated a 1 (and changed to 0)
lst <- vector(mode = "numeric")
elim <- 0
i <- 1
refine2(M, A, B, p_A, p_B, FAIL, elim, i, j, k, sc, h, lst, x)
}
The call to refine2 uses exactly the same values of M, A, B, p_A, p_B, FAIL, j,
k, sc, h and x as were passed to refine1. Those
might be good candidates to be variables in a big outside function, with
refine1 being nested within it, e.g.
refine <- function(M, A, B, p_A, p_B, FAIL, j, k, sc, h, x) {
refine1 <- function() {
lst <- ...
elim <- 0
i <- 1
refine2(elim, i, lst)
}
etc.
which might make it easier to read and fix. Doing this won't reduce the depth
of nesting of your functions, but it will save
some memory (and maybe some protection stack) and will make your functions
easier to read, so perhaps you can recognize what's wrong. (It does make
things slightly harder to debug: you can't say debug(refine1) outside of the
refine(), but you can use setBreakpoint() to set a breakpoint in it.)
Duncan Murdoch
badSum <- function(x) {
if (length(x) > 1) x[1] + badSum(x[-1])
else x
}
and you'll get the right result for vectors of lengths from 1 up to
around length 5000, but not for bigger ones. The solution in some
languages is to recognize when recursion is being used unnecessarily and
to optimize it away, but R doesn't do that. So the programmer has to
recognize when recursion isn't really needed and rewrite the function to
work without it. For example, in the case above, we don't need x after
extracting x[1], so there's no need to make a new call to badSum (which
preserves it). Just turn it into a loop:
notsobadSum <- function(x) {
result <- x[1]
while (length(x) > 1) {
x <- x[-1]
result <- result + x[1]
}
result
}
(This is still a bad way to compute a sum in R, it is just a simple
illustration).
So the algorithm seems to work.
I already tried to set options(expressions=500000), but
then I cause a protection stack overflow:
error: protect(): protection stack overflow
Is the problem that too many objects are stored in the stack?
Too many stack frames. You're not running out of memory, you're running
out of a particular type of memory. When you set expressions to 500000
you just started to run out of a different resource. The help page
?options tells you how to work around that one, but I suspect you really
need to rewrite your functions so they only recurse
when they need to.
Duncan Murdoch
If yes, somebody knows how to solve this
problem?
thanks for your replies
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
