Как улучшить этот метод двоичного поиска Java, чтобы найти лучший процентиль для данного значения? - PullRequest
Новая
       16

Как улучшить этот метод двоичного поиска Java, чтобы найти лучший процентиль для данного значения?

0 голосов
/ 01 мая 2019

У меня есть отсортированный массив значений процентилей цен на жилье в X транзакциях:

Double[] arr = {2418.0, 2535.0, 2652.0, 2808.0, 2808.0, 2808.0, 2808.0, 2808.0, 2808.0, 3657.0, 3816.0, 4144.0, 5429.0, 5429.0, 5429.0, 5429.0, 5429.0, 5518.0, 5518.0, 5518.0, 5518.0, 5518.0, 5607.0, 5607.0, 5607.0, 5607.0, 5607.0, 5607.0, 5696.0, 5696.0, 5696.0, 5696.0, 5696.0, 5785.0, 5785.0, 5785.0, 5785.0, 5785.0, 5874.0, 5874.0, 5874.0, 5874.0, 5874.0, 5874.0, 5963.0, 5963.0, 5963.0, 5963.0, 5963.0, 5963.0, 6052.0, 6052.0, 6052.0, 6052.0, 6052.0, 6052.0, 6141.0, 6141.0, 6141.0, 6141.0, 6141.0, 6141.0, 6230.0, 6230.0, 6230.0, 6230.0, 6230.0, 6319.0, 6319.0, 6319.0, 6319.0, 6319.0, 6408.0, 6408.0, 6408.0, 6497.0, 6497.0, 6497.0, 6586.0, 6586.0, 6645.4, 6675.0, 6764.0, 6853.0, 6942.0, 7120.0, 7337.3, 7924.2, 8244.5, 8564.0, 8840.0, 9062.2, 9285.9, 9492.1, 9717.5, 10013.2, 10668.4, 12034.5, 13386.0, 22868.0};

Таким образом, 1-й процентиль цен на жилье равен 2418, а 100-й процентиль цен на жилье равен 22868. Как и в случае с процентилями, исходя из входных данных, некоторые процентили могут иметь те же значения (как 6141, 6408 и другие в приведенный выше пример).

Сейчас я пишу метод, который, учитывая цену дома (не обязательно в исходных X транзакциях), найдет лучший процентиль, которому он принадлежит. Я написал этот двоичный код поиска, который, кажется, работает нормально, но я чувствую, что его можно улучшить:

`

public static int findRelevantPercentile(Double [] arr, double searchFor){   
    int start = 0;
    int end  = arr.length - 1;
    int middle;
    do{
        middle = (start + end) / 2;
        if (arr[middle] >= searchFor){
            end = middle;
        } else {
            start = middle;
        }
    }while(start + 1 < end);

    if (searchFor >= arr[end]){
        return arr.length;
    } else{
        return start + 1;
    }
}

`

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

Кстати, мне известен метод Arrays.binarysearch (..).

1 Ответ

0 голосов
/ 01 мая 2019

Простая вещь, которую, как я вижу, можно быстро улучшить, - это перемещение блока If, который находится в конце, в начало, чтобы в этих конкретных случаях он никогда не заходил в цикл, делая его немного быстрее.

Вот как это будет выглядеть после.

РЕДАКТИРОВАТЬ: я очистил его немного больше, изменив DO WHILE на WHILE и переместив объявление середины внутрь цикла, так как его область действия никогда не покидает цикл. 

public static int findRelevantPercentile(Double [] arr, double searchFor){   
    int start = 0;
    int end  = arr.length - 1;

    if (searchFor >= arr[end]){
        return arr.length;
    }
    while(start + 1 < end) {
        int middle = (start + end) / 2;
        if (arr[middle] >= searchFor){
            end = middle;
        } else {
            start = middle;
        }
    }
    return start + 1;
}
...