Snake partition performance

Start by setting up the snake partition

nproc <- 4
nfile <- 16
nrep <- ceiling(nfile / nproc / 2)
snakeseq <- rep(c(seq(1,nproc), seq(nproc,1)), nrep)[1:nfile]

Now a function to generate file sizes randomly, perform the partition, and report the total size assigned to each process.

partition <- function(random=FALSE) {
    sizes <- runif(nfile, 5, 20)
    if(!random) {
        sizes <- sort(sizes, decreasing=TRUE)
    }
    sapply(seq(1,nproc), function(i) {
        sum(sizes[snakeseq==i])
    })
}

This function calculates the Gini index of the assignments

gini <- function(sizes) {
    meansize <- mean(sizes)
    n <- length(sizes)
    combos <- expand.grid(sizes, sizes)
    num <- sum(abs(combos[[1]] - combos[[2]]))
    num / (2*n*n*meansize)
}

Now compute a bunch of them and get the distribution of Gini coefficients. Do the same for random values.

gsnake <- sapply(seq(1,250), function(i) {
    gini(partition())
})
grandom <- sapply(seq(1,250), function(i) {
    gini(partition(TRUE))
})

Distribution of Gini coefficients for the size partitions.

library(ggplot2)
pltdata <- data.frame(snake=gsnake, random=grandom)
ggplot(data=pltdata) + 
    geom_density(mapping=aes(x=snake, color='snake')) + 
    geom_density(mapping=aes(x=random, color='random')) +
    xlab('Gini coefficient of distribution') +
    ggthemes::theme_solarized_2(light=FALSE) + 
    ggthemes::scale_color_solarized()

cat('Random partition\n')

Random partition

mean(grandom)

[1] 0.0751094

quantile(grandom, c(0.025, 0.975))

      2.5%      97.5% 
0.02214389 0.14303694 

cat('Snake partition\n')

Snake partition

mean(gsnake)

[1] 0.01267433

quantile(gsnake, c(0.025, 0.975))

       2.5%       97.5% 
0.002984605 0.027710777