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/publicdomain/zero/1.0/
 */

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.5
Committed:	Tue Mar 15 19:47:04 2011 UTC (13 years, 1 month ago) by jsr166
Branch:	MAIN
CVS Tags:	release-1_7_0, HEAD
Changes since 1.4:	+1 -1 lines
Log Message:	Update Creative Commons license URL in legal notices
#	Content
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/publicdomain/zero/1.0/
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	public static void main(String[] args) throws Exception {
20	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	public long op(int i) {
50	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	static void seqRemoveAll(ParallelLongArray pa,
260	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	static ArrayList<Long> seqSelectAll(ParallelLongArray pa,
273	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	for (int i = 0; i < n; ++i)
289	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
298	static void checkSorted(ParallelLongArray pa) {
299	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
307
308	}