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

["Alex Riesen" <raa.lkml@gmail.com>]

2008/8/30 Junio C Hamano <gitster@pobox.com>:
>> +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.