[안드로이드] 가장 가까운값 찾기 (근사값 / 시간단축)

 

최근에 두 개의 데이터들을 통해서 가장 가까운 값들의 결과가 필요한 상황이 있었는데요,

(1) 근사 값을 구하는 방법 및 (2) 많은 근사값을 구해야 할때의 시간지연 대해 

정리하려고 합니다.

1. 근사값 구하기

여러 데이터들(targetList) 중에서 특정 값(value)과 가장 가까운 값을 찾는 메서드 입니다.

private fun getNearValue(targetList: ArrayList<Int>,
                         value: Int): Int {

    var temp: Int
    var min = Int.MAX_VALUE
    var nearValue = 0

    val size = targetList.size
    for (i in 0 until size) {
        temp = abs(targetList[i] - value)
        if (min > temp) {
            min = temp
            nearValue = targetList[i]
        }
    }
    return nearValue
}

여기서 해당 메서드를 사용할때 참조데이터(targetList) 길이가 짧고 메서드 호출을 해야되는 상황이 많지 않다면 위와같이 사용하시면 될 것같습니다.

 하지만 그 반대의 상항에서는 문제가 있습니다. 바로 시간이 오래 걸릴 수 있다는 점입니다.

override fun onCreate(savedInstanceState: Bundle?) {
    super.onCreate(savedInstanceState)
    setContentView(R.layout.activity_main)

    val startTime = System.currentTimeMillis()
    val nearValueList = ArrayList<Int>()

    val rnd = Random()
    val targetList = ArrayList<Int>()
    for (i in 0 until 20000) {
        targetList.add(rnd.nextInt(100000))
    }

    val valueList = ArrayList<Int>()
    for (i in 0 until 20000) {
        valueList.add(rnd.nextInt(100000))
    }

    val size = valueList.size
    for (i in 0 until size) {
        val nearValue = getNearValue(targetList, valueList[i])
        nearValueList.add(nearValue)
    }

    Log.d("logging", "targetList $targetList")
    Log.d("logging", "valueList $valueList")
    Log.d("logging", "nearValueList $nearValueList")

    val completedTime = System.currentTimeMillis()
    val timeStamp = SimpleDateFormat("ss.SSS").format(completedTime - startTime)
    Log.d("logging", "Operating time $timeStamp sec")
}

2만개의 valueList 에 있는 모든 데이터 근사값을 구하는데 걸린 시간은 2.5초정도로 확인되었습니다.

[Operating time 02.551 sec]

2. 근사값 구하기 - 시간단축

시간 단축방법을 고민하다가 근사값 구하는 메서드의 for문을 효율적으로 변경하려고합니다.

똑같은 조건에서 targetList 오름차순정렬을해줍니다.

override fun onCreate(savedInstanceState: Bundle?) {
    super.onCreate(savedInstanceState)
    setContentView(R.layout.activity_main)

    val startTime = System.currentTimeMillis()
    val nearValueList = ArrayList<Int>()

    val rnd = Random()
    val targetList = ArrayList<Int>()
    for (i in 0 until 20000) {
        targetList.add(rnd.nextInt(100000))
    }

    val valueList = ArrayList<Int>()
    for (i in 0 until 20000) {
        valueList.add(rnd.nextInt(100000))
    }

    targetList.sort() // 오름차순정렬(추가)

    val size = valueList.size
    for (i in 0 until size) {
        val nearValue = getNearValue(targetList, valueList[i])
        nearValueList.add(nearValue)
    }

    Log.d("logging", "targetList $targetList")
    Log.d("logging", "valueList $valueList")
    Log.d("logging", "nearValueList $nearValueList")

    val completedTime = System.currentTimeMillis()
    val timeStamp = SimpleDateFormat("ss.SSS").format(completedTime - startTime)
    Log.d("logging", "Operating time $timeStamp sec")
}

 

tagetList 가 오름차순정렬로 되었기때문에 근사값을 찾을 때 모든값을 비교할 필요가 없어집니다.

마지막으로 근사값이 업데이트 된 이후의 값들은 모두 그 차이가 더 클수밖에 없기 때문입니다.

private fun getNearValue(targetList: ArrayList<Int>,
                         value: Int): Int {

    var temp: Int
    var min = Int.MAX_VALUE
    var nearValue = 0

    val size = targetList.size
    for (i in 0 until size) {
        temp = abs(targetList[i] - value)
        if (min > temp) {
            min = temp
            nearValue = targetList[i]
        } else {
            break // 그 이후 값들은 모두 더 큰수이기 때문에 확인할 필요없음(추가)
        }
    }
    return nearValue
}

시간을 확인해보니 0.06초 정도가 소요되었습니다. 많이 단축되었네요

 [Operating time 00.065 sec]

 

 

끝으로..

코딩하다보면 for 문을 참 많이 사용하는데요..

불필요하게 for문을 끝까지 돌리고 있는게 또 있지 않을까..? 라는 걱정이 되네요

앞으로 for문은 한번씩 꼭 확인해야겠다는 생각이 들었습니다.