Streams API의 초기 디자인에서 디자인의 이론적 근거를 밝힐 수있는 몇 가지 사항이 있습니다.

2012 년에 우리는 언어에 람다를 추가하고 병렬 처리를 용이하게하는 컬렉션 지향 또는 “대량 데이터”연산 세트를 원했습니다. 게으른 체인 작업의 아이디어는이 시점에서 잘 확립되었습니다. 또한 중간 작업에서 결과를 저장하고 싶지 않았습니다.

우리가 결정해야 할 주요 문제는 체인의 객체가 API에서 어떻게 보이는지와 데이터 소스에 어떻게 연결되어 있는지였습니다. 소스는 종종 수집 이었지만 파일이나 네트워크에서 오는 데이터 또는 난수 생성기 등의 데이터를 즉시 지원하기를 원했습니다.

기존 작업이 디자인에 많은 영향을 미쳤습니다. 더 영향력있는 것은 구글의 구아바 도서관과 스칼라 컬렉션 도서관이었습니다. (구아바의 영향에 대해 아무도 놀라지 않는다면 구아바의 수석 개발자 인 Kevin Bourrillion 은 JSR-335 Lambda 에 있다는 점에 유의하십시오. . 전문가 그룹) 스칼라 컬렉션에, 우리는 특히 관심을 마틴 오더 스키하여이 이야기를 발견 Future- 교정 스칼라 컬렉션 : Mutable에서 Persistent, Parallel까지 . (Stanford EE380, 2011 년 6 월 1 일)

당시 우리의 프로토 타입 디자인은 주위에 Iterable있었습니다. 친숙한 작업은 filter, map, 등의 확장자 (기본) 방법이었다 Iterable. 하나를 호출하면 체인에 작업을 추가하고 다른 것을 반환Iterable . 터미널 작업 은 체인을 소스로 count불러 iterator()오며 각 단계의 반복자 내에서 작업이 구현되었습니다.

이것들은 Iterables이므로 iterator() 메소드를 두 번 이상 . 그러면 어떻게됩니까?

소스가 컬렉션 인 경우 대부분 잘 작동합니다. 컬렉션은 반복 가능하며 각 호출은iterator() 은 다른 활성 인스턴스와 독립적 인 고유 한 Iterator 인스턴스 생성하고 각 컬렉션을 독립적으로 통과합니다. 큰.

이제 파일에서 라인을 읽는 것과 같이 소스가 원샷 인 경우 어떻게해야합니까? 첫 번째 Iterator는 모든 값을 가져야하지만 두 번째 이후의 값은 비어 있어야합니다. 반복자 사이에 값을 인터리브해야 할 수도 있습니다. 또는 각 반복자가 동일한 값을 가져와야 할 수도 있습니다. 그렇다면 두 개의 이터레이터가 있고 하나가 다른 반복자보다 앞당기면 어떨까요? 누군가 읽을 때까지 두 번째 Iterator의 값을 버퍼링해야합니다. 더 나쁜 것은, 하나의 Iterator를 얻고 모든 값을 읽은 다음 두 번째 Iterator 를 얻는 다면 어떨까요? 가치는 지금 어디에서 오는가? 누군가 두 번째 Iterator를 원할 경우를 대비 하여 모두 버퍼링해야 합니까?

분명히 원샷 소스에 여러 반복자를 허용하면 많은 질문이 제기됩니다. 우리는 그들에게 좋은 대답이 없었습니다. 우리는 당신이 전화하면 어떻게 될지 일관되고 예측 가능한 행동을 원했습니다.iterator() 두 번 했습니다. 이로 인해 여러 순회를 허용하지 않고 파이프 라인을 한 번에 만들 수있었습니다.

또한 다른 사람들이 이러한 문제에 부딪 치는 것을 관찰했습니다. JDK에서 대부분의 Iterable은 콜렉션 또는 콜렉션 유사 오브젝트이며 여러 순회를 허용합니다. 어디에도 지정되지 않았지만 Iterables가 다중 순회를 허용한다는 기록되지 않은 기대가있는 것 같습니다. 주목할만한 예외는 NIO DirectoryStream 인터페이스입니다. 사양에는 다음과 같은 흥미로운 경고가 포함됩니다.

