一网打尽消息队列在大型分布式系统中的实战精髓

2024-03-10 14:08
文章标签 实战 队列 消息 分布式系统 大型 一网打尽 精髓

本文主要是介绍一网打尽消息队列在大型分布式系统中的实战精髓，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

640?wx_fmt=gif

 

本文大纲：

  1. 消息队列概述

  2. 消息队列应用场景

  3. 消息中间件示例（电商，日志系统）

  4. JMS消息服务

  5. 常用消息队列

  6. 参考资料

一、消息队列概述

 

消息队列中间件是分布式系统中重要的组件，主要解决应用耦合，异步消息，流量削锋等问题，以及实现高性能，高可用，可伸缩和最终一致性架构，是大型分布式系统不可缺少的中间件。

 

目前在生产环境，使用较多的消息队列有ActiveMQ，RabbitMQ，ZeroMQ，Kafka，MetaMQ，RocketMQ等。

 

二、消息队列应用场景

 

以下介绍消息队列在实际应用中常用的四个使用场景：异步处理，应用解耦，流量削锋和消息通讯。

 

1异步处理

 

场景说明：用户注册后，需要发注册邮件和注册短信。传统的做法有两种：

 

串行方式：将注册信息写入数据库成功后，发送注册邮件，再发送注册短信。以上三个任务全部完成后，返回给客户端。

 640?wx_fmt=png

 

并行方式：将注册信息写入数据库成功后，发送注册邮件的同时，发送注册短信。以上三个任务完成后，返回给客户端。与串行的差别是，并行的方式可以提高处理的时间。

 640?wx_fmt=png

 

假设三个业务节点每个使用50毫秒钟，不考虑网络等其他开销，则串行方式的时间是150毫秒，并行的时间可能是100毫秒。

 

因为CPU在单位时间内处理的请求数是一定的，假设CPU1秒内吞吐量是100次。则串行方式1秒内CPU可处理的请求量是7次（1000/150）。并行方式处理的请求量是10次（1000/100）。

 

小结：如以上案例描述，传统的方式系统的性能（并发量，吞吐量，响应时间）会有瓶颈。如何解决这个问题呢？

 

引入消息队列，将不是必须的业务逻辑，异步处理改造后的架构如下：

 

640?wx_fmt=png

 

按照以上约定，用户的响应时间相当于是注册信息写入数据库的时间，也就是50毫秒。注册邮件，发送短信写入消息队列后，直接返回，因此写入消息队列的速度很快，基本可以忽略，因此用户的响应时间可能是50毫秒。因此架构改变后，系统的吞吐量提高到每秒20 QPS。比串行提高了3倍，比并行提高了两倍。

 

2应用解耦

 

场景说明：用户下单后，订单系统需要通知库存系统。传统的做法是，订单系统调用库存系统的接口。如下图：

 

640?wx_fmt=png

 

传统模式的缺点：

 

  • 假如库存系统无法访问，则订单减库存将失败，从而导致订单失败；

  • 订单系统与库存系统耦合；

 

如何解决以上问题呢？引入应用消息队列后的方案，如下图：

 

640?wx_fmt=png

 

  • 订单系统：用户下单后，订单系统完成持久化处理，将消息写入消息队列，返回用户订单下单成功。

  • 库存系统：订阅下单的消息，采用拉/推的方式，获取下单信息，库存系统根据下单信息，进行库存操作。

  • 假如：在下单时库存系统不能正常使用。也不影响正常下单，因为下单后，订单系统写入消息队列就不再关心其他的后续操作了。实现订单系统与库存系统的应用解耦。

 

3流量削锋

 

流量削锋也是消息队列中的常用场景，一般在秒杀或团抢活动中使用广泛。

 

应用场景：秒杀活动，一般会因为流量过大，导致流量暴增，应用挂掉。为解决这个问题，一般需要在应用前端加入消息队列。

 

  1. 可以控制活动的人数；

  2. 可以缓解短时间内高流量压垮应用；

 640?wx_fmt=png

 

