Как сравнить два списка по пунктам в Kotlin - PullRequest
Новая
       10

Как сравнить два списка по пунктам в Kotlin

0 голосов
/ 02 августа 2020

как я могу сравнить «Список A» со «Списком B», и если «список A» имеет «n» элементов, которые соответствуют «списку B», создать «C список» из «списка A» с логическим значением, прикрепленным в качестве нового поля к каждому элементу, поэтому, если элемент был в «списке B», это правда, иначе false.

вот подробный пример того, что я пытаюсь сделать: 

data class ListAelement(
    val fieldA: Double = 2.0,
    //this is the field that i have to check with listB
    val id: String = "12345",
    val somefield: String,
    val someotherfield: String
)

data class ListBelement(
    //list b only has id
    val id: String = "12345"
)

data class ListCelement(
    val fieldA: Double = 2.0,
    val id: String = "12345",
    val somefield: String,
    val someotherfield: String,
    //this should be true if it is in ListB
    val isElementInA: Boolean
)



fun isEqual(listA: List<ListAelement>, listB: List<ListBelement>): List<ListCelement> {
    
   
    return emptyList()
}



fun main() {
    val listA = listOf<ListAelement>(
        ListAelement(1.2, "12345"),
        ListAelement(1.2, "12343"),
        ListAelement(1.2, "1234566"),
        ListAelement(1.2, "11233")
    )
    val listB = listOf<ListBelement>(ListBelement("12345"), ListBelement("123123"))
    //new list
    val listC = isEqual(listA, listB)

}

Пытался следовать 

val listASize = listA.size 
val listBSize = listB.size 
var counter = 0 
while (counter < listASize) { 
    var id = listA[counter].id 
    listB.forEach { 
         if (it.id == id) { 
           println("matched item $it") 
         } 
    } 
    counter++ 
}

принятый ответ работает так, как должен, вот что я пытался достичь:

«список A» - это ответ Api, «список B "- это локальная база данных, а список C предназначен для ее отображения и проверки наличия элемента в локальной базе данных

1 Ответ

0 голосов
/ 02 августа 2020

По сути, у вас есть проблема поиска.

Я немного изменил вашу реализацию, чтобы сделать ее более точной для справки: 

fun isEqual(listA: List<ListAelement>, listB: List<ListBelement>): List<ListCelement> {

    val listC: MutableList<ListCelement> = mutableListOf()

    // you don't need a while loop or a counter variable as you need to look at every item in list A
    listA.forEach { listAItem ->
        var found = false

        // search for each item in list A in list B
        // this is a linear search
        listB.forEach { listBItem -> 
             if (listBItem.id == listAItem.id) { 
               // println("matched item $it") 
               found = true // cache the result that it has been found rather than printing out
             } 
        }

        // create your list C with the ListCelement instance that holds the result of whether it was found in List B or not
        listC.add(
            ListCelement(id=listAItem.id, isElementInA=found)
        ) 
    }

    return listC
}

Текущая реализация имеет временную сложность = O (N * M) (где N и M - размеры списков A и B), потому что для каждого элемента в списке A вы должны перебирать список B при выполнении линейного поиска для него.

Это можно оптимизировать с помощью бинарного поиска . Однако двоичный поиск требует сортировки пространства поиска. В вашем случае список B, являющийся пространством поиска, должен быть отсортирован по полю id, так как вы определяете элементы списка A, которые находятся в списке B.

Он имеет временную сложность = O (log N) (где N - размер области поиска), потому что вы используете порядок в пространстве поиска, чтобы отбрасывать половину элементов при каждой попытке, пока вы не найдете свой элемент поиска или не уменьшите пространство поиска к одному элементу, который не является вашим элементом поиска, и в этом случае вы выходите из поиска.

Ниже представлена ​​реализация с использованием двоичного поиска: 

/**
 * We declare a package-level function main which returns Unit and takes
 * an Array of strings as a parameter. Note that semicolons are optional.
 */
data class ListAelement(
    val fieldA: Double = 2.0,
    // this is the field that i have to check with listB
    val id: String,
    val someField: String,
    val someOtherField: String
)

data class ListBelement(
    // list b only has id
    val id: String
)

data class ListCelement(
    val fieldA: Double = 2.0,
    val id: String,
    val someField: String,
    val someOtherField: String,
    // this should be true if it is in ListB
    val isElementInA: Boolean
)

fun isEqual(listA: List<ListAelement>, listB: List<ListBelement>): List<ListCelement> {
    val sortedListB = listB.sortedWith(compareBy({ it.id }))

    val listC: MutableList<ListCelement> = mutableListOf()
    
    listA.forEach { listAItem ->    
        listC.add(
            ListCelement(
                id=listAItem.id, 
                someField=listAItem.someField,
                someOtherField=listAItem.someOtherField,
                isElementInA=binarySearchListB(sortedListB, listAItem) // linear search replaced with this binary search
            )
        )
    }
    return listC
}

