Encuentra el valor más cercano en una lista de ordererd

Question

Me pregunto cómo escribirías un método simple de java para encontrar el entero del armario a un valor dado en una lista de enteros ordenados.

Aquí es mi primer intento:

public class Closest { 

    private static List<Integer> integers = new ArrayList<Integer>(); 

    static { 
     for (int i = 0; i <= 10; i++) { 
      integers.add(Integer.valueOf(i * 10)); 
     } 
    } 

    public static void main(String[] args) { 

     Integer closest = null; 
     Integer arg = Integer.valueOf(args[0]); 

     int index = Collections.binarySearch(
       integers, arg); 

     if (index < 0) /*arg doesn't exist in integers*/ { 
      index = -index - 1; 
      if (index == integers.size()) { 
       closest = integers.get(index - 1); 
      } else if (index == 0) { 
       closest = integers.get(0); 
      } else { 
       int previousDate = integers.get(index - 1); 
       int nextDate = integers.get(index); 
       if (arg - previousDate < nextDate - arg) { 
        closest = previousDate; 
       } else { 
        closest = nextDate; 
       } 
      } 
     } else /*arg exists in integers*/ { 
      closest = integers.get(index); 
     } 
     System.out.println("The closest Integer to " + arg + " in " + integers 
       + " is " + closest); 
    } 
} 

¿Qué opinas acerca de esta solución? Estoy seguro de que hay una manera más clara de hacer este trabajo ...

Tal vez tal método existe en alguna parte de las bibliotecas de Java y lo perdí ??

Manu

Answer 1

probar este pequeño método:

public int closest(int of, List<Integer> in) { 
    int min = Integer.MAX_VALUE; 
    int closest = of; 

    for (int v : in) { 
     final int diff = Math.abs(v - of); 

     if (diff < min) { 
      min = diff; 
      closest = v; 
     } 
    } 

    return closest; 
} 

algunos casos de prueba:

private final static List<Integer> list = Arrays.asList(10, 20, 30, 40, 50); 

@Test 
public void closestOf21() { 
    assertThat(closest(21, list), is(20)); 
} 

@Test 
public void closestOf19() { 
    assertThat(closest(19, list), is(20)); 
} 

@Test 
public void closestOf20() { 
    assertThat(closest(20, list), is(20)); 
} 

Answer 2

Ciertamente, usted puede simplemente utilizar un bucle para pasar por el y no perder de vista la diferencia entre el valor que se encuentra y el valor. Se vería más limpio, pero sería mucho más lento.

Ver: Finding closest match in collection of numbers

Answer 3

Creo que lo que tenemos es acerca de la forma más sencilla y eficiente de hacerlo. Encontrar el elemento "más cercano" en una lista ordenada no es algo que se encuentra comúnmente en la programación (normalmente busca el que es más grande o el que es más pequeño). El problema solo tiene sentido para los tipos numéricos, por lo que no es muy generalizable y, por lo tanto, sería inusual tener una función de biblioteca para él.

Answer 4

no han sido evaluados