用户的请求，服务器接收后，首先写入消息队列。假如消息队列长度超过最大数量，则直接抛弃用户请求或跳转到错误页面；

 

秒杀业务根据消息队列中的请求信息，再做后续处理。

 

4日志处理

 

日志处理是指将消息队列用在日志处理中，比如Kafka的应用，解决大量日志传输的问题。架构简化如下：

 

640?wx_fmt=png

 

  • 日志采集客户端，负责日志数据采集，定时写受写入Kafka队列；

  • Kafka消息队列，负责日志数据的接收，存储和转发；

  • 日志处理应用：订阅并消费kafka队列中的日志数据；

 

以下是新浪kafka日志处理应用案例：

转自（http://cloud.51cto.com/art/201507/484338.htm）

 

640?wx_fmt=png

 

  1. Kafka：接收用户日志的消息队列。

  2. Logstash：做日志解析，统一成JSON输出给Elasticsearch。

  3. Elasticsearch：实时日志分析服务的核心技术，一个schemaless，实时的数据存储服务，通过index组织数据，兼具强大的搜索和统计功能。

  4. Kibana：基于Elasticsearch的数据可视化组件，超强的数据可视化能力是众多公司选择ELK stack的重要原因。

 

5消息通讯

 

消息通讯是指，消息队列一般都内置了高效的通信机制，因此也可以用在纯的消息通讯。比如实现点对点消息队列，或者聊天室等。

 

点对点通讯：

 

640?wx_fmt=png

 

客户端A和客户端B使用同一队列，进行消息通讯。

 

聊天室通讯：

 

640?wx_fmt=png

 

客户端A，客户端B，客户端N订阅同一主题，进行消息发布和接收。实现类似聊天室效果。

 

以上实际是消息队列的两种消息模式，点对点或发布订阅模式。模型为示意图，供参考。

 

三、消息中间件示例

 

1电商系统

 

640?wx_fmt=jpeg

 

消息队列采用高可用，可持久化的消息中间件。比如ActiveMQ，RabbitMQ，RocketMQ。

 

（1）应用将主干逻辑处理完成后，写入消息队列。消息发送是否成功可以开启消息的确认模式。（消息队列返回消息接收成功状态后，应用再返回，这样保障消息的完整性）

 

（2）扩展流程（发短信，配送处理）订阅队列消息。采用推或拉的方式获取消息并处理。

 

（3）消息将应用解耦的同时，带来了数据一致性问题，可以采用最终一致性方式解决。比如主数据写入数据库，扩展应用根据消息队列，并结合数据库方式实现基于消息队列的后续处理。

 

2日志收集系统

 

640?wx_fmt=jpeg

 

分为Zookeeper注册中心，日志收集客户端，Kafka集群和Storm集群（OtherApp）四部分组成。

 

  • Zookeeper注册中心，提出负载均衡和地址查找服务；

  • 日志收集客户端，用于采集应用系统的日志，并将数据推送到kafka队列；

  • Kafka集群：接收，路由，存储，转发等消息处理；

  • Storm集群：与OtherApp处于同一级别，采用拉的方式消费队列中的数据；

 

四、JMS消息服务

 

讲消息队列就不得不提JMS 。JMS（JAVA Message Service,java消息服务）API是一个消息服务的标准/规范，允许应用程序组件基于JavaEE平台创建、发送、接收和读取消息。它使分布式通信耦合度更低，消息服务更加可靠以及异步性。

 

在EJB架构中，有消息bean可以无缝的与JM消息服务集成。在J2EE架构模式中，有消息服务者模式，用于实现消息与应用直接的解耦。

 

1消息模型

 

在JMS标准中，有两种消息模型P2P（Point to Point）,Publish/Subscribe(Pub/Sub)。

 

P2P模式

 

640?wx_fmt=png

 

