为了账号安全,请及时绑定邮箱和手机立即绑定

为什么Java Streams一次性出现?

/ 猿问

为什么Java Streams一次性出现?

慕瓜9086354 2019-10-23 14:34:10

与C#不同IEnumerable,在C#中,执行管道可以执行任意多次,而在Java中,流只能“迭代”一次。


对终端操作的任何调用都会关闭流,使其无法使用。这种“功能”带走了很多力量。


我想这不是技术原因。这种奇怪的限制背后的设计考虑是什么?


编辑:为了演示我在说什么,请考虑以下C#中的Quick-Sort实现:


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

{

  if (!ints.Any()) {

    return Enumerable.Empty<int>();

  }


  int pivot = ints.First();


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

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


  return QuickSort(lt).Concat(new int[] { pivot }).Concat(QuickSort(gt));

}

现在确定,我不主张这是快速排序的良好实现!但是,这是将lambda表达与流操作相结合的表达能力的一个很好的例子。


而且它不能用Java完成!我什至不能问一个流是否为空而不使它无法使用。


查看完整描述

3 回答

?
忽然笑

我对Streams API的早期设计有一些回忆,这可能有助于我们了解设计原理。


早在2012年,我们就在语言中添加了lambda,并且我们希望使用lambda进行编程的面向集合或“大量数据”的操作集可以促进并行性。到此为止,已经很好地确立了将操作延迟链接在一起的想法。我们也不希望中间操作存储结果。


我们需要确定的主要问题是该链中的对象在API中的外观以及它们如何连接到数据源。来源通常是集合,但我们也希望支持来自文件或网络的数据,或动态生成的数据(例如,随机数生成器)。


现有工作对设计有很多影响。更具影响力的是Google的Guava库和Scala收藏库。(如果有人对Guava的影响感到惊讶,请注意,Guava的首席开发人员Kevin Bourrillion正在JSR-335 Lambda专家组中。)在Scala系列中,我们发现Martin Odersky的演讲特别有趣:Future-验证Scala集合:从可变到持久到并行。(斯坦福大学EE380,2011年6月1日。)


我们当时的原型设计基于Iterable。熟悉业务filter,map等了对扩展名(默认)方法Iterable。调用一个将操作添加到链中,并返回另一个Iterable。像count这样的终端操作会调用iterator()到源的链,并且这些操作是在每个阶段的Iterator中实现的。


由于这些是Iterable,因此可以iterator()多次调用该方法。那应该怎么办?


如果源是集合,则通常可以正常工作。集合是可iterator()迭代的,并且每次调用都会产生一个独立的Iterator实例,该实例独立于任何其他活动实例,并且每个实例都独立遍历该集合。大。


现在,如果源是一次性的,例如从文件中读取行,该怎么办?也许第一个Iterator应该获取所有值,但是第二个和后续的应该为空。也许值应该在迭代器之间交织。或者,也许每个Iterator都应该获得所有相同的值。然后,如果您有两个迭代器而一个迭代器比另一个迭代器更远呢?有人将不得不在第二个Iterator中缓冲这些值,直到它们被读取为止。更糟糕的是,如果您获得一个Iterator并读取所有值,然后又获得另一个Iterator 怎么办?这些价值从何而来?是否有必要将它们全部缓冲,以防万一有人想要第二个Iterator?


显然,在一个源上允许多个Iterators引发了很多问题。我们没有给他们好的答案。如果您拨打iterator()两次电话,我们希望获得一致的,可预测的行为。这迫使我们朝着不允许多次遍历的方向前进,使流水线变成了一次性。


我们还观察到其他人陷入了这些问题。在JDK中,大多数Iterables是集合或类似集合的对象,它们允许多次遍历。它没有在任何地方指定,但是似乎有一个不成文的期望,即Iterables允许多次遍历。NIO DirectoryStream接口是一个明显的例外。它的规范包括以下有趣的警告:


