Trouver la valeur la plus proche dans une liste ordererd

Question

Je me demande comment vous pourriez écrire une méthode java simple pour trouver le placard Integer à une valeur donnée dans une liste entière triée.

Voici ma première tentative:

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); 
    } 
} 

Que pensez-vous de cette solution? Je suis sûr qu'il ya une façon plus propre de faire ce travail ...

Peut-être qu'une telle méthode existe quelque part dans les bibliothèques Java et je l'ai manqué ??

Manu

Answer 1

essayer cette petite méthode:

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; 
} 

quelques testcases:

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

Certes, vous pouvez simplement utiliser une boucle pour passer par la et de garder trace de la différence entre la valeur que vous êtes et la valeur. Cela aurait l'air plus propre, mais serait beaucoup plus lent.

Voir: Finding closest match in collection of numbers

Answer 3

Je pense que ce que vous avez est de la façon la plus simple et la plus efficace de le faire. Trouver l'élément "le plus proche" dans une liste triée n'est pas quelque chose que l'on rencontre couramment dans la programmation (vous recherchez généralement celui qui est le plus grand, ou celui qui est plus petit). Le problème n'a de sens que pour les types numériques, il n'est donc pas très généralisable, et il serait donc inhabituel d'avoir une fonction de bibliothèque pour cela.

Answer 4

Non testé

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

Je pense que votre réponse est probablement la façon la plus efficace de renvoyer un seul résultat.

Cependant, le problème avec votre approche est qu'il y a 0 (s'il n'y a pas de liste), 1 ou 2 solutions possibles. C'est lorsque vous avez deux solutions possibles à une fonction que vos problèmes commencent vraiment: Que se passe-t-il si ce n'est pas la réponse finale, mais seulement la première d'une série d'étapes pour déterminer une ligne d'action optimale? retour aurait fourni une meilleure solution? La seule chose à faire serait de considérer les deux réponses et de ne comparer les résultats d'un traitement ultérieur qu'à la fin. Pensez à la fonction racine carrée comme un problème quelque peu analogue à cela.

Answer 6

Pour résoudre le problème, j'étendrais l'interface comparable par une méthode distanceTo. L'implémentation de distanceTo renvoie une valeur double qui représente la distance prévue et qui est compatible avec le résultat de l'implémentation de compareTo.

L'exemple suivant illustre l'idée avec seulement des pommes. Vous pouvez échanger le diamètre en poids, volume ou douceur.Le sac retournera toujours le «plus proche d'Apple (plus similaire en taille, wight ou goût)

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 vous n'êtes pas massivement concernés sur la performance (étant donné que le jeu est recherché deux fois), je pense à l'aide d'un L'ensemble navigable conduit à un code plus clair:

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

Votre solution semble asymptotiquement optimale. Il pourrait être légèrement plus rapide (mais probablement moins maintenable) s'il utilisait Math.min/max. Une bonne JAT a probablement des intrinsèques qui rendent ces choses rapides.

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

Une solution sans recherche binaire (tire parti de la liste étant triée):

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]; 
}