test/extra166y/LongCombineDemo.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

import jsr166y.*;
import extra166y.*;
import java.util.*;

class LongCombineDemo {

    static final Random rng = new Random();
    static final long NPS = (1000L * 1000 * 1000);
    static ForkJoinPool fjpool = new ForkJoinPool();
    static int reps = 16;
    static final long maxValue = 1 << 12;

    public static void main(String[] args) throws Exception {
        int n = 1 << 20;
        long[] a = new long[n];
        ParallelLongArray pa = ParallelLongArray.createUsingHandoff(a, fjpool);
        long[] b = new long[n];
        ParallelLongArray pb = ParallelLongArray.createUsingHandoff(b, fjpool);
        System.out.printf("Using %d Longs, %d replications\n", n, reps);
        seqSelectTest(pa);
        selectTest(pa);
        seqRemoveTest(pa);
        removeTest(pa);
        seqUniqTest(pa);
        parUniqTest(pa);
        sortUniqTest(pa);
        seqFindTest(pa);
        parFindTest(pa);
        fjpool.shutdown();
    }

    static int nresets = 0;
    static void reset(ParallelLongArray pa) {
        pa.replaceWithGeneratedValue(CommonOps.longRandom(maxValue));
        if (nresets++ == 0) System.out.println(pa.summary());
    }

    static void resetToEvens(ParallelLongArray pa) {
        pa.replaceWithMappedIndex(evens);
    }

    static class Evens implements Ops.IntToLong {
        public long op(int i) {
            return ((long)(i << 1));
        }
    }

    static class Less implements Ops.BinaryLongPredicate {
        public boolean op(long a, long b) { return a < b; }
    }

    static class IsOdd implements Ops.LongPredicate {
        public boolean op(long x) {
            return (x & 1) != 0;
        }
    }

    static class IsEven implements Ops.LongPredicate {
        public boolean op(long x) {
            return (x & 1) == 0;
        }
    }


    static final Less less = new Less();
    static final IsOdd isOdd = new IsOdd();
    static final IsEven isEven = new IsEven();
    static final Evens evens = new Evens();

    static void parUniqTest(ParallelLongArray pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            last = System.nanoTime();
            ParallelLongArray u = pa.allUniqueElements();
            elapsed += System.nanoTime() - last;
            u.sort();
            checkSorted(u);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Uniq time             %7.3f\n", de);
    }

    static void seqUniqTest(ParallelLongArray pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            last = System.nanoTime();
            long[] u = seqUnique(pa.getArray());
            elapsed += System.nanoTime() - last;
            ParallelLongArray pu = ParallelLongArray.createUsingHandoff(u, fjpool);
            pu.sort();
            checkSorted(pu);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq Uniq time:        %7.3f\n", de);
    }

    static void sortUniqTest(ParallelLongArray pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            last = System.nanoTime();
            ParallelLongArray u = pa.all();
            u.sort();
            u.removeConsecutiveDuplicates();
            elapsed += System.nanoTime() - last;
            checkSorted(u);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Par Uniq Sort time :  %7.3f\n", de);
    }

