Collect cout or output as vector in recursive function

Question

I have a recursive function that prints a some in nodes in a tree as integer ids. After exporting the function to R, I cannot use the cout output for anything (or so it seems). What would be ideal is if (1) I can return the output as a vector or (2) parse the cout inside R without losing too much speed.

I would insert some code here but my function is particularly generic. Essentially I'm trying to return, say, the Fibonacci sequence as a vector instead of a sum but through a recursive function without using global or static variables.

For example, fib(6) would return inside R as:

[1] 0 1 1 2 3 5

So one could,

y <- fib(6)

y[4] and y[4:5] would return respectively,

[1] 2

[1] 2 3

Thanks in advance for insights and ideas in problem solving. Using a static variable was as far as I got on my own.

Do you mean "count" in both places or is "cout" a term of art? Just wondering — lawyeR, Feb 07 '15 at 16:35
@lawyeR No, he means `cout`. Google it. (And I don't think you can catch it as a return value for R. But I might be wrong.) — Roland, Feb 07 '15 at 16:37
Between the two options (vector vs capture output), I would recommend returning a vector using Rcpp, perhaps as `NumericVector`. It will be considerably faster than parsing it out manually. — r2evans, Feb 07 '15 at 16:42

score 3 · Answer 1 · answered Feb 07 '15 at 18:02

3

I discuss this problem at length with different hashing and memoization implementation in both R and C++ in chapter one of the Rcpp book.

answered Feb 07 '15 at 18:02

Dirk Eddelbuettel

360,940
56
644
725

score 1 · Answer 2 · answered Feb 07 '15 at 16:47

You should read this online book http://adv-r.had.co.nz/, and mostly the memoization part where your question is partly answered http://adv-r.had.co.nz/Function-operators.html:

Just add the function fib3 such as:

library(memoise)

fib2 <- memoise(function(n) {
  if (n < 2) return(1)
  fib2(n - 2) + fib2(n - 1)
})

fib3 <- memoise(function(n) sapply(1:n, fib2))

#> fib3(6)
#[1]  1  2  3  5  8 13

nrussell · Answer 3 · 2015-02-07T20:23:16.627

Just for fun, a slightly more involved approach that uses std::generate_n and a function object (fseq) in lieu of sapply:

#include <Rcpp.h>

struct fseq {
  public: 
    fseq() {
      current = 0;
    }

    int operator()() {
      int val = fib(current);
      current++;
      return val;
    }

    int fib(int n) {
      if (n==0) return 0;
      if (n==1) return 1;
      return fib(n-2) + fib(n-1);
    }

  private:
    int current;
};

// [[Rcpp::export(".fib")]]
int fib(int n) {
  if (n==0) return 0;
  if (n==1) return 1;
  return fib(n-2) + fib(n-1);
}

// [[Rcpp::export]]
std::vector<int> fib_seq(const int n) {
  if (n < 1) throw std::invalid_argument("n must be >= 1");

  std::vector<int> seq;
  seq.reserve(n);

  std::generate_n(std::back_inserter(seq), n, fseq());
  return seq;
}

library(microbenchmark)
##
R>  fib_seq(6)
[1] 0 1 1 2 3 5

R>  all.equal(fib_seq(6),.fib_seq(6))
[1] TRUE

.fib_seq <- function(n) sapply(0:(n-1), .fib)
##
R>  microbenchmark(
    fib_seq(6),.fib_seq(6),
    times=1000L,unit="us")
Unit: microseconds
        expr    min      lq      mean median      uq      max neval
  fib_seq(6)  1.561  1.9015  3.287824  2.108  2.3430 1046.021  1000
 .fib_seq(6) 27.239 29.0615 35.538355 30.290 32.8065 1108.266  1000

R>  microbenchmark(
    fib_seq(15),.fib_seq(15),
    times=100L,unit="us")
Unit: microseconds
         expr    min      lq     mean  median      uq     max neval
  fib_seq(15)  6.108  6.5875  7.46431  7.0795  7.7590  20.391   100
 .fib_seq(15) 57.243 60.7195 72.97281 63.8120 73.4045 231.707   100

R>  microbenchmark(
    fib_seq(28),.fib_seq(28),
    times=100L,unit="us")
Unit: microseconds
         expr      min       lq     mean   median       uq      max neval
  fib_seq(28) 2134.861 2143.489 2222.018 2167.364 2219.400 2650.854   100
 .fib_seq(28) 3705.492 3721.586 3871.314 3745.956 3852.516 5040.827   100

Note that these functions were parametrized to reflect your statement

For example, fib(6) would return inside R as:

[1] 0 1 1 2 3 5

Collect cout or output as vector in recursive function

3 Answers3