精华内容
下载资源
问答
  • 算符优先算法中优先函数的构造

    千次阅读 2020-11-04 10:29:09
    算符优先分析中“优先函数的简单构造!”


            这里我介绍的是一种简单的方法,不是书本的那个方法。是我后面那个参考资料上面的作者想出来的。因为这个是在知网上面找到的,是1997年的一篇文章。我就是一个总结,然后画几个比较清楚的图而已(因为从知网上下载的的pdf上面的图有点不太清楚)

    优先函数树形构造法

            我们教材上面的就是陈火旺老师的那本,然后方法就是找节点。这个方法虽然简单,但是操作起来的却有些麻烦,因为我们作图的时候,难免就会看不清楚,或者数错。下面介绍的树形构造法就可以避免这个问题,仅仅只需要根据优先矩阵就可以得出正确结果。

    操作步骤

    对于一个优先表先做如下几个步骤(假设优先函数存在)
    1 ) 对于f(a)对应行中“a>=b 的所有终结符b , 把g(b)作为f(a) 的子树。
    2) 对g(a) 对应列中有b <=a 的. 把f(a) 作为g(b)的子树.
    3 ) 对f(a)重做第( 1 ) 步, 对g(b) 重做第( 2 ) 步。
    4) 重复出现的f或g , 作记号不再对其执行第( 1) , ( 2) 步
    方向图
    5) 构造f(a)函数时, 以f(a) 为根结点, 按( 1 ) ,(2 ),( 3),( 4) 执行.
    6) 构造g(b)函数时, 以g(b) 为根结点, 按(2 ) ,( 1 ) , ( 3 ) , ( 4 ) 执行.
    按照以上5步先画出树,然后查树的节点数(包括根节点,做记号的不查),即可以得到根节点的优先函数值。
    但是我觉得这个操作步骤2有点问题。应该是b>=a的时候,就把f(a)作为g(b)的子树。我也自己做了实验,发现这样做才是正确的。不过也可能是我没有理解原作者的意思。反正,就目前看来,我都是按照如果b<=a,就把f(a)作为g(b)的子树。
    所以,下面我举例的例子,第(2)步都是按照“b>=a的时候,就把f(a)作为g(b)的子树”这个来做的。

    举例操作

            假如现有一个优先矩阵是这样的:这个例子是《编译原理》陈火旺老师(下面我说的教材,没有特别说明也是指的这本教材)那本书上面的。在90页。
    在这里插入图片描述
    那么我们现在用树形构造法来试试怎么得到这个优先函数。因为最后的答案是去掉了 i 和 # 之后得到的,所以我下面也将不会考虑 i 和 # 号。至于为什么不考虑 i 和 #,,就是因为这两个不是算符,我们算符优先函数主要针对的就是算符直接的优先级。但是优先关系矩阵中是给出了 i 和 # 与其他算符之间的优先关系的。我这里其实是有一个疑问的:因为在优先函数这里没有 i 的优先关系,那么在使用优先函数来分析一个句子是不是这个文法定义的合法的句子的时候,那么什么时候该移进这个 i 呢?希望知道的小伙伴可以在下面留言,我们讨论一下。

            计算f(+)的优先函数值。

    1. 从优先矩阵中可以得到:’+‘ >= 的算符有;’+’,’)’,’#'三个。因为不考虑i 和 #(下面就不提醒这一点了),所以f(+)的孩子节点有两个,分别是g(+)和g()),如下图所示。
      在这里插入图片描述
    2. 现在就来找g(’+’) 的子树。我这里还是采用的是如果b>=a,就把f(a)作为g(b)的子树。从优先表中可以看到的就是’+‘ >= 的算符有:’(’。注意,我这里说的’+‘是g(’+‘),也就是从’+‘那一列中寻找。在这里插入图片描述
      所以,g(’+’)的子树就是f(’(’);在这里插入图片描述
    3. 然后找到g(’)’) >=的算符:在这里插入图片描述
      但是f(’(’)已经出现过了(作为g(’+’)子树出现的),所以就不用画出来了。
    4. 然后就是寻找f(’(’) >=的算符。在这里插入图片描述但是g(’)’)也已经出现过了,所以这里也不用画出来了。
    5. 最后每一个节点我们都已经检查过了,没有可以重新添加的了。也就是趋于稳定了(编译原理里面好多都是这样子的,得使所有都不再变化的时候,算法就算结束了)。我们数一下节点的个数,就是4个,和书本95页给出的答案是一样的。

            同理,g(’+’)的树也可以这样画出来。我就给出最后的树,就不一一分析了。
    在这里插入图片描述

    自己的思考

            本质上书本上的画图和这里的画一颗树,都是优先级高的指向优先级低的,所以入度为0的节点,给的优先函数值应大一点,出度为0的,给出的优先函数值应该小一点。

            上面提到的这个简单的方法其本质善和我们教材上的方法是一样的。你可以将教材上的方法中的图给截取一部分出来。例如,你截取以g(’+’)作为顶点的树去看,发现就是和我上面画的一样。

            还有注意的一点就是:我们求出一组优先函数之后,就可以构造出无数组优先函数。所以,如果你求出来的和参考答案给出的不是一样的,也不一定是你错了。只要你的优先函数之间的关系和参考答案上给出的关系是一样的就可以了。

    参考资料

    构造优先函数的更简单方法_树型构造_潘群娜
    这个知网上我找到的一篇关于这个优先函数构造比较简单的方法,如果大家对上面的博客解释的不太清楚的话,可以去知网上看这个原作者写的文章。

    展开全文
  • 有些STL 容器提供了一些与算法同名的成员函数。大多数情况下,应该使用这些成员函数,而不是相应的STL算法。 有两个理由: 成员函数往往速度快。 成员函数通常与容器结合地更紧密,这是算法所不能比的。 set容器的...

    有些STL 容器提供了一些与算法同名的成员函数。大多数情况下,应该使用这些成员函数,而不是相应的STL算法。 有两个理由:

    • 成员函数往往速度快。
    • 成员函数通常与容器结合地更紧密,这是算法所不能比的。

    set容器的find成员函数以对数时间运行,而find算法以线性时间运行。

    效率并不是find成员函数和find算法之间的唯一差别。STL算法以相同性而判断两个对象是否具有相同的值,而关联容器使用等价性来进行它们的"相同性"测试。因此,在使用关联容器的时候,应该优先考虑成员函数形式的find、count、lower_bound等,而不是相应的STL算法,这些成员函数的行为与关联容器的其他成员函数能够保存更好的一致性。由于相等性和等价性之间的差别,STL算法不可能提供这样的一致性。

    对于标准的关联容器,选择成员函数而不选择对应的同名算法,这可以带来几方面的好处。

    • 可以获得对数时间的性能,而不是线性时间的性能。
    • 可以使用等价性来判断的那个两个值是否"相同",而等价性是关联容器的一个本质定义。
    • 在使用map和multimap的时候,将很自然地只考虑元素的键部分,而不是完整的键值对。

    对于list,性能几乎成为了全部考虑元素。

    remove、remove_if、unique、sort、merge以及reverse这些算法无一例外地需要拷贝list容器的对象,而这些版本的成员函数则无需任何对象拷贝,它们只是简单地维护好那些将list节点连接起来的指针。这些算法的时间复杂度并没有改变,但多数情况下维护指针的开销比拷贝对象要低得多,所以list成员函数应该会提供更好地性能。

    list成员函数的行为不同于其同名的算法。如果真的要从容器中删除对象的话,在调用remove、remove_if或者unique算法之后,必须接着调用erase。而list的remove、remove_if、unique成员函数则实实在在地删除了元素,所以无需再调用erase。

    sort算法与list的sort函数之间一个很重要的区别是,前者根本不能被应用于list容器上,list的迭代器只是双向迭代器,而sort算法要求随机访问迭代器。在merge算法和list的merge成员函数之间也存在这种区别。merge算法是不允许修改其源区间的,而list的merge成员函数总是在修改它所操作的链表。

    当需要在STL算法与容器的同名成员函数之间做出选择的时候,应该优先选择成员函数。成员函数的性能更为优越,而却它们更能够与容器的一贯行为保持一致。

    展开全文
  • 44. 优先使用标准的函数式接口 现在 Java 已经有 lambda 表达式,编写 API 的最佳实践已经发生了很大的变化。 例如,模板方法模式[Gamma95],其中一个子类重写原始方法以专门化其父类的行为,变得没有那么吸引人。 ...

    44. 优先使用标准的函数式接口

    现在 Java 已经有 lambda 表达式,编写 API 的最佳实践已经发生了很大的变化。 例如,模板方法模式[Gamma95],其中一个子类重写原始方法以专门化其父类的行为,变得没有那么吸引人。 现代替代的选择是提供一个静态工厂或构造方法来接受函数对象以达到相同的效果。 通常地说,可以编写更多以函数对象为参数的构造方法和方法。 选择正确的函数式参数类型需要注意。

    考虑 LinkedHashMap。 可以通过重写其受保护的 removeEldestEntry 方法将此类用作缓存,每次将新的 key 值加入到 map 时都会调用该方法。 当此方法返回 true 时,map 将删除传递给该方法的最久条目。 以下代码重写允许 map 增长到一百个条目,然后在每次添加新 key 值时删除最老的条目,并保留最近的一百个条目:

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
       return size() > 100;
    }
    

    这种技术很有效,但是你可以用 lambdas 做得更好。如果 LinkedHashMap 是现在编写的,那么它将有一个静态的工厂或构造方法来获取函数对象。查看 removeEldestEntry 方法的声明,你可能会认为函数对象应该接受一个 Map.Entry<K,V> 并返回一个布尔值,但是这并不完全是这样:removeEldestEntry 方法调用 size() 方法来获取条目的数量,因为 removeEldestEntry 是 map 上的一个实例方法。传递给构造方法的函数对象不是 map 上的实例方法,无法捕获,因为在调用其工厂或构造方法时 map 还不存在。因此,map 必须将自己传递给函数对象,函数对象把 map 以及最就的条目作为输入参数。如果要声明这样一个功能接口,应该是这样的:

    // Unnecessary functional interface; use a standard one instead.
    @FunctionalInterface 
    interface EldestEntryRemovalFunction<K,V>{
        boolean remove(Map<K,V> map, Map.Entry<K,V> eldest);
    }
    

    这个接口可以正常工作,但是你不应该使用它,因为你不需要为此目的声明一个新的接口。 java.util.function 包提供了大量标准函数式接口供你使用。 如果其中一个标准函数式接口完成这项工作,则通常应该优先使用它,而不是专门构建的函数式接口。 这将使你的 API 更容易学习,通过减少其不必要概念,并将提供重要的互操作性好处,因为许多标准函数式接口提供了有用的默认方法。 例如,Predicate 接口提供了组合判断的方法。 在我们的 LinkedHashMap 示例中,标准的 BiPredicate<Map<K,V>, Map.Entry<K,V>> 接口应优先于自定义的 EldestEntryRemovalFunction 接口的使用。

    java.util.Function 中有 43 个接口。不能指望全部记住它们,但是如果记住了六个基本接口,就可以在需要它们时派生出其余的接口。基本接口操作于对象引用类型。Operator 接口表示方法的结果和参数类型相同。Predicate 接口表示其方法接受一个参数并返回一个布尔值。Function 接口表示方法其参数和返回类型不同。Supplier 接口表示一个不接受参数和返回值 (或「供应」) 的方法。最后,Consumer 表示该方法接受一个参数而不返回任何东西,本质上就是使用它的参数。六种基本函数式接口概述如下:

    接口方法示例
    UnaryOperator<T>T apply(T t)String::toLowerCase
    BinaryOperator<T>T apply(T t1, T t2)BigInteger::add
    Predicate<T>boolean test(T t)Collection::isEmpty
    Function<T,R>R apply(T t)Arrays::asList
    Supplier<T>T get()Instant::now
    Consumer<T>void accept(T t)System.out::println

    在处理基本类型 int,long 和 double 的操作上,六个基本接口中还有三个变体。 它们的名字是通过在基本接口前加一个基本类型而得到的。 因此,例如,一个接受 int 的 Predicate 是一个 IntPredicate,而一个接受两个 long 值并返回一个 long 的二元运算符是一个 LongBinaryOperator。 除 Function 接口变体通过返回类型进行了参数化,其他变体类型都没有参数化。 例如,LongFunction<int[]> 使用 long 类型作为参数并返回了 int[] 类型。

    Function 接口还有九个额外的变体,当结果类型为基本类型时使用。 源和结果类型总是不同,因为从类型到它自身的函数是 UnaryOperator。 如果源类型和结果类型都是基本类型,则使用带有 SrcToResult 的前缀 Function,例如 LongToIntFunction(六个变体)。如果源是一个基本类型,返回结果是一个对象引用,那么带有 ToObj 的前缀 Function,例如 DoubleToObjFunction (三种变体)。

    有三个包含两个参数版本的基本功能接口,使它们有意义:BiPredicate <T,U>BiFunction <T,U,R>BiConsumer <T,U>。 也有返回三种相关基本类型的 BiFunction 变体:ToIntBiFunction <T,U>ToLongBiFunction<T,U>ToDoubleBiFunction <T,U>Consumer 有两个变量,它们带有一个对象引用和一个基本类型:ObjDoubleConsumer <T>ObjIntConsumer <T>ObjLongConsumer <T>。 总共有九个两个参数版本的基本接口。

    最后,还有一个 BooleanSupplier 接口,它是 Supplier 的一个变体,它返回布尔值。 这是任何标准函数式接口名称中唯一明确提及的布尔类型,但布尔返回值通过 Predicate 及其四种变体形式支持。 前面段落中介绍的 BooleanSupplier 接口和 42 个接口占所有四十三个标准功能接口。 无可否认,这是非常难以接受的,并且不是非常正交的。 另一方面,你所需要的大部分功能接口都是为你写的,而且它们的名字是经常性的,所以在你需要的时候不应该有太多的麻烦。

    大多数标准函数式接口仅用于提供对基本类型的支持。 不要试图使用基本的函数式接口来装箱基本类型的包装类而不是基本类型的函数式接口。 虽然它起作用,但它违反了第 61 条中的建议:「优先使用基本类型而不是基本类型的包装类」。使用装箱基本类型的包装类进行批量操作的性能后果可能是致命的。

    现在你知道你应该通常使用标准的函数式接口来优先编写自己的接口。 但是,你应该什么时候写自己的接口? 当然,如果没有一个标准模块能够满足您的需求,例如,如果需要一个带有三个参数的 Predicate,或者一个抛出检查异常的 Predicate,那么需要编写自己的代码。 但有时候你应该编写自己的函数式接口,即使与其中一个标准的函数式接口的结构相同。

    考虑我们的老朋友 Comparator <T>,它的结构与 ToIntBiFunction <T, T> 接口相同。 即使将前者添加到类库时后者的接口已经存在,使用它也是错误的。 Comparator 值得拥有自己的接口有以下几个原因。 首先,它的名称每次在 API 中使用时都会提供优秀的文档,并且使用了很多。 其次,Comparator 接口对构成有效实例的构成有强大的要求,这些要求构成了它的普遍契约。 通过实现接口,就要承诺遵守契约。 第三,接口配备很多了有用的默认方法来转换和组合多个比较器。

    如果需要一个函数式接口与 Comparator 共享以下一个或多个特性,应该认真考虑编写一个专用函数式接口,而不是使用标准函数式接口:

    • 它将被广泛使用,并且可以从描述性名称中受益。
    • 它拥有强大的契约。
    • 它会受益于自定义的默认方法。

    如果选择编写你自己的函数式接口,请记住它是一个接口,因此应非常小心地设计(详见第 21 条)。

    请注意,EldestEntryRemovalFunction 接口(第 199 页)标有 @FunctionalInterface 注解。 这种注解在类型类似于 @Override。 这是一个程序员意图的陈述,它有三个目的:它告诉读者该类和它的文档,该接口是为了实现 lambda 表达式而设计的;它使你保持可靠,因为除非只有一个抽象方法,否则接口不会编译; 它可以防止维护人员在接口发生变化时不小心地将抽象方法添加到接口中。 始终使用 @FunctionalInterface 注解标注你的函数式接口。

    最后一点应该是关于在 api 中使用函数接口的问题。不要提供具有多个重载的方法,这些重载在相同的参数位置上使用不同的函数式接口,如果这样做可能会在客户端中产生歧义。这不仅仅是一个理论问题。ExecutorServicesubmit 方法可以采用 Callable<T>Runnable 接口,并且可以编写需要强制类型转换以指示正确的重载的客户端程序(详见第 52 条)。避免此问题的最简单方法是不要编写在相同的参数位置中使用不同函数式接口的重载。这是条目 52 中建议的一个特例,「明智地使用重载」。

    总之,现在 Java 已经有了 lambda 表达式,因此必须考虑 lambda 表达式来设计你的 API。 在输入上接受函数式接口类型并在输出中返回它们。 一般来说,最好使用 java.util.function.Function 中提供的标准接口,但请注意,在相对罕见的情况下,最好编写自己的函数式接口。

    展开全文
  • 46. 优先考虑流中无副作用的函数 如果你是一个刚开始使用流的新手,那么很难掌握它们。仅仅将计算表示为流管道是很困难的。当你成功时,你的程序将运行,但对你来说可能没有意识到任何好处。流不仅仅是一个 API,它...

    46. 优先考虑流中无副作用的函数

    如果你是一个刚开始使用流的新手,那么很难掌握它们。仅仅将计算表示为流管道是很困难的。当你成功时,你的程序将运行,但对你来说可能没有意识到任何好处。流不仅仅是一个 API,它是基于函数式编程的范式(paradigm)。为了获得流提供的可表达性、速度和某些情况下的并行性,你必须采用范式和 API。

    流范式中最重要的部分是将计算结构化为一系列转换,其中每个阶段的结果尽可能接近前一阶段结果的纯函数(pure function)。 纯函数的结果仅取决于其输入:它不依赖于任何可变状态,也不更新任何状态。 为了实现这一点,你传递给流操作的任何函数对象(中间操作和终结操作)都应该没有副作用。

    有时,可能会看到类似于此代码片段的流代码,该代码构建了文本文件中单词的频率表:

    // Uses the streams API but not the paradigm--Don't do this!
    Map<String, Long> freq = new HashMap<>();
    try (Stream<String> words = new Scanner(file).tokens()) {
        words.forEach(word -> {
            freq.merge(word.toLowerCase(), 1L, Long::sum);
        });
    }
    

    这段代码出了什么问题? 毕竟,它使用了流,lambdas 和方法引用,并得到正确的答案。 简而言之,它根本不是流代码; 它是伪装成流代码的迭代代码。 它没有从流 API 中获益,并且它比相应的迭代代码更长,更难读,并且更难于维护。 问题源于这样一个事实:这个代码在一个终结操作 forEach 中完成所有工作,使用一个改变外部状态(频率表)的 lambda。forEach 操作除了表示由一个流执行的计算结果外,什么都不做,这是「代码中的臭味」,就像一个改变状态的 lambda 一样。那么这段代码应该是什么样的呢?

    // Proper use of streams to initialize a frequency table
    Map<String, Long> freq;
    try (Stream<String> words = new Scanner(file).tokens()) {
        freq = words
            .collect(groupingBy(String::toLowerCase, counting()));
    }
    

    此代码段与前一代码相同,但正确使用了流 API。 它更短更清晰。 那么为什么有人会用其他方式写呢? 因为它使用了他们已经熟悉的工具。 Java 程序员知道如何使用 for-each 循环,而 forEach 终结操作是类似的。 但 forEach 操作是终端操作中最不强大的操作之一,也是最不友好的流操作。 它是明确的迭代,因此不适合并行化。 forEach 操作应仅用于报告流计算的结果,而不是用于执行计算。 有时,将 forEach 用于其他目的是有意义的,例如将流计算的结果添加到预先存在的集合中。

    改进后的代码使用了收集器(collector),这是使用流必须学习的新概念。Collectors 的 API 令人生畏:它有 39 个方法,其中一些方法有多达 5 个类型参数。好消息是,你可以从这个 API 中获得大部分好处,而不必深入研究它的全部复杂性。对于初学者来说,可以忽略收集器接口,将收集器看作是封装缩减策略(reduction strategy)的不透明对象。在此上下文中,reduction 意味着将流的元素组合为单个对象。 收集器生成的对象通常是一个集合(它代表名称收集器)。

    将流的元素收集到真正的集合中的收集器非常简单。有三个这样的收集器:toList()toSet()toCollection(collectionFactory)。它们分别返回集合、列表和程序员指定的集合类型。有了这些知识,我们就可以编写一个流管道从我们的频率表中提取出现频率前 10 个单词的列表。

    // Pipeline to get a top-ten list of words from a frequency table
    List<String> topTen = freq.keySet().stream()
        .sorted(comparing(freq::get).reversed())
        .limit(10)
        .collect(toList());
    

    注意,我们没有对 toList 方法的类收集器进行限定。静态导入收集器的所有成员是一种惯例和明智的做法,因为它使流管道更易于阅读。

    这段代码中唯一比较棘手的部分是我们把 comparing(freq::get).reverse() 传递给 sort 方法。comparing 是一种比较器构造方法(详见第 14 条),它具有一个 key 的提取方法。该函数接受一个单词,而“提取”实际上是一个表查找:绑定方法引用 freq::getfrequency 表中查找单词,并返回单词出现在文件中的次数。最后,我们在比较器上调用 reverse 方法,因此我们将单词从最频繁到最不频繁进行排序。然后,将流限制为 10 个单词并将它们收集到一个列表中就很简单了。

    前面的代码片段使用 Scannerstream 方法在 scanner 实例上获取流。这个方法是在 Java 9 中添加的。如果正在使用较早的版本,可以使用类似于条目 47 中 (streamOf(Iterable<E>)) 的适配器将实现了 Iteratorscanner 序转换为流。

    那么收集器中的其他 36 种方法呢?它们中的大多数都是用于将流收集到 map 中的,这比将流收集到真正的集合中要复杂得多。每个流元素都与一个键和一个值相关联,多个流元素可以与同一个键相关联。

    最简单的映射收集器是 toMap(keyMapper、valueMapper),它接受两个函数,一个将流元素映射到键,另一个映射到值。在条目 34 中的 fromString 实现中,我们使用这个收集器从 enum 的字符串形式映射到 enum 本身:

    // Using a toMap collector to make a map from string to enum
    private static final Map<String, Operation> stringToEnum =
        Stream.of(values()).collect(
            toMap(Object::toString, e -> e));
    

    如果流中的每个元素都映射到唯一键,则这种简单的 toMap 形式是完美的。 如果多个流元素映射到同一个键,则管道将以 IllegalStateException 终止。

    toMap 更复杂的形式,以及 groupingBy 方法,提供了处理此类冲突 (collisions) 的各种方法。一种方法是向 toMap 方法提供除键和值映射器(mappers)之外的 merge 方法。merge 方法是一个 BinaryOperator<V>,其中 V是 map 的值类型。与键关联的任何附加值都使用 merge 方法与现有值相结合,因此,例如,如果 merge 方法是乘法,那么最终得到的结果是是值 mapper 与键关联的所有值的乘积。

    toMap 的三个参数形式对于从键到与该键关联的选定元素的映射也很有用。例如,假设我们有一系列不同艺术家(artists)的唱片集(albums),我们想要一张从唱片艺术家到最畅销专辑的 map。这个收集器将完成这项工作。

    // Collector to generate a map from key to chosen element for key
    Map<Artist, Album> topHits = albums.collect(
       toMap(Album::artist, a->a, maxBy(comparing(Album::sales))));
    

    请注意,比较器使用静态工厂方法 maxBy,它是从 BinaryOperator 静态导入的。 此方法将 Comparator<T> 转换为 BinaryOperator<T>,用于计算指定比较器隐含的最大值。 在这种情况下,比较器由比较器构造方法 comparing 返回,它采用 key 提取器函数 Album::sales。 这可能看起来有点复杂,但代码可读性很好。 简而言之,它说,「将专辑(albums)流转换为地 map,将每位艺术家(artist)映射到销售量最佳的专辑。」这与问题陈述出奇得接近。

    toMap 的三个参数形式的另一个用途是产生一个收集器,当发生冲突时强制执行 last-write-wins 策略。 对于许多流,结果是不确定的,但如果映射函数可能与键关联的所有值都相同,或者它们都是可接受的,则此收集器的行为可能正是您想要的:

    // Collector to impose last-write-wins policy
    toMap(keyMapper, valueMapper, (oldVal, newVal) ->newVal)
    

    toMap 的第三个也是最后一个版本采用第四个参数,它是一个 map 工厂,用于指定特定的 map 实现,例如 EnumMapTreeMap

    toMap 的前三个版本也有变体形式,名为 toConcurrentMap,它们并行高效运行并生成 ConcurrentHashMap 实例。

    除了 toMap 方法之外,Collectors API 还提供了 groupingBy 方法,该方法返回收集器以生成基于分类器函数 (classifier function)将元素分组到类别中的 map。 分类器函数接受一个元素并返回它所属的类别。 此类别来用作元素的 map 的键。 groupingBy 方法的最简单版本仅采用分类器并返回一个 map,其值是每个类别中所有元素的列表。 这是我们在条目 45 中的 Anagram 程序中使用的收集器,用于生成从按字母顺序排列的单词到单词列表的 map:

    Map<String, Long> freq = words
            .collect(groupingBy(String::toLowerCase, counting()));
    

    groupingBy 的第三个版本允许指定除 downstream 收集器之外的 map 工厂。 请注意,这种方法违反了标准的可伸缩参数列表模式 (standard telescoping argument list pattern):mapFactory 参数位于 downStream 参数之前,而不是之后。 此版本的 groupingBy 可以控制包含的 map 以及包含的集合,因此,例如,可以指定一个收集器,它返回一个 TreeMap,其值是 TreeSet

    groupingByConcurrent 方法提供了 groupingBy 的所有三个重载的变体。 这些变体并行高效运行并生成 ConcurrentHashMap 实例。 还有一个很少使用的 grouping 的亲戚称为 partitioningBy。 代替分类器方法,它接受 predicate 并返回其键为布尔值的 map。 此方法有两种重载,除了 predicate 之外,其中一种方法还需要 downstream 收集器。

    通过 counting 方法返回的收集器仅用作下游收集器。 Stream 上可以通过 count 方法直接使用相同的功能,因此没有理由说 collect(counting())。 此属性还有十五种收集器方法。 它们包括九个方法,其名称以 summingaveragingsummarizing 开头(其功能在相应的原始流类型上可用)。 它们还包括 reduce 方法的所有重载,以及 filter,mappingflatMappingcollectingAndThen 方法。 大多数程序员可以安全地忽略大多数这些方法。 从设计的角度来看,这些收集器代表了尝试在收集器中部分复制流的功能,以便下游收集器可以充当「迷你流(ministreams)」。

    我们还有三种收集器方法尚未提及。 虽然他们在收 Collectors 类中,但他们不涉及集合。 前两个是 minBymaxBy,它们取比较器并返回比较器确定的流中的最小或最大元素。 它们是 Stream 接口中 minmax 方法的次要总结,是 BinaryOperator 中类似命名方法返回的二元运算符的类似收集器。 回想一下,我们在最畅销的专辑中使用了 BinaryOperator.maxBy 方法。

    最后的 Collectors 中方法是 join,它仅对 CharSequence 实例(如字符串)的流进行操作。 在其无参数形式中,它返回一个简单地连接元素的收集器。 它的一个参数形式采用名为 delimiter 的单个 CharSequence 参数,并返回一个连接流元素的收集器,在相邻元素之间插入分隔符。 如果传入逗号作为分隔符,则收集器将返回逗号分隔值字符串(但请注意,如果流中的任何元素包含逗号,则字符串将不明确)。 除了分隔符之外,三个参数形式还带有前缀和后缀。 生成的收集器会生成类似于打印集合时获得的字符串,例如[came, saw, conquered]

    总之,编程流管道的本质是无副作用的函数对象。 这适用于传递给流和相关对象的所有许多函数对象。 终结操作 forEach 仅应用于报告流执行的计算结果,而不是用于执行计算。 为了正确使用流,必须了解收集器。 最重要的收集器工厂是 toListtoSettoMapgroupingByjoin

    展开全文
  • Effective STL 第五条 区间成员函数优先于与之对应的单元素成员 原因 一、易写易懂 1. 通过使用区间成员函数,通常可以少写一些代码 2.使用区间成员函数通常会得到意图清晰和更加直接的代码 二、优越性:效率 ...
  • 常用激活函数(激励函数)理解与总结

    万次阅读 多人点赞 2018-05-13 23:07:19
    学习神经网络的时候我们总是听到激活函数这个词,而且很多资料都会提到常用的激活函数,比如Sigmoid函数、tanh函数、Relu函数。那么我们就来详细了解下激活函数方方面面的知识。本文的内容包括几个部分: 什么是...
  • C++学习之深入理解虚函数--虚函数表解析 标签: C++C++虚函数虚函数表解析虚函数表 2014-03-27 11:05 11838人阅读 评论(6) 收藏 举报  分类:   C++语言(79)  目录(?)[+] ...
  • 深入理解多态虚函数--虚函数表解析

    千次阅读 2018-02-09 15:02:13
    C++中的虚函数的作用主要是实现了多态的机制。关于多态,简而言之就是用父类型别的指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”,这是一种泛型技术。...
  • 数据结构实现 6.4:优先队列_基于链表实现(C++版)1. 概念及基本框架2. 基本操作程序实现2.1 入队操作2.2 出队操作2.3 查找操作2.4 其他操作3. 算法复杂度分析3.1 入队操作3.2 出队操作3.3 查找操作4. 完整代码 1. ...
  • C++_多态(深入理解虚函数表

    千次阅读 多人点赞 2021-05-08 13:23:17
    军人买票时是优先买票 怎么构成多态 并没有构成多态,形参p对象,全部调用了Person类的成员函数。 多态与重写 这时候就需要使用虚函数来构成多态。 梳理一下,多态的条件: 继承类中,需要对虚函数进行重写。 ...
  • 假设当前已对前i个物品进行了某种特定的选择,且背包中已装入物品的重量是w,获得的价值是v,计算该结点的目标函数上界的一个简单方法是,将背包中剩余容量全部装入第i+1个物品,并可以将背包装满,于是,得到限界...
  • item 44:优先使用与泛型算法同名的成员函数一些容器拥有和stl泛型算法同名的成员函数。关联容器提供count()、find()、lower_bound()、upper_bound(),和equal_range(),而list提供了remove()、remove_if()、unique...
  • 优先搜索,而且,调用了基于邻接的存储结构的对图G 深度优先搜索和广度优先搜索的 函数DFSTraverse1()和BFSTraverse1()。 // algo7-11.cpp 检验深度优先和广度优先的程序(邻接存储结构) #include"c1.h" ...
  • CJOJ 2484 函数最小值 / Luogu 2085 函数最小值(STL优先队列,堆)
  • 2.图的存储结构之邻接 3.图的遍历-深度优先搜索遍历DFS:Depth First Search 3.1图的遍历-广度优先搜索遍历BFS:Breadth First Search 3.2深度优先遍历和广度优先遍历实现代码 4.DFS的一应用小例子 注意:图...
  • 函数模板和普通函数区别结论: 1、函数模板不允许自动类型转化...2、C++编译器优先考虑普通函数; 3、如果函数模版可以产生一个更好的匹配,那么选择模版; 4、可以通过空模版实参列表的语法限定编译器只通过模版匹配;
  • 图的遍历有两种遍历方式:深度优先遍历(depth-first search)和广度优先遍历(breadth-first search)。 因为深度优先需要无路可走时按照来路往回退,正好是后进先出。 广度优先则需要保证先访问顶点的未访问邻接点先...
  • 另外还实现了一个层次优先遍历函数。该函数用一个队列实现该多叉树的层次优先遍历。首先将根节点入队列,然后检测队列是否为空,如果不为空,将队列出队列,访问出队列的节点,然后该节点的子节点指针入队列,依次...
  • } } } /** * 从指定顶点vertex开始进行广度优先遍历 * * @param vertex 从vertex顶点开始进行广度优先遍历 */ public void bfs(int vertex) { boolean[] visited = new boolean[numberOfVertex]; Arrays.fill...
  • 优先队列

    千次阅读 2015-05-07 20:31:50
    优先队列我们在之前讲过的《堆的基础知识》和《堆排序》之后,我们来讲讲最大堆和最小堆的具体应用优先队列!优先队列基础知识我们来看看这样的场景,给定你一组数据,要你在这组数据里面找到最大的那个数据,你要...
  • C++定义函数

    千次阅读 2019-07-16 15:26:07
    一、函数传递参数的方式 术语: 主调函数:调用其他函数函数,大部分时候为main函数 被调函数:被其他函数如main函数调用的函数 变元:在主调函数中传递给被调函数的变量或常量,如函数调用语句function(a,b)...
  • js系列教程4-函数函数参数全解

    千次阅读 2017-08-09 18:55:27
    //自定义函数函数声明,会优先加载。调用函数时会先在本机活动对象中查询,即当前js文件中查询,如果没有才会向上查询,所以在两个js文件中定义相同函数名,js文件内调用各自的函数,其他文件中调用最后声明的函数...
  • #include #include #include #include #define MAXVERTEX 10 //最大顶点数 ...typedef struct ArcNode //结点的类型定义 { int adjvex; //边指向的顶点的位置 struct ArcNode *nextarc; //指示下一个与该顶
  • /* *本文实现了深度优先搜索和人工智能中常用的A*搜索。 *本文中假设图由ROWS*COLS大小的矩阵,1代表不可通行,0代表可通行,矩阵中的2可看做图的起点和终点... *估价函数F(x)=G(x)+H(x),G(x)为从起始节点到当前节点
  • Dijkstra算法堆/优先队列优化前言额外知识简介堆与优先队列STL库重载Dijkstra分析及优化分析优化代码实现存储结构边点优先队列函数初始化添加边Dijkstra主函数后记 前文:Dijkstra算法&&邻接数组 前言 ...
  • 深度优先搜索(DFS)与广度优先搜索(BFS)详解

    千次阅读 多人点赞 2020-11-07 18:44:06
    深度优先搜索与宽度优先搜索详解 深度优先搜索(DFS)和宽度优先搜索(BFS)都是常见的搜索算法。在学习DFS和BFS之前,我们首先得知道递归函数的概念。 1. 递归函数 通俗地讲,一个函数自己调用自己的行为就叫递归,...
  • 深度优先搜索

    万次阅读 多人点赞 2017-08-10 09:01:35
    深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在...
  • 实验要求: 1.[实验项目] 实现LL(1)分析中控制程序(驱动程序);完成以下描述赋值语句的LL(1)文法的LL(1...(1)构造该算符优先文法的优先关系矩阵或优先函数; (2)输入串应是词法分析的输出二元式序列,即某算...
  • 当变量名与函数名重复时,变量优先函数 原理:函数的编译过程比变量复杂 优点:防止函数内部变量被外部污染 与普通函数的区别: 普通函数有定义,按需执行,变量可能被污染 立即执行函数只要有定义直接执行 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 218,397
精华内容 87,358
关键字:

优先表得到优先函数