On 24 Dec 2007 10:11:02 +0300, Egor Pasko <[EMAIL PROTECTED]> wrote:
> On the 0x3B6 day of Apache Harmony Andrew Zhang wrote:
> > On Dec 24, 2007 7:44 AM, Nathan Beyer <[EMAIL PROTECTED]> wrote:
> >
> > > Can post the code that you're seeing this in? At least a
> > > representative example of the code would be needed to do any analysis.
> >
> >
> > Hi,
> >
> > You can find code here:
> >
> http://zhanghuangzhu.blogspot.com/2007/12/quicksort-runs-slower-on-harmony.html
>
> How to compile this?
Sorry, my mistake...
I pasted the source code directly to the blog. I didn't use <, > , so
"<...>" is gone. Here's the code:
import java.util.*;
public class GenericQuicksort {
public static void main(String[] args) {
int[] ints = new int[50000];
for (int i = 0; i < ints.length; i++) {
ints[i] = i + 1;
}
QuickSortableIntArray sample = new QuickSortableIntArray(ints);
long begin = System.currentTimeMillis();
GenericQuicksort.qsort(sample);
long end = System.currentTimeMillis();
System.out.println("elapsed: " + (end - begin) + "ms");
}
private static class Range {
int _from;
int _to;
public Range(int from, int to) {
_from = from;
_to = to;
}
}
public static void qsort(QuickSortable sortable) {
LinkedList<Range> stack = new LinkedList<Range>();
addRange(stack, 0, sortable.size() - 1);
qsort(sortable, stack);
}
private static void qsort(QuickSortable sortable, LinkedList<Range>
stack) {
while (!stack.isEmpty()) {
Range range = stack.removeFirst();
int from = range._from;
int to = range._to;
int pivot = to;
int left = from;
int right = to;
while (left < right) {
while (left < right && sortable.compare(left, pivot) < 0) {
left++;
}
while (left < right && sortable.compare(right, pivot) >= 0)
{
right--;
}
swap(sortable, left, right);
}
swap(sortable, to, right);
addRange(stack, from, right - 1);
addRange(stack, right + 1, to);
}
}
private static void addRange(LinkedList<Range> stack, int from, int to)
{
if (to - from < 1) {
return;
}
stack.addFirst(new Range(from, to));
}
private static void swap(QuickSortable sortable, int left, int right) {
if (left == right) {
return;
}
sortable.swap(left, right);
}
public static class QuickSortableIntArray implements QuickSortable {
private int[] ints;
public QuickSortableIntArray(int[] ints) {
this.ints = ints;
}
public int compare(int leftIndex, int rightIndex) {
return ints[leftIndex] - ints[rightIndex];
}
public int size() {
return ints.length;
}
public void swap(int leftIndex, int rightIndex) {
int temp = ints[leftIndex];
ints[leftIndex] = ints[rightIndex];
ints[rightIndex] = temp;
}
}
}
public interface QuickSortable {
public int size();
public int compare(int leftIndex, int rightIndex);
public void swap(int leftIndex, int rightIndex);
}
>
> |shell> javac GenericQuicksort.java
> |GenericQuicksort.java:36: incompatible types
> |found : java.lang.Object
> |required: GenericQuicksort.Range
> |Range range = stack.removeFirst();
> | ^
> |Note: GenericQuicksort.java uses unchecked or unsafe operations.
> |Note: Recompile with -Xlint:unchecked for details.
> |1 error
>
> P.S. I suspect this is a recompilation problem since Jitrino.JET
> generates very push-pop intensive code. Plz, check with -Xtrace:em (on
> debug build) that recomilation to Jitrino.OPT actually happened.
>
> >
> > >
> > > -Nathan
> > >
> > > On Dec 22, 2007 11:35 AM, Andrew Zhang <[EMAIL PROTECTED]>
> wrote:
> > > > Hi,
> > > >
> > > > I just found quick sort is very slow (4x) on Harmony compared with
> RI. I
> > > > didn't mean Arrays.sort method here, but a stack based
> implementation of
> > > > quick sort. The code has a lot of push/pop operation. Any idea?
> > > >
> > > > --
> > > > Best regards,
> > > > Andrew Zhang
> > > >
> > > > http://zhanghuangzhu.blogspot.com/
> > > >
> > >
> >
> >
> >
> > --
> > Best regards,
> > Andrew Zhang
> >
> > db4o - database for Android: www.db4o.com
> > http://zhanghuangzhu.blogspot.com/
>
> --
> Egor Pasko
>
>
--
Best regards,
Andrew Zhang
db4o - database for Android: www.db4o.com
http://zhanghuangzhu.blogspot.com/
