089
089
16天前 · 2 人阅读

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() {
		
		@Overridepublicvoidaccept(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() {
		
		@Overridepublicvoidaccept(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() {
		
		@Overridepublicvoidaccept(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在迭代时,第二个参数指向数组的起始下标(包括),第三个参数指向原数组的结束下标(不包括)。还是进入代码好好研究一下。

具体实现

以下是Arraysspliterator函数:

publicstatic Spliterator.OfInt spliterator(int[] array, int startInclusive, int endExclusive){
        return Spliterators.spliterator(array, startInclusive, endExclusive,
                                        Spliterator.ORDERED | Spliterator.IMMUTABLE);
    }
复制代码

继续跟踪下Spliterators.spliterator

publicstatic Spliterator.OfInt spliterator(int[] array, int fromIndex, int toIndex,
                                                int additionalCharacteristics){
        checkFromToBounds(Objects.requireNonNull(array).length, fromIndex, toIndex);
        returnnew IntArraySpliterator(array, fromIndex, toIndex, additionalCharacteristics);
    }
复制代码

已经到底层实现了,由于具体实现时代码量并不大,故可以直接看下IntArraySpliterator类的源码了

staticfinalclassIntArraySpliteratorimplementsSpliterator.OfInt{
        // 指向原数组的arrayprivatefinalint[] array;
        // 分组迭代的起始下标(包括)privateint index;        
        // 分组迭代的结束下标(不包括)privatefinalint fence;  // one past last index// 分组迭代的特征privatefinalint characteristics;

        
        publicIntArraySpliterator(int[] array, int additionalCharacteristics){
            this(array, 0, array.length, additionalCharacteristics);
        }

        
        publicIntArraySpliterator(int[] array, int origin, int fence, int additionalCharacteristics){
            this.array = array;
            this.index = origin;
            this.fence = fence;
            this.characteristics = additionalCharacteristics | Spliterator.SIZED | Spliterator.SUBSIZED;
        }

        @Overridepublic OfInt trySplit(){
            int lo = index, mid = (lo + fence) >>> 1;
            return (lo >= mid)
                   ? null
                   : new IntArraySpliterator(array, lo, index = mid, characteristics);
        }

        @OverridepublicvoidforEachRemaining(IntConsumer action){
            int[] a; int i, hi; // hoist accesses and checks from loopif (action == null)
                thrownew NullPointerException();
            if ((a = array).length >= (hi = fence) &&
                (i = index) >= 0 && i < (index = hi)) {
                do { action.accept(a[i]); } while (++i < hi);
            }
        }

        @OverridepublicbooleantryAdvance(IntConsumer action){
            if (action == null)
                thrownew NullPointerException();
            if (index >= 0 && index < fence) {
                action.accept(array[index++]);
                returntrue;
            }
            returnfalse;
        }

        @OverridepubliclongestimateSize(){ return (long)(fence - index); }

        @Overridepublicintcharacteristics(){
            return characteristics;
        }

        @Overridepublic Comparator<? super Integer> getComparator() {
            if (hasCharacteristics(Spliterator.SORTED))
                returnnull;
            thrownew 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

publicinterfaceIntConsumer{
       
        voidaccept(int value);
       
        default IntConsumer andThen(IntConsumer after){
            Objects.requireNonNull(after);
            return (int t) -> { accept(t); after.accept(t); };
        }
    }
复制代码

在前面介绍分割迭代时已经讲到accept操作,这个操作是IntConsumer接口定义的函数。IntConsumer定义两个函数,acceptandThenaccept函数接收数组的元素,并对元素进行操作,但是操作本身不改变原数组元素的值;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() {
		
		@Overridepublicvoidaccept(int value){
			// TODO Auto-generated method stub
			System.out.println(value);
		}
	};
	sInt.tryAdvance(consumer.andThen(new IntConsumer() {
		
		@Overridepublicvoidaccept(int value){
			// TODO Auto-generated method stub
			System.out.println("i am after");
		}
	}));
复制代码

程序输出:3 i am after

使用场景

既然说spliterator是并行遍历机制,接下来给一个并行遍历的demo,先定义一个SpliteratorThread:

publicclassSpliteratorThread<T> extendsThread{
	private Spliterator<T> mSpliterator;
	publicSpliteratorThread(Spliterator<T> spliterator){
		mSpliterator = spliterator;
	}
	
	@Overridepublicvoidrun(){
		// TODO Auto-generated method stubsuper.run();
		if (mSpliterator != null) {
			mSpliterator.forEachRemaining(new Consumer<T>() {

				@Overridepublicvoidaccept(T t){
					// TODO Auto-generated method stub
					System.out.println( Thread.currentThread().getName() + "-" + t + " ");
				}
			});
		}
	}
}
复制代码

然后是一个测试入口:

publicclassClient{
	publicstaticvoidmain(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之后待遍历的位置后移一位

关注微信公众号,最新技术干货实时推送

收藏 0
java
评论 ( 0 )