int[] randomArray; // your array you want to find the closest 
     int theValue; // value the closest should be near to 

     for (int i = 0; i < randomArray.length; i++) { 
      int compareValue = randomArray[i]; 

      randomArray[i] -= theValue; 
     } 

     int indexOfClosest = 0; 
     for (int i = 1; i < randomArray.length; i++) { 
      int compareValue = randomArray[i]; 

      if(Math.abs(randomArray[indexOfClosest] > Math.abs(randomArray[i]){ 
       indexOfClosest = i; 
      } 
     } 

Answer 5

Creo que su respuesta es probablemente la forma más eficiente para devolver un solo resultado.

Sin embargo, el problema con su enfoque es que hay 0 (si no hay una lista), 1 o 2 soluciones posibles. Es cuando tienes dos soluciones posibles para una función que tus problemas realmente comienzan: ¿qué pasa si esta no es la respuesta final, sino solo la primera de una serie de pasos para determinar un curso de acción óptimo, y la respuesta que no respondiste? el regreso habría proporcionado una mejor solución? Lo único correcto es considerar ambas respuestas y comparar los resultados del procesamiento posterior solo al final.

Considere la función de raíz cuadrada como un problema algo análogo a esto.

Answer 6

Para resolver el problema, ampliaría la interfaz comparable mediante el método distanceTo. La implementación de distanceTo devuelve un valor doble que representa la distancia prevista y que es compatible con el resultado de la implementación compareTo.

El siguiente ejemplo ilustra la idea con solo manzanas. Puede cambiar el diámetro en peso, volumen o dulzura.La bolsa siempre devolverá la manzana 'más cerca' (más similar en tamaño, Wight o sabor)

public interface ExtComparable<T> extends Comparable<T> { 
    public double distanceTo(T other); 
} 

public class Apple implements Comparable<Apple> { 
    private Double diameter; 

    public Apple(double diameter) { 
     this.diameter = diameter; 
    } 

    public double distanceTo(Apple o) { 
     return diameter - o.diameter; 
    } 

    public int compareTo(Apple o) { 
     return (int) Math.signum(distanceTo(o)); 
    } 
} 

public class AppleBag { 
    private List<Apple> bag = new ArrayList<Apple>(); 

    public addApples(Apple...apples){ 
     bag.addAll(Arrays.asList(apples)); 
     Collections.sort(bag); 
    } 

    public removeApples(Apple...apples){ 
     bag.removeAll(Arrays.asList(apples)); 
    } 

    public Apple getClosest(Apple apple) { 
     Apple closest = null; 
     boolean appleIsInBag = bag.contains(apple); 
     if (!appleIsInBag) { 
     bag.addApples(apple); 
     } 

     int appleIndex = bag.indexOf(apple); 
     if (appleIndex = 0) { 
     closest = bag.get(1); 
     } else if(appleIndex = bag.size()-1) { 
     closest = bag.get(bag.size()-2); 
     } else { 
     double absDistToPrev = Math.abs(apple.distanceTo(bag.get(appleIndex-1)); 
     double absDistToNext = Math.abs(apple.distanceTo(bag.get(appleIndex+1)); 
     closest = bag.get(absDistToNext < absDistToPrev ? next : previous); 
     } 

     if (!appleIsInBag) { 
     bag.removeApples(apple); 
     } 

     return closest; 
    } 
} 

Answer 7

Si no está preocupado masivamente en el rendimiento (teniendo en cuenta que el conjunto está registrada en dos ocasiones), creo que el uso de un El conjunto navegable conduce a un código más claro:

public class Closest 
{ 
    private static NavigableSet<Integer> integers = new TreeSet<Integer>(); 

    static 
    { 
    for (int i = 0; i <= 10; i++) 
    { 
     integers.add(Integer.valueOf(i * 10)); 
    } 
    } 

    public static void main(String[] args) 
    { 
    final Integer arg = Integer.valueOf(args[0]); 
    final Integer lower = integers.lower(arg); 
    final Integer higher = integers.higher(arg); 

    final Integer closest; 
    if (lower != null) 
    { 
     if (higher != null) 
     closest = (higher - arg > arg - lower) ? lower : higher; 
     else 
     closest = lower; 
    } 
    else 
     closest = higher; 

    System.out.println("The closest Integer to " + arg + " in " + integers + " is " + closest); 
    } 
} 

Answer 8

Su solución parece ser asintóticamente óptima. Puede ser un poco más rápido (aunque probablemente menos sostenible) si usó Math.min/max. Un buen JIT probablemente tiene intrínsecos que hacen que estos sean rápidos.

int index = Collections.binarySearch(integers, arg); 
if (index < 0) { 
    int previousDate = integers.get(Math.max(0, -index - 2)); 
    int nextDate = integers.get(Math.min(integers.size() - 1, -index - 1)); 
    closest = arg - previousDate < nextDate - arg ? previousDate : nextDate; 
} else { 
    closest = integers.get(index); 
} 

Answer 9

Una solución sin búsqueda binaria (se aprovecha de la lista está ordenada):

public int closest(int value, int[] sorted) { 
    if(value < sorted[0]) 
    return sorted[0]; 

    int i = 1; 
    for(; i < sorted.length && value > sorted[i] ; i++); 

    if(i >= sorted.length) 
    return sorted[sorted.length - 1]; 

    return Math.abs(value - sorted[i]) < Math.abs(value - sorted[i-1]) ? 
     sorted[i] : sorted[i-1]; 
}