4
\$\begingroup\$

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")
    }
}
\$\endgroup\$
  • \$\begingroup\$ I was able to resolve it by simply removing the assignment of out <- i \$\endgroup\$ – DaveGerson Apr 15 '15 at 5:37
  • \$\begingroup\$ Welcome to CodeReview, DaveGerson. \$\endgroup\$ – Legato Apr 15 '15 at 7:31
  • \$\begingroup\$ Your code does not create any significant data other than the one read through readLines so it is unclear what the problem is. I really doubt that removing out <- i is really what made a difference. It is not one variable holding an integer that will make a difference. \$\endgroup\$ – flodel Apr 15 '15 at 23:22
  • \$\begingroup\$ I think it has something to do with how code-eval calculates memory. It seems like all assignments are added to the memory usage for the algorithm. I've tried destroying objects throughout the code in order to lessen the total memory usage but it doesn't have any effect. \$\endgroup\$ – DaveGerson Apr 15 '15 at 23:26
  • \$\begingroup\$ the inputs here are a string like the following "x y z". x in this case is fizz, y is buzz, and z is how high you count to. \$\endgroup\$ – DaveGerson Apr 15 '15 at 23:28
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the solution @flodel. I will test this code out tonight and see what the memory usage is. \$\endgroup\$ – DaveGerson Apr 21 '15 at 15:34
0
\$\begingroup\$

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")
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.