[PATCH] sparse-checkout: optimize string_list construction
Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list' by constructing it unsorted and sorting it afterwards.
Signed-off-by: amisha <amishhhaaaa@gmail.com>
---
Note for reviewers:
I identified this as a strong candidate for optimization because we are
pulling entries from a hashmap. Since hashmaps inherently guarantee
uniqueness of keys, using string_list_append() is safe here.
builtin/sparse-checkout.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c
index 15d51e60a8..0a44808ed2 100644
--- a/builtin/sparse-checkout.c
+++ b/builtin/sparse-checkout.c
@@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,
hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {
/* pe->pattern starts with "/", skip it */
- string_list_insert(&sl, pe->pattern + 1);
+ string_list_append(&sl, pe->pattern + 1);
}
string_list_sort(&sl);
--
2.51.0
amisha <amishhhaaaa@gmail.com>