Nutri Capture 백엔드 - 이진 탐색 적용

#1 삽입 함수 리팩토링

#1-1 리팩토링할 함수

// in NutrientViewModel.kt

private fun findIndexToInsert(list: SnapshotStateList<DayMealView>, newItem: DayMealView): Int {
    for(i: Int in list.indices) {
        if(newItem < list[i]) {
            return i
        }
    }
    // 삽입할 위치가 없다면 맨 끝(list.size)에 삽입
    return list.size
}

NutrientViewModel에는 정렬된 배열에 새 원소를 삽입하는 함수 findIndexToInsert()가 있다. 기존 findIndexToInsert()는 위 코드에서 보듯 선택 정렬의 원리로 짰다.
 

#1-2 이진 탐색

이진 탐색 (Binary search)

findIndexToInsert()는 정렬된 배열에서의 삽입을 수행한다. 즉, 이진 탐색의 원리를 적용할 수 있다.
 

#1-3 리팩토링된 함수

// in NutrientViewModel.kt

private fun findIndexToInsert(list: SnapshotStateList<DayMealView>, newItem: DayMealView): Int {
    var min = 0
    var max = list.size - 1

    while (min <= max) {
        val mid = (min + max) / 2

        // up
        if (list[mid] < newItem) {
            min = mid + 1

        // down
        } else if (list[mid] > newItem) {
            max = mid - 1

        // equal
        } else { // list[mid] == newItem
            return mid + 1
        }
    }

    return max + 1
}

이진 탐색이지만 내가 찾는 원소의 index를 반환하지는 않는다. 대신, 내가 삽입하고자 하는 원소를 어느 인덱스에 넣어야 할 지를 반환한다.
 

#2 테스트

#2-1 Unit Testing

[Android] Unit Testing - 기초

리팩토링한 함수 로직에 문제가 있거나 추후 심화시킬 때 문제가 생길 가능성이 있다. 따라서, 확실하게 매듭짓기 위해서 테스트 클래스를 만들어 테스트를 진행한다. 추후 로직을 심화시킬 때도, 지금 만들어둔 테스트 클래스를 활용하면 될 것이다.
 

#2-2 간소화한 findIndexToInsert()

// 간소화 전 인수: (list: SnapshotStateList<DayMealView>, newItem: DayMealView)
private fun findIndexToInsert(list: List<Long>, newItem: Long): Int {
    ...
}

테스트 클래스에서 사용할 findIndexToInsert()다. DayMealView는 총 3개의 비교 조건을 가지고 비교하지만, 여기에서는 mealId만을 가지고 비교한다. 왜냐하면, 3개의 비교 조건은 단순한 "<", ">", "==" 비교이기 때문이다. 하나를 검증하면 나머지는 따라온다. 따라서 findIndexToInsert가 (mealId과 다른 비교 조건이 전부 포함된) DayMealView가 아닌, mealId를 인수로 받도록 수정한다. DayMealView를 그대로 둬도 되지만 시간이 많이 걸릴 것이다. 지금 내게 필요한 것은 로직 검증이다.
 

#2-3 테스트 케이스

// 1
DayMealView.mealId의 배열: {} (빈 배열)
배열에 넣을 새 mealId: 1
삽입된 mealId의 위치(index): 0

// 2
DayMealView.mealId의 배열: {1, 7, 13}
배열에 넣을 새 mealId: 9
삽입된 mealId의 위치(index): 2

// 3
DayMealView.mealId의 배열: {2, 6, 7, 8, 10}
배열에 넣을 새 mealId: 11
삽입된 mealId의 위치(index): 5 

// 4
DayMealView.mealId의 배열: {1, 2, 3, 4}
배열에 넣을 새 mealId: 2
삽입된 mealId의 위치(index): 2

테스트에 사용할 예제다. 이 모든 예제들을 통과해야 리팩토링이 잘 완료된 것일테다.
 

#2-4 테스트 클래스

// package com.example.nutri_capture_new

import com.google.common.truth.Truth
import org.junit.Test


class FindIndexToInsertTest {
    private data class TestCase(
        val oldItems: List<Long>, val newItem: Long, val correctInsertedIndex: Int
    )

    private val testCases = listOf(
        TestCase(
            oldItems = emptyList(),
            newItem = 1,
            correctInsertedIndex = 0
        ),
        TestCase(
            oldItems = listOf(1, 7, 13),
            newItem = 9,
            correctInsertedIndex = 2
        ),
        TestCase(
            oldItems = listOf(2, 6, 7, 8, 10),
            newItem = 11,
            correctInsertedIndex = 5
        ),
        TestCase(
            oldItems = listOf(1, 2, 3, 4),
            newItem = 2,
            correctInsertedIndex = 2
        ),
    )

    @Test
    fun findIndexToInsert_givenTestcases_returnsCorrectIndex() {
        for (testCase in testCases) {
            val result = findIndexToInsert(testCase.oldItems, testCase.newItem)
            Truth.assertThat(result).isEqualTo(testCase.correctInsertedIndex)
        }
    }
}

private fun findIndexToInsert(list: List<Long>, newItem: Long): Int {
    var min = 0
    var max = list.size - 1

    while (min <= max) {
        val mid = (min + max) / 2

        // up
        if (list[mid] < newItem) {
            min = mid + 1

        // down
        } else if (list[mid] > newItem) {
            max = mid - 1

        // equal
        } else { // list[mid] == newItem
            return mid + 1
        }
    }

    return max + 1
}

위와 같이 작성해, Local unit test 자리에 넣는다. 처음에는 NutrientViewModel 클래스의 복사본을 통째로 테스트 클래스로 만들려고 했으나, 아직은 뷰모델에서 테스트할 게 없고 작성 도중에 불필요한 노력이라는 생각이 들어 중간에 그만뒀다.
 

#2-5 테스트 결과

무사히 통과했다. 또, 앱도 잘 동작한다.
 

#3 요약

NutrientViewModel.findIndexToInsert()의 로직에 이진 탐색을 적용했다.
 

#4 완성된 앱

#4-1 이 게시글 시점의 Commit

GitHub - Kanmanemone/nutri-capture-new

 

#4-2 본 프로젝트의 가장 최신 Commit

GitHub - Kanmanemone/nutri-capture-new