Сбор неизвестного числа результатов в цикле

Question

Что такое идиоматический способ сбора результатов в цикле в R, если количество конечных результатов неизвестно заранее? Вот игрушка пример:

results = vector('integer') 
i=1L 
while (i < bigBigBIGNumber) { 
    if (someCondition(i)) results = c(results, i) 
    i = i+1 
} 
results 

Проблема с этим примером является то, что (я предполагаю) он будет иметь квадратную сложность, как должен быть перераспределен на каждом Append вектор. (Это правильно?) Я ищу решение, которое позволяет избежать этого.

Я нашел Filter, но для этого требуется предварительная генерация 1:bigBigBIGNumber, которую я хочу избежать, чтобы сэкономить память. (Вопрос: действительно for (i in 1:N) также заранее создать 1:N и сохранить его в памяти?)

Я мог бы сделать что-то вроде список связаны, как это:.

results = list() 
i=1L 
while (i < bigBigBIGNumber) { 
    if (someCondition(i)) results = list(results, i) 
    i = i+1 
} 
unlist(results) 

(Обратите внимание, что это не конкатенация Это построив такую ​​структуру, как list(list(list(1),2),3), затем сплющивание с помощью unlist.)

Есть ли лучший способ, чем этот? Что такое идиоматический способ, который обычно используется? (Я очень новичок в R.) Я ищу предложение о том, как решить эту проблему. Предложения, как о компактном (легко писать), так и быстродействующем коде, приветствуются! (Но я хотел бы сосредоточиться на быстрой и эффективной памяти.)

Answer 1

Вот алгоритм, который удваивает размер списка вывода, как он заполняет, достигая несколько линейное время вычислений, как показывают эталонные тесты:

test <- function(bigBigBIGNumber = 1000) { 

    n <- 10L 
    results <- vector("list", n) 
    m <- 0L 
    i <- 1L 
    while (i < bigBigBIGNumber) { 
    if (runif(1) > 0.5) { 
     m <- m + 1L 
     results[[m]] <- i 
     if (m == n) { 
     results <- c(results, vector("list", n)) 
     n <- n * 2L 
     } 
    } 
    i = i + 1L 
    } 
    unlist(results) 
} 

system.time(test(1000)) 
# user system elapsed 
# 0.008 0.000 0.008 
system.time(test(10000)) 
# user system elapsed 
# 0.090 0.002 0.093 
system.time(test(100000)) 
# user system elapsed 
# 0.885 0.051 0.936 
system.time(test(1000000)) 
# user system elapsed 
# 9.428 0.339 9.776 

Answer 2

ближе ко второму вы перечислили:

results <- list() 
    for (i in ...) { 
     ... 
    results[[i]] <- ... 
} 

Обратите внимание, что i не нужно быть integer, может быть character, и т. д.

Кроме того, при необходимости вы можете использовать results[[length(results)]] <- ..., но если у вас уже есть итератор, вероятно, не будет.

Answer 3

Если вы не можете вычислить 1:bigBigNumber, подсчитайте записи, создайте вектор, затем заполните его.

num <- 0L 
i <- 0L 
while (i < bigBigNumber) { 
    if (someCondition(i)) num <- num + 1L 
    i <- i + 1L 
} 
result <- integer(num) 
num <- 0L 
while (i < bigBigNumber) { 
    if (someCondition(i)) { 
    result[num] <- i 
    num <- num + 1L } 
    i <- i + 1L 
} 

(. Этот код не тестировался)

Если вы можете вычислить 1:bigBigBIGNumber, это также будет работать:

Я предполагаю, что вы хотите, чтобы вызвать функцию, а не просто лавировать на сами индексы. Нечто подобное может быть ближе к тому, что вы хотите:

values <- seq(bigBigBIGNumber) 
sapply(values[someCondition(values)], my_function) 

Answer 4

Предположительно, максимальный размер, который вы готовы терпеть; предварительно распределить и заполнить этот уровень, а затем обрезать, если необходимо. Это позволяет избежать риска не удовлетворить требование удвоения размера, даже если потребуется небольшой объем памяти; он не срабатывает раньше и включает только одно, а не перераспределение log (n). Вот функция, которая принимает максимальный размер, функцию генерации и токен, возвращаемый функцией генерации, когда нет ничего, что можно было бы генерировать.Мы получаем до п результатов, прежде чем вернуться

filln <- 
    function(n, FUN, ..., RESULT_TYPE="numeric", DONE_TOKEN=NA_real_) 
{ 
    results <- vector(RESULT_TYPE, n) 
    i <- 0L 
    while (i < n) { 
     ans <- FUN(..., DONE_TOKEN=DONE_TOKEN) 
     if (identical(ans, DONE_TOKEN)) 
      break 
     i <- i + 1L 
     results[[i]] <- ans 
    } 

    if (i == n) 
     warning("intolerably large result") 
    else length(results) <- i 
    results 
} 

Вот генератор

fun <- function(thresh, DONE_TOKEN) { 
    x <- rnorm(1) 
    if (x > thresh) DONE_TOKEN else x 
} 

и в действии

> set.seed(123L); length(filln(10000, fun, 3)) 
[1] 163 
> set.seed(123L); length(filln(10000, fun, 4)) 
[1] 10000 
Warning message: 
In filln(10000, fun, 4) : intolerably large result 
> set.seed(123L); length(filln(100000, fun, 4)) 
[1] 23101 

Мы можем бенчмарк накладные расходы, примерно, по сравнению с чем-то, что знает, в укажите, сколько места потребуется

f1 <- function(n, FUN, ...) { 
    i <- 0L 
    result <- numeric(n) 
    while (i < n) { 
     i <- i + 1L 
     result[i] <- FUN(...) 
    } 
    result 
} 

Здесь мы проверить время и стоимость одного результата

>  set.seed(123L); system.time(res0 <- filln(100000, fun, 4)) 
    user system elapsed 
    0.944 0.000 0.948 
>  set.seed(123L); system.time(res1 <- f1(23101, fun, 4)) 
    user system elapsed 
    0.688 0.000 0.689 
> identical(res0, res1) 
[1] TRUE 

, который в этом примере является, конечно, затмеваемого простым вектором раствора (ов)

set.seed(123L); system.time(res2 <- rnorm(23101)) 
identical(res0, res2)