group by 语句怎么优化?

一、一个简单使用示例

我这里创建一张订单表

CREATE TABLE `order_info` (
  `id` int NOT NULL AUTO_INCREMENT COMMENT '主键',
  `order_no` int NOT NULL COMMENT '订单号',
  `goods_id` int NOT NULL DEFAULT '0' COMMENT '商品id',
  `goods_name` varchar(50) NOT NULL COMMENT '商品名称',
  `order_status` int NOT NULL DEFAULT '0' COMMENT '订单状态:1待支付,2成功支付,3支付失败,4已关闭',
  `pay_type` int NOT NULL DEFAULT '0' COMMENT '支付方式:1微信支付,2支付宝支付',
  `price` decimal(11,2) DEFAULT NULL COMMENT '订单金额',
  `pay_time` datetime DEFAULT NULL COMMENT '支付时间',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uk_order_no` (`order_no`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 ROW_FORMAT=DYNAMIC COMMENT='订单信息表';

同时也在表里插了一些数据

现在我们这里执行group by语句

select goods_name, count(*) as num
from order_info
group by goods_name

很明显,这里就可以统计出来 每件商品一共有多少订单数据!


二、group by 原理分析

2.1、explain 分析

不同的数据库版本,用explain执行的结果并不一致,同样是上面sql语句

MySQL 5.7版本

  • Extra 这个字段的Using temporary表示在执行分组的时候使用了临时表

  • Extra 这个字段的 Using filesort 表示使用了排序

MySQL 8.0版本

我们通过对比可以发现:mysql 8.0 开始 group by 默认是没有排序的了!

接下来我们来解释下,为什么在没有加索引的情况下会有临时表产生。

2.2、聊一聊 Using temporary

Using temporary表示由于排序没有走索引、使用union子查询连接查询,group_concat()count(distinct)表达式的求值等等创建了一个内部临时表。

注意这里的临时表可能是内存上的临时表,也有可能是硬盘上的临时表,理所当然基于内存的临时表的时间消耗肯定要比基于硬盘的临时表的实际消耗小。

但不是说多大临时数据都可以直接存在内存的临时表,而是当超过最大内存临时表的最大容量就是转为存入磁盘临时表

当mysql需要创建临时表时,选择内存临时表还是硬盘临时表取决于参数tmp_table_sizemax_heap_table_size,当所需临时表的容量大于两者的最小值时,mysql就会使用硬盘临时表存放数据。

用户可以在mysql的配置文件里修改该两个参数的值,两者的默认值均为16M。

mysql> show global variables like 'max_heap_table_size';
+---------------------+----------+
| Variable_name       | Value    |
+---------------------+----------+
| max_heap_table_size | 16777216 |
+---------------------+----------+
1 row in set

mysql> show global variables like 'tmp_table_size';
+----------------+----------+
| Variable_name  | Value    |
+----------------+----------+
| tmp_table_size | 16777216 |
+----------------+----------+
1 row in set

2.3、group by 是如何产生临时表的

同样以该sql分析

select goods_name, count(*) as num
from order_info
group by goods_name

这个SQL产生临时表的执行流程如下

  1. 创建内存临时表,表里面有两个字段:goods_name 和 num;

  2. 全表扫描 order_info 表,取出 goods_name = 某商品(比如围巾、耳机、茶杯等)的记录

    • 临时表没有 goods_name = 某商品的记录,直接插入,并记为 (某商品,1);
    • 临时表里有 goods_name = 某商品的记录,直接更新,把 num 值 +1
  3. 重复步骤 3 直至遍历完成,然后把结果集返回客户端。

这个流程的执行图如下:


三、group by 使用中注意的一个问题

我们来思考一个问题

select的 列 和group by的 列 不一致会报错吗?

比如

 select goods_id, goods_name, count(*) as num
 from order_info
 group by goods_id;

上面我们想根据商品id进行分组,统计每个商品的订单数量,但是我们分组只根据 goods_id分组,但在查询列的时候,既要返回goods_id,也要返回goods_name。

我们这么写因为我们知道:一样的goods_id一定有相同的 goods_name,所以就没必要写成 group by goods_id,goods_name;

但上面这种写法一定会被支持吗?未必!

我们分别以mysql5.7版本和8.0版本做下尝试。

mysql5.7版本

我们发现是可以查询的到的。

mysql8.0版本

我们在执行上面sql发现报错了,没错同样的sql在不同的mysql版本执行结果并不一样,我们看下报什么错!

出现这个错误的原因是 mysql 的 sql_mode 开启了 ONLY_FULL_GROUP_BY 模式

该模式的含义就是: 对于group by聚合操作,如果在select中的列,没有在group by中出现,那么这个sql是不合法的,因为列不在group by从句中。

这其实是一种更加严谨的做法。

就比如上面这个sql,如果存在这个商品的名称被修改过了,但是它们的id确还是一样的,那么这个时候展示的商品名称是修改前的还是修改后的呢?

那对于上面这种情况,mysql5.7版本是如何做的呢?

1.创建内存临时表,表里面有三个字段:goods_id,goods_name 和 num;

2.当我第一次这个goods_id=1对应 goods_name=面包 时,那么这个id对应goods_name就是面包,就算后面这个id对应的是火腿面包,鸡腿面包,这都不管,

只要第一个是面包,那就固定是这个名称了。这叫先到先得原则。

如果你的8.0版本不想要 ONLY_FULL_GROUP_BY 模式,那关闭就可以了。


四、group by 如何优化

group by在使用不当的时候,很容易就会产生慢SQL 问题。因为它既用到临时表,又默认用到排序。有时候还可能用到磁盘临时表。

这里总结4点优化经验

  1. 分组字段加索引

  2. order by null 不排序

  3. 尽量使用内存临时表

  4. SQL_BIG_RESULT

4.1、分组字段加索引

-- 我们给goods_id添加索引
alter table order_info add index idx_goods_id (goods_id)

然后再看下执行计划

很明显 之前的 Using temporary 和 Using filesort 都没有了,只有Using index(使用索引了)

4.2、order by null 不排序

如果需求是不用排序,我们就可以这样做。在 sql 末尾加上 order by null

select goods_id, count(*) as num
from order_info
group by goods_id
order by null

但是如果是已经走了索引,或者说8.0的版本,那都不需要加 order by null,因为上面也说了8.0默认就是不排序的了。

4.3、尽量使用内存临时表

因为上面也说了,临时表也分为内存临时表和磁盘临时表。如果数据量实在过大,大到内存临时表都不够用了,这时就转向使用磁盘临时表。

内存临时表的大小是有限制的,mysql 中 tmp_table_size 代表的就是内存临时表的大小,默认是 16M。当然你可以自定义社会中适当大一点,这就要根据实际情况来定了。

4.4、SQL_BIG_RESULT

如果数据量实在过大,大到内存临时表都不够用了,这时就转向使用磁盘临时表。

而发现不够用再转向这个过程也是很耗时的,那我们有没有一种方法,可以告诉 mysql 从一开始就使用 磁盘临时表呢?

因此,如果预估数据量比较大,我们使用SQL_BIG_RESULT 这个提示直接用磁盘临时表。

explain select sql_big_result goods_id, count(*) as num
from order_info
group by goods_id

从执行结果来看 确实已经不存在临时表了。


五、一个很有意思的优化案例

为了让效果看去明显点,我在这里在数据库中添加了100万条数据(整整插了一下午呢)。

同时说明下当前数据库版本是8.0.22

执行得sql如下:

select goods_id, count(*) as num
from order_info
where pay_time >= '2022-12-01 00:00:00' and pay_time <= '2022-12-31 23:59:59'
group by goods_id;

5.1、不加任何索引

我们发现当我们什么索引都没加执行时间是: 0.67秒

我们在执行下explain

我们发现没有走任何索引,而且有临时表存在,那我是不是考虑给goods_id 加一个索引?

5.2、仅分组字段加索引

alter table order_info add index idx_goods_id(goods_id);

我们在执行下explain

确实是走了 上面创建的idx_goods_id,索引,那查询效率是不是要起飞了?

我们在执行下上面的查询sql

执行时间是: 21.82秒!

是不是很神奇,明明我的分组字段加了索引,而且从执行计划来看确实走了索引,而且也不存在Using temporary临时表了,怎么速度反而下来了,这是为什么呢?

原因:

虽然说我们用到了idx_goods_id 索引,那我们看上图执行计划中 rows = 997982,说明啥,说明虽然走了索引,但是从扫描数据来看依然是全表扫描呢,为什么会这样?

首先group by用到索引,那就在索引树上索引数据,但是因为加了where条件,还是需要在去表里检索几乎所有的数据, 这样子,还不如直接去表里进行全表扫,这样还更快些。

所以没有索引反而更快了

5.3、查询字段和分组字段建立组合索引

那我们给 pay_time 和 goods_id建立组合索引呢?

 -- 先删除idx_goods_id索引
drop index idx_goods_id on order_info;
 -- 再新建组合索引
alter table order_info add index idx_payTime_goodsId(pay_time,goods_id);

我们在执行下explain

这次可以很明显的看到

  • Extra 这个字段的Using index 表示该查询条件确实用到了索引,而且是索引覆盖

  • Extra 这个字段的 Using temporary 表示在执行分组的时候使用了临时表

为什么会这样,其实原因很简单

range类型查询字段后面的索引全都无效

因为pay_time是范围查询,索引goods_id无效,所以分组一样有临时表存在!

我们在看下查询时间

执行时间是: 0.04秒!

是不是快到起飞,虽然我们从执行计划来看依然还是存在 Using temporary ,但查询速度却非常快。

关键点就在Using index(索引覆盖),虽然排序是无法走索引了,但是不需要回表查询,这个效率提升是惊人的!

5.4、仅查询字段建立索引

上面说了就算建立了 pay_time,goods_id 组合索引,对于goods_id 分组依然不走索引的。

这里我自建立 pay_time单个索引

 -- 先删除组合索引
drop index idx_payTime_goodsId on order_info;
 -- 再新建单个索引
alter table order_info add index idx_pay_time(pay_time);

这次可以很明显的看到

  • Extra 这个字段的using index condition 需要回表查询数据,但是有部分数据是在二级索引过滤后,再回表查询数据,减少了回表查询的数据行数

  • Extra 这个字段的Using MRR 优化器将随机 IO 转化为顺序 IO 以降低查询过程中 IO 开销

  • Extra 这个字段的 Using temporary 表示在执行分组的时候使用了临时表

查看查询时间

执行时间 0.56秒!

从结果看出,跟最开始不加索引查询速度相差不多,原因是什么呢?

最主要原因就是虽然走了索引,但是依然还需要回表查询,查询效率并没有提高多少!

那我们思考如何优化呢,既然上面走了回表,我们是不是可以不走回表查询,这里修改下sql

select goods_id, count(*) as num
from order_info
where id in (
	select id
	from order_info
	where pay_time >= '2022-12-01 00:00:00'
	and pay_time <= '2022-12-31 23:59:59'
)
group by goods_id;

查看查询时间

执行时间 0.39秒!

速度确实有提升,我们在执行下explain

我们可以看到 没有了using index condition,而有了Using index,说明不需要再回表查询,而是走了索引覆盖!



声明: 公众号如需转载该篇文章,发表文章的头部一定要 告知是转至公众号: 后端元宇宙。同时也可以问本人要markdown原稿和原图片。其它情况一律禁止转载!

本文转载于网络 如有侵权请联系删除

相关文章

  • Golang中interface内部构造与面试真题分析

    本篇通过一些面试真题,来分析interface的几点注意及内部底层结构,提纲如下:一、interface的赋值问题二、interface的内部结构(iface与eface)三、interface{}与*interface{}一、interface的赋值问题01以下代码能编译过去吗?为什么?代码packagemain import( "fmt" ) typePeopleinterface{ Speak(string)string } typeStduentstruct{} func(stu*Stduent)Speak(thinkstring)(talkstring){ ifthink=="love"{ talk="Youareagoodboy" }else{ talk="hi" } return } funcmain(){ varpeoPeople=Stduent{} think:="love" fmt.Println(peo.Speak(think)) }复制02分析与说明继承

  • 如果通过 IP 判断是否是爬虫

    通过IP判断爬虫如果你查看服务器日志,看到密密麻麻的IP地址,你一眼可以看出来那些IP是爬虫,那些IP是正常的爬虫,就像这样:logscreen在这密密麻麻的日志里面,我们不仅要分辨出真正的爬虫IP,同时也要分辨出伪造的爬虫IP,实属不易。如果查看服务器日志,我们可以先通过User-agent大致判断出是爬虫还是正常用户,例如:Mozilla/5.0(compatible;SemrushBot/7~bl;+http://www.semrush.com/bot.html)这个是SemrushBot的爬虫Mozilla/5.0(compatible;bingbot/2.0;+http://www.bing.com/bingbot.htm)这个是bing搜索引擎的爬虫Mozilla/5.0(Linux;Android6.0.1;Nexus5XBuild/MMB29P)AppleWebKit/537.36(KHTML,likeGecko)Chrome/90.0.4430.97MobileSafari/537.36(compatible;Googlebot/2.1;+http://www.goo

  • mysql-解压版安装配置详解

    1、下载MySQL解压版,MySQL解压版官网下载参考2、配置环境变量 高级系统设置->环境变量,新建一个系统变量MYSQL_HOME,变量值为mysql的解压路径,如:D:/dev_config_soft/mysql-5.7.20-winx64,然后在path里添加;%MYSQL_HOME%\bin注意前后分号。3、新建my.ini文件 以前的版本解压后或许会存在my-default.ini文件,若没有,手动创建该文件,内容为:[mysqld] port=3306 basedir=D:/dev_config_soft/mysql-5.7.20-winx64 datadir=D:/dev_config_soft/mysql-5.7.20-winx64/data max_connections=200 character-set-server=utf8 default-storage-engine=INNODB sql_mode=NO_ENGINE_SUBSTITUTION,STRICT_TRANS_TABLES [mysql] default-character-set=utf8

  • centos7 ssh免密登录(shell脚本)

    centos7sshshellcentos7ssh免密登录(shell脚本)环境(centos7)hostnameipnode192.168.100.199node1192.168.100.101node2192.168.100.1021.分别修改主机名hostnamectlset-hostname<hostname>复制2.分别修改hosts127.0.0.1localhostlocalhost.localdomainlocalhost4localhost4.localdomain4 ::1localhostlocalhost.localdomainlocalhost6localhost6.localdomain6 192.168.100.199node 192.168.100.101node1 192.168.100.102node2复制3.在node上执行下面的脚本#!/bin/bash yum-yinstallexpect #PWD登录密码 PWD=111111 ips=$(cat/etc/hosts|grep-v"::"|grep-v"

  • macOS NSTableView鼠标右键菜单

    macOS开发中对于鼠标的支持没有Windows那种的鼠标悬停功能,需要自己手动去实现。幸运的是可以检测鼠标在NSView的滑入和退出等事件,我们可以通过这种方式来实现鼠标的监听,开确认是否显示菜单,然后转换为对应的位置,再根据位置后去搜找对应cell,之后添加菜单显示操作即可实现啦?定义一个protocol```@objcprotocolContextMenu{@objcfunctableView(_tableView:NSTableView,menuForRowsrows:IndexSet)->NSMenu?@objcfunctableView(_tableView:NSTableView,clickForRowrow:Int)->Void}```extensiontableview重写鼠标事件```extensionNSTableView{openoverridefuncmenu(forevent:NSEvent)->NSMenu?{letlocation=self.convert(event.locationInWindow,from:nil)letrow=s

  • vueRouter-编程式的导航 原

    除了使用<router-link>创建a标签来定义导航链接,我们还可以借助router的实例方法,通过编写代码来实现。 router.push(location) 想要导航到不同的url,则使用router.push方法。这个方法会像history栈添加一个新的记录, 所以,当用户点击浏览器后退按钮时,则回到之前的url 当你点击<router-link>时,这个方法会在内部调用,所以说,点击<router-link:to="...">等同于调用 router.push(...) 该方法的参数可以是一个字符串路径,或者一个描述地址的对象,例如: //字符串 router.push("home") //对象 router.push({path:"home"}) 命名的路由 router.push({name:"user",params:{userId:123}}) //带查询参数,变成/register?plan=private router.push({path:

  • 蓝鲸智云的幕后英雄:管控平台

    01蓝鲸简介蓝鲸智云,简称蓝鲸,是腾讯游戏运营部“腾讯智营”下的子品牌。它是一套基于PaaS的企业研发运营一体化技术解决方案,提供了一个完整的研发、运维、运营的PaaS技术平台。平台提供了完善的前后台开发框架、调度引擎、公共组件等模块,帮助业务的产品和技术人员快速构建低成本、免运维的支撑工具和运营系统。蓝鲸智云是腾讯游戏运营部沉淀多年的技术运营支撑体系,承担着数百款业务线上运营的使命。 对于蓝鲸不太了解和熟悉的同学可以移步这里:http://bk.tencent.com/index/,还有这里:http://docs.bk.tencent.com/product_white_paper/introduction/请相信,你打开的不是两个链接,而是运维的新世界和新天地。02IT基础架构运维的重点-服务器运维服务器(包括物理机和虚拟机)可能是企业IT运维管理中最常见、数量最多的一类管理对象。在中大型企业的IT环境中,服务器这类对象往往具有以下特点: 数量庞大 上千台是家常便饭,有的企业环境甚至达到数千台甚至上万台,大型互联网公司甚至可以达到数十万台。数量庞大情况下,就要求我们有能力批量的、

  • python源码阅读笔记之线程机制

    六,python的线程机制 GIL锁的机制,来源于python的内存管理和为了实现多线程,对共享内存资源的互斥实现。 当然,python对进程的支持很好,这在linux下,很有比线程更好的使用,因为在linux里没有线程的概念, 有着的是轻量级的进程以及pipeline等进程间通信。 如果非要使用线程,解释器只有一个,导致的各种线程必须要获得字节码解释器,也就是GIL。 有两个核心问题:在何时挂起当前线程,选择下一个线程?在众多等待的线程中选择其中一个? 对于第一个问题,python通过执行的字节码指令弄的,如下: importsys sys.getcheckinterval() Out[2]:100 100条指令便会切换下一个。 至于第二个问题:由底层的操作系统决定,因为python的线程实际上是将obj这些直接调用的Event指令。 在thread模块中,有如下的方法: staticPyMethodDeflock_methods[]={ {"acquire_lock",(PyCFunction)lock_PyThread_acquire_lock, ME

  • 安全科普:什么是暴力破解攻击?如何检测和防御?

    点击标题下「大数据文摘」可快捷关注众所周知,iCloud艳照门其实并不高明,黑客通过暴力破解攻击不断尝试登录用户的账号名和密码,最终获取好莱坞明星的iCloud账号。什么是暴力破解攻击?怎样检测暴力破解攻击以及怎样防护呢?什么是暴力破解攻击?暴力破解攻击是指攻击者通过系统地组合所有可能性(例如登录时用到的账户名、密码),尝试所有的可能性破解用户的账户名、密码等敏感信息。攻击者会经常使用自动化脚本组合出正确的用户名和密码。对防御者而言,给攻击者留的时间越长,其组合出正确的用户名和密码的可能性就越大。这就是为什么时间在检测暴力破解攻击时是如此的重要了。怎样检测暴力破解攻击?暴力破解攻击是通过巨大的尝试次数获得一定成功率的的。因此在web(应用程序)日志上,你会经常发现有很多的登录失败条目,而且这些条目的IP地址通常还是同个IP地址。有时你又会发现不同的IP地址会使用同一个账户、不同的密码进行登录。大量的暴力破解请求会导致服务器日志中出现大量异常记录,从中你会发现一些奇怪的进站前链接(referringurls),比如:http://user:password@website.com/log

  • linux设备驱动第四篇:linux驱动调试方法

    上一篇我们大概聊了如何写一个简单的字符设备驱动,我们不是神,写代码肯定会出现问题,我们需要在编写代码的过程中不断调试。在普通的c应用程序中,我们经常使用printf来输出信息,或者使用gdb来调试程序,那么驱动程序如何调试呢?我们知道在调试程序时经常遇到的问题就是野指针或者数组越界带来的问题,在应用程序中运行这种程序就会报segmentationfault的错误,而由于驱动程序的特殊性,出现此类情况后往往会直接造成系统宕机,并会抛出oops信息。那么我们如何来分析oops信息呢,甚至根据oops信息来定位具体的出错的代码行呢?下面就根据一个简单的实例来说明如何调试驱动程序。如何根据oops定位代码行我们借用linux设备驱动第二篇:构造和运行模块里面的helloworld程序来演示出错的情况,含有错误代码的helloworld如下:#include<linux/init.h> #include<linux/module.h> MODULE_LICENSE("DualBSD/GPL"); staticinthello_init(void) {

  • 通过自定义配置实现插件式设计

    软件设计有一句话叫做“约定优于配置”,很多人将其作为拒绝配置的理由。但是,“约定”和“配置”的使用,都有个度的问题。我不赞为了所谓的扩展性,为你的应用设计一套只有你自己才能看懂的配置体系。但是,在很多场景中,配置是提供应用灵活度的首要甚至是唯一途径。对于框架的设计者来说,对于配置的驾驭是一项基本的技能。可能你很少使用自定义配置,可能你理解的自定义配置仅仅限于AppSetting,不过我想你应该对于System.Configuration这个命名空间下的几个基本的类型有基本的了解。比如ConfigurationSection、ConfigurationElement、ConfigurationElementCollection等。本篇文章不会介绍关于System.Configuration的基础知识,而是通过一个简单的例子为你讲述一些所谓“高级”的知识点,比如“不可识别配置元素的动态解析”。(源代码从这里下载)目录 一、通过自定义配置实现的最终效果 二、相关配置类型的定义 三、两个重要的类型:NameTypeConfigurationElement和NameTypeConfigurati

  • aix 查看内存,CPU 配置信息

    内存lsattr-Elmem0cpulsdev-C|grepprocCPU的信息lsattr-Elproc0   #bootinfo-r查看物理内存     使用命令#  lsdev-Ccmemory查看配置的物理内存设备,下面为其输出示例:  mem0Available00-00Memory   L2cache0Available00-00L2Cache 再使用命令#lsattr-Elmem0输出如下  size512TotalamountofphysicalmemoryinMbytes  False   goodsize512AmountofusablephysicalmemoryinMbytesFalse 此例说明机器的物理内存为512MB。如果前面lsdev的输出中有设备名mem1,则使用同样的命令查看其对应的大小并依此类推。       再补充一个方法svmo

  • 边工作边刷题:70天一遍leetcode: day 97-1

    SortTransformedArray 要点: 知道了解法就容易了:本质:如何把一个单调的转化成双向单调的:结构包括两部分:原array的选择方向(双指针)和填结果array的方向。 min/max在inputsortedarray的中间点,所以双向验证,另外根据开口方向,决定从两边走是越来越大还是越来越小决定从那边填结果array。 a==0的情况可以和a>0的情况相同:因为变成单调的,无论升降,都是某一边一直占优势,所以和a>0或a<0没差别。 https://repl.it/C9tc/1 classSolution(object): defsortTransformedArray(self,nums,a,b,c): """ :typenums:List[int] :typea:int :typeb:int :typec:int :rtype:List[int] """ defcalRes(num): returna*num*num+b*num+c n=len(nums) res=[] i,j=0,n-1 ifa>=0: whilei<=j:

  • 2020 巅峰极客 Re部分WriteUp

    virus 附件下载:https://wwa.lanzous.com/iZh5tgy9gbg 代码分为三部分 以'-'为间隔,将flag的第一部分转换为整型数字,并且满足后项-前项分别为[0x13,0x19,0x1a,0x1c]。最后一项为len(flag)-lastpos('-') 以'-'为间隔,将中间的字符串分别存储到road中 checkflag,即走四个20x...的迷宫,从s->d。以第1点存储的顺序,决定迷宫的顺序。通过确定后面的字符串顺序,前面的数字也会被确定。 1~4为:-dddddddddsssssaaaaaaaaawww-sdsdsdsdsdsdsddwdwdwdwdwdwdw-aaaaaaaaasssssssddddddddd-wwwwwdddddddddsssss importitertools a=['-dddddddddsssssaaaaaaaaawww','-sdsdsdsdsdsdsddwdwdwdwdwdwdw','-aaaaaaaaasssssssddddddddd','-wwwwwdddddddddsssss'] b=list(ite

  • 堆排序

    前言:   堆性质定义   大根堆:arr(i)>arr(2*i+1)&&arr(i)>arr(2*i+2)   小根堆:arr(i)<arr(2*i+1)&&arr(i)<arr(2*i+2)   堆排序基本思想:   1.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端   2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1   3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组    (一)代码 privatestaticvoidsort(int[]array){ intlen=array.length; //构建大根堆 buildMaxHeap(array,len); for(inti=len-1;i>0;i--){ //因为上面已经构建好了大根堆 //0的位置就是最大的值,将最大值与最后一位交换, //再将剩余的数,重新构建大根堆 swap(array,0,i); len--

  • leetcode-20. Valid Parentheses

    20.ValidParentheses Givenastringcontainingjustthecharacters '(', ')', '{', '}', '[' and ']',determineiftheinputstringisvalid. Thebracketsmustcloseinthecorrectorder, "()" and "()[]{}" areallvalidbut "(]" and "([)]" arenot. 判断字符括号是否匹配正确。 java代码: publicclassSolution{ publicbooleanisValid(Strings){ Stacka=newStack(); inti=0; while(i!=s.length()){ switch(s.charAt(i)){ case'[': a.push('['); break; case'(': a.push('('); break;

  • BZOJ 3675: [Apio2014]序列分割

    Description 将一个序列切割\(k\)次,每次切割的收益是两边和的乘积,求最大收益.\(n\leqslant1\times10^5,k\leqslant200\) Solution 斜率优化DP.. 因为什么\((a+b)c+ab=a(b+c)+bc\).. 所以他是只与结果有关的,跟切割方法无关,随便切就行... \(f[i][j]=max\{f[k][j-1]+s[k](s[i]-s[k])\}\) 斜率正好是前缀和,并且单调不降.. 所以直接斜率优化那一套就行了... Code /************************************************************** Problem:3675 User:BeiYu Language:C++ Result:Accepted Time:14596ms Memory:84112kb ****************************************************************/ #include<bits/stdc++.h> usingna

  • __bridge, __bridge_transfer, __bridge_retained

    转载自微信公众号“知识小集”   __bridge,__bridge_transfer,__bridge_retained 几乎是一百年多前的知识点了,关于它们在ARC下的用法已有大量文章。但是这东西乍一看好简单,实际上也确实简单,但过段时间不接触再来用却难免又会犯迷糊。因此本文以更加详细的方式梳理一遍,旨在讲清楚来龙去脉,而不止是用法。 0.一些说明 针对后面会用到的描述做一些说明。 CF对象:由CoreFoundation创建,管理的对象,比如CFStringRef、CFArrayRef等,或者其他由系统SDK的C风格API创建,管理的对象,比如ABAddressBookRef; OC对象:就是OC对象; 所有权:管理对象生命周期的权利,准确说其实是:将对象进行RetainCount -1 的权利和义务; ARC管理:对象生命周期的retain与release操作由编译器生成的代码进行管理,不需要手动管理; CF手动管理:对象生命周通过手动调用CFRetain/CFRelease来管理。 1.__bridge 用以将C

  • 数据库小练习2

    数据库小练习2: 新建一张exam表,字段数据如下图:   CREATETABLEexam(idINT,NAMEVARCHAR(10),englishVARCHAR(10),chineseVARCHAR(10),mathVARCHAR(10)) INSERTINTOexam(id,NAME,english,chinese,math)VALUES(1,'张三',85,74,91);INSERTINTOexam(id,NAME,english,chinese,math)VALUES(2,'李四',98,90,83);INSERTINTOexam(id,NAME,english,chinese,math)VALUES(3,'王五',85,84,59);INSERTINTOexam(id,NAME,english,chinese,math)VALUES(4,'赵六',75,79,76);INSERTINTOexam(id,NAME,english,chinese,math)VALUES(5,'田七',69,63,98);INSERTINTOexam(id,NAME,english,

  • 中国八大菜系食谱系列——————川菜

    川菜简介 川菜烹饪经典一百例,川菜也叫四川菜,以成都菜、重庆菜和自贡菜为主组成。味道有麻辣、怪味、家常、陈皮、椒盐、荔枝、酸辣、蒜泥、麻酱、芥末等三十多种,以麻辣、鱼香、怪味独善其长。烹饪手法多样,常用的有炒、爆、熘、炸、煎、烧、烩、焖、煮、拌、腌、槽等几十种。 在高级宴席中,辣味菜只占一个到两个菜,其他一般都是糖醋、荔枝、咸酸多一些。大辣、大麻的菜只是在一些家常菜中占很大一部分。川菜的另一个特点就是选料主要是鸡鸭鱼肉、四季蔬菜、豆制品等。原料价格便宜,因此适合很多工薪阶层。川菜流行的原因:烹饪方法多、味型多、原料便宜。适应很多场合。   1、东坡肉 原料:猪五花肉800g  调料:花椒1g料酒15g盐15g 姜片20g 葱段50g 菜油30g 香油5g糖色5g 鲜汤150g 酱油5g 制作方法:先把猪肉放在冷水锅中加热,等到水开以后,改用小火煮到断生(八分熟,在熟与不熟的边界)时捞出,在皮面上抹上酱油,然后皮朝下,放在热油锅中。炸成棕红色时捞出。炒锅内放底油、葱、姜掂炒,加入料酒、鲜汤,加盐、白糖、加入糖

  • GDUFE ACM-1254

    题目:http://acm.gdufe.edu.cn/Problem/read/id/1254   闹钟人生 TimeLimit:2000/1000ms(Java/Others) ProblemDescription: 已知一个时钟一开始指向0点,顺时针走了n个小时,求它最终所指向的数字(时间按12进制计算)。复制 Input: 多组输入,每组一个n(-10^7<=n<=10^7)复制 Output: 输出指针所指数字复制 SampleInput: 4 12 15复制 SampleOutput: 4 0 3思路:每12一个循环,注意是逆时针还是顺时针转,还有要注意,每转12个小时,都是指向0而不是12难度:非常简单代码:复制 1#include<stdio.h> 2intmain() 3{ 4longlongn; 5while(scanf("%lld",&n)!=EOF) 6{ 7if(n<0) 8if(n%12==0)printf("0\n"); 9elseprintf("%lld\n",12+n%12);

相关推荐

推荐阅读