P2P模式包含三个角色：消息队列（Queue），发送者(Sender)，接收者(Receiver)。每个消息都被发送到一个特定的队列，接收者从队列中获取消息。队列保留着消息，直到他们被消费或超时。

 

P2P的特点：

 

  • 每个消息只有一个消费者（Consumer）(即一旦被消费，消息就不再在消息队列中)

  • 发送者和接收者之间在时间上没有依赖性，也就是说当发送者发送了消息之后，不管接收者有没有正在运行，它不会影响到消息被发送到队列

  • 接收者在成功接收消息之后需向队列应答成功

 

如果希望发送的每个消息都会被成功处理的话，那么需要P2P模式。

 

Pub/sub模式

 

640?wx_fmt=png

 

包含三个角色主题（Topic），发布者（Publisher），订阅者（Subscriber） 。多个发布者将消息发送到Topic,系统将这些消息传递给多个订阅者。

 

Pub/Sub的特点：

 

  • 每个消息可以有多个消费者。

  • 发布者和订阅者之间有时间上的依赖性。针对某个主题（Topic）的订阅者，它必须创建一个订阅者之后，才能消费发布者的消息。

  • 为了消费消息，订阅者必须保持运行的状态。

 

为了缓和这样严格的时间相关性，JMS允许订阅者创建一个可持久化的订阅。这样，即使订阅者没有被激活（运行），它也能接收到发布者的消息。

 

如果希望发送的消息可以不被做任何处理、或者只被一个消息者处理、或者可以被多个消费者处理的话，那么可以采用Pub/Sub模型。

 

2消息消费

 

在JMS中，消息的产生和消费都是异步的。对于消费来说，JMS的消息者可以通过两种方式来消费消息。

 

（1）同步

 

订阅者或接收者通过receive方法来接收消息，receive方法在接收到消息之前（或超时之前）将一直阻塞；

 

（2）异步

 

订阅者或接收者可以注册为一个消息监听器。当消息到达之后，系统自动调用监听器的onMessage方法。

 

JNDI：Java命名和目录接口,是一种标准的Java命名系统接口。可以在网络上查找和访问服务。通过指定一个资源名称，该名称对应于数据库或命名服务中的一个记录，同时返回资源连接建立所必须的信息。

 

JNDI在JMS中起到查找和访问发送目标或消息来源的作用。

 

3JMS编程模型

 

ConnectionFactory

 

创建Connection对象的工厂，针对两种不同的jms消息模型，分别有QueueConnectionFactory和TopicConnectionFactory两种。可以通过JNDI来查找ConnectionFactory对象。

 

Destination

 

Destination的意思是消息生产者的消息发送目标或者说消息消费者的消息来源。对于消息生产者来说，它的Destination是某个队列（Queue）或某个主题（Topic）;对于消息消费者来说，它的Destination也是某个队列或主题（即消息来源）。

 

所以，Destination实际上就是两种类型的对象：Queue、Topic可以通过JNDI来查找Destination。

 

Connection

 

Connection表示在客户端和JMS系统之间建立的链接（对TCP/IP socket的包装）。Connection可以产生一个或多个Session。跟ConnectionFactory一样，Connection也有两种类型：QueueConnection和TopicConnection。

 

Session

 

Session是操作消息的接口。可以通过session创建生产者、消费者、消息等。Session提供了事务的功能。当需要使用session发送/接收多个消息时，可以将这些发送/接收动作放到一个事务中。同样，也分QueueSession和TopicSession。

 

消息的生产者

 

消息生产者由Session创建，并用于将消息发送到Destination。同样，消息生产者分两种类型：QueueSender和TopicPublisher。可以调用消息生产者的方法（send或publish方法）发送消息。

 

消息消费者

 

消息消费者由Session创建，用于接收被发送到Destination的消息。两种类型：QueueReceiver和TopicSubscriber。可分别通过session的createReceiver(Queue)或createSubscriber(Topic)来创建。当然，也可以session的creatDurableSubscriber方法来创建持久化的订阅者。

 

