Java迭代器spliterator
tags : java-collections
spliterator
是java1.8引入的一种并行遍历的机制,Iterator
提供也提供了对集合数据进行遍历的能力,但一个是顺序遍历,一个是并行遍历。
如上图所示,Arrays
的分割迭代函数有2种形式,spliterator(xxx [])
, spliterator(xxx [] , int, int)
, 具体的xxx
包括int
, long
, double
, T
,下文就以int
类型作为demo进行分析。
举个栗子
Spliterator.OfInt sInt = Arrays.spliterator(arr);
IntConsumer consumer = new IntConsumer() {
@Override
public void accept(int value) {
// TODO Auto-generated method stub
System.out.println(value);
}
};
sInt.tryAdvance(consumer);
程序输出:1
将代码修改一下:
int [] arr = {1,2,3,4,5,6,7,8,9};
Spliterator.OfInt sInt = Arrays.spliterator(arr, 2, 5);
IntConsumer consumer = new IntConsumer() {
@Override
public void accept(int value) {
// TODO Auto-generated method stub
System.out.println(value);
}
};
sInt.tryAdvance(consumer);
程序输出:3
突然有点感觉,spliterator
的第二个和第三个参数可能是指原数组的起始和结束下标,再把代码修改一下:
int [] arr = {1,2,3,4,5,6,7,8,9};
Spliterator.OfInt sInt = Arrays.spliterator(arr, 2, 5);
IntConsumer consumer = new IntConsumer() {
@Override
public void accept(int value) {
// TODO Auto-generated method stub
System.out.println(value);
}
};
sInt.tryAdvance(consumer);
sInt.tryAdvance(consumer);
sInt.tryAdvance(consumer);
sInt.tryAdvance(consumer);
sInt.tryAdvance(consumer);
程序输出:3
4
5
可以确定,spliterator
在迭代时,第二个参数指向数组的起始下标(包括),第三个参数指向原数组的结束下标(不包括)。还是进入代码好好研究一下。
具体实现
以下是Arrays
的spliterator
函数:
public static Spliterator.OfInt spliterator(int[] array, int startInclusive, int endExclusive) {
return Spliterators.spliterator(array, startInclusive, endExclusive,
Spliterator.ORDERED | Spliterator.IMMUTABLE);
}
继续跟踪下Spliterators.spliterator
public static Spliterator.OfInt spliterator(int[] array, int fromIndex, int toIndex,
int additionalCharacteristics) {
checkFromToBounds(Objects.requireNonNull(array).length, fromIndex, toIndex);
return new IntArraySpliterator(array, fromIndex, toIndex, additionalCharacteristics);
}
已经到底层实现了,由于具体实现时代码量并不大,故可以直接看下IntArraySpliterator
类的源码了
static final class IntArraySpliterator implements Spliterator.OfInt {
// 指向原数组的array
private final int[] array;
// 分组迭代的起始下标(包括)
private int index;
// 分组迭代的结束下标(不包括)
private final int fence; // one past last index
// 分组迭代的特征
private final int characteristics;
public IntArraySpliterator(int[] array, int additionalCharacteristics) {
this(array, 0, array.length, additionalCharacteristics);
}
public IntArraySpliterator(int[] array, int origin, int fence, int additionalCharacteristics) {
this.array = array;
this.index = origin;
this.fence = fence;
this.characteristics = additionalCharacteristics | Spliterator.SIZED | Spliterator.SUBSIZED;
}
@Override
public OfInt trySplit() {
int lo = index, mid = (lo + fence) >>> 1;
return (lo >= mid)
? null
: new IntArraySpliterator(array, lo, index = mid, characteristics);
}
@Override
public void forEachRemaining(IntConsumer action) {
int[] a; int i, hi; // hoist accesses and checks from loop
if (action == null)
throw new NullPointerException();
if ((a = array).length >= (hi = fence) &&
(i = index) >= 0 && i < (index = hi)) {
do { action.accept(a[i]); } while (++i < hi);
}
}
@Override
public boolean tryAdvance(IntConsumer action) {
if (action == null)
throw new NullPointerException();
if (index >= 0 && index < fence) {
action.accept(array[index++]);
return true;
}
return false;
}
@Override
public long estimateSize() { return (long)(fence - index); }
@Override
public int characteristics() {
return characteristics;
}
@Override
public Comparator<? super Integer> getComparator() {
if (hasCharacteristics(Spliterator.SORTED))
return null;
throw new IllegalStateException();
}
}
trySplit
函数很好理解,将原始IntArraySpliterator
的起始下标index和结束下标fence的和的1/2作为新的分割迭代spliterator
的结束下标,构造新的分割迭代对象,原始对象的index也修改为起始下标index和结束下标fence的和的1/2。
tryAdvance
函数对index下标指向的元素执行accept
操作并且index自增1,这就可以解释上面例子的结果了。
forEachReaming
函数从index下标开始,对fence
之前的每一个元素执行accept
操作。
estimateSize
函数获取剩余还没有进行accept
操作的元素的数量。
IntConsumer
public interface IntConsumer {
void accept(int value);
default IntConsumer andThen(IntConsumer after) {
Objects.requireNonNull(after);
return (int t) -> { accept(t); after.accept(t); };
}
}
在前面介绍分割迭代时已经讲到accept
操作,这个操作是IntConsumer
接口定义的函数。IntConsumer
定义两个函数,accept
, andThen
。accept
函数接收数组的元素,并对元素进行操作,但是操作本身不改变原数组元素的值;andThen
接口允许提供一个新的IntConsumer
对象,原对象执行完accept
函数后会执行新的对象的accept
函数,看下demo
int [] arr = {1,2,3,4,5,6,7,8,9};
Spliterator.OfInt sInt = Arrays.spliterator(arr, 2, 5);
IntConsumer consumer = new IntConsumer() {
@Override
public void accept(int value) {
// TODO Auto-generated method stub
System.out.println(value);
}
};
sInt.tryAdvance(consumer.andThen(new IntConsumer() {
@Override
public void accept(int value) {
// TODO Auto-generated method stub
System.out.println("i am after");
}
}));
程序输出:3
i am after
使用场景
既然说spliterator
是并行遍历机制,接下来给一个并行遍历的demo,先定义一个SpliteratorThread
:
public class SpliteratorThread<T> extends Thread {
private Spliterator<T> mSpliterator;
public SpliteratorThread(Spliterator<T> spliterator) {
mSpliterator = spliterator;
}
@Override
public void run() {
// TODO Auto-generated method stub
super.run();
if (mSpliterator != null) {
mSpliterator.forEachRemaining(new Consumer<T>() {
@Override
public void accept(T t) {
// TODO Auto-generated method stub
System.out.println( Thread.currentThread().getName() + "-" + t + " ");
}
});
}
}
}
然后是一个测试入口:
public class Client {
public static void main(String [] args) {
int [] arr = {1,2,3,4,5,6,7,8,9,10};
Spliterator<Integer> spliterator0 = Arrays.spliterator(arr);
Spliterator<Integer> spliterator1 = spliterator0.trySplit();
Spliterator<Integer> spliterator2 = spliterator1.trySplit();
Thread t0 = new SpliteratorThread<>(spliterator0);
t0.setName("t0");
Thread t1 = new SpliteratorThread<>(spliterator1);
t1.setName("t1");
Thread t2 = new SpliteratorThread<>(spliterator2);
t2.setName("t2");
t0.start();
t1.start();
t2.start();
}
}
执行一下:
t1-3
t2-1
t0-6
t2-2
t1-4
t0-7
t1-5
t0-8
t0-9
t0-10
对结果进行梳理一下,线程t0遍历的元素:6,7,8,9,10;线程t1遍历的元素:3,4,5;线程t2遍历的元素:1,2。每个线程内部元素的遍历是有序的,但是线程的调度是无序的,以上结果显示了3个线程并行遍历的流程,这就是分割遍历最常用的场景。
总结
- 分割遍历的主要目的是为了实现并行遍历
- 分割遍历是在原数组的基础上进行遍历,遍历的过程中不会对原数组的元素进行修改
- 分割的规则是从待遍历的范围的中间位置进行分割
- 执行
tryAdvance
之后待遍历的位置后移一位