Encuentre el valor positivo mínimo

Question

¿Cuál es el mejor algoritmo para encontrar el valor positivo no nulo más pequeño a partir de un número fijo (en este caso 3) de valores o devolver 0 si no hay preguntas positivas?

Mi enfoque ingenuo está por debajo (en Delphi, pero siéntase libre de usar lo que quiera), pero creo que hay una manera más elegante.

value1Temp := MaxInt; 
value2Temp := MaxInt; 
value3Temp := MaxInt; 

if (value1T > 0) then 
    value1Temp := value1; 
if (value2 > 0) then 
    value2Temp := value2; 
if (value3 > 0) then 
    value3Temp := value3; 

Result := Min(value1Temp, Min(value2Temp, value3Temp)); 
if Result = MaxInt then 
    Result := 0; 

Editar: Lo sentimos añadido lo que se necesita si no hay números positivos. Pensé que ya lo tenía allí antes, pero debo haberlo perdido.

Answer 1

que haría esto:

Resultado: = MAXINT;
si value1> 0 then Resultado: = min (Resultado, valor1);
if value2> 0 then Result: = min (Result, value2);
si value3> 0 then Resultado: = min (Resultado, valor3);
si Result = MaxInt then Result: = 0;

Si quieres que en un bucle con un número arbitrario de preguntas, entonces:

Resultado: = MAXINT;
para I: = 1 a N do
      si valor [I]> 0 entonces Resultado: = min (Resultado, valor [I]);
si Result = MaxInt then Result: = 0;

Si desea que la matriz de valores para ser basado en cero, cambiar el bucle sea: de 0 a N-1

Creo que este código hace que sea muy claro exactamente lo que se está haciendo.

Poner las declaraciones "then" en la misma línea hace que el código parezca más limpio en este caso simple, pero puede escribir las declaraciones "then" en la siguiente línea si lo considera necesario.

Answer 2

lo haría un poco de bucle (Esto está en C, no soy un tipo Delphi):

int maxPositiveValue(int *number, int listSize) 
{ 
    int i, result = 0; 

    for(i = 0; i < listSize; i++) 
    { 
     if(number[i] > 0 && (number[i] < result || result == 0)) 
      result = number[i]; 
    } 

    return result; 
} 

La ventaja de este código es que es muy fácil de leer y se puede escalar fácilmente a hacer frente a cualquier lista de valores de longitud.

ACTUALIZACIÓN: He cambiado el código en respuesta a los comentarios que he recibido a continuación.

Este nuevo código es un poco más complejo, pero ahora se encargará de:

1. El caso en el que la lista no contiene números enteros positivos (devuelve 0).
2. El caso donde la lista contiene una o más ocurrencias de INT_MAX.
3. Una lista de cualquier longitud.

Answer 3

Estoy de acuerdo con Adam. En realidad, no va a hacer más rápido que una búsqueda lineal algorítmicamente, si solo necesita el número natural más pequeño en un contenedor.

Su código debería ejecutarse bastante rápido, lo más probable es que se traduzca a un CMOV en x86, por lo que la instrucción if dentro del ciclo for no costará mucho de todos modos.

Si va a terminar queriendo todos los números distintos de cero en orden, entonces por supuesto sería mucho mejor ordenar, y luego empalmar.

Answer 4

Result := Min(IfThen(Value1 > 0, Value1, MAXINT), 
       Min(IfThen(Value2 > 0, Value2, MAXINT), 
        IfThen(Value3 > 0, Value3, MAXINT))); 

Un bucle no funcionará si las entradas no son una lista/matriz, según la pregunta.

No está claro a partir de la pregunta qué debe hacer la función si ninguno de los tres es positivo y distinto de cero.

Answer 5

• Ir a través de los valores de la lista, deshacerse de ellos hasta que encuentre un valor positivo, ajuste min-valor a la misma
• Ir a través de los valores en el resto de la lista
  • Si 0 < corriente de valor < min-valor, ajuste min-valor a la corriente de valor
• retorno min-valor

Answer 6

Esto funciona sin importar el tipo de los elementos del array es

template <typename T> 
T min_pos(T* a, int n) 
{ 
    int i /* = 0 */ /* Edit: commented this out */; 

    // Find the first positive element in the array 
    for (i = 0; i < n; ++i) 
     if (a[i] > 0) 
      break; 

    // If no positive element was found, return 0 
    if (i == n) 
     return 0; 

    T res = a[i]; 

    // Search the rest of the array for an element 
    // that is positive yet smaller than res 
    for (++i; i < n; ++i) 
    { 
     if ((a[i] > 0) && (a[i] < res)) 
      res = a[i]; 
    } 

    return res; 
} 

