Skip to content

Instantly share code, notes, and snippets.

@primaryobjects
Last active December 8, 2020 22:03
Show Gist options
  • Save primaryobjects/8755398629a4e2ef74dd to your computer and use it in GitHub Desktop.
Save primaryobjects/8755398629a4e2ef74dd to your computer and use it in GitHub Desktop.
Map Reduce example in R. Demonstrates applying a map and reduce function to an input array, resulting in a hash of key/value pairs. This example maps a method to find prime divisors of each input value and then reduces the result by summing the input value for each prime divisor. See demo at http://www.r-fiddle.org/#/fiddle?id=tyir23SG&version=1
is.prime <- function(num) {
if (num == 2) {
TRUE
} else if (any(num %% 2:(num-1) == 0)) {
FALSE
} else {
TRUE
}
}
divisors <- function(x){
# Vector of numberes to test against
y <- seq_len(x)
# Modulo division. If remainder is 0 that number is a divisor of x so return it
y[ x%%y == 0 ]
}
primeDivisors <- function(input) {
# Get divisors of the value.
d <- divisors(input)
# Get only those divisors that are prime.
d[sapply(d, is.prime) == TRUE]
}
mapReduce <- function(input, map, reduceFunc) {
# Apply the map function to the input.
intermediate <- sapply(input, function(i) {
results <- map(i)
# Format the result as (result, input).
sapply(results, function(r) {
list(r, i)
})
})
# Apply the reduce function to the intermediate result.
reduce(intermediate, reduceFunc)
}
reduce <- function(input, reduceFunc) {
# Reduce values to a hash by key.
hash <- new.env()
# Iterate over the input.
sapply(input, function(i) {
# Unlist the mapReduce result, so we look at each key/value pair.
a <- unlist(i)
# Iterate over the key/value pairs in the first group.
sapply(seq(from=1, to=length(a), by=2), function(index) {
# Get the key.
key <- as.character(a[index])
# Get the value.
value <- a[index + 1]
# Initialize the hash value.
if (is.null(hash[[key]])) {
hash[[key]] <- 0
}
# Apply reduce method to the existing hash value for the key and the new value.
#hash[[key]] <- hash[[key]] + value
hash[[key]] <- reduceFunc(hash[[key]], value)
})
})
hash
}
#
# The map function takes an integer i and produces the list of pairs (p,i) such that p is a prime divisor of i. For example, map(12) = [(2,12), (3,12)].
# The reduce function is addition. That is, reduce(p, [i1, i2, ...,ik]) is (p,i1+i2+...+ik).
#
# Detail: The map function returns a list of prime divisors for the input. For example, for 15, the prime divisors are 3 and 5.
# The reduce function joins the same prime divisors together by summing their original inputs.
# For example, for the prime divisor 2, we add 24 + 30 = 54, resulting in a hash of [2, 54].
#
# Compute the output, if the input is the set of integers 15, 21, 24, 30, 49.
#
# Input: 15, 21, 24, 30, 49
#
# map(15) = [(3, 15), (5, 15)]
# map(21) = [(3, 21), (7, 21)]
# map(24) = [(2, 24), (3, 24)]
# map(30) = [(2, 30), (3, 30), (5, 30)]
# map(49) = [(7, 49)]
#
# reduce(2, 54)
# reduce(3, 90)
# reduce(5, 45)
# reduce(7, 70)
#
m <- mapReduce(c(15, 21, 24, 30, 49), primeDivisors, sum)
# Show result.
sapply(ls(m), function(key) {
m[[key]]
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment