Reducing memory usage for FizzBuzz in R

Question

I've been trying all night to get my fizzbuzz to use below 20 MB of RAM but I can't seem to get it much smaller than this.

# Sample code to read test cases
args <- commandArgs(trailingOnly=TRUE)
test.cases <- strsplit(readLines(args[[1]], warn=FALSE), '\n')
args <- NULL
for (test in test.cases) {
    if (length(test) > 0) {
        # ignore test if it is an empty line
        # 'test' represents the test case, do something with it
        test <- as.numeric(unlist(strsplit(test, " ")))
        x <- 0
        y <- 0
        for(i in 1: test[3]) {
            if(i != 1) cat(" ")
            flag <- TRUE
            out <- i
            x <- x + 1
            y <- y + 1 
            if( x == test[1] ) {
                cat("F")
                x <- 0
                flag <- FALSE
            }
            if( y == test[2] ) {
                cat("B")
                y <- 0
                flag <- FALSE
            }
            if(flag) cat(out)
        }

        cat("\n")
    }
}

Answer 1

Thanks for providing the link, it helped a lot in understanding what you were after. I will provide two versions for you to consider. The first one is algorithmically similar to yours, except written a little more in the "R style". The second one will make a more efficient use of memory since that seems to be important too.

I will also assume that the input file in args[[1]] is like the one in the link, i.e. contains lines like the two below:

3 5 10
2 7 15

Version 1:

args <- commandArgs(trailingOnly = TRUE)
input.file <- args[[1]]
test.cases <- strsplit(readLines(input.file, warn=FALSE), ' ')
for (test in test.cases) {
   stopifnot(length(test) == 3L)
   XYN <- as.integer(test)
   X <- XYN[1]
   Y <- XYN[2]
   N <- XYN[3]
   i <- seq_len(N)
   is.divisible.by.X <- (i %% X) == 0L
   is.divisible.by.Y <- (i %% Y) == 0L
   out <- as.character(i)
   out[is.divisible.by.X & is.divisible.by.Y] <- "FB"
   out[is.divisible.by.X] <- "F"
   out[is.divisible.by.Y] <- "B"
   cat(out, sep = " ")
   cat("\n")
}

Some noticeable improvements are:

1. some assumption checking with stopifnot
2. the use of variable names that are closer to the problem write-up (X, Y, N) or more descriptive, e.g., is.divisible.by.X
3. the use of %% for finding if a number is divisible by X or Y
4. vectorization (notice how one of your for loops is gone), which should make your code faster
5. The use of seq_len(N) instead of 1:N is more robust in the case when N is zero.

---

Version 2:

args <- commandArgs(trailingOnly = TRUE)
input.file <- args[[1]]
file.handle <- file(input.file, open = "r")
repeat {
   line <- readLines(file.handle, n = 1)
   if (length(line) == 0L) break  # end of file
   test <- strsplit(line, " ")[[1]]
   XYN <- as.integer(test)
   X <- XYN[1]
   Y <- XYN[2]
   N <- XYN[3]
   i <- 1L
   while (i <= N) {
      is.divisible.by.X <- (i %% X) == 0L
      is.divisible.by.Y <- (i %% Y) == 0L
      out <- if (is.divisible.by.X & is.divisible.by.Y) "FB" else
             if (is.divisible.by.X) cat("F") else
             if (is.divisible.by.Y) cat("B") else as.character(i)
      cat(out, "")
      i <- i + 1L
   }
   cat("\n")
}
close(file.handle)

How is that different from version 1? Here we are careful to read the file and process it line-by-line instead of reading the whole file in memory. Also, when processing each line, we are careful not to generate the seq_len(N) vector in memory and pre-compute the output for all the values. Instead, we are counting from 1 to N and processing each value one at a time.

Because version 2 uses a while loop in place of the vectorization happening in version 1, it will be slower. But it will use a lot less memory, especially if the file contains a large number of rows or large values for N, both things could make version 1 fail.

I hope this helps. Let me know if you have questions.

Answer 2

I was able to resolve it by simply removing the assignment of

out <- i

The total improvement was from 24621056 to 1662976.

args <- commandArgs(trailingOnly=TRUE)
test.cases <- strsplit(readLines(args[[1]], warn=FALSE), '\n')
args <- NULL
for (test in test.cases) {
    if (length(test) > 0) {
        # ignore test if it is an empty line
        # 'test' represents the test case, do something with it
        test <- as.numeric(unlist(strsplit(test, " ")))
        x <- 0
        y <- 0
        for(i in 1: test[3]) {
            if(i != 1) cat(" ")
            flag <- TRUE
            x <- x + 1
            y <- y + 1 
            if( x == test[1] ) {
                cat("F")
                x <- 0
                flag <- FALSE
            }
            if( y == test[2] ) {
                cat("B")
                y <- 0
                flag <- FALSE
            }
            if(flag) cat(i)
        }

        cat("\n")
    }
}