]> git.ipfire.org Git - thirdparty/vim.git/commit
patch 9.1.0891: building the completion list array is inefficient v9.1.0891
authorglepnir <glephunter@gmail.com>
Wed, 27 Nov 2024 20:53:53 +0000 (21:53 +0100)
committerChristian Brabandt <cb@256bit.org>
Wed, 27 Nov 2024 20:53:53 +0000 (21:53 +0100)
commit80b662009c0fe8f1728a3f3a2c8013b7eebf6745
treef14889b11490742ab66930faa9fb0d1948875125
parentac023e8baae65584537aa3c11494dad6f71770af
patch 9.1.0891: building the completion list array is inefficient

Problem:  building the completion list array is inefficient
Solution: refactor and improve ins_compl_build_pum() func
          (glepnir)

current time complexity is O(n^2). I guess garray is not used here to save memory and avoid efficiency
is caused by heap memory allocation. A simple way is to add an extra pointer as a single linked list
to store the matching compl_T, and traverse this single linked list to generate compl_match_array.
The time complexity is O(n x m). The worst case is m=n, but we can still get a little improvement.
Because the if condition does not need to be run at one time. This should be a good solution for now.
Later we may be able to complete it in O(lgn) time. But this requires more reconstruction. So this is
the first step.

closes: #16125

Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
src/insexpand.c
src/version.c