Answer 7

Ésta es C#

public int GetSmallestPositive(IList<int> pValues) 
{ 
    if(pValues == null) 
    { 
     throw new ArgumentNullException("pValues"); 
    } 
    int _negNumCount = 0; 
    int _smallest = int.MaxValue; 
    for(int i = 0; i < pValues.Count; ++i) 
    { 
     if(pValues[i] < _smallest) 
     { 
      if(pValues[i] <= 0) 
      { 
       ++_negNumCount; 
       continue; 
      } 
      _smallest = pValues[i]; 
      if(_smallest == 1) 
      { 
       return 1; 
      } 
     } 
    } 
    return (_negNumCount == pValues.Count) ? 0 : _smallest; 
} 

En este caso, y en su ejemplo, estoy usando enteros, por lo que 1 es el el número más pequeño distinto de cero. Siempre que ponga sus datos en una lista, funcionará para todos los valores que desee.

Editar: Se corrigió para devolver 0 si la lista está llena de números negativos. Lanzar excepción si pValues ​​es nulo.

Answer 8

//return the smallest non-zero positive number, or null. 
//relying on Min or Max is considered cheating. 
public static int? smallestNonZeroPositiveNumberOfThree(
    int val1, int val2, int val3) 
{ 
    //we have no guarantee that any of the 3 inputs will be positive 
    int? result = null; 
    if (val1 > 0) 
    { 
     result = val1; 
     if (val2 > 0 && val2 < result) { result = val2; } 
     if (val3 > 0 && val3 < result) { result = val3; } 
    } 
    else if (val2 > 0) 
    { 
     result = val2; 
     if (val3 > 0 && val3 < result) { result = val3; } 
    } 
    else if (val3 > 0) 
    { 
     result = val3; 
    } 
    return result; 
} 

Answer 9

Una versión C# que cubre todas las bases (creo):

public int GetMinimumPositiveValue(IEnumerable<int> values) 
{ 
    int result = int.MaxValue; 
    bool hasPositiveValue = false; 

    foreach (int value in values) 
    { 
     if(value == 1) { return value; } 

     if(value > 0) 
     { 
      hasPositiveValue = true; 

      if(value < result) 
      { 
       result = value; 
      } 
     } 
    } 

    return hasPositiveValue ? result : 0; 
} 

Answer 10

Esto es lo que me ocurrió después de pensarlo un poco más

Result := 0; 
if value1 > 0 then 
    Result := value1; 
if (value2 > 0) and ((Result = 0) or (value2 < Result)) then 
    Result := value2; 
if (value3 > 0) and ((Result = 0) or (value3 < Result)) then 
    Result := value3; 

Por supuesto si tener una lista, los algoritmos más genéricos son mejores.

Answer 11

Veo demasiadas líneas de códigos para aquellos que intentan resolver el problema general en C#. Si los valores es una continuación IEnumerable<int>

values.Select(v => (int?)v) 
     .Where(v => v > 0) 
     .Min() ?? 0; 

devuelve el valor positivo más pequeño en values si existe otro caso devuelve 0. Aquí, estoy explotando el hecho de que Enumerable.Min(IEnumerable<int?>) devolverá null si la secuencia está vacía. Por lo tanto, filtramos los valores no positivos y luego buscamos el mínimo. Si todos los valores son no positivos, obtenemos cero como se desea y de lo contrario encontramos el mínimo de los valores positivos.

Answer 12

Aquí hay una versión C riffs fuera de la solución en el puesto pregunta, pero soluciona el caso en el que todos los valores son MAXINT ...

int foo(int value1, int value2, int value3) 
{ 
    int value1Temp, value2Temp, value3Temp, tempMax; 
    value1Temp = max(value1, 0); 
    value2Temp = max(value2, 0); 
    value3Temp = max(value3, 0); 
    tempMax = value1Temp | value2Temp | value3Temp; 
    if (value1Temp == 0) { value1Temp = tempMax; } 
    if (value2Temp == 0) { value2Temp = tempMax; } 
    if (value3Temp == 0) { value3Temp = tempMax; } 
    return min(value1Temp, min(value2Temp, value3Temp)); 
} 

También es posible hacer esto de una manera libre de rama así, desde el mínimo y el máximo pueden ser implementados como operaciones libres de la rama:

int min(int x, int y) 
{ 
    return y + ((x - y) & -(x < y)); 
} 

