From:
<jmf...@cn...> - 2005-11-28 18:46:50
Attachments:
errlist-verbose.txt.gz
|
Hi everybody, I have been researching (and hacking around) about the=20 StackOverflowError problem I described you one week ago, and these are=20 my conclussions: 1.- There is no bug in FastQSort algorithm, but eXist does generate the=20 worst cases for the algorithm (those of them related to recursive=20 calls). I added a try/catch construction around QuickSort recursive=20 calls inside FastQSort.QuickSort in order to print the values of l, r, i=20 and j when the StackOverflowError is fired. The file I have attached to=20 this e-mail contains the standard output and error messages from eXist=20 in embedded mode, plus the different l, r, i and j values. As you can=20 see there, although it is still converging, it is slow. 2.- I have found a way to mitigate this recursion problem, related to=20 the last QuickSort recursive call inside QuickSort (I have unfolded it=20 because it is a typical tail-recursion case). Here it is the change for=20 QuickSort(List,int,int) (for instance): private final static void QuickSort(List a, int l, int r) //---------------------------------------------------- { int M =3D 4; int i; int j; Object v; while ((r - l) > M) { // 26july00: following [.][1] -> [.][0] i =3D (r + l) / 2; if (((Comparable) a.get(l)).compareTo(a.get(i)) > 0) swap(a, l, i); // Tri-Median Methode! if (((Comparable) a.get(l)).compareTo(a.get(r)) > 0) swap(a, l, r); if (((Comparable) a.get(i)).compareTo(a.get(r)) > 0) swap(a, i, r); j =3D r - 1; swap(a, i, j); i =3D l; v =3D a.get(j); for (;;) { while (((Comparable) a.get(++i)).compareTo(v) < 0); while (((Comparable) a.get(--j)).compareTo(v) > 0); if (j < i) break; swap(a, i, j); } swap(a, i, r - 1); QuickSort(a, l, j); l =3D i + 1; } } I have tested it and at least the StackOverflowError is not fired for=20 the scenario I explained you last time. Similar changes should be=20 applied to the different QuickSort versions inside FastQSort. The long=20 term solution is either replacing FastQSort implementations by an=20 algorithm which limits the recursion calls (I'm working on that, with no=20 clear success yet), or changing the way eXist generates the list/array=20 of elements to be ordered, so they are not one of the worst cases for=20 the current implementation of the sorting algorithm. Best Regards, Jos=E9 Mar=EDa --=20 Jos=E9 Mar=EDa Fern=E1ndez Gonz=E1lez e-mail: jmf...@cn... Tlfn: (+34) 91 585 54 50 Fax: (+34) 91 585 45 06 Grupo de Dise=F1o de Proteinas Protein Design Group Centro Nacional de Biotecnolog=EDa National Center of Biotechnology C.P.: 28049 Zip Code: 28049 C/. Darwin n=BA 3 (Campus Cantoblanco, U. Aut=F3noma), Madrid (Spain) |
From: Wolfgang M. <wol...@gm...> - 2005-11-28 21:50:42
|
Hi, > 2.- I have found a way to mitigate this recursion problem, related to > the last QuickSort recursive call inside QuickSort (I have unfolded it > because it is a typical tail-recursion case). Here it is the change for > QuickSort(List,int,int) (for instance): It's great you found this! I discovered this variant of quick sort somewhere on the web (can't remember where) and adopted it to my needs. If you find a better algorithm which limits the amount of recursion, it will be more than welcome. Changing the way in which eXist passes the list would be difficult. FastQSort is called in different contexts, and in some cases, the lists may already be pre-ordered. Wolfgang |