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

    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];
        ParallelArray<Long> pa = ParallelArray.createUsingHandoff(a, fjpool);
        System.out.printf("Using %d Longs, %d replications\n", n, reps);
        for (int iters = 0; iters < 3; ++iters) {
            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(ParallelArray<Long> pa) {
        pa.replaceWithGeneratedValue(rlg);
        if (nresets++ == 0) System.out.println(pa.summary());
    }

    static void resetToEvens(ParallelArray<Long> pa) {
        pa.replaceWithMappedIndex(evens);
    }

    static class Evens implements Ops.IntToObject<Long> {
        public Long op(int i) {
            return Long.valueOf((long)(i << 1));
        }
    }

    static class IsOdd implements Ops.Predicate<Long> {
        public boolean op(Long x) {
            return (x.longValue() & 1) != 0;
        }
    }

    static class IsEven implements Ops.Predicate<Long> {
        public boolean op(Long x) {
            return (x.longValue() & 1) == 0;
        }
    }

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

    static void parUniqTest(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            last = System.nanoTime();
            ParallelArray<Long> 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(ParallelArray<Long> 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;
            ParallelArray<Long> pu = ParallelArray.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(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            last = System.nanoTime();
            ParallelArray<Long> 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(ParallelArray<Long> 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;
            ParallelArray<Long> 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);
            Long a = u.withFilter(isOdd).any();
            if (a != null)
                throw new Error("found " + a);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("RemoveAll time :      %7.3f\n", de);
    }

    static void seqRemoveTest(ParallelArray<Long> 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;
            ParallelArray<Long> 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);
            Long a = u.withFilter(isOdd).any();
            if (a != null)
                throw new Error("found " + a);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq RemoveAll time :  %7.3f\n", de);
    }

    static void selectTest(ParallelArray<Long> 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();
            ParallelArray<Long> u = pa.withFilter(isOdd).all();
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != oddSize)
                throw new Error(usize + " should be " + evenSize);
            Long a = u.withFilter(isEven).any();
            if (a != null)
                throw new Error("found " + a);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("SelectAll time :      %7.3f\n", de);
    }

    static void seqSelectTest(ParallelArray<Long> 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(ParallelArray<Long> 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.valueOf(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(ParallelArray<Long> 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.valueOf(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(ParallelArray<Long> pa,
                             Ops.Predicate<Long> 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;
        }
        for (int j = k; j < n; ++j)
            a[j] = null;
        pa.setLimit(k);
    }

    static ArrayList<Long> seqSelectAll(ParallelArray<Long> pa,
                                        Ops.Predicate<Long> 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(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(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(ParallelArray<Long> pa) {
        int n = pa.size();
        for (int i = 0; i < n - 1; i++) {
            if (pa.get(i).compareTo(pa.get(i+1)) >= 0) {
                throw new Error("Unsorted at " + i + ": " + pa.get(i) + " / " + pa.get(i+1));
            }
        }
    }

    static final class RandomLongGenerator implements Ops.Generator<Long> {
        public Long op() {
            return new Long(ThreadLocalRandom.current().nextLong(maxValue));
        }
    }

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