虽然DirectoryStream扩展了Iterable,但它不是通用的Iterable,因为它仅支持单个Iterator。调用迭代器方法以获得第二个或后续迭代器,则抛出IllegalStateException。


[粗体显示]


这似乎异常且令人不愉快,以至于我们不想创建一大堆可能只是一次的新Iterable。这使我们不再使用Iterable。


大约在这个时候,布鲁斯·埃克尔(Bruce Eckel)发表了一篇文章,描述了他在Scala遇到的麻烦。他写了这段代码:


// Scala

val lines = fromString(data).getLines

val registrants = lines.map(Registrant)

registrants.foreach(println)

registrants.foreach(println)

这很简单。它将文本行解析为Registrant对象并将其打印两次。除了它实际上只打印一次。事实证明,他认为这registrants是一个集合,而实际上它是一个迭代器。第二个调用foreach遇到一个空的迭代器,从该迭代器中耗尽所有值,因此不打印任何内容。


这种经历使我们相信,如果尝试多次遍历,获得清晰可预测的结果非常重要。它还强调了区分类似于流水线的惰性结构与存储数据的实际集合的重要性。反过来,这将惰性管道操作分离到新的Stream接口中,并且仅将急切的,可变的操作直接保留在Collection上。布莱恩·格茨(Brian Goetz)对此做了解释。


允许对基于集合的管道进行多次遍历,而对非基于集合的管道却不允许进行遍历怎么办?这是不一致的,但是很明智。如果您正在从网络中读取值,则当然无法再次遍历它们。如果要遍历它们多次,则必须将它们显式拉入集合中。


但是,让我们探索允许从基于集合的管道进行多次遍历。假设您这样做:


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

it.into(dest1);

it.into(dest2);

(该into操作现在是拼写的collect(toList())。)


如果source是一个集合,则第一个into()调用将创建一个Iterators链返回到Source,执行管道操作,并将结果发送到目标。第二次调用into()将创建另一个Iterators链,并再次执行管道操作。这显然没有错,但是确实可以对每个元素第二次执行所有过滤和映射操作。我认为许多程序员会对这种行为感到惊讶。


如上所述,我们一直在与Guava开发人员交谈。他们拥有的很酷的东西之一是一个想法墓地,他们在其中描述他们决定不实施的功能以及原因。惰性集合的想法听起来很酷,但这是他们不得不说的。考虑一个List.filter()返回a 的操作List:


这里最大的问题是太多的操作变成了昂贵的线性时间命题。如果您想过滤列表并返回列表,而不仅仅是Collection或Iterable,则可以使用ImmutableList.copyOf(Iterables.filter(list, predicate)),它“ 预先说明”它的功能以及它的价格。


举一个具体的例子,什么是成本get(0)或size()上的列表?对于像这样的常用类ArrayList,它们是O(1)。但是,如果您在延迟过滤的列表中调用其中之一,则它必须在后备列表上运行过滤器,突然这些操作都是O(n)。更糟糕的是,它必须遍历每个操作的后备列表。


在我们看来,这太懒了。设置一些操作并推迟实际执行,直到您“ Go”为止是一回事。这是另一种以隐藏潜在大量计算的方式进行设置的方法。