DirectoryStream은 Iterable을 확장하지만 단일 Iterator 만 지원하므로 범용 Iterable이 아닙니다. 반복자 메소드를 호출하여 두 번째 또는 후속 반복자를 확보하면 IllegalStateException이 발생합니다.

[원본으로 굵게]

이것은 독특하고 불쾌한 것처럼 보였으며 한 번만 할 수있는 새로운 Iterable을 많이 만들고 싶지 않았습니다. 이로 인해 Iterable을 사용하지 못하게되었습니다.

이시기에 브루스 에켈 (Bruce Eckel) 의 기사가 스칼라와 관련된 문제를 묘사 한 것으로 나타났다. 그는이 코드를 작성했다 :

// Scala
val lines = fromString(data).getLines
val registrants = lines.map(Registrant)
registrants.foreach(println)
registrants.foreach(println)

꽤 간단합니다. 텍스트 줄을 Registrant개체 로 구문 분석 하고 두 번 인쇄합니다. 실제로는 한 번만 인쇄합니다. 그는 생각했다registrants 그것이 반복자 일 때 컬렉션 . 두 번째 호출은 foreach모든 값이 소진 된 빈 반복자 를 만나므로 아무것도 인쇄하지 않습니다.

이러한 경험은 여러 번의 순회를 시도 할 경우 명확하게 예측 가능한 결과를 얻는 것이 매우 중요하다는 것을 우리에게 확신 시켰습니다. 또한 데이터를 저장하는 실제 컬렉션과 게으른 파이프 라인 유사 구조를 구별하는 것이 중요하다는 점을 강조했습니다. 결과적으로 게으른 파이프 라인 작업을 새로운 Stream 인터페이스로 분리하고 컬렉션에서 직접 열성적인 변이 작업 만 유지했습니다. Brian Goetz는 이에 대한 이론적 근거를 설명 했습니다.

컬렉션 기반 파이프 라인에는 다중 순회를 허용하지만 컬렉션 기반이 아닌 파이프 라인에는 허용하지 않는 것은 어떻습니까? 일관성이 없지만 합리적입니다. 물론 네트워크에서 값을 읽는다면 당신은 다시 통과 할 수 없다. 여러 번 트래버스하려면 트래버스를 명시 적으로 가져와야합니다.

그러나 컬렉션 기반 파이프 라인에서 여러 순회를 허용하도록하겠습니다. 당신이 이것을했다고 가정 해 봅시다.

Iterable<?> it = source.filter(...).map(...).filter(...).map(...);
it.into(dest1);
it.into(dest2);

( into이제 철자가 철자가되었습니다 collect(toList()).)

소스가 콜렉션 인 경우 첫 번째 into()호출은 소스에 반복기 체인을 다시 작성하고 파이프 라인 조작을 실행 한 후 결과를 대상으로 보냅니다. 두 번째 호출 into()은 다른 반복자 체인을 작성하고 파이프 라인 조작을 다시 실행 합니다 . 이것은 분명히 잘못된 것은 아니지만 각 요소에 대해 모든 필터 및 맵 작업을 두 번 수행하는 효과가 있습니다. 많은 프로그래머들이이 행동에 놀랐을 것이라고 생각합니다.

위에서 언급했듯이 우리는 구아바 개발자들과 대화하고있었습니다. 그들이 가지고있는 멋진 것 중 하나는 Idea Graveyard입니다. 여기 에는 이유와 함께 구현 하지 않기로 결정한 기능이 설명되어 있습니다 . 게으른 컬렉션에 대한 아이디어는 꽤 멋지게 들리지만 여기에 그들이 말해야 할 것이 있습니다. 다음 List.filter()을 반환 하는 작업을 고려하십시오 List.

여기서 가장 큰 관심사는 너무 많은 작업이 비싸고 선형적인 시간 제안이된다는 것입니다. 컬렉션이나 Iterable뿐만 아니라 목록을 필터링하고 목록을 다시 가져 오려면을 사용할 수 있습니다 ImmutableList.copyOf(Iterables.filter(list, predicate)).

구체적인 예를 촬영하려면 비용 무엇 get(0)이나 size()목록에이? 와 같이 일반적으로 사용되는 클래스 ArrayList는 O (1)입니다. 그러나 지연 필터링 된 목록에서이 중 하나를 호출하면 백업 목록에서 필터를 실행해야하며 갑자기 이러한 작업은 모두 O (n)입니다. 더 나쁜 것은 모든 작업 에서 지원 목록을 탐색해야한다는 것 입니다.

