Re: [PATCH updated] git wrapper: DWIM mistyped commands
2008/8/30 Junio C Hamano <gitster@pobox.com>:
Show 19 quoted lines
>> +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)?not only similarity, but strcmp as well.
> I wonder if it makes sense to give an otherwise unused "score" member to
Hmm, it is a _non-existing_ member of cmdname, isn't it?
> 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).
I think I'll take the struct cmdname->len over.
Alex Riesen <raa.lkml@gmail.com>