Kim & Kutzner tamc2008 paper: analysis in the case of a lot of identical key elements for sorting #2
Comments
nsajko
pushed a commit
that referenced
this issue
Mar 25, 2019
Most chars in URLs are lowercase, so check that first. Performance change: String-4 7.62µs ± 1% 7.27µs ± 3% -4.61% (p=0.008 n=5+5) QueryEscape/#00-4 92.6ns ± 3% 90.3ns ± 1% -2.48% (p=0.016 n=5+5) QueryEscape/#1-4 515ns ± 4% 510ns ± 2% ~ (p=0.683 n=5+5) QueryEscape/#2-4 375ns ± 1% 343ns ± 1% -8.52% (p=0.008 n=5+5) QueryEscape/#3-4 758ns ± 1% 699ns ± 1% -7.83% (p=0.008 n=5+5) QueryEscape/#04-4 6.06µs ± 1% 5.74µs ± 1% -5.38% (p=0.008 n=5+5) PathEscape/#00-4 140ns ± 1% 135ns ± 2% -3.85% (p=0.008 n=5+5) PathEscape/#1-4 511ns ± 3% 507ns ± 3% ~ (p=0.587 n=5+5) PathEscape/#2-4 372ns ± 1% 342ns ± 2% -8.22% (p=0.008 n=5+5) PathEscape/#3-4 747ns ± 1% 685ns ± 1% -8.30% (p=0.008 n=5+5) PathEscape/#04-4 5.94µs ± 1% 5.64µs ± 3% -4.98% (p=0.008 n=5+5) QueryUnescape/#00-4 111ns ± 4% 110ns ± 2% ~ (p=0.952 n=5+5) QueryUnescape/#1-4 390ns ± 0% 391ns ± 2% ~ (p=0.714 n=5+5) QueryUnescape/#2-4 297ns ± 5% 295ns ± 3% ~ (p=0.524 n=5+5) QueryUnescape/#3-4 543ns ± 3% 556ns ± 2% +2.39% (p=0.032 n=5+5) QueryUnescape/#04-4 3.23µs ± 3% 3.22µs ± 2% ~ (p=1.000 n=5+5) PathUnescape/#00-4 111ns ± 1% 110ns ± 3% ~ (p=0.881 n=5+5) PathUnescape/#1-4 389ns ± 2% 386ns ± 2% ~ (p=0.444 n=5+5) PathUnescape/#2-4 297ns ± 1% 295ns ± 3% ~ (p=0.738 n=5+5) PathUnescape/#3-4 557ns ± 3% 553ns ± 2% ~ (p=0.810 n=5+5) PathUnescape/#04-4 2.94µs ± 2% 2.97µs ± 2% ~ (p=0.222 n=5+5) Change-Id: I7e6d64cd5f8f5218cb40f52f0015168a8674aabb Reviewed-on: https://go-review.googlesource.com/c/go/+/168883 Reviewed-by: Brad Fitzpatrick <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@vdobler
Please take a look at Theorem 1 in the paper. It proves that the merge takes O(n) assignments, but the reasoning for the case where the rotation based variant of Hwang&Lin should be used for local merges is left to the reader to prove in the end, with a pointer to Lemma 3. To be honest, it seems to me that the proof does not even work for that case, that is that the merge is O(n * sqrt(n)) in that case instead of O(n).
Links to paper: https://pdfs.semanticscholar.org/9533/29f19587e24b0969b7e0b55d5e92f3dcab2a.pdf
http://itbe.hanyang.ac.kr/ak/papers/tamc2008.pdf
The text was updated successfully, but these errors were encountered: