test/extra166y/LongSetOpsDemo.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 LongSetOpsDemo {

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