Re: [PATCH updated] git wrapper: DWIM mistyped commands

[Junio C Hamano <gitster@pobox.com>]

Alex Riesen <raa.lkml@gmail.com> writes:

> @@ -257,9 +258,70 @@ int is_in_cmdlist(struct cmdnames *c, const char *s)
> ...
> +static const char *levenshtein_cmd;
> +static int similarity(const char *cmd) {
> +	return levenshtein(levenshtein_cmd, cmd, 0, 2, 1, 4);
> +}
> +
> +static int levenshtein_compare(const void *p1, const void *p2)
>  {
> +	const struct cmdname *const *c1 = p1, *const *c2 = p2;
> +	const char *s1 = (*c1)->name, *s2 = (*c2)->name;
> +	int l1 = similarity(s1);
> +	int l2 = similarity(s2);
> +	return l1 != l2 ? l1 - l2 : strcmp(s1, s2);
> +}
> ...
> +	levenshtein_cmd = cmd;
> +	qsort(main_cmds.names, main_cmds.cnt,
> +	      sizeof(*main_cmds.names), levenshtein_compare);

Isn't this awfully inefficient?

You have one mistyped command name to compute distance against, and want
to sort the available 100+ command names by that distance.  In qsort(),
levenshtein_compare() will be called O(N log N) times (depending on your
qsort implementation)?

I wonder if it makes sense to give an otherwise unused "score" member to
the "struct cmdname", compute the distance only once per each command, and
use that as the sort key (alternatively you can have a separate int[N]
array to store similarity values for each item in the cmdnames list, only
used inside this codepath).