이것은 우리에게 게으름을 너무 많이 보였다 . 일부 작업을 설정하고 “이동”할 때까지 실제 실행을 연기하는 것이 한 가지입니다. 잠재적으로 많은 양의 재 계산을 숨기는 방식으로 설정하는 것이 또 다른 방법입니다.

비선형 또는 “재사용 불가능”스트림을 허용하지 않기 위해 Paul Sandoz 는 “예기치 않거나 혼란스러운 결과”를 발생 시키는 잠재적 결과 를 설명했습니다 . 또한 병렬 실행으로 인해 작업이 더욱 까다로워 질 것이라고 언급했습니다. 마지막으로, 부작용이 발생한 파이프 라인 작업은 작업이 예기치 않게 여러 번 실행되거나 프로그래머가 예상 한 것과 다른 횟수로 실행되는 경우 어렵고 모호한 버그로 이어질 수 있다고 덧붙였습니다. (그러나 Java 프로그래머는 부작용이있는 람다 식을 쓰지 않습니까? 그렇습니까?)

따라서 Java 8 Streams API 디자인의 기본 이론은 원샷 통과를 허용하고 엄격하게 선형 (분기 없음) 파이프 라인이 필요합니다. 여러 다른 스트림 소스에서 일관된 동작을 제공하고 지연 작업과 지연 동작을 명확하게 분리하며 간단한 실행 모델을 제공합니다.

와 관련하여 IEnumerableC # 및 .NET의 전문가와는 거리가 멀기 때문에 잘못된 결론을 도출하면 (신중하게) 수정되는 것에 감사드립니다. 그러나 IEnumerable여러 순회가 다른 소스와 다르게 동작 할 수있는 것으로 보입니다 . 그리고 중첩 IEnumerable연산 의 분기 구조를 허용하므로 상당한 재 계산이 발생할 수 있습니다. 시스템마다 다른 장단점이 있지만 Java 8 Streams API 디자인에서 피해야 할 두 가지 특성이 있습니다.

OP가 제시 한 퀵 정렬 예제는 흥미롭고 수수께끼이며 다소 무섭습니다. 호출은를 QuickSort가져 와서 IEnumerable를 반환 IEnumerable하므로 최종 IEnumerable이 통과 될 때까지 실제로 정렬이 수행되지 않습니다 . 그러나 호출이하는 것처럼 보이는 IEnumerables것은 퀵 정렬이 실제로 수행하지 않고 분할을 반영 하는 트리 구조를 구축 하는 것입니다. (이것은 결국 게으른 계산입니다.) 소스에 N 개의 요소가 있으면 트리는 가장 넓은 N 개의 요소가되고 lg (N) 레벨의 깊이가됩니다.

다시 한 번 C # 또는 .NET 전문가가 아니므로을 통해 피벗 선택과 같은 무해한 통화가 ints.First()외형보다 비싸 질 것 같습니다. 물론 첫 번째 수준은 O (1)입니다. 그러나 오른쪽 가장자리의 나무 깊이에있는 파티션을 고려하십시오. 이 파티션의 첫 번째 요소를 계산하려면 전체 소스를 순회해야합니다 (O (N) 작업). 그러나 위의 파티션은 게 으르므로 O (lg N) 비교를 요구하여 다시 계산해야합니다. 따라서 피벗을 선택하는 것은 O (N lg N) 작업이 될 것이며 이는 전체 종류만큼 비쌉니다.

그러나 우리는 반환 된을 횡단 할 때까지 실제로 정렬하지 않습니다 IEnumerable. 표준 퀵 정렬 알고리즘에서 각 분할 수준은 분할 수를 두 배로 늘립니다. 각 파티션의 크기는 절반에 불과하므로 각 수준은 O (N) 복잡성으로 유지됩니다. 파티션 트리는 O (lg N) 높이이므로 총 작업량은 O (N lg N)입니다.

게으른 IEnumerables 트리를 사용하면 트리 아래쪽에 N 개의 파티션이 있습니다. 각 파티션을 계산하려면 N 요소의 순회가 필요하며 각 요소는 트리에서 lg (N) 비교가 필요합니다. 트리의 맨 아래에있는 모든 파티션을 계산하려면 O (N ^ 2 lg N) 비교가 필요합니다.

