Как абстрагировать бинарный поиск, не относящийся к структуре данных?

У меня есть программа на Java, в которой я обнаружил, что вручную реализовал алгоритм бинарного поиска 3 раза. Проблема в том, что этот поиск не выполняется по заполненной структуре данных; скорее, это вызовы численного метода, который требует больших вычислительных ресурсов (отсюда и бинарный поиск; я пытаюсь уменьшить количество вызовов этого метода). Заголовки методов выглядят так:

double computeValue1 (Thing thing, int parameter, int seed)

Этот метод всегда возвращает двойное значение между 0 и 1. Функция является монотонно возрастающей (более высокие значения seed всегда возвращают более высокий результат; таким образом, бинарный поиск оправдан). Я использую поиск, чтобы найти значение seed, которое возвращает значение, наиболее близкое к 0,5 (при фиксированных Thing и parameter).

Так что в идеале в Java должен быть какой-то абстрактный библиотечный метод, который я мог бы использовать для выполнения этого поиска, вместо того, чтобы записывать детали в свой код. Более того, на самом деле у меня есть это 3 разных раза для 3 разных методов оценки (скажем, computeValue1, computeValue2, а затем в третий раз, когда я выполняю тот же поиск по parameter, сохраняя фиксированными Thing и seed).

Что было бы элегантным способом абстрагироваться от бинарного поиска, чтобы я не поддерживал 3 отдельных метода поиска (по одному вокруг каждого из 3 методов вычисления), которые в основном делают одно и то же?


java search abstraction numerical-methods
person Daniel R. Collins    schedule 04.02.2016    source источник
comment
Не могли бы вы включить еще немного кода?   -  person shmosel    schedule 04.02.2016
comment
Если вы используете Java 8, возможно, вы могли бы сделать что-то вроде этого: double <T> computeValue(T thing, int parameter, int seed, Function<Thing, Double> expensiveFunction)   -  person marstran    schedule 04.02.2016

Ответы (1)


arrow_upward
2
arrow_downward

Пока тип данных для параметра поиска тот же (int в вашем случае), вы можете сделать это:

public int binarySearch(double targetValue, int from, int to, Function<Integer, Integer> compute) {
    while (...) {
        int currentParameter = ...;
        int currentValue = compute.apply(currentParameter);
        ...
    }
}

Назовите это так в Java 8:

int seed1 = binarySearch(0.42, 0, 1000, s -> computeValue1(someThing, someParameter, s));
int seed2 = binarySearch(0.42, 0, 1000, s -> computeValue2(someThing, someParameter, s));
int param = binarySearch(0.42, 0, 1000, p -> computeValue1(someThing, p, someSeed));

Если у вас нет Java 8, вам нужно определить интерфейс Function самостоятельно:

public interface Function<TParameter, TResult> {
    TResult apply(TParameter parameter);
}

и вызовите поиск с анонимным внутренним классом:

int seed1 = binarySearch(0.42, 0, 1000, new Function<Integer, Integer>() {
    public Integer apply(Integer parameter) {
        return computeValue1(someThing, someParameter, parameter));
    }
});
person Aasmund Eldhuset    schedule 04.02.2016
comment
Это здорово, я не знал, что в Java 8 теперь вы можете передавать методы в качестве параметров. Спасибо за эту новость! (Кроме того, самопровозглашенный класс Function был более элегантным, чем я мог придумать, хорошая штука.) - person Daniel R. Collins; 04.02.2016
comment
Спасибо! (Однако Java 8 даже лучше, так как использует ковариантность и контравариантность, что дает большую гибкость подписи параметра метода.) Обратите внимание, однако, что в этом примере я не передаю метод, я передавая лямбда-выражение, которое (вместе с потоками) — самая замечательная (и давно назревшая) функция Java 8. Вы также можете передавать методы: binarySearch(0.42, 0, 1000, this::myMethod), но тогда сигнатура этого метода должна соответствовать типу параметра Function. - person Aasmund Eldhuset; 04.02.2016
comment
Просто впервые узнаю о лямбда-выражениях в Java, и я хотел бы дать этому около сотни голосов. Так мило! - person Daniel R. Collins; 06.02.2016