arrays - uva - piña cantidad de fibra dietaria

Encuentre cada elemento que sea menor que algún elemento a su derecha

Question

Necesito encontrar elementos de un vector que son menos de uno o más elementos que vienen después. Es fácil de hacer en un bucle:

x = some_vector_values;
for m = 1 : length(x)
  if( any( x(m+1:end) > x(m) )
    do_such_and_such;
  end
end

pero la velocidad me está matando. Me estoy rascando la cabeza tratando de encontrar una solución eficaz, pero estoy en blanco. La longitud de la matriz puede ser del orden de miles y tengo que hacer esto para muchas matrices diferentes.

Answer 1

@NKN tiene razón. Ordenar.

x = some_vector_values;  

[Y,I]=sort(x);  %sort in order, get indices
dy=gradient(Y); %get difference vector same size as input vector
ind=find(dy~=0);%ignore places that are equal to the value of interest

for m = 1 : length(ind)
    do_such_and_such to Y(ind(m));
end

La mejor de las suertes

Answer 2

Este debería ser un algoritmo que toma O (n) tiempo y O (n) memoria: etiqueta el último elemento de tu matriz el elemento máximo. Itera hacia atrás sobre la matriz. Siempre que tengas un elemento más pequeño que tu máximo, guárdalo. De lo contrario, se convierte en tu nuevo máximo. Esto debería obtener todos los elementos que necesita con un solo pase.

Answer 3

Esto utiliza un enfoque de dividir y vencer (similar a la búsqueda binaria):

1. Encuentra el máximo del vector.
2. Todos los elementos a su izquierda son aceptados, mientras que el máximo en sí mismo es rechazado.
3. Para aquellos elementos a la derecha del máximo, aplique el paso 1.

Aunque no he hecho un análisis cuidadoso, creo que la complejidad promedio es O ( n ), o como máximo O ( n log n ). La memoria es O ( n ).

El resultado es un vector lógico ind que contiene true para los elementos aceptados y false para los elementos rechazados. El resultado final sería x(ind) .

x = [3 4 3 5 6 3 4 1];
n = numel(x);
ind = false(1,n); %// intiallization
s = 1; %// starting index of the part of x that remains to be analyzed
while s <= n %// if s > n we have finished
    [~, m] = max(x(s:end)); %// index of maximum within remaining part of x
    ind(s:s-2+m) = true; %// elements to its left are accepted
    s = s+m; %// update start of remaining part
end

El tiempo de funcionamiento se puede reducir un poco cambiando la condición while s < n a while s < n , porque el último elemento siempre se rechaza.

Answer 4

Si desea encontrar elementos que sean inferiores a algún elemento a su derecha, puede hacer esto también:

x = some_values''; % x should be a column vector to use this
h = hankel(x);
m = max(h,[],2);
f = find(x<m) %returns indices or f = (a<m) %returns true/false

La matriz de Hankel mostrará los elementos a la derecha a medida que avanza por las filas.

Luego puede usar los índices o verdadero / falso para iterar a través de un ciclo for y realizar algunas operaciones. Aquí hay un ejemplo:

x =

     9
     8
    16
    16
     4
    10
     9
    13
    15
     1

>> h = hankel(x)

h =

     9     8    16    16     4    10     9    13    15     1
     8    16    16     4    10     9    13    15     1     0
    16    16     4    10     9    13    15     1     0     0
    16     4    10     9    13    15     1     0     0     0
     4    10     9    13    15     1     0     0     0     0
    10     9    13    15     1     0     0     0     0     0
     9    13    15     1     0     0     0     0     0     0
    13    15     1     0     0     0     0     0     0     0
    15     1     0     0     0     0     0     0     0     0
     1     0     0     0     0     0     0     0     0     0

>> m = max(h,[],2)

m =

    16
    16
    16
    16
    15
    15
    15
    15
    15
     1

>> f = find(a<m)

f =

     1
     2
     5
     6
     7
     8

Answer 5

Su algoritmo es tan lento ya que if any(...) tiene que verificar n elementos en la primera iteración, entonces n-1 elementos en la segunda iteración ... hasta que verifique un solo elemento en la última iteración. ¡En general, tiene que hacer aproximadamente n^2/2 comparaciones, por lo que su tiempo de ejecución es cuadrático en función de la longitud del vector de entrada!

Una solución que es lineal en tiempo y memoria puede ser primero calcular un vector con el máximo desde ese punto hasta el final, que puede calcularse en un pase hacia atrás (se podría llamar a esto un máximo acumulado invertido, que no se puede vectorizar ). Después de esto, este vector se compara directamente con x (no probado):

% calculate vector mx for which mx(i) = max(x(i:end))
mx = zeros(size(x));
mx(end) = x(end);
for i = length(x)-1:-1:1 % iterate backwards
    mx(i) = max(x(i), mx(i+1));
end

for i = 1:length(x) - 1
    if mx(i) > x(i)
        do_such_and_such(i);
    end
end

En caso de que no le importe el orden en que se ejecuta do_such_and_such , estos bucles for pueden incluso combinarse así:

mx = x(end);
for i = length(x)-1:-1:1 % iterate backwards
    if x(i) < mx
        do_such_and_such(i);
    end
    mx = max(x(i), mx); % maximum of x(i:end)
end

Answer 6

Versión de una línea

comparisons = any(triu(bsxfun(@gt,x(:).'',x(:))),2)