Как получение средних величин треугольного массива, не используя условные

Я строю массив (20x20) для курсоров, которые должны быть использованными ниже в Колебании Scorecard.

Чтобы осуществлять соответствующие оценки, он берется diagonal стоимость которых - полученные результаты исторических.

Со счастьем diagonal они получаются promedios чтобы получать треугольный нижний массив: lower треугольный matrix

Для того, чтобы отобразила предыдущее здесь маленькая схема:

introducir la descripción de la imagen aquí

Ввиду того, что массив относительно маленький (20x20) он действительный использовать атаку грубой силы

promedioMatrizTriangular <- function(diagonal){
    len <- length(diagonal)
    m <- matrix(0, nrow=len, ncol = len)
    m <- diag(diagonal)

    for (j in 1:len) {        # columnas
        for (i in 1:len){     # filas

            if(i>j) m[i,j]<-mean(diagonal[j:i]) 

        }
    }

    round(m, digits = 1)
}

Скроллируя предыдущую функцию с диагональю, показанной в предварительной схеме, он имеется:

promedioMatrizTriangular(c(9,11,8,5))

     [,1] [,2] [,3] [,4]
[1,]  9.0  0.0  0.0    0
[2,] 10.0 11.0  0.0    0
[3,]  9.3  9.5  8.0    0
[4,]  8.2  8.0  6.5    5

А именно функционируй, но..., если имелся массив 1000x1000 это подразумевало бы выполнять if(i>j) миллион раз.

Тогда для ответа, любой подход, который был бы использован и который поддержит в сокращение этого миллиона операций, будет принят как стоившая.

Nota: Algunas aplicaciones prácticas de la matriz triangular:

2
задан 14.03.2019, 20:48
3 ответа

Рассуждения

В этом случае funci¦n promedioMatrizTriangular у него есть цена computacional O(n²), у этого нет значительного попадания, если длина диагонали (n) упорствует в стоимости pequeños.

, Когда наблюдается структура массива (4x4), ценит в себе, что нет операций mean в última колонна, это подразумевает, что индекс j идет от 1 до len-1.

С другой стороны, у линий sà - есть операции в última их, а именно: i=len.

Также предоставляет себе важную информацию внутри if: i>j это, прибавленное к факту, что разрывы в линиях массива благоразумные и как в этом случае их de uno a uno, возможно утверждать, что i=j+1.

Предыдущее может случаться следующего способа:

, Когда j=1, индекс i начинается в линии 2, и когда j=len-1, имеется i=len.

Вариант

Тогда из-за выставленный c¦digo quedar¦ - в as¦-:

promedioMatrizTriangular <- function(diagonal){
    len <- length(diagonal)
    m <- matrix(0, nrow=len, ncol = len)
    m <- diag(diagonal)

    for (j in 1:(len-1)) {        # columnas
        for (i in (j+1):len){     # filas

            m[i,j]<-mean(diagonal[j:i]) 

        }
    }

    round(m, digits = 1)
}

promedioMatrizTriangular(c(9,11,8,5))

     [,1] [,2] [,3] [,4]
[1,]  9.0  0.0  0.0    0
[2,] 10.0 11.0  0.0    0
[3,]  9.3  9.5  8.0    0
[4,]  8.2  8.0  6.5    5

, Поскольку s¦lo пробегаются ячейки d¦nde, уходит выполнять mean, количество операций имеет форму: O(n(n-1)/2)

Обобщая

могут изображать графически две O( ) - что denotarÃ: n как f1 и f2 - чтобы видеть Ваше поведение, когда имеются diagonales понятых в ранге 2:1000

f1 <- Vectorize(function(x) x*x, 'x')
f2 <- Vectorize(function(x) x*(x-1)/2, 'x')
r <- 2:1000

plot(r, f1(r), type = "l", lty=2,  col="red", yaxt = "n", ylab="Operaciones (Miles)", xlab="Longitud Diagonal")
lines(r, f2(r), type = "l",  col="blue")

# cambiando la nomenclatura del eje y: notese que en plot se limpio el eje y:  yaxt = "n"
axis(2, at = y <- seq(0, 1e6, by = 10e4),  labels = paste0(y/1000, "k"))
legend("topleft", col = c("Red","Blue"), lty=c(2,1), lwd=c(1,1), cex=0.75, c("Ataque Fuerza Bruta", "Indexando"))

introducir la descripción de la imagen aquí

1
ответ дан 19.11.2019, 22:09

Способ понимать массивы состоит в том, чтобы видеть их простым плоским вектором, таким образом, мы можем учиться лучше, с которым patr¦n встречаются комбинации элемента диагонали, которые нужно выбирать, давайте видеть:

introducir la descripción de la imagen aquí

