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

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 30, 2008, 15:36 UTC
Message-ID: <7vsksm1pmd.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <20080828212722.GF6439@steel.home>

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

Show 19 quoted lines

> @@ -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).