MessageListener

 

消息监听器。如果注册了消息监听器，一旦消息到达，将自动调用监听器的onMessage方法。EJB中的MDB（Message-Driven Bean）就是一种MessageListener。

 

深入学习JMS对掌握JAVA架构，EJB架构有很好的帮助，消息中间件也是大型分布式系统必须的组件。这里主要做全局性介绍，具体的深入需要大家学习，实践，总结，领会。

 

五、常用消息队列

 

一般商用的容器，比如WebLogic，JBoss，都支持JMS标准，开发上很方便。但免费的比如Tomcat，Jetty等则需要使用第三方的消息中间件。本部分内容介绍常用的消息中间件（Active MQ,Rabbit MQ，Zero MQ,Kafka）以及他们的特点。

 

1ActiveMQ

 

ActiveMQ 是Apache出品，最流行的，能力强劲的开源消息总线。ActiveMQ 是一个完全支持JMS1.1和J2EE 1.4规范的 JMS Provider实现，尽管JMS规范出台已经是很久的事情了，但是JMS在当今的J2EE应用中间仍然扮演着特殊的地位。

 

ActiveMQ特性如下：

 

  1. 多种语言和协议编写客户端。语言: Java,C,C++,C#,Ruby,Perl,Python,PHP。应用协议：OpenWire,Stomp REST,WS Notification,XMPP,AMQP

  2. 完全支持JMS1.1和J2EE 1.4规范 （持久化，XA消息，事务)

  3. 对Spring的支持，ActiveMQ可以很容易内嵌到使用Spring的系统里面去，而且也支持Spring2.0的特性

  4. 通过了常见J2EE服务器（如 Geronimo,JBoss 4,GlassFish,WebLogic)的测试，其中通过JCA 1.5 resource adaptors的配置，可以让ActiveMQ可以自动的部署到任何兼容J2EE 1.4 商业服务器上

  5. 支持多种传送协议：in-VM,TCP,SSL,NIO,UDP,JGroups,JXTA

  6. 支持通过JDBC和journal提供高速的消息持久化

  7. 从设计上保证了高性能的集群，客户端-服务器，点对点

  8. 支持Ajax

  9. 支持与Axis的整合

  10. 可以很容易得调用内嵌JMS provider，进行测试

 

2RabbitMQ

 

RabbitMQ是流行的开源消息队列系统，用erlang语言开发。RabbitMQ是AMQP（高级消息队列协议）的标准实现。支持多种客户端，如：Python、Ruby、.NET、Java、JMS、C、PHP、ActionScript、XMPP、STOMP等，支持AJAX，持久化。用于在分布式系统中存储转发消息，在易用性、扩展性、高可用性等方面表现不俗。

 

结构图如下：

 

640?wx_fmt=png

 

几个重要概念：

 

  • Broker：简单来说就是消息队列服务器实体。

  • Exchange：消息交换机，它指定消息按什么规则，路由到哪个队列。

  • Queue：消息队列载体，每个消息都会被投入到一个或多个队列。

  • Binding：绑定，它的作用就是把exchange和queue按照路由规则绑定起来。

  • Routing Key：路由关键字，exchange根据这个关键字进行消息投递。

  • vhost：虚拟主机，一个broker里可以开设多个vhost，用作不同用户的权限分离。

  • producer：消息生产者，就是投递消息的程序。

  • consumer：消息消费者，就是接受消息的程序。

  • channel：消息通道，在客户端的每个连接里，可建立多个channel，每个channel代表一个会话任务。

 

消息队列的使用过程，如下：

 

（1）客户端连接到消息队列服务器，打开一个channel。

（2）客户端声明一个exchange，并设置相关属性。

（3）客户端声明一个queue，并设置相关属性。

（4）客户端使用routing key，在exchange和queue之间建立好绑定关系。

（5）客户端投递消息到exchange。

 

