Java-метод для поиска ближайшего совпадения с данным номером. в несортированном массиве целых чисел

Question

Мне потребовалась помощь в отношении Java-программы, чтобы найти ближайшее совпадение с любым целым числом в несортированном массиве целых чисел.

Могу ли я получить предложения по поводу:

* How to get start off with this?
* Should i first sort the array

Спасибо всем

Answer 1

Если вам нужно выполнить поиск только один раз , вы можете отсканировать массив от начала до конца, отслеживая значение, ближайшее к искомому.

Если вам нужно многократно искать в одном и том же массиве , вы должны предварительно отсортировать массив, а затем повторно использовать двоичный поиск.

Answer 2

Если вы не можете отсортировать массив, или вы делаете это только один раз, вы можете сделать.

public static int closest1(int find, int... values) {
    int closest = values[0];
    for(int i: values)
       if(Math.abs(closest - find) > Math.abs(i - find))
           closest = i;
    return closest;
}

Это вернет одно ближайшее значение. Если вы ищете значение, равное между двумя значениями, вы получите первое.

---

Оптимизированная версия.

public static int closest2(int find, int... values) {
    int closest = values[0];
    int distance = Math.abs(closest - find);
    for(int i: values) {
       int distanceI = Math.abs(i - find);
       if(distance > distanceI) {
           closest = i;
           distance = distanceI;
       }
    }
    return closest;
}

---

Многопоточная версия

public static int closest3(final int find, final int... values) {
    final int procs = Runtime.getRuntime().availableProcessors();
    ExecutorService es = Executors.newFixedThreadPool(procs);
    List<Future<Integer>> futures = new ArrayList<Future<Integer>>();
    final int blockSize = values.length / procs;
    for (int i = 0; i < procs; i++) {
        final int start = blockSize * i;
        final int end = Math.min(blockSize * (i + 1), values.length);
        futures.add(es.submit(new Callable<Integer>() {
            @Override
            public Integer call() throws Exception {
                int closest = values[start];
                int distance = Math.abs(closest - find);
                for (int i = start + 1; i < end; i++) {
                    int n = values[i];
                    int distanceI = Math.abs(n - find);
                    if (distance > distanceI) {
                        closest = i;
                        distance = distanceI;
                    }
                }
                return closest;
            }
        }));
    }
    es.shutdown();
    int[] values2 = new int[futures.size()];
    try {
        for (int i = 0; i < futures.size(); i++)
            values2[i] = futures.get(i).get();
        return closest2(find, values2);
    } catch (Exception e) {
        throw new AssertionError(e);
    }
}

выполнение этого теста

Random rand = new Random();
int[] ints = new int[100 * 1000 * 1000];
for (int i = 0; i < ints.length; i++)
    ints[i] = rand.nextInt();

for (int i = 0; i < 5; i++) {
    long start1 = System.nanoTime();
    closest1(i, ints);
    long time1 = System.nanoTime() - start1;

    long start2 = System.nanoTime();
    closest2(i, ints);
    long time2 = System.nanoTime() - start2;

    long start3 = System.nanoTime();
    closest3(i, ints);
    long time3 = System.nanoTime() - start3;
    System.out.printf("closest1 took %,d ms, closest2 took %,d ms, closest3 took %,d ms %n", time1 / 1000 / 1000, time2 / 1000 / 1000, time3 / 1000 / 1000);
}

для печати 100 миллионов значений

closest1 took 623 ms, closest2 took 499 ms, closest3 took 181 ms 
closest1 took 645 ms, closest2 took 497 ms, closest3 took 145 ms 
closest1 took 625 ms, closest2 took 495 ms, closest3 took 134 ms 
closest1 took 626 ms, closest2 took 494 ms, closest3 took 134 ms 
closest1 took 627 ms, closest2 took 495 ms, closest3 took 134 ms 

Использование второго подхода экономит 0,8 мс на миллион записей. Третий подход намного быстрее для больших массивов, но более медленным для меньших.

Answer 3

/**
 * @return the index of the closest match to the given value
 */
int nearestMatch(int[] array, int value) {
    if (array.length == 0) {
        throw new IllegalArgumentException();
    }
    int nearestMatchIndex = 0;
    for (int i = 1; i < array.length; i++) {
        if ( Math.abs(value - array[nearestMatchIndex])
                > Math.abs(value - array[i]) ) {
            nearestMatchIndex = i;
        }
    }
    return nearestMatchIndex;
}

Answer 4

Нет, вам не нужно предварительно сортировать массив.Просто запустите его, записав позицию и значение текущего ближайшего совпадения, обновляя его на каждой итерации, если это необходимо.Это займет O (n) время, в то время как сортировка займет O (n lg n) (если только вы не выполните сортировку с подсчетом, что не всегда применимо).

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

Answer 5

Да, отсортировать массив , а затем использовать Arrays.binarySearch(int[], int)

Возвращает:
индекс ключа поиска, если он содержится в массиве; в противном случае (-(insertion point) - 1). Точка вставки определяется как точка, в которой ключ будет вставлен в массив: индекс первый элемент больше, чем ключ или длина, если все элементы в массив меньше указанного ключ. Обратите внимание, что это гарантирует, что возвращаемое значение будет >= 0, если и только если ключ найден.

Answer 6

Не сортируйте массив в первую очередь, так как он изменит исходный массив.

Вместо этого, просматривайте массив, отслеживая разницу между текущим элементом массива и заданным значением (и элементом массива ссамая маленькая разница пока).Сложность здесь линейна;Вы не можете победить это с сортировкой