    static void removeTest(ParallelLongArray pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            int psize = pa.size();
            int oddSize = pa.withFilter(isOdd).size();
            int evenSize = psize - oddSize;
            ParallelLongArray u = pa.all();
            last = System.nanoTime();
            u.removeAll(isOdd);
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != evenSize)
                throw new Error(usize + " should be " + evenSize);
            int ai = u.withFilter(isOdd).anyIndex();
            if (ai >= 0)
                throw new Error("found " + ai);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("RemoveAll time :      %7.3f\n", de);
    }

    static void seqRemoveTest(ParallelLongArray pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            int psize = pa.size();
            int oddSize = pa.withFilter(isOdd).size();
            int evenSize = psize - oddSize;
            ParallelLongArray u = pa.all();
            last = System.nanoTime();
            seqRemoveAll(u, isOdd);
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != evenSize)
                throw new Error(usize + " should be " + evenSize);
            int ai = u.withFilter(isOdd).anyIndex();
            if (ai >= 0)
                throw new Error("found " + ai);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq RemoveAll time :  %7.3f\n", de);
    }

    static void selectTest(ParallelLongArray pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            int psize = pa.size();
            int oddSize = pa.withFilter(isOdd).size();
            int evenSize = psize - oddSize;
            last = System.nanoTime();
            ParallelLongArray u = pa.withFilter(isOdd).all();
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != oddSize)
                throw new Error(usize + " should be " + evenSize);
            int ai = u.withFilter(isEven).anyIndex();
            if (ai >= 0)
                throw new Error("found " + ai);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("SelectAll time :      %7.3f\n", de);
    }

    static void seqSelectTest(ParallelLongArray pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            int psize = pa.size();
            int oddSize = pa.withFilter(isOdd).size();
            int evenSize = psize - oddSize;
            last = System.nanoTime();
            ArrayList<Long> u = seqSelectAll(pa, isOdd);
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != oddSize)
                throw new Error(usize + " should be " + evenSize);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq SelectAll time :  %7.3f\n", de);
    }


    static void parFindTest(ParallelLongArray pa) {
        Random rng = new Random();
        int n = pa.size();
        long last;
        long elapsed = 0;
        resetToEvens(pa);
        last = System.nanoTime();
        for (int i = 0; i < reps * 16; ++i) {
            int rnd = rng.nextInt(n * 2);
            boolean expect = (rnd & 1) == 0;
            long t = (long)(rnd);
            boolean contains = pa.indexOf(t) >= 0;
            if (expect != contains)
                throw new Error();
        }
        elapsed += System.nanoTime() - last;
        double de = (double)(elapsed) / NPS;
        System.out.printf("Par index time :      %7.3f\n", de);
    }

    static void seqFindTest(ParallelLongArray pa) {
        List<Long> pal = pa.asList();
        Random rng = new Random();
        int n = pa.size();
        long last;
        long elapsed = 0;
        resetToEvens(pa);
        last = System.nanoTime();
        for (int i = 0; i < reps * 16; ++i) {
            int rnd = rng.nextInt(n * 2);
            boolean expect = (rnd & 1) == 0;
            long t = (long)(rnd);
            boolean contains = pal.indexOf(t) >= 0;
            if (expect != contains)
                throw new Error();
        }
        elapsed += System.nanoTime() - last;
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq index time :      %7.3f\n", de);
    }

    static void seqRemoveAll(ParallelLongArray pa,
                             Ops.LongPredicate selector) {
        long[] a = pa.getArray();
        int n = pa.size();
        int k = 0;
        for (int i = 0; i < n; ++i) {
            long x = a[i];
            if (!selector.op(x))
                a[k++] = x;
        }
        pa.setLimit(k);
    }

    static ArrayList<Long> seqSelectAll(ParallelLongArray pa,
                                        Ops.LongPredicate selector) {
        ArrayList<Long> al = new ArrayList<Long>();
        long[] a = pa.getArray();
        int n = pa.size();
        for (int i = 0; i < n; ++i) {
            long x = a[i];
            if (selector.op(x))
                al.add(Long.valueOf(x));
        }
        return al;
    }

    static long[] seqUnique(long[] a) {
        int n = a.length;
        HashSet<Long> m = new HashSet<Long>(n);
        for (int i = 0; i < n; ++i)
            m.add(Long.valueOf(a[i]));
        int ul = m.size();
        long[] u = new long[ul];
        int k = 0;
        for (Long e : m)
            u[k++] = e;
        return u;
    }

    static void checkSorted(ParallelLongArray pa) {
        int n = pa.size();
        for (int i = 0; i < n - 1; i++) {
            if (pa.get(i) >= pa.get(i+1)) {
                throw new Error("Unsorted at " + i + ": " + pa.get(i) + " / " + pa.get(i+1));
            }
        }
    }


}
Revision:	1.4
Committed:	Sat Oct 16 16:38:37 2010 UTC (13 years, 7 months ago) by jsr166
Branch:	MAIN
Changes since 1.3:	+1 -1 lines
Log Message:	whitespace
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/licenses/publicdomain
5			*/
6
7			import jsr166y.*;
8			import extra166y.*;
9			import java.util.*;
10
11			class LongCombineDemo {
12
13			static final Random rng = new Random();
14			static final long NPS = (1000L * 1000 * 1000);
15			static ForkJoinPool fjpool = new ForkJoinPool();
16			static int reps = 16;
17			static final long maxValue = 1 << 12;
18
19	jsr166	1.3	public static void main(String[] args) throws Exception {
20	dl	1.1	int n = 1 << 20;
21			long[] a = new long[n];
22			ParallelLongArray pa = ParallelLongArray.createUsingHandoff(a, fjpool);
23			long[] b = new long[n];
24			ParallelLongArray pb = ParallelLongArray.createUsingHandoff(b, fjpool);
25			System.out.printf("Using %d Longs, %d replications\n", n, reps);
26			seqSelectTest(pa);
27			selectTest(pa);
28			seqRemoveTest(pa);
29			removeTest(pa);
30			seqUniqTest(pa);
31			parUniqTest(pa);
32			sortUniqTest(pa);
33			seqFindTest(pa);
34			parFindTest(pa);
35			fjpool.shutdown();
36			}
37
38			static int nresets = 0;
39			static void reset(ParallelLongArray pa) {
40			pa.replaceWithGeneratedValue(CommonOps.longRandom(maxValue));
41			if (nresets++ == 0) System.out.println(pa.summary());
42			}
43
44			static void resetToEvens(ParallelLongArray pa) {
45			pa.replaceWithMappedIndex(evens);
46			}
47
48			static class Evens implements Ops.IntToLong {
49	jsr166	1.2	public long op(int i) {
50	dl	1.1	return ((long)(i << 1));
51			}
52			}
53
54			static class Less implements Ops.BinaryLongPredicate {
55			public boolean op(long a, long b) { return a < b; }
56			}
57
58			static class IsOdd implements Ops.LongPredicate {
59			public boolean op(long x) {
60			return (x & 1) != 0;
61			}
62			}
63
64			static class IsEven implements Ops.LongPredicate {
65			public boolean op(long x) {
66			return (x & 1) == 0;
67			}
68			}
69
70
71			static final Less less = new Less();
72			static final IsOdd isOdd = new IsOdd();
73			static final IsEven isEven = new IsEven();
74			static final Evens evens = new Evens();
75
76			static void parUniqTest(ParallelLongArray pa) {
77			int n = pa.size();
78			long last;
79			long elapsed = 0;
80			for (int i = 0; i < reps; ++i) {
81			reset(pa);
82			last = System.nanoTime();
83			ParallelLongArray u = pa.allUniqueElements();
84			elapsed += System.nanoTime() - last;
85			u.sort();
86			checkSorted(u);
87			}
88			double de = (double)(elapsed) / NPS;
89			System.out.printf("Uniq time %7.3f\n", de);
90			}
91
92			static void seqUniqTest(ParallelLongArray pa) {
93			int n = pa.size();
94			long last;
95			long elapsed = 0;
96			for (int i = 0; i < reps; ++i) {
97			reset(pa);
98			last = System.nanoTime();
99			long[] u = seqUnique(pa.getArray());
100			elapsed += System.nanoTime() - last;
101			ParallelLongArray pu = ParallelLongArray.createUsingHandoff(u, fjpool);
102			pu.sort();
103			checkSorted(pu);
104			}
105			double de = (double)(elapsed) / NPS;
106			System.out.printf("Seq Uniq time: %7.3f\n", de);
107			}
108
109			static void sortUniqTest(ParallelLongArray pa) {
110			int n = pa.size();
111			long last;
112			long elapsed = 0;
113			for (int i = 0; i < reps; ++i) {
114			reset(pa);
115			last = System.nanoTime();
116			ParallelLongArray u = pa.all();
117			u.sort();
118			u.removeConsecutiveDuplicates();
119			elapsed += System.nanoTime() - last;
120			checkSorted(u);
121			}
122			double de = (double)(elapsed) / NPS;
123			System.out.printf("Par Uniq Sort time : %7.3f\n", de);
124			}
125
126			static void removeTest(ParallelLongArray pa) {
127			int n = pa.size();
128			long last;
129			long elapsed = 0;
130			for (int i = 0; i < reps; ++i) {
131			reset(pa);
132			int psize = pa.size();
133			int oddSize = pa.withFilter(isOdd).size();
134			int evenSize = psize - oddSize;
135			ParallelLongArray u = pa.all();
136			last = System.nanoTime();
137			u.removeAll(isOdd);
138			elapsed += System.nanoTime() - last;
139			int usize = u.size();
140			if (usize != evenSize)
141			throw new Error(usize + " should be " + evenSize);
142			int ai = u.withFilter(isOdd).anyIndex();
143			if (ai >= 0)
144			throw new Error("found " + ai);
145			}
146			double de = (double)(elapsed) / NPS;
147			System.out.printf("RemoveAll time : %7.3f\n", de);
148			}
149
150			static void seqRemoveTest(ParallelLongArray pa) {
151			int n = pa.size();
152			long last;
153			long elapsed = 0;
154			for (int i = 0; i < reps; ++i) {
155			reset(pa);
156			int psize = pa.size();
157			int oddSize = pa.withFilter(isOdd).size();
158			int evenSize = psize - oddSize;
159			ParallelLongArray u = pa.all();
160			last = System.nanoTime();
161			seqRemoveAll(u, isOdd);
162			elapsed += System.nanoTime() - last;
163			int usize = u.size();
164			if (usize != evenSize)
165			throw new Error(usize + " should be " + evenSize);
166			int ai = u.withFilter(isOdd).anyIndex();
167			if (ai >= 0)
168			throw new Error("found " + ai);
169			}
170			double de = (double)(elapsed) / NPS;
171			System.out.printf("Seq RemoveAll time : %7.3f\n", de);
172			}
173
174			static void selectTest(ParallelLongArray pa) {
175			int n = pa.size();
176			long last;
177			long elapsed = 0;
178			for (int i = 0; i < reps; ++i) {
179			reset(pa);
180			int psize = pa.size();
181			int oddSize = pa.withFilter(isOdd).size();
182			int evenSize = psize - oddSize;
183			last = System.nanoTime();
184			ParallelLongArray u = pa.withFilter(isOdd).all();
185			elapsed += System.nanoTime() - last;
186			int usize = u.size();
187			if (usize != oddSize)
188			throw new Error(usize + " should be " + evenSize);
189			int ai = u.withFilter(isEven).anyIndex();
190			if (ai >= 0)
191			throw new Error("found " + ai);
192			}
193			double de = (double)(elapsed) / NPS;
194			System.out.printf("SelectAll time : %7.3f\n", de);
195			}
196
197			static void seqSelectTest(ParallelLongArray pa) {
198			int n = pa.size();
199			long last;
200			long elapsed = 0;
201			for (int i = 0; i < reps; ++i) {
202			reset(pa);
203			int psize = pa.size();
204			int oddSize = pa.withFilter(isOdd).size();
205			int evenSize = psize - oddSize;
206			last = System.nanoTime();
207			ArrayList<Long> u = seqSelectAll(pa, isOdd);
208			elapsed += System.nanoTime() - last;
209			int usize = u.size();
210			if (usize != oddSize)
211			throw new Error(usize + " should be " + evenSize);
212			}
213			double de = (double)(elapsed) / NPS;
214			System.out.printf("Seq SelectAll time : %7.3f\n", de);
215			}
216
217
218			static void parFindTest(ParallelLongArray pa) {
219			Random rng = new Random();
220			int n = pa.size();
221			long last;
222			long elapsed = 0;
223			resetToEvens(pa);
224			last = System.nanoTime();
225			for (int i = 0; i < reps * 16; ++i) {
226			int rnd = rng.nextInt(n * 2);
227			boolean expect = (rnd & 1) == 0;
228			long t = (long)(rnd);
229			boolean contains = pa.indexOf(t) >= 0;
230			if (expect != contains)
231			throw new Error();
232			}
233			elapsed += System.nanoTime() - last;
234			double de = (double)(elapsed) / NPS;
235			System.out.printf("Par index time : %7.3f\n", de);
236			}
237
238			static void seqFindTest(ParallelLongArray pa) {
239			List<Long> pal = pa.asList();
240			Random rng = new Random();
241			int n = pa.size();
242			long last;
243			long elapsed = 0;
244			resetToEvens(pa);
245			last = System.nanoTime();
246			for (int i = 0; i < reps * 16; ++i) {
247			int rnd = rng.nextInt(n * 2);
248			boolean expect = (rnd & 1) == 0;
249			long t = (long)(rnd);
250			boolean contains = pal.indexOf(t) >= 0;
251			if (expect != contains)
252			throw new Error();
253			}
254			elapsed += System.nanoTime() - last;
255			double de = (double)(elapsed) / NPS;
256			System.out.printf("Seq index time : %7.3f\n", de);
257			}
258
259	jsr166	1.2	static void seqRemoveAll(ParallelLongArray pa,
260	dl	1.1	Ops.LongPredicate selector) {
261			long[] a = pa.getArray();
262			int n = pa.size();
263			int k = 0;
264			for (int i = 0; i < n; ++i) {
265			long x = a[i];
266			if (!selector.op(x))
267			a[k++] = x;
268			}
269			pa.setLimit(k);
270			}
271
272	jsr166	1.2	static ArrayList<Long> seqSelectAll(ParallelLongArray pa,
273	dl	1.1	Ops.LongPredicate selector) {
274			ArrayList<Long> al = new ArrayList<Long>();
275			long[] a = pa.getArray();
276			int n = pa.size();
277			for (int i = 0; i < n; ++i) {
278			long x = a[i];
279			if (selector.op(x))
280			al.add(Long.valueOf(x));
281			}
282			return al;
283			}
284
285			static long[] seqUnique(long[] a) {
286			int n = a.length;
287			HashSet<Long> m = new HashSet<Long>(n);
288	jsr166	1.2	for (int i = 0; i < n; ++i)
289	dl	1.1	m.add(Long.valueOf(a[i]));
290			int ul = m.size();
291			long[] u = new long[ul];
292			int k = 0;
293			for (Long e : m)
294			u[k++] = e;
295			return u;
296			}
297	jsr166	1.2
298	jsr166	1.4	static void checkSorted(ParallelLongArray pa) {
299	dl	1.1	int n = pa.size();
300			for (int i = 0; i < n - 1; i++) {
301			if (pa.get(i) >= pa.get(i+1)) {
302			throw new Error("Unsorted at " + i + ": " + pa.get(i) + " / " + pa.get(i+1));
303			}
304			}
305			}
306	jsr166	1.2
307	dl	1.1
308			}