保罗·桑多兹(Paul Sandoz)在提议禁止非线性流或“不可重用”流时,将其允许产生的潜在后果是“意外或令人困惑的结果”。他还提到并行执行会使事情变得更加棘手。最后,我要补充一点,如果该管道操作被意外执行了多次,或者至少与程序员预期的执行次数不同,则具有副作用的流水线操作会导致困难且难以理解的错误。(但是Java程序员不会编写带有副作用的lambda表达式,对吗?


因此,这是Java 8 Streams API设计的基本原理,该设计允许一次性遍历并且需要严格的线性(无分支)管道。它在多个不同的流源之间提供一致的行为,它清楚地将懒惰操作与急切操作分开,并且提供了直接的执行模型。


关于IEnumerable,我距离C#和.NET专家还很远,因此,如果我得出任何错误的结论,请(认真地)更正我将不胜感激。但是,它确实IEnumerable允许多次遍历在不同的源上表现出不同的行为。并且它允许嵌套IEnumerable操作的分支结构,这可能会导致一些重大的重新计算。尽管我理解不同的系统会做出不同的取舍,但这是我们在Java 8 Streams API设计中要避免的两个特征。


OP给出的快速排序示例很有趣,令人困惑,我很遗憾地说,这有些令人恐惧。调用QuickSort采用IEnumerable并返回IEnumerable,因此在IEnumerable遍历末尾之前实际上不会进行任何排序。但是,该调用似乎要做的是建立一个树结构,IEnumerables该树结构反映了quicksort会实际执行的分区。(毕竟,这是惰性计算。)如果源包含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以这种方式来构建复杂的计算结构确实很酷。但是,如果确实像我认为的那样增加了计算复杂性,那么除非特别小心,否则应该避免这种方式的编程。


查看完整回答
反对 回复 2019-10-23
?
PIPIONE

背景

虽然问题看起来很简单,但实际答案需要一些背景才能理解。如果您想跳到结论,请向下滚动...


选择您的比较点-基本功能

使用基本概念,C#的IEnumerable概念与JavaIterable更紧密相关,Java能够创建所需的任意数量的Iterators。IEnumerables创建IEnumerators。Java的Iterable创造Iterators


每个概念的历史是相似的,在这两个IEnumerable和Iterable有一个基本的动机,让“换每个”风格遍历数据收集的成员。这太过简单了,因为它们不仅允许这样做,而且它们也通过不同的进度到达该阶段,但是无论如何这都是一个重要的共同特征。


让我们比较一下该功能:在两种语言中,如果一个类实现IEnumerable/ Iterable,则该类必须至少实现一个方法(对于C#GetEnumerator和Java iterator())。在每种情况下,从该(IEnumerator/ Iterator)返回的实例都允许您访问数据的当前成员和后续成员。for-each语言语法中使用了此功能。


选择您的比较点-增强功能

IEnumerableC#中的C语言已扩展为允许许多其他语言功能(大部分与Linq相关)。添加的功能包括选择,预测,聚合等。这些扩展具有在集理论中使用的强烈动机,类似于SQL和关系数据库的概念。


Java 8还添加了功能,以支持使用Streams和Lambdas进行一定程度的功能编程。请注意,Java 8流不是主要由集合理论驱动的,而是由功能编程驱动的。无论如何,有很多相似之处。


所以,这是第二点。C#的增强功能是对IEnumerable概念的增强。但是,在Java中,增强功能是通过创建Lambda和Streams的新基本概念来实现的,然后还创建了一种相对简单的方法来Iterators与IterablesStreams 相互转换,反之亦然。


因此,将IEnumerable与Java的Stream概念进行比较是不完整的。您需要将其与Java中合并的Streams和Collections API进行比较。


在Java中,流与Iterables或Iterators不同

流并非旨在以与迭代器相同的方式解决问题:


迭代器是描述数据序列的一种方式。

流是描述数据转换序列的一种方式。

使用Iterator,您将获得一个数据值,对其进行处理,然后获得另一个数据值。


使用Streams,您可以将一系列函数链接在一起,然后将输入值提供给流,并从组合的序列中获取输出值。注意,用Java术语来说,每个函数都封装在一个Stream实例中。Streams API允许您以链接Stream一系列转换表达式的方式链接实例序列。


为了完成该Stream概念,您需要一个数据源来提供流,并需要一个使用该流的终端函数。


实际上,将值馈入流的方式可能来自Iterable,但Stream序列本身不是Iterable,而是复合函数。


Stream从某种意义上说,A 也是懒惰的,因为它仅在您从中请求值时才起作用。


请注意Streams的以下重要假设和功能:


一个Stream在Java是一种转换引擎,它把一个数据项的一个状态,到另一个状态。

流没有数据顺序或位置的概念,只需转换它们的要求即可。

可以向流提供许多来源的数据,包括其他流,迭代器,可迭代对象,集合,

您无法“重置”流,就像“对转换进行重新编程”一样。重置数据源可能是您想要的。

从逻辑上讲,任何时候流中都只有1个数据项在运行(除非该流是并行流,此时每个线程只有1个数据项)。这独立于数据源,该数据源可能具有比当前“准备好”提供给流的更多项,或者独立于可能需要聚合并减少多个值的流收集器。

流可以是不受限制的(无限的),仅受数据源或收集器(也可以是无限的)的限制。

流是“可链接的”,过滤一个流的输出是另一流。输入到流并由其转换的值可以依次提供给另一个进行不同转换的流。处于转换状态的数据从一个流流向下一个流。您无需干预并从一个流中提取数据并将其插入下一个流。

C#比较

当您认为Java Stream只是供应,流和收集系统的一部分,并且Streams和Iterators经常与Collections一起使用时,难怪很难将相同的概念与几乎所有内容都嵌入到IEnumerableC#中的单个概念中。


在所有Java Iterator,Iterable,Lambda和Stream概念中,IEnumerable的各个部分(以及与之密切相关的概念)都是显而易见的。


Java概念可以做的小事情在IEnumerable中很难,反之亦然。


结论

这里没有设计问题,只是语言之间的概念匹配问题。

流以不同方式解决问题

流向Java添加功能(它们添加了不同的做事方式,它们并没有剥夺功能)

在解决问题时,添加流可为您提供更多选择,将其归类为“增强能力”,而不是“减少”,“夺走”或“限制”,这是公平的。


为什么Java Streams一次性出现?

这个问题被误导了,因为流是函数序列,而不是数据。根据提供流的数据源,您可以重置数据源,并提供相同或不同的流。


与C#的IEnumerable不同,在IEnumerable中,执行管道可以执行任意多次,而在Java中,流只能“迭代”一次。

将a IEnumerable与a 比较Stream是错误的。IEnumerable与Java相比,您要说的上下文可以根据需要执行任意多次,最好与Java Iterables重复执行。Java Stream代表IEnumerable概念的子集,而不是提供数据的子集,因此不能被“重新运行”。


对终端操作的任何调用都会关闭流,使其无法使用。这种“功能”带走了很多力量。

从某种意义上说,第一个陈述是正确的。不是“夺走权力”的说法。您仍在比较Streams IEnumerables。流中的终端操作类似于for循环中的“ break”子句。如果需要,并且可以重新提供所需的数据,您总是可以自由地拥有另一个流。再次,如果您认为语句IEnumerable更像是Iterable,则Java会很好。


我想这不是技术原因。这种奇怪的限制背后的设计考虑是什么?

原因是技术性的,并且出于简单的原因,Stream是其认为是的子集。流子集不控制数据供应,因此您应该重置供应而不是流。在这种情况下,这并不奇怪。


QuickSort示例

您的quicksort示例具有签名:


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

您正在将输入IEnumerable视为数据源:


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

此外,返回值也是IEnumerable数据的供应,并且由于这是排序操作,因此供应的顺序很重要。如果您认为Java Iterable类是对此的适当匹配,特别是的List特殊化Iterable,因为List是具有保证顺序或迭代的数据源,则与您的代码等效的Java代码为:


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));

}    

