Skip to content

Possible O(n^2) instead of O(n) cost ? #108

@Dennis4b

Description

@Dennis4b

Consider the following example:

def test() = {
    val itemCount = 1000
    val filterText = Var("")
    val items = Var( (0 until itemCount).map(idx => (idx, s"Item ${idx}")))
    val filteredItems = items.signal.combineWith(filterText.signal).map{
        case (its, "") => its
        case (its, x) => its.filter(_._2.contains(x)).toList
    }

    div(
        div(
            input(
                `type`("text"),
                value <-- filterText,
                onInput.mapToValue --> filterText
            )
        ),
        div(
            children <-- filteredItems.split(_._1)( (idx, initial, fstream) => {
                div(s"I am item: ${initial._2}")
            })
        )
    )
}                                                                                            

(As test input, just enter for example "2")

With itemCount = 1000, it takes well under a second to react
With itemCount = 2000, it takes several seconds to react
With itemCount = 3000, it takes until the browser warns about stopping the script because things are taking so long

I believe this should be linear degradation in n. Could there be a list lookup (instead of map lookup), or nested iteration, or similar, causing the execution time to explode as n grows?

(yes, while unusual, I have a component like this in production, currently with React where this works ok-ish, but creating the next version in Laminar and running into this problem)

Happy to test any suggestions!

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions