Добавляйте последовательные элементы вектора до значения

Question

Я хотел бы рассчитать минимальное количество последовательных элементов в векторе, которое при добавлении (последовательно) будет меньше заданного значения.

Например, в следующем векторе

ev<-c(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 2.7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3.27, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 370.33, 1375.4, 
1394.03, 1423.8, 1360, 1269.77, 1378.8, 1350.37, 1425.97, 1423.6, 
1363.4, 1369.87, 1365.5, 1294.97, 1362.27, 1117.67, 1026.97, 
1077.4, 1356.83, 565.23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 356.83, 
973.5, 0, 240.43, 1232.07, 1440, 1329.67, 1096.87, 1331.37, 1305.03, 
1328.03, 1246.03, 1182.3, 1054.53, 723.03, 1171.53, 1263.17, 
1200.37, 1054.8, 971.4, 936.4, 968.57, 897.93, 1099.87, 876.43, 
1095.47, 1132, 774.4, 1075.13, 982.57, 947.33, 1096.97, 929.83, 
1246.9, 1398.2, 1063.83, 1223.73, 1174.37, 1248.5, 1171.63, 1280.57, 
1183.33, 1016.23, 1082.1, 795.37, 900.83, 1159.2, 992.5, 967.3, 
1440, 804.13, 418.17, 559.57, 563.87, 562.97, 1113.1, 954.87, 
883.8, 1207.1, 1046.83, 995.77, 803.93, 1036.63, 946.9, 887.33, 
727.97, 733.93, 979.2, 1176.8, 1241.3, 1435.6)

Какое минимальное количество элементов, которое при последовательном добавлении (как в порядке в векторе) будет суммироваться, скажем, 20000

Для большей ясности мне нужно следующее: Начните с ev [1] и добавляйте последовательно до 20000. Запишите количество элементов, которое вы должны были добавить, чтобы получить 20000 как r [1]. Затем начните с ev [2] и добавьте до 20000 и так далее. Записал количество элементов, которые вы должны были добавить до 20000 как r [2]. Сделайте это на всю длину ев. Затем верните мин (г)

Например

j<-c(1, 2, 3, 5, 7, 9, 2).

Я хочу минимальное количество элементов, которое при последовательном добавлении дает, скажем,> 20. Это должно быть 3 (5 + 7 + 9)

Большое спасибо

Answer 1

Хорошо, я сделаю снимок: этот найдет длину минимальной последовательности чисел которые составляют до или выше max. Он не претендует на быструю скорость, но имеет O(2n) сложность по времени:

Я заставил его вернуть и начальный индекс, и длину.

f <- function(x, max=10) {
  s <- 0
  len <- Inf
  start <- 1
  j <- 1
  for (i in seq_along(x)) {
     s <- s + x[i]
     while (s >= max) {
       if (i-j+1 < len) {
         len <- i-j+1
         start <- j
       }
       s <- s - x[j]
       j <- j + 1
     }
  }

  list(start=start, length=len)
  # uncomment the line below if you don't need the start index...
  #len
}

r <- f(ev, 20000) # list(start=245, length=15)
sum(ev[seq(r$start, len=r$length)]) # 20275.42

# Test speed:
x <- sin(1:1e6)

system.time( r <- f(x, 1.9) ) # 1.54 secs

# Compile the function makes it 9x faster...
g <- compiler::cmpfun(f)
system.time( r <- g(x, 1.9) ) # 0.17 secs

Answer 2

library(zoo) # Needed for rollapply
N <- 20000 # The desired sum we want to achieve
j <- 0
for(i in 1:length(ev)){
    k <- rollapply(ev, i, sum)
    j[i] <- max(k)
    if(j[i] >= N){
        break
    }
}
i # contains how many consecutive elements you need to sum (15)
j[i] # contains the corresponding sum(20275.42)

В настоящее время это не говорит вам, где конкретное подмножество находится в векторе, но другое использование rollapply может получить эту информацию.

Есть другие способы сделать это, но если у вас естьдействительно длинный вектор вырвется из цикла, так что вы не рассчитываете больше, чем нужно.Основная идея состоит в том, чтобы использовать rollapply для создания вектора последовательных сумм длины k, а затем найти максимум этого.Если это меньше, чем мы хотим сделать то же самое для сумм длины k + 1.Повторяйте до тех пор, пока мы не найдем сумму, превышающую желаемый порог.

Редактировать:

Похоже, что это примерно в 100 раз быстрее.Я не сравнивал его с ответом Томми (который, вероятно, быстрее, чем этот, но это обеспечит значительное ускорение по сравнению с моим первоначальным методом.

Правка 2: перемещение [-n] и удаление предупреждений ускоряет этосовсем немного.

myfun <- function(ev, N){
    i <- 1
    n <- length(ev)
    j <- ev
    repeat{
        j <- (j[-n] + ev[-c(1:i)])
        i <- i+1
        n <- n-1
        if(max(j) >= N | i > length(ev)){
            break;
        }
    }
    return(i)
}

myfun(ev, 20000)

# And stealing the idea from Tommy gives a nice speedup as well
myfuncomp <- compiler:cmpfun(myfun)
myfuncomp(ev, 20000)
myfunc3 <- compiler:cmpfun(myfun, options = list(optimize = 3))
myfunc3(ev, 20000)

library(rbenchmark) # For testing
# If you have Tommy's functions loaded as f and g you can compare
benchmark(f(ev, 20000), g(ev, 20000), myfun(ev, 20000), myfuncomp(ev, 20000), myfunc3(ev, 20000))

Answer 3

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

x=1:length(ev)
 plot(x,ev)
 lxy <- loess(ev~x )
 lines(predict(lxy, x=1:length(y)))
 title(main="loess() fit of ev")

Но в области наиболее плотных значений значения довольно плоские.

 x=1:length(y); y=c(356.83, 
 973.5, 0, 240.43, 1232.07, 1440, 1329.67, 1096.87, 1331.37, 1305.03, 
 1328.03, 1246.03, 1182.3, 1054.53, 723.03, 1171.53, 1263.17, 
 1200.37, 1054.8, 971.4, 936.4, 968.57, 897.93, 1099.87, 876.43, 
 1095.47, 1132, 774.4, 1075.13, 982.57, 947.33, 1096.97, 929.83, 
 1246.9, 1398.2, 1063.83, 1223.73, 1174.37, 1248.5, 1171.63, 1280.57, 
 1183.33, 1016.23, 1082.1, 795.37, 900.83, 1159.2, 992.5, 967.3, 
 1440, 804.13, 418.17, 559.57, 563.87, 562.97, 1113.1, 954.87, 
 883.8, 1207.1, 1046.83, 995.77, 803.93, 1036.63, 946.9, 887.33, 
 727.97, 733.93, 979.2, 1176.8, 1241.3, 1435.6)

 lxyhi <- loess(y~x)
 plot(x,y)
 lines(predict(lxyhi, x=1:length(y)))

Answer 4

ты имеешь в виду что-то подобное?

> sum(ifelse(cumsum(ev)<=200000, 1, 0))
[1] 364