请注意,存在一个错误(我已复制了此错误),因为该排序不能优雅地处理重复值,它是一个“唯一值”排序。


还要注意,Java代码如何使用数据源(List),并在不同的点使用流概念,并且在C#中,这两个“个性”可以用just表示IEnumerable。另外,虽然我已经使用List了基本类型,但是我可以使用更通用的类型Collection,并且如果迭代器到流转换很小,我可以使用更通用的类型。Iterable


查看完整回答
反对 回复 2019-10-23
?
缥缈止盈

Streams是围绕Spliterators 建立的,s是有状态的可变对象。他们没有“重置”动作,实际上,要求支持这种倒带动作将“夺走很多力量”。怎么会Random.ints()被认为来处理这样的要求?


另一方面,对于Stream具有可追溯原点的,很容易构造等效项Stream以再次使用。只需将构成的步骤Stream放入可重用的方法即可。请记住,重复这些步骤并不是昂贵的操作,因为所有这些步骤都是惰性操作。实际的工作从终端操作开始,并且取决于实际的终端操作,可能会执行完全不同的代码。


这种方法的作者将由您自己来指定两次调用该方法所隐含的含义:该方法是否再现与为未修改的数组或集合创建的流完全相同的序列,或者它会产生带有语义相似,但元素不同,例如随机整数流或控制台输入行流等。


