| Message ID | 20250213090040.16133-2-meetsoni3017@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | merge-recursive: optimize time complexity | expand |
On Thu, Feb 13, 2025 at 1:00 AM Meet Soni <meetsoni3017@gmail.com> wrote: > > Avoid O(n^2) complexity in `process_renames()` when building a sorted > `string_list` by constructing it unsorted and sorting it afterward, > reducing the complexity to O(n log n). > > Signed-off-by: Meet Soni <meetsoni3017@gmail.com> > --- > merge-recursive.c | 15 +++++++-------- > 1 file changed, 7 insertions(+), 8 deletions(-) > > diff --git a/merge-recursive.c b/merge-recursive.c > index 5dfaf32b2c..884ccf99a5 100644 > --- a/merge-recursive.c > +++ b/merge-recursive.c > @@ -2758,23 +2758,22 @@ static int process_renames(struct merge_options *opt, > const struct rename *sre; > > /* > - * FIXME: As string-list.h notes, it's O(n^2) to build a sorted > - * string_list one-by-one, but O(n log n) to build it unsorted and > - * then sort it. Note that as we build the list, we do not need to > - * check if the existing destination path is already in the list, > - * because the structure of diffcore_rename guarantees we won't > - * have duplicates. > + * Note that as we build the list, we do not need to check if the > + * existing destination path is already in the list, because the > + * structure of diffcore_rename guarantees we won't have duplicates. > */ > for (i = 0; i < a_renames->nr; i++) { > sre = a_renames->items[i].util; > - string_list_insert(&a_by_dst, sre->pair->two->path)->util > + string_list_append(&a_by_dst, sre->pair->two->path)->util > = (void *)sre; > } > for (i = 0; i < b_renames->nr; i++) { > sre = b_renames->items[i].util; > - string_list_insert(&b_by_dst, sre->pair->two->path)->util > + string_list_append(&b_by_dst, sre->pair->two->path)->util > = (void *)sre; > } > + string_list_sort(&a_by_dst); > + string_list_sort(&b_by_dst); > > for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) { > struct string_list *renames1, *renames2Dst; > -- > 2.34.1 This version looks good to me.
diff --git a/merge-recursive.c b/merge-recursive.c index 5dfaf32b2c..884ccf99a5 100644 --- a/merge-recursive.c +++ b/merge-recursive.c @@ -2758,23 +2758,22 @@ static int process_renames(struct merge_options *opt, const struct rename *sre; /* - * FIXME: As string-list.h notes, it's O(n^2) to build a sorted - * string_list one-by-one, but O(n log n) to build it unsorted and - * then sort it. Note that as we build the list, we do not need to - * check if the existing destination path is already in the list, - * because the structure of diffcore_rename guarantees we won't - * have duplicates. + * Note that as we build the list, we do not need to check if the + * existing destination path is already in the list, because the + * structure of diffcore_rename guarantees we won't have duplicates. */ for (i = 0; i < a_renames->nr; i++) { sre = a_renames->items[i].util; - string_list_insert(&a_by_dst, sre->pair->two->path)->util + string_list_append(&a_by_dst, sre->pair->two->path)->util = (void *)sre; } for (i = 0; i < b_renames->nr; i++) { sre = b_renames->items[i].util; - string_list_insert(&b_by_dst, sre->pair->two->path)->util + string_list_append(&b_by_dst, sre->pair->two->path)->util = (void *)sre; } + string_list_sort(&a_by_dst); + string_list_sort(&b_by_dst); for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) { struct string_list *renames1, *renames2Dst;
Avoid O(n^2) complexity in `process_renames()` when building a sorted `string_list` by constructing it unsorted and sorting it afterward, reducing the complexity to O(n log n). Signed-off-by: Meet Soni <meetsoni3017@gmail.com> --- merge-recursive.c | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-)