Skip to content

consider binary search in simplify.R #16

@shawnlaffan

Description

@shawnlaffan

The while loop in simplify.R takes a long time with large data sets. It seems to iterate from one end of the list to close to the minimum threshold.

while(min(pct) < pct_thr && length(pct) > k_thr) {

I don't entirely follow the code at the moment but if min(pct) always decreases monotonically then one can use a binary search to reduce the number of calculations. This will work in O(log n) time instead of O(n), on average.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions