Spliterator

Spliterator

• 분할할 수 있는 반복자
• splitable iterator

public interface Spliterator<T> {
    boolean tryAdvance(Consumer<? super T> action);
    Spliterator<T> trySplit();
    long estimateSize();
    int characteristics();
}

tryAdvance

• 현재 요소에 Consumer를 수행 후, 다음 요소가 있는지 리턴

trySplit

• 분할이 불가능한 경우, null 리턴
• 분할 가능한 경우, 분할시킨 새로 생성한 Spliterator 리턴
• 분할하고 나머지 부분 계속해서 trySplit 시도

estimateSize

• 탐색해야할 요소의 개수를 리턴

Characteristic

Characteristic	Description
ORDERED	리스트처럼 요소에 정해진 순서가 있으므로 Spliterator는 요소를 탐색하고 분할할 때 이 순서에 유의해야한다.
DISTINCT	x, y 두요소를 방문했을 때 x.equals(y)는 항상 false를 반환한다.
SORTED	탐색된 요소는 미리 정의된 정렬 순서를 따른다.
SIZED	크기가 알려진 소스로 Spliterator를 생성했으므로 estimatedSize()는 정확한 값을 반환한다.
NON-NULL	탐색하는 모든 요소는 null이 아니다
IMMUTABLE	모든 요소는 불변이다. 즉 요소를 탐색하는 동안 요소를 추가하거나, 삭제하거나, 수정할 수 없다.
CONCURRENT	동기화 없이 Spliterator의 소스를 여러 쓰레드에서 동시에 고칠 수 있따.
SUBSIZED	Spliterator 자신 그리고 분할되는 모든 Spliterator는 SIZED 특성을 가진다.

Example

• 문장에서 단어 갯수 구하기 (스페이스 문자 기준)
• 입력값

"Nel mezzo del cammin di nostra vita mi ritrovai in una selva oscura che la dritta via era smarrita "

•  
• 정답은 19

1. Procedural Programming

public static int countWordsIteratively(String s) {  
  int counter = 0;  
  boolean lastSpace = true;  
  for (char c : s.toCharArray()) {  
    if (Character.isWhitespace(c)) {  
      lastSpace = true;  
    }  
    else {  
      if (lastSpace) {  
        counter++;  
      }  
      lastSpace = Character.isWhitespace(c);  
    }  
  }  
  return counter;  
}

Input

SENTENCE = "Nel   mezzo del cammin  di nostra  vita mi  ritrovai in una  selva oscura che la  dritta via era   smarrita "

Execution

public static main(String[] args) {
    System.out.println("Found " + countWordsIteratively(SENTENCE) + " words");
}

Execution Result

Found 19 words  // OK

---

2. Custom Reducing with Stream

class WordCounter {  
  private final int counter;  
  private final boolean lastSpace;  

  public WordCounter() {  
    this(0, true);  
  }  

  public WordCounter(int counter, boolean lastSpace) {  
    this.counter = counter;  
    this.lastSpace = lastSpace;  
  }  

  public WordCounter accumulate(Character c) {  
    if (Character.isWhitespace(c)) {  
      return lastSpace ? this : new WordCounter(counter, true);  
    }  
    else {  
      return lastSpace ? new WordCounter(counter + 1, false) : this;  
    }  
  }  

  public WordCounter combine(WordCounter wordCounter) {  
    return new WordCounter(counter + wordCounter.counter, wordCounter.lastSpace);  
  }  

  public int getCounter() {  
    return counter;  
  }  
}

Execution

public static int countWordsWithCustomReducing(String s, boolean isParallel) {  
  Stream<Character> stream = IntStream.range(0, s.length()).mapToObj(s::charAt);  

  if (isParallel) {  
    stream = stream.parallel();  
  }  

  return countWordsWithCustomReducing(stream);  
}

public static main(String[] args) {
    System.out.println("Found " + countWordsWithCustomReducing(SENTENCE, false) + " words");
}

Execution Result

Found 19 words  // OK

Execution (With Parallel Stream)

public static main(String[] args) {
    System.out.println("Found " + countWordsWithCustomReducing(SENTENCE, false) + " words");
}

Execution Result (With Parallel Stream)

• Wrong Answer

Found 43 words  // Wrong

---

3. Custom Spliterator

private static class WordCounterSpliterator implements Spliterator<Character> {  
  private static final int SPLIT_BUCKET_SIZE = 10;  
  private final String string;  
  private int currentIndex = 0;  

  private WordCounterSpliterator(String string) {  
    this.string = string;  
  }  

  @Override  
  public boolean tryAdvance(Consumer<? super Character> action) {  
    action.accept(string.charAt(currentIndex++));  
    return currentIndex < string.length();  
  }  

  @Override  
  public Spliterator<Character> trySplit() {  
    int currentSize = string.length() - currentIndex;  
    if (currentSize < SPLIT_BUCKET_SIZE) {  
      return null;  
    }  
    for (int splitIndex = currentSize / 2 + currentIndex; splitIndex < string.length(); splitIndex++) {  
      if (Character.isWhitespace(string.charAt(splitIndex))) {  
        Spliterator<Character> spliterator =  
            new WordCounterSpliterator(string.substring(currentIndex, splitIndex));  
        currentIndex = splitIndex;  
        return spliterator;  
      }  
    }  
    return null;  
  }  

  @Override  
  public long estimateSize() {  
    return string.length() - currentIndex;  
  }  

  @Override  
  public int characteristics() {  
    return ORDERED + SIZED + SUBSIZED + NONNULL + IMMUTABLE;  
  }  
}

Execution

public static int countWordsWithSpliterator(String s) {  
  Spliterator<Character> spliterator = new WordCounterSpliterator(s);  
  Stream<Character> stream = StreamSupport.stream(spliterator, true);  
  return countWordsWithCustomReducing(stream);  
}

public static main(String[] args) {
    System.out.println("Found " + countWordsWithSpliterator(SENTENCE) + " words");
}

Execution Result

Found 19 words  // OK