exchange接收到消息后，就根据消息的key和已经设置的binding，进行消息路由，将消息投递到一个或多个队列里。

 

3ZeroMQ

 

号称史上最快的消息队列，它实际类似于Socket的一系列接口，他跟Socket的区别是：普通的socket是端到端的（1:1的关系），而ZMQ却是可以N：M 的关系，人们对BSD套接字的了解较多的是点对点的连接，点对点连接需要显式地建立连接、销毁连接、选择协议（TCP/UDP）和处理错误等，而ZMQ屏蔽了这些细节，让你的网络编程更为简单。ZMQ用于node与node间的通信，node可以是主机或者是进程。

 

引用官方的说法：“ZMQ(以下ZeroMQ简称ZMQ)是一个简单好用的传输层，像框架一样的一个socket library，他使得Socket编程更加简单、简洁和性能更高。是一个消息处理队列库，可在多个线程、内核和主机盒之间弹性伸缩。ZMQ的明确目标是“成为标准网络协议栈的一部分，之后进入Linux内核”。现在还未看到它们的成功。但是，它无疑是极具前景的、并且是人们更加需要的“传统”BSD套接字之上的一 层封装。ZMQ让编写高性能网络应用程序极为简单和有趣。”

 

特点是：

  • 高性能，非持久化；

  • 跨平台：支持Linux、Windows、OS X等。

  • 多语言支持；C、C++、Java、.NET、Python等30多种开发语言。

  • 可单独部署或集成到应用中使用；

  • 可作为Socket通信库使用。

 

与RabbitMQ相比，ZMQ并不像是一个传统意义上的消息队列服务器，事实上，它也根本不是一个服务器，更像一个底层的网络通讯库，在Socket API之上做了一层封装，将网络通讯、进程通讯和线程通讯抽象为统一的API接口。支持“Request-Reply “，”Publisher-Subscriber“，”Parallel Pipeline”三种基本模型和扩展模型。

 

ZeroMQ高性能设计要点：

 

（1）无锁的队列模型

 

对于跨线程间的交互（用户端和session）之间的数据交换通道pipe，采用无锁的队列算法CAS；在pipe两端注册有异步事件，在读或者写消息到pipe的时，会自动触发读写事件。

 

（2）批量处理的算法

 

对于传统的消息处理，每个消息在发送和接收的时候，都需要系统的调用，这样对于大量的消息，系统的开销比较大，zeroMQ对于批量的消息，进行了适应性的优化，可以批量的接收和发送消息。

 

（3）多核下的线程绑定，无须CPU切换

 

区别于传统的多线程并发模式，信号量或者临界区， zeroMQ充分利用多核的优势，每个核绑定运行一个工作者线程，避免多线程之间的CPU切换开销。

 

4Kafka

 

Kafka是一种高吞吐量的分布式发布订阅消息系统，它可以处理消费者规模的网站中的所有动作流数据。这种动作（网页浏览，搜索和其他用户的行动）是在现代网络上的许多社会功能的一个关键因素。这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。对于像Hadoop的一样的日志数据和离线分析系统，但又要求实时处理的限制，这是一个可行的解决方案。Kafka的目的是通过Hadoop的并行加载机制来统一线上和离线的消息处理，也是为了通过集群机来提供实时的消费。

 

Kafka是一种高吞吐量的分布式发布订阅消息系统，有如下特性：

 

  1. 通过O(1)的磁盘数据结构提供消息的持久化，这种结构对于即使数以TB的消息存储也能够保持长时间的稳定性能。（文件追加的方式写入数据，过期的数据定期删除）

  2. 高吞吐量：即使是非常普通的硬件Kafka也可以支持每秒数百万的消息。

  3. 支持通过Kafka服务器和消费机集群来分区消息。

  4. 支持Hadoop并行数据加载。

 

Kafka相关概念：

 

  • Broker

 

Kafka集群包含一个或多个服务器，这种服务器被称为broker[5]。

 

  • Topic

 

