Расчет квантилей для больших данных

Есть как минимум три варианта:

1. Вы уверены, что он должен быть из полного комплекта? 10% выборка здесь должна быть очень хорошим приближением.
2. 300 000 элементов — это не так уж и много для вектора, но матрица-столбец размером 300 000 x 100+ — это очень много. Вытащите в память только нужный вам столбец, а не всю матрицу (при необходимости можно повторить для каждого столбца).
3. Do it sequentially, possibly in conjunction with a smaller sample to get you started in the right ballpark. For the 5th percentile, you just need to know how many items are above the current guess and how many are below. So something like:
   1. Take a 1% sample, find the 5th percentile of it. Jump some tolerance above and below, such that you're sure the exact 5th percentile lies in that range.
   2. Читать в матрице кусками. Для каждого фрагмента подсчитайте количество наблюдений выше диапазона и ниже диапазона. Затем сохраните все наблюдения, лежащие в пределах диапазона.
   3. Когда вы прочитали последний фрагмент, у вас теперь есть три фрагмента информации (счет вверху, счет внизу, вектор наблюдений внутри). Один из способов получить квантиль — отсортировать весь вектор и найти n-е наблюдение, и вы можете сделать это с приведенными выше фрагментами информации: отсортировать наблюдения в пределах диапазона и найти (n-count_below)th.

Изменить: пример (3).

Обратите внимание, что я не лучший разработчик алгоритмов и что кто-то почти наверняка разработал для этого лучший алгоритм. Кроме того, эта реализация не особенно эффективна. Если для вас важна скорость, рассмотрите Rcpp или даже более оптимизированный для этого R. Создавать кучу списков, а затем извлекать из них значения не так уж и умно, но прототипировать таким образом было легко, поэтому я пошел по этому пути.

library(plyr)

set.seed(1)

# -- Configuration -- #
desiredQuantile <- .25

# -- Generate sample data -- #

# Use some algorithm (sampling, iteration, or something else to come up with a range you're sure the true value lies within)
guessedrange <- c( .2, .3 )
# Group the observations to correspond to the OP's files
dat <- data.frame( group = rep( seq(100), each=100 ), value = runif(10000) )

# -- Apply the algorithm -- #

# Count the number above/below and return the values within the range, by group
res <- dlply( dat, .( group ), function( x, guessedrange ) {
  above <- x$value > guessedrange[2]
  below <- x$value < guessedrange[1]
  list(
    aboveCount  = sum( above ),
    belowCount = sum( below ),
    withinValues = x$value[ !above & !below ]
  )
}, guessedrange = guessedrange )
# Exract the count of values below and the values within the range
belowCount <- sum( sapply( res, function(x) x$belowCount ) )
belowCount
withinValues <- do.call( c, sapply( res, function(x) x$withinValues ) )
str(withinValues)
# Count up until we find the within value we want
desiredQuantileCount <- floor( desiredQuantile * nrow(dat) ) #! Should fix this so it averages when there's a tie
sort(withinValues)[ desiredQuantileCount - belowCount + 1 ]
# Compare to exact value
quantile( dat$value, desiredQuantile )

В конце концов, значение немного отличается от точной версии. Я подозреваю, что меня сбило с толку одно или какое-то столь же глупое объяснение, но, возможно, я упускаю что-то фундаментальное.