顺便说一下,为了避免混淆,终端操作消耗的Stream是从不同的闭合的Stream作为调用close()流上做(这是需要的具有相关联的资源,如通过产生,例如流Files.lines())。


这似乎很混乱,从误导的比较茎IEnumerable用Stream。An IEnumerable表示提供实际值的能力IEnumerator,因此类似于IterableJava中的。相反,a Stream是一种迭代器,可与a媲美,IEnumerator因此断言这种数据类型可以在.NET中多次使用是错误的,对此的支持IEnumerator.Reset是可选的。这里讨论的示例使用了一个事实,IEnumerable可以使用an 来获取new, IEnumerator并且该Java也可以与Java一起使用Collection。你可以得到一个新的Stream。如果Java开发人员决定直接将Stream操作添加到Iterable,中间操作将返回另一个操作Iterable,它确实具有可比性,并且可以以相同的方式工作。


但是,开发人员对此表示反对,并且在此问题中讨论了该决定。最大的问题是关于急切的Collection操作和惰性Stream操作的困惑。通过查看.NET API,我(是的,个人而言)发现它是合理的。虽然IEnumerable单独看看上去很合理,但是特定的Collection将有很多直接操作Collection的方法,并且有许多方法返回lazy IEnumerable,而方法的特殊性质并不总是可以直观地识别出来的。我发现(在我看了几分钟后)最糟糕的例子是,List.Reverse()它的名称与继承的名称完全匹配(对于扩展方法,这是正确的终点吗?),Enumerable.Reverse()却具有完全矛盾的行为。


当然,这是两个不同的决定。第一个使Stream类型不同于Iterable/ 的类型Collection,第二个使Stream一种一次性迭代器而不是另一种可迭代。但是这些决定是一起做出的,可能是从未考虑过将这两个决定分开考虑的情况。创建它的初衷并不是与.NET相提并论。


API的实际设计决定是添加改进的迭代器类型Spliterator。Spliterators可以由旧的Iterables(这是对它们进行改装的方式)或全新的实现来提供。然后,Stream作为高级前端添加到了较低的Spliterators中。而已。您可能会讨论不同的设计是否会更好,但是考虑到现在的设计方式,这不会提高生产力,也不会改变。


您还需要考虑另一个实现方面。Streams 不是不变的数据结构。每个中间操作都可以返回一个Stream封装了旧实例的新实例,但它也可以替代地操纵自己的实例并返回自己(这并不排除对同一操作都执行)。众所周知的示例是类似parallel或的操作unordered,它们不会添加其他步骤,而是会操纵整个管道。具有如此可变的数据结构并尝试重用(或者更糟的是,同时使用多次)效果不佳……


为了完整起见,这是您的快速排序示例,已转换为Java StreamAPI。它表明它并没有真正“夺走很多能量”。


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());

}


查看完整回答
反对 回复 2019-10-23

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信