精华内容
下载资源
问答
  • GC(Allocation Failure)引发的一些JVM知识点梳理

    万次阅读 多人点赞 2018-10-12 17:08:51
    日前查看某个程序的日志,发现一直在报GC相关的信息,不确定这样的信息是代表正确还是不...[GC (Allocation Failure) [ParNew: 367523K->1293K(410432K), 0.0023988 secs] 522739K->156516K(1322496K), 0.0025...

    日前查看某个程序的日志,发现一直在报GC相关的信息,不确定这样的信息是代表正确还是不正确,所以正好借此机会再复习下GC相关的内容:

    以其中一行为例来解读下日志信息:

    [GC (Allocation Failure) [ParNew: 367523K->1293K(410432K), 0.0023988 secs] 522739K->156516K(1322496K), 0.0025301 secs] [Times: user=0.04 sys=0.00, real=0.01 secs]

     

    GC

    表明进行了一次垃圾回收,前面没有Full修饰,表明这是一次Minor GC ,注意它不表示只GC新生代,并且现有的不管是新生代还是老年代都会STW

    Allocation Failure

    表明本次引起GC的原因是因为在年轻代中没有足够的空间能够存储新的数据了。

    ParNew

        表明本次GC发生在年轻代并且使用的是ParNew垃圾收集器。ParNew是一个Serial收集器的多线程版本,会使用多个CPU和线程完成垃圾收集工作(默认使用的线程数和CPU数相同,可以使用-XX:ParallelGCThreads参数限制)。该收集器采用复制算法回收内存,期间会停止其他工作线程,即Stop The World。

    367523K->1293K(410432K):单位是KB

    三个参数分别为:GC前该内存区域(这里是年轻代)使用容量,GC后该内存区域使用容量,该内存区域总容量。

    0.0023988 secs

        该内存区域GC耗时,单位是秒

    522739K->156516K(1322496K)

    三个参数分别为:堆区垃圾回收前的大小,堆区垃圾回收后的大小,堆区总大小。

    0.0025301 secs

    该内存区域GC耗时,单位是秒

    [Times: user=0.04 sys=0.00, real=0.01 secs]

        分别表示用户态耗时,内核态耗时和总耗时

     

    分析下可以得出结论:

        该次GC新生代减少了367523-1293=366239K

        Heap区总共减少了522739-156516=366223K

        366239 – 366223 =16K,说明该次共有16K内存从年轻代移到了老年代,可以看出来数量并不多,说明都是生命周期短的对象,只是这种对象有很多。

        我们需要的是尽量避免Full GC的发生,让对象尽可能的在年轻代就回收掉,所以这里可以稍微增加一点年轻代的大小,让那17K的数据也保存在年轻代中。

     

    GC时,什么方法判断哪些对象需要回收:

    1. 引用计数法(已经不用了)
    2. 可达性分析法

    前一种简而言之就是给对象添加一个引用计数器,有其他地方引用时这个计数器+1,引用失效时-1,为0时就可以删除掉了。但是它不能解决循环引用的问题,所以一般使用的都是后一种算法。

    可达性分析法的基本思路就是通过一系列名为GC Roots的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链(Reference Chain),当一个对象到GC Roots没有任何引用链相连时,则证明此对象是不可用的,那就可以回收掉了。

    GC Roots一般都是些堆外指向堆内的引用,例如:

    1. JVM栈中引用的对象
    2. 方法区中静态属性引用的对象
    3. 方法区中常量引用的对象
    4. 本地方法栈中引用的对象 

     

     

    以CMS为例,补充一些知识点介绍:

    复制算法介绍:

    因为新生代对象生命周期一般很短,现在一般将该内存区域划分为三块部分,一块大的叫Eden,两块小的叫Survivor。他们之间的比例一般为8:1:1。

    使用的时候只使用Eden + 一块Survivor。用Eden区用满时会进行一次minor gc,将存活下面的对象复制到另外一块Survivor上。如果另一块Survivor放不下(对应虚拟机参数为 XX:TargetSurvivorRatio默认50,50%),对象直接进入老年代

    (使用CMS时,默认的新生代收集器是ParNew)(有时新生代GC时,需要找到老年代中引用的新生代对象,这个时候会用到一种叫“卡表”的技术,避免老年代的全表扫描,具体怎么操作的暂时还不知道……)

     

    Survivor区的意义:

        如果没有survivor,Eden每进行一次minor gc,存活的对象就会进入老年代,老年代很快被填满就会进入major gc。由于老年代空间一般很大,所以进行一次gc耗时要长的多!尤其是频繁进行full GC,对程序的响应和连接都会有影响!

        Survivor存在就是减少被送到老年代的对象,进而减少Full gc的发生。默认设置是经历了15次minor gc还在新生代中存活的对象才会被送到老年代。

     

    为什么要有两个Survivor:

        主要是为了解决内存碎片化和效率问题。如果只有一个Survivor时,每触发一次minor gc都会有数据从Eden放到Survivor,一直这样循环下去。注意的是,Survivor区也会进行垃圾回收,这样就会出现内存碎片化问题。如下图所示:

     

        碎片化会导致堆中可能没有足够大的连续空间存放一个大对象,影响程序性能。如果有两块Survivor就能将剩余对象集中到其中一块Survivor上,避免碎片问题。如下图所示:

     

    Minor GC和Full GC的区别以及触发条件:

    Minor GC:

        对于复制算法来说,当年轻代Eden区域满的时候会触发一次Minor GC,将Eden和From Survivor的对象复制到另外一块To Survivor上。

        注意:如果某个对象存活的时间超过一定Minor gc次数会直接进入老年代,不在分配到To Survivor上(默认15次,对应虚拟机参数 -XX:+MaxTenuringThreshold)。

     

    Full GC:

    用于清理整个堆空间。它的触发条件主要有以下几种:

    1. 显式调用System.gc方法(建议JVM触发)。
    2. 方法区空间不足(JDK8及之后不会有这种情况了,详见下文)
    3. 老年代空间不足,引起Full GC。这种情况比较复杂,有以下几种:

    3.1 大对象直接进入老年代引起,由-XX:PretenureSizeThreshold参数定义

    3.2 Minor GC时,经历过多次Minor GC仍存在的对象进入老年代。上面提过,由-XX:MaxTenuringThreashold参数定义

    3.3 Minor GC时,动态对象年龄判定机制会将对象提前转移老年代。年龄从小到大进行累加,当加入某个年龄段后,累加和超过survivor区域 * -XX:TargetSurvivorRatio的时候,从这个年龄段往上的年龄的对象进入老年代

    3.4 Minor GC时,Eden和From Space区向To Space区复制时,大于To Space区可用内存,会直接把对象转移到老年代

     

    JVM的空间分配担保机制可能会触发Full GC:

    在进行Minor GC之前,JVM的空间担保分配机制可能会触发3.2、3.3和3.4发生,即触发一次Full GC。

    空间担保分配是指在发生Minor GC之前,虚拟机会检查老年代最大可用的连续空间是否大于新生代所有对象的总空间。

    如果大于,则此次Minor GC是安全的。

    如果小于,则虚拟机会查看HandlePromotionFailure设置值是否允许担保失败。如果HandlePromotionFailure=true,那么会继续检查老年代最大可用连续空间是否大于历次晋升到老年代的对象的平均大小,如果大于,则尝试进行一次Minor GC,但这次Minor GC依然是有风险的,失败后会重新发起一次Full gc;如果小于或者HandlePromotionFailure=false,则改为直接进行一次Full GC。

    所有才会说一次Full GC很有可能是由一次Minor GC触发的。

     

    PS:JDK8中HotSpot为什么要取消永久代

        JDK8取消了永久代,新增了一个叫元空间(Metaspace)的区域,对应的还是JVM规范中的方法区(主要存放一些class和元数据的信息)。区别在于元空间使用的并不是JVM中的内存,而是使用本地内存

        而这么做的原因大致有以下几点:

           1、字符串存在永久代中,容易出现性能问题和内存溢出。

      2、类及方法的信息等比较难确定其大小,因此对于永久代的大小指定比较困难,太小容易出现永久代溢出,太大则容易导致老年代溢出。

      3、永久代会为 GC 带来不必要的复杂度,并且回收效率偏低。

      4、Oracle 可能会将HotSpot 与 JRockit 合二为一。

     

    补充下JDK8内存模型图:

     

     

     

     

    参考:

     

    https://blog.csdn.net/antony9118/article/details/51425581(两个Survivor的意义)

    https://zhidao.baidu.com/question/1111800566588999699.html(Full GC什么时候触发)

    https://blog.csdn.net/l1394049664/article/details/81486470#%E4%BA%94%E3%80%81java8%E5%86%85%E5%AD%98%E6%A8%A1%E5%9E%8B%E5%9B%BE(JDK8内存模型图)

    https://blog.csdn.net/quinnnorris/article/details/75040538(可达性分析算法解析)

    https://segmentfault.com/a/1190000007726689(卡表是什么)

     

     

    展开全文
  • Pachinko Allocation

    2015-12-14 05:50:08
    A specific model similar to latent dirichlet allocation.
  • Allocation Tracker的使用

    2018-03-15 10:54:32
    Allocation Tracker的使用,Allocation Tracker:追踪内存分配信息,包含AS和Eclipse中的使用
  • Memory-Allocation-源码

    2021-03-13 14:54:07
    Memory-Allocation
  • allocation

    allocation

    GET /_cluster/allocation/explain

    返回集群中分片分配的解释。如分片为什么未分配,为什么分配到当前节点而不是其他节点。

    查询参数

    参数说明
    include_disk_info如果为true,则会返回磁盘使用和分片情况,默认为false。
    include_yes_decisions如果为true,则返回决策为YES的解释说明,默认为false。

    请求体

    参数说明
    index指定需要解释的索引名称,需要与shard、primary联合使用。
    shard指定要解释的分片id,需要与index、primary联合使用。
    primary如果为true,则返回指定分片的主分片解释,需要与index、shard联合使用。
    current_node指定节点id或节点名称,则只返回位于指定节点上的分片的解释,需要与index、shard、primary联合使用。

    返回信息

    字段说明
    index索引名称。
    shard分片id。
    primary是否主分片。
    current_state分片当前状态。
    unassigned_info

    分片最初未分配原因,包括具体原因、时间、以及最近分配状态。

    cluster_infoinclude_disk_info为true时返回,包括节点信息、分片大小、分片路径。
    can_allocate是否可分配分片。
    allocate_explanation分配说明。
    node_allocation_decisions

    节点分配决策,包括节点id、名称、通信地址、节点属性、节点决策、决策器信息(决策器名称、决策、说明)。

    can_remain_on_current_node是否允许分片保留在当前节点上。
    can_remain_decisions分片保留决策信息(决策器名称、决策、说明)。
    can_move_to_other_node是否允许移动到其他节点上。
    move_explanation移动说明。
    can_rebalance_cluster是否允许再平衡。
    can_rebalance_cluster_decisions再平衡决策信息(决策器名称、决策、说明)。
    can_rebalance_to_other_node是否允许再平衡到其他节点。
    rebalance_explanation再平衡说明。

     

    展开全文
  • RAMBO Resource Allocation for Microservices
  • Allocation Rate和GC(Allocation Failure) Allocation Rate, 翻译为分配速率, 而不是分配率; 因为不是百分比,而是单位时间内分配的量; 高分配速率(High Allocation Rate) 分配速率(Allocation rate)表示单位时间...

                        Allocation Rate和GC(Allocation Failure)


    Allocation Rate, 翻译为分配速率, 而不是分配率; 因为不是百分比,而是单位时间内分配的量;

    高分配速率(High Allocation Rate)

    分配速率(Allocation rate)表示单位时间内分配的内存量。通常使用 MB/sec作为单位, 也可以使用 PB/year 等。

    分配速率过高就会严重影响程序的性能。在JVM中会导致巨大的GC开销。

    如何测量分配速率?

    指定JVM参数: -XX:+PrintGCDetails -XX:+PrintGCTimeStamps , 通过GC日志来计算分配速率. GC日志如下所示:

    0.291: [GC (Allocation Failure) 
    		[PSYoungGen: 33280K->5088K(38400K)] 
    		33280K->24360K(125952K), 0.0365286 secs] 
    	[Times: user=0.11 sys=0.02, real=0.04 secs] 
    0.446: [GC (Allocation Failure) 
    		[PSYoungGen: 38368K->5120K(71680K)] 
    		57640K->46240K(159232K), 0.0456796 secs] 
    	[Times: user=0.15 sys=0.02, real=0.04 secs] 
    0.829: [GC (Allocation Failure) 
    		[PSYoungGen: 71680K->5120K(71680K)] 
    		112800K->81912K(159232K), 0.0861795 secs] 
    	[Times: user=0.23 sys=0.03, real=0.09 secs]

    计算 上一次垃圾收集之后,与下一次GC开始之前的年轻代使用量, 两者的差值除以时间,就是分配速率。 通过上面的日志, 可以计算出以下信息:

    1. JVM启动之后 291ms, 共创建了 33,280 KB 的对象。 第一次 Minor GC(小型GC) 完成后, 年轻代中还有 5,088 KB 的对象存活。
    2. 在启动之后 446 ms, 年轻代的使用量增加到 38,368 KB, 触发第二次GC, 完成后年轻代的使用量减少到 5,120 KB
    3. 在启动之后 829 ms, 年轻代的使用量为 71,680 KB, GC后变为 5,120 KB

    可以通过年轻代的使用量来计算分配速率, 如下表所示:

    EventTimeYoung beforeYoung afterAllocated duringAllocation rate
    1st GC291ms33,280KB5,088KB33,280KB114MB/sec
    2nd GC446ms38,368KB5,120KB33,280KB215MB/sec
    3rd GC829ms71,680KB5,120KB66,560KB174MB/sec
    Total829msN/AN/A133,120KB161MB/sec

    通过这些信息可以知道, 在测量期间, 该程序的内存分配速率为 161 MB/sec

    分配速率的意义

    分配速率的变化,会增加或降低GC暂停的频率, 从而影响吞吐量。 但只有年轻代的 minor GC 受分配速率的影响, 老年代GC的频率和持续时间不受 分配速率(allocation rate)的直接影响, 而是受到 提升速率(promotion rate)的影响。
    在得出 “Eden区越大越好” 这个结论前, 我们注意到, 分配速率可能会,也可能不会影响程序的实际吞吐量。 吞吐量和分配速率有一定关系, 因为分配速率会影响 minor GC 暂停, 但对于总体吞吐量的影响, 还要考虑 Major GC(大型GC)暂停, 而且吞吐量的单位不是 MB/秒, 而是系统所处理的业务量。

    高分配速率对JVM的影响

    首先,我们应该检查程序的吞吐量是否降低。如果创建了过多的临时对象, minor GC的次数就会增加。如果并发较大, 则GC可能会严重影响吞吐量。
     

    解决方案

    在某些情况下,只要增加年轻代的大小, 即可降低分配速率过高所造成的影响。增加年轻代空间并不会降低分配速率, 但是会减少GC的频率。如果每次GC后只有少量对象存活, minor GC 的暂停时间就不会明显增加。
     

    过早提升(Premature Promotion)

    提升速率(promotion rate), 用于衡量单位时间内从年轻代提升到老年代的数据量。一般使用 MB/sec 作为单位, 和分配速率类似。

    JVM会将长时间存活的对象从年轻代提升到老年代。根据分代假设, 可能存在一种情况, 老年代中不仅有存活时间长的对象,也可能有存活时间短的对象。这就是过早提升:对象存活时间还不够长的时候就被提升到了老年代。

    major GC 不是为频繁回收而设计的, 但 major GC 现在也要清理这些生命短暂的对象, 就会导致GC暂停时间过长。这会严重影响系统的吞吐量。

    如何测量提升速率

    可以指定JVM参数 -XX:+PrintGCDetails -XX:+PrintGCTimeStamps , 通过GC日志来测量提升速率. JVM记录的GC暂停信息如下所示:

    0.291: [GC (Allocation Failure) 
    		[PSYoungGen: 33280K->5088K(38400K)] 
    		33280K->24360K(125952K), 0.0365286 secs] 
    	[Times: user=0.11 sys=0.02, real=0.04 secs] 
    0.446: [GC (Allocation Failure) 
    		[PSYoungGen: 38368K->5120K(71680K)] 
    		57640K->46240K(159232K), 0.0456796 secs] 
    	[Times: user=0.15 sys=0.02, real=0.04 secs] 
    0.829: [GC (Allocation Failure) 
    		[PSYoungGen: 71680K->5120K(71680K)] 
    		112800K->81912K(159232K), 0.0861795 secs] 
    	[Times: user=0.23 sys=0.03, real=0.09 secs]

    从上面的日志可以得知: GC之前和之后的 年轻代使用量以及堆内存使用量。这样就可以通过差值算出老年代的使用量。GC日志中的信息可以表述为:

    EventTimeYoung decreasedTotal decreasedPromotedPromotion rate
    (事件)(耗时)(年轻代减少)(整个堆内存减少)(提升量)(提升速率)
    1st GC291ms28,192K8,920K19,272K66.2 MB/sec
    2nd GC446ms33,248K11,400K21,848K140.95 MB/sec
    3rd GC829ms66,560K30,888K35,672K93.14 MB/sec
    Total829ms  76,792K92.63 MB/sec

    根据这些信息, 就可以计算出观测周期内的提升速率。平均提升速率为 92 MB/秒, 峰值为 140.95 MB/秒

    请注意, 只能根据 minor GC 计算提升速率。 Full GC 的日志不能用于计算提升速率, 因为 major GC 会清理掉老年代中的一部分对象。

    提升速率的意义

    和分配速率一样, 提升速率也会影响GC暂停的频率。但分配速率主要影响 minor GC, 而提升速率则影响 major GC 的频率。有大量的对象提升,自然很快将老年代填满。 老年代填充的越快, 则 major GC 事件的频率就会越高。
    此前说过, full GC 通常需要更多的时间, 因为需要处理更多的对象, 还要执行碎片整理等额外的复杂过程。

    过早提升的影响

    一般来说,过早提升的症状表现为以下形式:

    1. 短时间内频繁地执行 full GC。
    2. 每次 full GC 后老年代的使用率都很低, 在10-20%或以下。
    3. 提升速率接近于分配速率。

       

    解决方案

    简单来说, 要解决这类问题, 需要让年轻代存放得下暂存的数据。是增加年轻代的大小, 设置JVM启动参数, 类似这样: -Xmx64m -XX:NewSize=32m, 程序在执行时, Full GC 的次数自然会减少很多, 只会对 minor GC的持续时间产生影响。

    项目GC日志一直打印出Allocation Failure的日志,以其中一行为例来解读下日志信息:

    [GC (Allocation Failure) [ParNew: 367523K->1293K(410432K), 0.0023988 secs] 
    522739K->156516K(1322496K), 0.0025301 secs] [Times: user=0.04 sys=0.00, real=0.01 secs]

    GC:表明进行了一次垃圾回收,前面没有Full修饰,表明这是一次Minor GC ,注意它不表示只GC新生代,并且现有的不管是新生代还是老年代都会STW(stop-the-word)。

    Allocation Failure:表明本次引起GC的原因是因为在年轻代中没有足够的空间能够存储新的数据了。

    ParNew:表明本次GC发生在年轻代并且使用的是ParNew垃圾收集器。ParNew是一个Serial收集器的多线程版本,会使用多个CPU和线程完成垃圾收集工作(默认使用的线程数和CPU数相同,可以使用-XX:ParallelGCThreads参数限制)。该收集器采用复制算法回收内存,期间会停止其他工作线程,即Stop The World。

    367523K->1293K(410432K):单位是KB,三个参数分别为:GC前该内存区域(这里是年轻代)使用容量,GC后该内存区域使用容量,该内存区域总容量。

    0.0023988 secs: 该内存区域GC耗时,单位是秒

    522739K->156516K(1322496K):三个参数分别为:堆区垃圾回收前的大小,堆区垃圾回收后的大小,堆区总大小。

    0.0025301 secs:该内存区域GC耗时,单位是秒

    [Times: user=0.04 sys=0.00, real=0.01 secs]

    real:指的是操作从开始到结束所经过的墙钟时间(WallClock Time)
    user:指的是用户态消耗的CPU时间;
    sys:指的是内核态消耗的CPU时间。
    墙钟时间包括各种非运算的等待耗时,例如等待磁盘I/O、等待线程阻塞,而CPU时间不包括这些耗时,但当系统有多CPU或者多核的话,多线程操作会叠加这些CPU时间,所以看到user或sys时间超过real时间是完全正常的。
    user + sys 就是CPU花费的实际时间,注意这个值统计了所有CPU上的时间,如果进程工作在多线程的环境下,叠加了多线程的时间,这个值是会超出 real 所记录的值的,即 user + sys >= real 。
    多次real time时间大于usr time + sys time,表明可能有两个问题,一个是IO操作密集,另一个是cpu(分配)的额度不够。

    分析下可以得出结论:

        该次GC新生代减少了367523-1293=366239K

        Heap区总共减少了522739-156516=366223K

        366239 – 366223 =16K,说明该次共有16K内存从年轻代移到了老年代,可以看出来数量并不多,说明都是生命周期短的对象,只是这种对象有很多。

        我们需要的是尽量避免Full GC的发生,让对象尽可能的在年轻代就回收掉,所以这里可以稍微增加一点年轻代的大小,让那17K的数据也保存在年轻代中。

    解决方式:直接修改配置参数 -Xmn4g  (这里需要根据需求来设置)

    有时候,增加新生代堆内存并不能解决办法。
    当minor GC 的频率太高了,这说明创建了大量的对象。另外, 如果年轻代在 GC 之后的使用量又很低, 也没有 full GC 发生。 这表明, GC对吞吐量造成了严重的影响。
    可以通过分配分析其找出大部分垃圾产生的位置,对代码处理对象进行优化。
    刚巧今天遇到一个线上bug:
    今天项目一直在报full GC,是结算时,内存存入了大量的trade数据,现在新建一个settlementTrade对象,只存必要的字段,然后然后将--xx:xmx 和--xx:xms 从10G调整为16G,新生代xmn不变,他准备上线,我等下瞄瞄他优化后的结果,循环full gc,每次都得stw, 严重影响了吞吐量.
    系统内存存入的数据量变少, 内存也扩大。

    展开全文
  • Latent Dirichlet Allocation.pdf
  • QoE and Energy Aware Resource Allocation in Small Cell Networks with Power Selection, Load Management and Channel Allocation
  • Note Taker Allocation-开源

    2021-07-14 20:02:17
    Note Taker Allocation - 一种为残疾学生分配笔记者的系统,将笔记者的可用性与学生时间表相匹配。
  • Channel Allocation

    2017-08-04 11:18:51
    Channel Allocation Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other) Total Submission(s) : 36 Accepted Submission(s) : 17 Problem Description When a radio

    Channel Allocation

    Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 20000/10000K (Java/Other)
    Total Submission(s) : 36   Accepted Submission(s) : 17
    Problem Description
    When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels. 

    Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.
     

    Input
    The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,...,I and J. A network with zero repeaters indicates the end of input. <br> <br>Following the number of repeaters is a list of adjacency relationships. Each line has the form: <br> <br>A:BCDH <br> <br>which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form <br> <br>A: <br> <br>The repeaters are listed in alphabetical order. <br> <br>Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross. <br>
     

    Output
    For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.
     

    Sample Input
      
    2 A: B: 4 A:BC B:ACD C:ABD D:BC 4 A:BCD B:ACD C:ABD D:ABC 0
     

    Sample Output
      
    1 channel needed. 3 channels needed. 4 channels needed.
         这是一个我给单词绕到了的题,英文这个东西真是博大精深,一词多义啊。读题的时候,什么广播、中继器的,都不认识,查单词出来的,但是另一个词 channel (咋一看很像香奈儿啊,当然我也不会傻到以为这是香奈儿的意思),查出来词义是这个样子的:  n. 通道;频道;海峡    vt. 引导,开导;形成河道    我一看通道,以为这是电缆线一类的意思,毕竟传输信号嘛,那就是相邻的不能接入同一个通道里面,但是他也没说怎么接通道啊,然后翻来覆去想不到题意是个啥意思,实在没办法去题解看题意,人家的解释是:频道。哪里接过来意思就像是给每个中继器染色,相邻的不能同一个颜色,这样就明白的多了。明白了题意就好做的多了,深搜回溯,求最小值。输出的地方也要注意啊,名词单复数加不加 -s的看不看的到!!!

    代码如下:
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    using namespace std;
    int mapp[30][30];
    int vis[30];//点 i  颜色
    int n,minn,flag;
    int ok(int x,int c)//判断 x 是否能 染 c
    {
        for(int i=1;i<=n;i++)
        {
            if(mapp[x][i]==1 && vis[i]==c)
                return 0;
        }
        return 1;
    }
    void ioan(int x,int color)
    {
        if(x>n)
        {
            flag=1;
            if(minn>color)
                minn=color;
            return ;
        }
        //int f=0;
        for(int i=1;i<=color;i++)//在 x 上染色
        {
            if(ok(x,i))
            {
                //f=1;
                vis[x]=i;
                ioan(x+1,color);
                if(flag==1)
                    return ;
                vis[x]=0;
            }
        }
        {
            vis[x]=color+1;
            ioan(x+1,color+1);
        }
    }
    int main()
    {
        //freopen("D:\\aaa.txt","r",stdin);
        string s;
        int l,x,y;
        while(cin>>n&&n)
        {
            minn=9999;
            flag=0;
            memset(mapp,0,sizeof(mapp));
            memset(vis,0,sizeof(vis));
            for(int i=0;i<n;i++)
            {
                cin>>s;
                l=s.size();
                x=s[0]-'A'+1;
                for(int i=2;i<l;i++)
                {
                    y=s[i]-'A'+1;
                    mapp[x][y]=1;
                    mapp[y][x]=1;
                }
            }
    
            ioan(1,1);
            if(minn==1)
                cout<<minn<<" channel needed."<<endl;
            if(minn!=1)
                cout<<minn<<" channels needed."<<endl;
        }
        return 0;
    }
    






    展开全文
  • pcba_allocation-源码

    2021-04-04 11:39:18
    pcba_allocation 由Ken Ken创建 该工具可基于SCR在不同站点之间进行PCBA分配。 它使用基于中央准则的排名逻辑来确定待办事项的优先级和准则。
  • The Allocation Instrumenter is a Java agent written using the java.lang.instrument API and ASM. Each allocation in your Java program is instrumented; a user-defined callback is invoked on each ...
  • ifpe-time-allocation-源码

    2021-03-16 23:30:04
    ifpe-time-allocation
  • Allocation Tracker(Android Studio)工具使用说明。 Allocation Tracker(AS)工具比Allocation Tracker(Eclipse)工具强大的地方是更炫酷,更清晰,但是能做的事情都是一样的。
  • Allocation Failure

    2015-07-16 18:08:00
    up vote 8 down vote accepted "Allocation Failure" is a cause of GC cycle to kick..."Allocation Failure" means what no more space left in Eden to allocate object. So, it is normal cause of young GC....
  • Power Allocation in NOMA_NOMAPOWER_please8nm_NOMAallocation_noma_powerallocation_源码.rar
  • asset_allocation_case.rar

    2020-09-18 20:05:42
    asset allocation case study MATLAB code 配合博文【FinE】Asset Allocation Case Study使用
  • Memory allocation详解

    千次阅读 2019-09-29 14:56:40
    Memory allocation详解 在C++中,我们可以很方便的动态分配内存,那么动态分配后的初始化顺序和释放内存时候的析构顺序究竟是怎样的呢,我们来回顾一下 首先我们想看一个案例: 首先假设我们有一个User类 class User...
  • Allocation Removal by Partial Evaluation in a Tracing JITCarl Friedrich Bolza Antonio Cunia Maciej Fijałkowskib Michael LeuschelaSamuele Pedronic Armin Rigoaa Heinrich-Heine-Universität Düsseldorf,...
  • Rate allocation games in multiuser multimedia communications
  • flutter和c/c++交互的allocation方法,具体的使用方法,自行查找
  • Approximately Truthful Mechanisms for Radio Spectrum Allocation
  • Learning Probabilistic Kernel from Latent Dirichlet Allocation
  • Joint Offloading and Resource Allocation_globecom
  • The paper addresses the issue of reconfigurability allocation for satellite attitude control system with constraints and with considering the lack of reconfigurability statistics data and the ...
  • model and rate allocation theory in the wavelet domain is applied. Under this framework, a novel logo watermarking algorithm using reversible discrete wavelet transform is proposed. Based on multi-...
  • allocation of power using NOMA technology
  • 为什么研究Dynamic Allocation的源码? 在线上任务执行的过程中,有些任务占用着Yarn资源却并行度极低,比如申请了100核cpu(现象持续时间超过了executor idle time),但那个stage只有9个running task。 最关键的是,...
  • 内存分配源代码MemoryAllocation

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 119,340
精华内容 47,736
关键字:

allocation