changes in this version:
- Updated comment and commit message as per review.
- Added another commit implementing optimization logic.
- added an RFC tag since, if the changes in 2nd commit are
appropriate, we can apply similar logic in other places as
well.
Meet Soni (2):
merge-recursive: optimize time complexity for process_renames
merge-recursive: optimize time complexity for get_unmerged
merge-recursive.c | 25 ++++++++++++-------------
1 file changed, 12 insertions(+), 13 deletions(-)
Range-diff:
1: ec96e4010e ! 1: c7dca6e971 merge-recursive: optimize string_list construction
@@ Metadata
Author: Meet Soni <meetsoni3017@xxxxxxxxx>
## Commit message ##
- merge-recursive: optimize string_list construction
+ merge-recursive: optimize time complexity for process_renames
- Avoid O(n^2) complexity when building a sorted `string_list` by
- constructing it unsorted and sorting it afterward, reducing the
- complexity to O(n log n).
+ 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@xxxxxxxxx>
## merge-recursive.c ##
@@ merge-recursive.c: static int process_renames(struct merge_options *opt,
- struct string_list b_by_dst = STRING_LIST_INIT_NODUP;
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
-: ---------- > 2: 78a007be7d merge-recursive: optimize time complexity for get_unmerged
--
2.34.1