每条发布到Kafka集群的消息都有一个类别，这个类别被称为Topic。（物理上不同Topic的消息分开存储，逻辑上一个Topic的消息虽然保存于一个或多个broker上但用户只需指定消息的Topic即可生产或消费数据而不必关心数据存于何处）。

 

  • Partition

 

Parition是物理上的概念，每个Topic包含一个或多个Partition、。

 

  • Producer

 

负责发布消息到Kafka broker。

 

  • Consumer

 

消息消费者，向Kafka broker读取消息的客户端。

 

  • Consumer Group

 

每个Consumer属于一个特定的Consumer Group（可为每个Consumer指定group name，若不指定group name则属于默认的group）。

 

一般应用在大数据日志处理或对实时性（少量延迟），可靠性（少量丢数据）要求稍低的场景使用。

 

六、参考资料

 

以下是本次分享参考的资料和推荐大家参考的资料。

 

JMS：

  • http://blog.sina.com.cn/s/blog_3fba24680100r777.html

  • http://blog.csdn.net/jiuqiyuliang/article/details/46701559

 

RabbitMQ：

  • http://baike.baidu.com/link?url=s2cU-QgOsXan7j0AM5qxxlmruz6WEeBQXX-Bbk0O3F5jt9Qts2uYQARxQxl7CBT2SO2NF2VkzX_XZLqU-CTaPa

  • http://blog.csdn.net/sun305355024sun/article/details/41913105

 

ZeroMQ：

  • http://www.searchtb.com/2012/08/zeromq-primer.html

  • http://blog.csdn.net/yangbutao/article/details/8498790

  • http://wenku.baidu.com/link?url=yYoiZ_pYPCuUxEsGQvMMleY08bcptZvwF3IMHo2W1i-ti66YXXPpLLJBGXboddwgGBnOehHiUdslFhtz7RGZYkrtMQQ02DV5sv9JFF4LZnK

 

Kafka：

  • http://baike.baidu.com/link?url=qQXyqvPQ1MVrw9WkOGSGEfSX1NHy4unsgc4ezzJwU94SrPuVnrKf2tbm4SllVaN3ArGGxV_N5hw8JTT2-lw4QK

  • http://www.infoq.com/cn/articles/apache-kafka/

  • http://www.mincoder.com/article/3942.shtml

 

相关专题：

  • 一篇文读懂缓存在大型分布式系统中的最佳应用

 

作者介绍 侯忠好

  • 网名：ITFLY8，十年工作经验，目前从事电商系统开发，熟悉设计模式，架构模式，分布式系统设计。业余时间致力于技术总结和架构知识的传播。

 

经作者同意授权转载

来源：ITFLY8架构师之家

 

这篇关于一网打尽消息队列在大型分布式系统中的实战精髓的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/794465。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
poj 3190 优先队列+贪心

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 2431 poj 3253 优先队列的运用

poj 2431 poj 3253 优先队列的运用

poj 2431： 题意： 一条路起点为0， 终点为l。 卡车初始时在0点，并且有p升油，假设油箱无限大。 给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。 问最少加几次油可以到达终点，若不能到达，输出-1。 解析： 《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一
阅读更多...
滚雪球学Java(87)：Java事务处理：JDBC的ACID属性与实战技巧！真有两下子！

滚雪球学Java(87)：Java事务处理：JDBC的ACID属性与实战技巧！真有两下子！

咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE啦，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~ 🏆本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，助你一臂之力，带你早日登顶🚀，欢迎大家关注&&收藏！持续更新中，up！up！up！！ 环境说明：Windows 10
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
POJ2010 贪心优先队列

POJ2010 贪心优先队列

c头牛,需要选n头（奇数）；学校总共有f的资金， 每头牛分数score和学费cost，问合法招生方案中,中间分数（即排名第(n+1)/2）最高的是多少。 n头牛按照先score后cost从小到大排序； 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2