[Java] 정렬된 리스트에서 근사값 구하기

코딩하게된 배경 TMI ~

회사에서 마우스 좌표를 기준으로 X값을 받아와 차트 그려진 그래프의 Y값을 도출하는 기능을 구현해야 하는 경우가 생겼다. 문제는 받아오는 X의 값은 연속적인 값인데, 도출해야하는 Y좌표를 담고 있는 데이터는 <key(x좌표), value> 형식이라 마우스 좌표의 X값에 근사한 X좌표를 구해 해당 값을 Key로 Y좌표 값을 구해야 했다. 따라서 정렬된 X좌표의 리스트에서 입력된 값의 근사값을 가져오는 알고리즘을 구현하게 됐다.

이진 탐색을 이용한 근사값 구하기

레거시 사전 조건

• 탐색 대상은 Double.toString() 값을 담은 문자열 List
• 입력되는 값은 double 형식
• 문자열 List는 순차적으로 이미 정렬된 상태

로직 흐름

1. 정렬된 리스트에서 inputValue의 Index 탐색 (IndexOf() 호출)
2. 존재하지 않는다면 BinarySearch 알고리즘으로 inputValue와 가장 근사한 두 값의 인덱스 탐색
3. low, high 인덱스의 값 중 inputValue와 더 가까운 값을 반환

public static int searchApproxIdx(List<String> collection, double inputValue){
        int returnIdx = collection.indexOf(Double.toString(inputValue));

        if(returnIdx < 0) {
            int low = 0;
            int high = collection.size() - 1;

            while(low <= high) {
                int midIdx = (high + low)/2;
                double midValue = Double.parseDouble(collection.get(midIdx));

                if(midValue == inputValue) {
                    return midIdx;
                } else if(midValue < inputValue) {
                    low = midIdx + 1;
                } else {
                    high = midIdx - 1;
                }
            }

            double lowValue = Math.abs(Double.parseDouble(collection.get(low)) - inputValue);
            double highValue = Math.abs(Double.parseDouble(collection.get(high)) - inputValue);

            returnIdx = lowValue > highValue ? high : low;
        }

        return returnIdx;
    }

알고리즘 테스트 결과

대강 테스트를 위한 리스트를 생성하는 메서드와 테스트를 진행하는 메서드를 생성해서 돌려줬다. 평균적으로 5만 건 정도 차팅했던 것 같아서 리스트 사이즈도 그 정도로 맞췄다.

public void runTest(double inputValue) {
        List<String> collection = makeStrCollection(50000);

        long startTime = System.currentTimeMillis();

        int approxIdx = searchApproxIdx(collection, inputValue);

        if(approxIdx > 0){
            System.out.println(inputValue + "의 근사값에 대한 인덱스: " + approxIdx + ", 값: " + collection.get(approxIdx));
        } else {
            System.out.println("근사값이 없습니다.");
        }

        long endTime = System.currentTimeMillis();

        System.out.println("============= 소요시간 : " + (endTime - startTime)/1000d + "s =============");
    }

    public List<String> makeStrCollection(int size) {
        List<String> collection = new ArrayList<>();

        for(int idx = 0; idx < size; idx++){
            collection.add(Double.toString(idx * 0.035));
        }

        return collection;
    }

결과는 매우 만족스러움! 마우스 이벤트라 최대한 빠르고 연산 수를 줄이는 방안으로... 출근해서 직접 적용하고 테스트 해봐야쥐... (참고로 List에 담기는 값이 double 형식이 아닌 케이스는 없다는 가정이기 때문에 parseDouble() 메서드의 예외처리는 따로 안해줬다)