// the kotlin collections package ships with a binarySearch() function https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/binary-search.html
// I have opted to implement a custom one so that I can have a Boolean return type
fun binarySearchListB(searchSpace:List<ListBelement>, searchItem: ListAelement, leftIndex:Int = 0, rightIndex: Int = searchSpace.size - 1): Boolean {
    val midIndex: Int = (leftIndex + rightIndex) / 2
    val midItem: ListBelement = searchSpace[midIndex]

    // exit condition if item does not exist
    if (leftIndex == rightIndex && searchItem.id != searchSpace[leftIndex].id) {
        return false
    }

    if (midItem.id == searchItem.id) {
        // found
        return true
    } else if(searchItem.id < midItem.id) {
        // go to the left
        return binarySearchListB(searchSpace, searchItem, leftIndex, midIndex - 1)
    } else if(searchItem.id > midItem.id) {
        // go to the right
        return binarySearchListB(searchSpace, searchItem, midIndex + 1, rightIndex)
    }
    return false
}

fun main(args: Array<String>) {
    val listA = listOf<ListAelement>(
        ListAelement(1.2, "12345", "someField", "someOtherField"),
        ListAelement(1.2, "12343", "someField", "someOtherField"),
        ListAelement(1.2, "1234566", "someField", "someOtherField"),
        ListAelement(1.2, "11233", "someField", "someOtherField")
    )
    val listB = listOf<ListBelement>(ListBelement("1234566"), ListBelement("12345"), ListBelement("123123"))
    // new list
    val listC = isEqual(listA, listB)
    println(listC)
}

Вот результат: 

[ListCelement(fieldA=2.0, id=12345, someField=someField, someOtherField=someOtherField, isElementInA=true), ListCelement(fieldA=2.0, id=12343, someField=someField, someOtherField=someOtherField, isElementInA=false), ListCelement(fieldA=2.0, id=1234566, someField=someField, someOtherField=someOtherField, isElementInA=true), ListCelement(fieldA=2.0, id=11233, someField=someField, someOtherField=someOtherField, isElementInA=false)]

ОБНОВЛЕНИЕ:

Вот обновление, которое преобразует список B в HashSet строк, содержащих идентификаторы ListBelement, чтобы получить поиск с постоянным временем (т.е. O (1) ), как предложено в комментариях: 

/**
 * We declare a package-level function main which returns Unit and takes
 * an Array of strings as a parameter. Note that semicolons are optional.
 */
data class ListAelement(
    val fieldA: Double = 2.0,
    // this is the field that i have to check with listB
    val id: String,
    val someField: String,
    val someOtherField: String
)

data class ListBelement(
    // list b only has id
    val id: String
)

data class ListCelement(
    val fieldA: Double = 2.0,
    val id: String,
    val someField: String,
    val someOtherField: String,
    // this should be true if it is in ListB
    val isElementInA: Boolean
)

fun isEqual(listA: List<ListAelement>, listB: List<ListBelement>): List<ListCelement> {
    // construct a HashSet of string ids from listB
    // there could be a more idiomatic way to do it
    // more about HashSet here -> https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-hash-set/
    val listBHashSet: HashSet<String> = hashSetOf()
    listB.forEach { listBItem -> 
        listBHashSet.add(listBItem.id)
    }
    
    val listC: MutableList<ListCelement> = mutableListOf()
    
    listA.forEach { listAItem ->    
        listC.add(
            ListCelement(
                id=listAItem.id, 
                someField=listAItem.someField,
                someOtherField=listAItem.someOtherField,
                isElementInA=listBHashSet.contains(listAItem.id) // linear search replaced with this hashset lookup search
            )
        )
    }
    return listC
}

fun main(args: Array<String>) {
    val listA = listOf<ListAelement>(
        ListAelement(1.2, "12345", "someField", "someOtherField"),
        ListAelement(1.2, "12343", "someField", "someOtherField"),
        ListAelement(1.2, "1234566", "someField", "someOtherField"),
        ListAelement(1.2, "11233", "someField", "someOtherField")
    )
    val listB = listOf<ListBelement>(ListBelement("1234566"), ListBelement("12345"), ListBelement("123123"))
    // new list
    val listC = isEqual(listA, listB)
    println(listC)
}

Вывод: 

[ListCelement(fieldA=2.0, id=12345, someField=someField, someOtherField=someOtherField, isElementInA=true), ListCelement(fieldA=2.0, id=12343, someField=someField, someOtherField=someOtherField, isElementInA=false), ListCelement(fieldA=2.0, id=1234566, someField=someField, someOtherField=someOtherField, isElementInA=true), ListCelement(fieldA=2.0, id=11233, someField=someField, someOtherField=someOtherField, isElementInA=false)]
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...