int max(int x, int y) 
{ 
    return x - ((x - y) & -(x < y)); 
} 

int foo(int value1, int value2, int value3) 
{ 
    int value1Temp, value2Temp, value3Temp, tempMax, mask; 
    value1Temp = max(value1, 0); 
    value2Temp = max(value2, 0); 
    value3Temp = max(value3, 0); 
    tempMax = value1Temp | value2Temp | value3Temp; 
    mask = -(value1Temp > 0); 
    value1Temp = (value1Temp & mask) | (tempMax & ~mask); 
    mask = -(value2Temp > 0); 
    value2Temp = (value2Temp & mask) | (tempMax & ~mask); 
    mask = -(value3Temp > 0); 
    value3Temp = (value3Temp & mask) | (tempMax & ~mask); 
    return min(value1Temp, min(value2Temp, value3Temp)); 
} 

para obtener más antecedentes sobre por qué usted quiere nunca hacer esto, vea: Is "If" Expensive? y Bit Twiddling Hacks.

Editar: Acabó mi intento anterior de una solución sin ramificación, que en realidad no funcionó. Se agregó una nueva solución libre de ramificaciones que debería funcionar.

Answer 13

una ligera mejora en la sugerencia de Jason que maneja correctamente colecciones vacías y colecciones que contienen sólo valores negativos:

values.Min(r => r > 0 ? r : (int?)null) ?? 0 

Answer 14

¿Qué hay de la siguiente función (en Delphi, por supuesto):

function LowestPositiveInt(IntArr : array of Integer):Integer; 
var 
    iX : integer; 
    bValid : boolean; 
begin 
    Result := MaxInt; 
    bValid := False; 
    for ix := 0 to High(IntArr) do 
    if (IntArr[ix] > 0) then 
     begin 
     bValid := true; 
     if (IntArr[iX] < Result) then 
      Result := IntArr[ix]; 
     end; 
    if not bValid then 
    Result := 0; 
end; 

luego llamar es como el siguiente:

ShowMessage(IntToStr(LowestPositiveInt([5,2,3,-1,12]))); 

Esto debería return 2. La ventaja de este enfoque es que la matriz puede tomar cualquier cantidad de elementos, incluidas las variables enteras ...así que usar el ejemplo anterior se podría decir:

Result := LowestPositiveInt([ Value1, Value2, Value3 ]); 

EDITAR Actualizado a manejar el LowestPosititiveInt ([MAXINT, MAXINT, MAXINT]) escenario.

Answer 15

Lo que quiere es un selection algorithm si trabaja con un número no fijo de valores.

Sin embargo, si su código solo necesita verificar tres valores, debe evitar los bucles y algoritmos específicos, y solo concentrarse en micro optimizaciones — específicamente, con la menor ramificación posible.

Hay algunas cosas sobre esto en Hacker's Delight, capítulo 4, donde puede encasillar su entero con signo en unsigned para reducir a la mitad el número de ramas. Esto se realiza en el smallest_v2() en el C-código de abajo:

#include <stdio.h> 
#include <limits.h> 

int smallest_v1(int a, int b, int c) 
{ 
     int min = INT_MAX; 

     min = a>0 && a<min ? a : min; 
     min = b>0 && b<min ? b : min; 
     min = c>0 && c<min ? c : min; 
} 

// See Hacker's Delight, chapter 4. 
int smallest_v2(int a, int b, int c) 
{ 
     int min = INT_MAX; 

     if ((unsigned) a < min) min = a; 
     if ((unsigned) b < min) min = b; 
     if ((unsigned) c < min) min = c; 

     return min; 
} 

int main() 
{ 
     printf("min v1: %d\n", smallest_v1(-10, 7, 3)); 
     printf("min v2: %d\n", smallest_v1(-10, 7, 3)); 
} 

Básicamente, el libro dice que si usted quiere comprobar si

1 <= i <= 10 

entonces esto es lo mismo que hacer una comparación sin firma

(unsigned)(i - 1) <= 9 

El libro también ofrece una prueba. Lo que obtienes es una mejor predicción de bifurcación en tu código. Debe hacer un programa de prueba y cronometrarlo.

Answer 16

No sé Delphi, pero aquí es una solución rápida en Ruby (Suponga que los números están en una lista)

[1,2,42,-12].delete_if{|n| n <= 0 }.min || 0 

Algorithmically, se elimina todo lo negativo (o 0) elementos, entonces se encuentran el mínimo. Si no hay elementos positivos, [].min devuelve nil, por lo que el || 0 final da el '0' solicitado como respuesta.