могут видеть, что есть patr¦n, как сочетаются они números диагонали, в нижней части будь показана в каждом случае, все элементы диагонали нужно считать и с тех пор, как posici¦n из этой мы возьмем их. Прием с этим, он состоит в том, чтобы производить главные файлы для векторов cantidades и posiciones и брать на себя ответственность (мне не хватает background matemÃ: костариканский как чтобы это показывать), что этот patr¦n повторяется с любым dimensi¦n, который мы выбирали бы (В моих доказательствах он это делает). Вышедшие

promedioMatrizTriangular <- function(diagonal) {

    n = length(diagonal)
    # Genero los vectores para el recorte de la diagonal
    cantidades <- unlist(lapply(rep(n:1), FUN=function(x) c(rep(0,(n-x)),rep(1:x))))
    posiciones <- unlist(lapply(rep(1:n), FUN=function(x) c(rep(0,(x-1)), rep(x, n-(x-1)))))

    # Recorto la diagonal dado un índice 
    diag_mean <- function(x) {
        mean(diagonal[posiciones[x]:(posiciones[x] + (cantidades[x]-1))])
    }

    # Para cada valor de 1:n*n, recortamos la diagonal y calculamos la media
    # retornamos directamente la matriz
    matrix(lapply(1:(n*n), FUN=function(x) ifelse(posiciones[x]==0,0,diag_mean(x))), nrow=n)
}

:

> promedioMatrizTriangular(c(9))
     [,1]
[1,] 9   
> promedioMatrizTriangular(c(9, 11))
     [,1] [,2]
[1,] 9    0   
[2,] 10   11  
> promedioMatrizTriangular(c(9, 11, 8))
     [,1]     [,2] [,3]
[1,] 9        0    0   
[2,] 10       11   0   
[3,] 9.333333 9.5  8   
> promedioMatrizTriangular(c(9, 11, 8, 5))
     [,1]     [,2] [,3] [,4]
[1,] 9        0    0    0   
[2,] 10       11   0    0   
[3,] 9.333333 9.5  8    0   
[4,] 8.25     8    6.5  5   
> promedioMatrizTriangular(c(9, 11, 8, 5, 6))
     [,1]     [,2] [,3]     [,4] [,5]
[1,] 9        0    0        0    0   
[2,] 10       11   0        0    0   
[3,] 9.333333 9.5  8        0    0   
[4,] 8.25     8    6.5      5    0   
[5,] 7.8      7.5  6.333333 5.5  6   

, По крайней мере, мы можем устанавливать, что по мере того, как наша диагональ растет, массив dimensi¦n n-1 продолжает поддерживать.

я не думаю, что он mÃ: s "performante", что tú soluci¦n, но по крайней мере это aproximaci¦n, отличный от проблемы.

1
ответ дан 19.11.2019, 22:09
  • 1
    Мне нравится @Patricio Moracho aná lisis, который ты выдвинул: " видеть массив вектором plano" . Adicionalmente, если diagonal есть у длины 1 вынесен вашей funció n, что-то, что в варианте, что planteé просто он не прокручивает изображение в окне, по крайней мере просвет, который он добавлял бы условные, но это было справедливым то, что querí чтобы предотвращать. – Hubert Ronald 15.03.2019, 12:13

Вместо 2 циклов expl¦-citos укрытые могут быть использованными циклы impl¦-citos с sapply(). В этом случае я думаю, что for - mÃ: s просветы. Этот funci¦n очень компактный и делает работу, но достаточно запутана.

promedio_matriz_triangular <- function(diagonal) {

  #Defino una función que crea cada columna de la matriz de salida
  #head() va reduciendo el largo de diagonal a medida que "bajo" una fila
  media_col <- function(x) sapply(seq_along(x), function(i) mean(head(x, i)))

  #Paso esa función sobre una versión cada vez más corta de diagonal
  #el rev() es necesario por algún motivo
  #el c() es para rellenar de 0 a la izquierda, igualando el largo de los vectores
  #sapply() coerciona a matriz por defecto
  sapply(rev(seq_along(diagonal)), function(j) c(rep(0, length(diagonal)-j), media_col(tail(diagonal, j))))
}

Eliminé первоначальный ответ из-за того, что является неправильная (он был для различной проблемы)

1
ответ дан 19.11.2019, 22:09
  • 1
    Хьюберт, có я говорю está подумавший, чтобы получать прямо массив, не диагональ. funció n diag () возврати неожиданный результат, если ты перемещаешь его вектор или не прямоугольный массив. Má s поздно я это исправляю с có я говорю защиту. – mpaladino 15.03.2019, 08:12
  • 2
    Хьюберт, предыдущий ответ был спутан, так как не посредничал интервал по отношению к точкам диагонали. Эта осложнена и я сомневаюсь, что он очень rá попросите, но по крайней мере дай ожидаемый результат. – mpaladino 15.03.2019, 17:44
  • 3
    Стой @mpaladino, интересное состоит в том, чтобы показывать различные приближения к выставленному случаю для того, чтобы сообщество benefice и гениальный, что ты использовал tail в solució n, в общем один использует эту funció n, чтобы видеть, если дата está заверши, хорошо ahí. – Hubert Ronald 15.03.2019, 19:30