<br><br><div class="gmail_quote">On Wed, Sep 30, 2009 at 10:07 PM, Enzo Michelangeli <span dir="ltr">&lt;<a href="mailto:enzomich@gmail.com">enzomich@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="im">From: &quot;Sturla Molden&quot; &lt;<a href="mailto:sturla@molden.no">sturla@molden.no</a>&gt;<br>
</div>Sent: Thursday, October 01, 2009 6:09 AM<br>
<div class="im"><br>
&gt; Enzo Michelangeli skrev:<br>
&gt;&gt; Dear all,<br>
&gt;&gt;<br>
&gt;&gt; A few days ago I posted to <a href="http://projects.scipy.org/scipy/ticket/999" target="_blank">http://projects.scipy.org/scipy/ticket/999</a> a<br>
&gt;&gt; drop-in replacement for scipy.stats.kendalltau.<br>
&gt; Why do you re-implement mergesort in pure Python?<br>
&gt;<br>
&gt; ndarrays have a sort method that can use mergesort.<br>
&gt;<br>
&gt; Python lists has the same (timsort is mergesort on steroids).<br>
<br>
</div>Because Knight&#39;s algorithm needs to count the number of swaps (or, to be<br>
more precise, the number of swaps that would be performed by an equivalent<br>
bubblesort). In the code, that&#39;s the purpose of the variable exchcnt .<br>
<br>
An alternative algorithm for the Kendall Tau developed by David Christensen,<br>
and described at <a href="http://www.springerlink.com/content/p33qu44058984082/" target="_blank">http://www.springerlink.com/content/p33qu44058984082/</a> (with<br>
a Delphi implementation), replaces the mergesort step with one based on<br>
balanced binary trees (AVL in his case, but I guess RBT would also work).<br>
Unfortunately, neither the standard Python library nor NumPy/SciPy appear to<br>
implement such useful data structures, and what is available either doesn&#39;t<br></blockquote><div><br>Yep, we could use some more of those useful data structures. A &quot;computer science&quot; library would be useful. The scipy.spacial library is step in that direction but it would be nice if there were more such.<br>
<br>Chuck <br></div><br></div>