Stata The Stata listserver
[Date Prev][Date Next][Thread Prev][Thread Next][Date index][Thread index]

Re: st: RE: is ordering with -bysort- unique?


From   Jingsong Cui <cui@temple.edu>
To   statalist@hsphsun2.harvard.edu
Subject   Re: st: RE: is ordering with -bysort- unique?
Date   Wed, 11 Jun 2003 10:11:34 -0400

What Nick said is interesting, and a little puzzling at 
first thought. The problem that different results are 
returned for the same input is indeed possible, if any 
randomized algorithm, for example, randomized quicksort, is 
used during -sort-. (I do not know which sort algorithm(s) 
Stata uses.)

One version of randomizations is, as Nick described, to 
permute the original input before any sorting is done. As I 
understand, the main purpose of this extra step is to make 
sure the performance of quicksorting is independent of the 
original input. That is, after randomization, sorting will 
achieve expected efficiency most of the time, even when the 
original input is badly ordered. In the jargons of computer 
scientist, for any input, most randomizations will cause 
quicksort to perform nearly as well as the average case of O
(nlgn).

Jingsong Cui
Department of Economics
Temple University

Nick said:
---- Original message ----
>Date: Tue, 10 Jun 2003 22:54:10 +0100
>From: "Nick Cox" <n.j.cox@durham.ac.uk>  
>Subject: st: RE: is ordering with -bysort- unique?  
>To: <statalist@hsphsun2.harvard.edu>

>Will the answer be the same? In general, I doubt it.
>At least some of the time Stata appears to randomize
>the order a little before -sort-ing, although I can't
>remember why I think I know that; anyway, I doubt that the 
answer
>is reproducible. I wouldn't depend on it.
>
>Nick
>n.j.cox@durham.ac.uk
>
*
*   For searches and help try:
*   http://www.stata.com/support/faqs/res/findit.html
*   http://www.stata.com/support/statalist/faq
*   http://www.ats.ucla.edu/stat/stata/



© Copyright 1996–2014 StataCorp LP   |   Terms of use   |   Privacy   |   Contact us   |   What's new   |   Site index