Answer 17

¿Está buscando la estética o la velocidad?

En este último caso, no puedo pensar en la forma en que podría realizar esta prueba las veces suficientes para ser detectable en una aplicación: simplemente no importa.

Saludos

Answer 18

En DELPHI - si su dominio es los números enteros, y si se puede satisfacer sus argumentos en enteros largos, y si se puede evitar pasar el entero mínimo ($ 80000000), entonces esto le dará el resultado que desee sin ninguna bifurcación condicional:

function cmMinInt(XX, YY, ZZ : longint) : longint; 
begin 
    result := max(0,longint(
    min(longint((XX-1) xor $80000000), 
    min(longint((YY-1) xor $80000000), 
    longint((ZZ-1) xor $80000000) 
    )) xor $80000000)+1); 
end; 

la técnica depende de una reasignación sin pérdida reversible del tipo entero largo para que el rango que nos interesa - los números enteros de 1 a MAXINT - permanecer en orden y ocupan los valores más bajos. Simplemente alternar el bit de signo casi da lo que necesitamos, excepto que no queremos 0 incluido en el rango inferior. Restar 1 primero (y volver a agregarlo más tarde) corrige eso. La operación xor utilizada aquí amplía ambos operandos a int64, que requiere una conversión explícita a longint para que la función mínima produzca el resultado correcto. Finalmente, si los operandos son todos neg, el mínimo se encontrará en el rango superior, y la respuesta será neg. En este caso, queremos que la respuesta sea 0, por lo que simplemente la recortamos con la función max.

Aquí es lo mismo matemáticas distribuidos en varias instrucciones para facilitar la lectura:

function cmMinInt(XX, YY, ZZ : longint) : longint; 
begin 
    // swap ordinal coding for range MININT..0 with range 1..MAXINT 
    XX := XX-1;    // move region division to between 0 and 1 
    XX := XX xor $80000000; // swap regions, preserving ordering 
    XX := longint(XX);  // cram back into signed 32-bit 
    // similarly with YY and ZZ 
    YY := longint((YY-1) xor $80000000); 
    ZZ := longint((ZZ-1) xor $80000000); 
    // find min of three recoded values 
    result := min(XX,min(YY,ZZ)); 
    // swap ordering back again 
    result := result xor $80000000; // swap regions, preserving ordering 
    result := result+1;    // move region division back home 
    result := longint(result);  // cram back into signed 32-bit 
    // if all three were neg, result at this point is neg -- clip to zero 
    result := max(0,result); 
end; 

-Al.

Answer 19

En Haskell, como es habitual, es más fácil resolver el problema general y luego declarar un caso especial.

foo xs = let xs1 = filter (>0) xs in if null xs1 then 0 else minimum xs1 

foo3 x1 x2 x3 = foo [x1, x2, x3] 

Answer 20

Difícil de creer Delphi sigue estando limitado a dos valores en la función Min. :-(

En Python podría configurar una función para trabajar con cualquier número de argumentos de esta manera:

def PosMin(*numbers): 
    try: 
     return min(num for num in numbers if num > 0) 
    except: 
     return 0 

Por desgracia, la función "min" lanza una excepción si termina sin valores (por ejemplo, una lista vacía o en este caso no hay números> 0) por lo que la excepción tiene que ser capturada. Hay una propuesta para la próxima versión de python para agregar un valor centinela y parece que va a ser aceptado. En ese caso, el código habría sido

return min (num for num in numbers if num > 0, sentinel=0) 

sin necesidad de la excepción manejo de iones

Answer 21

function MinPositive(const AIntegers: array of Integer): Integer; 
var 
    LoopI: Integer; 
    LFirstPositivePos: Integer; 
begin 
    Result := 0; 
    LFirstPositivePos := MaxInt; 
    for LoopI := Low(AIntegers) to High(AIntegers) do 
    begin 
    if (AIntegers[LoopI] > 0) then 
    begin 
     Result := AIntegers[LoopI]; 
     LFirstPositivePos := LoopI; 
     Break; 
    end; 
    end; 

    for LoopI := LFirstPositivePos to High(AIntegers) do 
    begin 
    if (AIntegers[LoopI] > 0) and (AIntegers[LoopI] < Result) then 
    begin 
     Result := AIntegers[LoopI]; 
    end; 
    end; 
end; 

function MinPositive3(const I1, I2, I3: Integer): Integer; 
begin 
    Result := MinPositive([I1, I2, I3]); 
end;