[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#20365: 24.5; all-completions returns duplicates for Info-read-node-n
From: |
Dmitry Gutov |
Subject: |
bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1 |
Date: |
Sun, 19 Apr 2015 19:44:04 +0300 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:36.0) Gecko/20100101 Thunderbird/36.0 |
On 04/19/2015 02:53 PM, Oleh Krehel wrote:
About the duplicate entries, I think it should be the responsibility
of the caller to remove the duplicates.
That could have been a decent argument if we're discussing a new API,
and not an already widely-used one.
Here's my line of thought: a
completion function is expected to have an O(N) complexity, where N is
the amount of candidates. Removing duplicates is O(N^2) at worst, and
O(NlogN) at best.
O(NlogN) is closer to the truth:
First, you copy - O(N), then sort - O(NlogN), then call
`delete-consecutive-dups' (linear time).
So the completion function should not attempt to
remove the duplicates. It's doesn't affect the performance when I do
it for 1000 candidates, but when it's 20k (`describe-function') it can
have an impact.
Even on a decently-sized collection (38K), this takes only 80ms:
(delete-consecutive-dups (sort (all-completions "" obarray) #'string<))
That's not terrible.
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Oleh Krehel, 2015/04/18
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Stefan Monnier, 2015/04/18
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Oleh Krehel, 2015/04/18
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Stefan Monnier, 2015/04/18
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Oleh Krehel, 2015/04/19
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Drew Adams, 2015/04/19
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1,
Dmitry Gutov <=
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Oleh Krehel, 2015/04/19
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Dmitry Gutov, 2015/04/19
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Stefan Monnier, 2015/04/19
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Oleh Krehel, 2015/04/20
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Oleh Krehel, 2015/04/20
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Stefan Monnier, 2015/04/20
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Oleh Krehel, 2015/04/20
- bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Stefan Monnier, 2015/04/20
bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1, Drew Adams, 2015/04/18