(이것이 맞나요? 나는 이것을 믿을 수 없습니다. 누군가 나를 위해 이것을 확인하십시오.)

어쨌든 IEnumerable복잡한 계산 구조를 구축하기 위해 이런 식으로 사용될 수있는 것은 참으로 시원합니다 . 그러나 내가 생각하는 것만 큼 계산 복잡성을 증가시키는 경우이 방법을 프로그래밍하면 매우 신중하지 않으면 피해야 할 것 같습니다.

답변

IEnumerable<int> QuickSort(IEnumerable<int> ints)

IEnumerable<int> lt = ints.Where(i => i < pivot);

Stream<Integer> quickSort(List<Integer> ints) {
    // Using a stream to access the data, instead of the simpler ints.isEmpty()
    if (!ints.stream().findAny().isPresent()) {
        return Stream.of();
    }

    // treating the ints as a data collection, just like the C#
    final Integer pivot = ints.get(0);

    // Using streams to get the two partitions
    List<Integer> lt = ints.stream().filter(i -> i < pivot).collect(Collectors.toList());
    List<Integer> gt = ints.stream().filter(i -> i > pivot).collect(Collectors.toList());

    return Stream.concat(Stream.concat(quickSort(lt), Stream.of(pivot)),quickSort(gt));
}    

static Stream<Integer> quickSort(Supplier<Stream<Integer>> ints) {

  final Optional<Integer> optPivot = ints.get().findAny();
  if(!optPivot.isPresent()) return Stream.empty();

  final int pivot = optPivot.get();

  Supplier<Stream<Integer>> lt = ()->ints.get().filter(i -> i < pivot);
  Supplier<Stream<Integer>> gt = ()->ints.get().filter(i -> i > pivot);

  return Stream.of(quickSort(lt), Stream.of(pivot), quickSort(gt)).flatMap(s->s);
}

List<Integer> l=new Random().ints(100, 0, 1000).boxed().collect(Collectors.toList());
System.out.println(l);
System.out.println(quickSort(l::stream)
    .map(Object::toString).collect(Collectors.joining(", ")));

static Stream<Integer> quickSort(Supplier<Stream<Integer>> ints) {
    return ints.get().findAny().map(pivot ->
         Stream.of(
                   quickSort(()->ints.get().filter(i -> i < pivot)),
                   Stream.of(pivot),
                   quickSort(()->ints.get().filter(i -> i > pivot)))
        .flatMap(s->s)).orElse(Stream.empty());
}

IEnumerable<int> numbers = new int[] { 1, 2, 3, 4, 5 };

foreach (var n in numbers) {
    Console.WriteLine(n);
}

IEnumerable<int> numbers = new int[] { 1, 2, 3, 4, 5 };

IEnumerator<int> enumerator = numbers.GetEnumerator();
while (enumerator.MoveNext()) {
    Console.WriteLine(enumerator.Current);
}

class Generator : IEnumerator<int> {
    Random _r;
    int _current;
    int _count = 0;

    public Generator(Random r) {
        _r = r;
    }

    public bool MoveNext() {
        _current= _r.Next();
        _count++;
        return _count <= 5;
    }

    public int Current {
        get { return _current; }
    }
 }

class RandomNumberStream : IEnumerable<int> {
    Random _r = new Random();
    public IEnumerator<int> GetEnumerator() {
        return new Generator(_r);
    }
    public IEnumerator IEnumerable.GetEnumerator() {
        return this.GetEnumerator();
    }
}

IEnumerable<int> numbers = new RandomNumberStream();

foreach (var n in numbers) {
    Console.WriteLine(n);
}
foreach (var n in numbers) {
    Console.WriteLine(n);
}

    Spliterator<String> split = Stream.of("hello","world")
                                      .map(s->"prefix-"+s)
                                      .spliterator();

    Stream<String> replayable1 = StreamSupport.stream(split,false);
    Stream<String> replayable2 = StreamSupport.stream(split,false);


    replayable1.forEach(System.out::println);
    replayable2.forEach(System.out::println);

prefix-hello
prefix-world

prefix-hello
prefix-world
prefix-hello
prefix-world