处理器基础知识总结

本文的知识点比较零散,主要是关于处理器的一些基本知识,大部分内容来源于参考资料并给出了自己的理解和整理。

一,什么是处理器

先描述下一般处理器的概念,维基百科的定义是 “In computing, a processor is an electronic circuit which performs operations on some external data source, usually memory or some other data stream”。最为常见的处理器有 CPU(可以运行任何程序)、GPU(图形图像处理)和 DSP(处理数字信号),还有专门用来做 DNN 应用神经网络处理器。

处理器或处理单元是对外部数据源(通常是内存或其他数据流)执行操作的电子组件(数字电路)。

CPU 的主要运作原理,不论其外观,都是执行储存于被称为程序里的一系列指令。在此讨论的是遵循普遍的冯·诺伊曼结构(von Neumann architecture)设计的设备。程序以一系列数字储存在计算机存储器中。差不多所有的冯·诺伊曼 CPU 的运作原理可分为四个阶段:提取、解码、执行和写回

而专用处理器就是针对特定应用或者领域的处理器,类似于是我们经常说的 Domain Specific Architecture 的概念。

二,指令集基础

什么是 ISA

指令集(Instruction Set Architecture, ISA)是计算机抽象模型的一部分,它定义了软件如何控制 CPUISA 充当硬件和软件的接口,指示了处理器能够实现什么功能以及如何实现。简单来说,ISA 就是传统上软件和硬件的分界线,是用户和硬件交互的唯一方式。

ISA 定义了硬件支持的数据类型、寄存器、硬件如何管理内存、关键特性(如虚拟内存)、微处理器可以执行哪些指令,以及多个 ISA 实现的输入输出模型。ISA 可以通过添加指令或其他功能或通过添加对更大地址和数据值的支持来扩展。

来源 What is Instruction Set Architecture (ISA)? - Arm

ISA 功能

大多数 ISA(典型如 x86-Intel CPU 的指令集),将程序的行为描述成每条指令都是顺序执行的,一条指令结束后,下一条在开始。

ISA 提供的主要指令可以分为四大类功能:

  1. 执行运算或处理的功能,比如算术操作指令;
  2. 控制程序流,比如循环、判断分支和跳转指令;
  3. 实现数据搬移,如内存到寄存器,寄存器之间数据搬移等指令;
  4. 最后就是一些辅助指令,如 debug、中断和 cache 之类的指令。

三,CPU 设计与实现

整数范围

CPU 数字表示方法是一个设计上的选择,这个选择影响了设备的工作方式。一些早期的数字计算机内部使用电气模型来表示通用的十进制(基于 10进位)记数系统数字。还有一些罕见的计算机使用三进制表示数字。几乎所有的现代的 CPU 使用二进制系统来表示数字,这样数字可以用具有两个值的物理量来表示,例如高低电平等等。

时钟频率

主频=外频×倍频。大部分的 CPU,甚至大部分的时序逻辑设备,本质上都是同步的,即它们被设计和使用的前题是假设都在同一个同步信号中工作。

指令周期(Instruction cycle)

指令周期是指 CPU 要执行一条机器指令经过的步骤,由若干机器周期组成。一般会经历“取指”,“译码”,“发射/执行”和“写回”这些操作。处理器执行程序的过程就是不断重复这几个操作。

指令流水线(Instruction pipeline)

在1978年的 Intel 8086 处理器都只能一次执行单指令。 Intel首次在486芯片中开始使用,原理是:当指令之间不存在相关时,它们在流水线中是可以重叠起来并行执行。

当一条指令,完成了“取指”操作,开始进行“译码”的时候,取指模块就可以取程序的下一条指令了,这样可以让这些模块不至于闲着没用,即指令流水线可以两个以上的指令同时执行(类似车间流水线)。一般的四层流水线架构如下图所示,不同的颜色格表示不同的指令

指令并行(Instruction-level parallelism)

同时执行多条指令。比如,一边从 memory 读数据,一边进行 fft 处理。我们经常听到的超标量(Superscalar),超长指令字(VLIW),乱序执行( Out-of-order execution)等等技术都是发掘指令级并行的技术。

数据并行(Data parallelism):

一个人指令同时处理多个数据。我们常听到的向量处理器(vector procesor),张量处理器(Tensor processor)多数都是利用了 SIMD一条指令可以处理多个数据,比如一个向量乘法)技术。

并发与并行

并发与并行的通俗理解参考知乎问答-指令级并行,线程级并行,数据级并行区别?线程的概念是什么?如下:

线程级并行(Thread-Lever Parallelism)

线程级并行主要由下面两种技术的支撑:

  1. 超线程技术:2004年,奔腾4实现了Hyper-Threading.(单核心双线程)
  2. 多核技术-物理核心: 2005年,英特尔宣布他的第一个双核心 EM64T 处理器,和 Pentium D840超线程技术实现了单个物理核心同时两个线程,也就是别人常说的虚拟内核数。比如单物理核心实现的双线程,它同时可以处理两个线程,它的物理核心数其实是是1个,通过Hyperthreading技术实现的线程级并行(Thread Lever Parallelism)。至于技术细节的实现,这涉及到高速缓存的知识。

线程级并行的好处:

  • 当运行多任务时,它减少了之前的操作系统模拟出来的并发,那么用户进行多任务处理时可以运行更多的程序进行并发了。
  • 它可以使单个程序运行更快。(仅当该程序有大量线程可以并行处理时)

虽然在 1960 年代已经通过操作系统已经实现了线程级并发, 但这种频繁的上下文切换意味损失了 CPU 的处理效率。

性能

CPU 的性能和速度取决于时钟频率(一般以赫兹或十亿赫兹计算,即 hzGhz)和每周期可处理的指令IPC),两者合并起来就是每秒可处理的指令(IPS)。IPS 值代表了 CPU 在几种人工指令序列下“高峰期”的执行率,指示和应用。

参考资料

  1. 深入理解计算机系统-第三版
  2. 专用处理器设计
  3. https://www.zhihu.com/question/21823699/answer/111606716
本文转载于网络 如有侵权请联系删除

相关文章

  • Kubernetes 使用kubeadm创建集群

    实践环境CentOS-7-x86_64-DVD-1810Docker19.03.9Kubernetesversion:v1.20.5开始之前1台Linux操作或更多,兼容运行deb,rpm确保每台机器2G内存或以上确保当控制面板的结点机,其CPU核数为双核或以上确保集群中的所有机器网络互连目标安装一个Kubernetes集群控制面板基于集群安装一个Podnetwork以便集群之间可以相互通信安装指导安装Docker安装过程略注意,安装docker时,需要指Kubenetes支持的版本(参见如下),如果安装的docker版本过高导致,会提示以下问题WARNINGSystemVerification]:thisDockerversionisnotonthelistofvalidatedversions:20.10.5.Latestvalidatedversion:19.03复制安装docker时指定版本sudoyuminstalldocker-ce-19.03.9docker-ce-cli-19.03.9containerd.io复制如果没有安装docker,运行kubeadminit时会

  • 添加配套插件报错

    报错Notice:Constant__TYPECHO_ADMIN__alreadydefinedin/www/根目录/admin/common.phponline6复制打开/admin/目录下的common.php,替换以下代码define('__TYPECHO_ADMIN__',true);复制换成if(!defined('__TYPECHO_ADMIN__')){ define('__TYPECHO_ADMIN__',true); }复制版权属于:青城 本文链接:https://blog.2gh1.cn/archives/291/ 转载时须注明出处及本声明

  • Install Tomcat

    前言Tomcat是一款开源的JavaServlet实现,简单来说就是一个java应用解析容器TheApacheTomcat®softwareisanopensourceimplementationoftheJavaServlet,JavaServerPages,JavaExpressionLanguageandJavaWebSockettechnologies常与Apache一起配合实现WebApp,Apache提供静态内容的服务,Tomcat提供动态内容的服务CMDBuild也是通过Tomcat来提供WEB服务,在研究CMDBuild之前,需要对Tomcat进行简单的了解Tomcat依赖java运行环境,所以正常运行前的提是需要有相应版本的JDK这里分享一下Tomcat的安装方法Tip:当前的版本为9.0.5,但是在此演示的版本为8.5.28,原因为CMDBuild官方推荐此版本,为了考虑兼容性,就没有使用最新的版本操作环境[root@h210~]#hostnamectl Statichostname:h210 Iconname:computer-vm Chassis:vm Mach

  • Maxwell 系列(四)—— bootstrap数据全量导入

    1、bootstrap使用 Maxwell允许您将数据“引导”到流中。这将执行select*fromtable和将结果输出到您的流中,从而允许您从头开始播放流来重新创建整个数据集。binlog被清除maxwell是可以记录binlog读取的position,如果binlog被清除,则position无意义。数据初始化 项目刚启动,需要把已经存在的历史数据同步到流中,然后再使用增量的方式抽取。您可以使用该maxwell-bootstrap实用程序从命令行开始boostrap操作。optiondescription--log_levelLOG_LEVELloglevel(DEBUG,INFO,WARNorERROR)--userUSERmysqlusername--passwordPASSWORDmysqlpassword--hostHOSTmysqlhost--portPORTmysqlport--databaseDATABASEmysqldatabasecontainingthetabletobootstrap--tableTABLEmysqltabletobootstrap--whe

  • Facebook Messenger向第三方应用泄露用户访问令牌

    该篇Writeup讲述作者在测试FacebookMessengeriOSApp的过程中,发现MessengeriOSApp在调用动图消息图标的过程中,会把用户的访问令牌(accesstoken)泄露给第三方动图搜索引擎。以下是作者的发现过程。漏洞发现某天,我在测试一个iOSApp,但几个小时过去了却一无所获。之后,我想转移下注意力,打算干点其它的。刚好我大学同学通过Messenger发来了一条消息,我打开Messenger应用APP想找个GIF动图表情回复他。此时我电脑里的Burp正在抓包,而其中产生了很多TenorGIF动图的请求包,我马上深入对其中的请求响应进行了检查,之后,我发现了很多“access_token”被泄露到了TenorGIF动图请求包中。也就是说,FacebookMessengeriOSApp用户在发送一些GIF动图的过程中,FacebookMessengeriOSApp会把用户的“access_token”泄露给TenorGIF的动图请求,即把用户的MessengeriOSApp“access_token”发起送到了Tenor服务端去。此时,我非常高兴,总算有点可

  • 基于Canal与Flink实现数据实时增量同步(二)

    背景在数据仓库建模中,未经任何加工处理的原始业务层数据,我们称之为ODS(OperationalDataStore)数据。在互联网企业中,常见的ODS数据有业务日志数据(Log)和业务DB数据(DB)两类。对于业务DB数据来说,从MySQL等关系型数据库的业务数据进行采集,然后导入到Hive中,是进行数据仓库生产的重要环节。如何准确、高效地把MySQL数据同步到Hive中?一般常用的解决方案是批量取数并Load:直连MySQL去Select表中的数据,然后存到本地文件作为中间存储,最后把文件Load到Hive表中。这种方案的优点是实现简单,但是随着业务的发展,缺点也逐渐暴露出来:性能瓶颈:随着业务规模的增长,SelectFromMySQL->SavetoLocalfile->LoadtoHive这种数据流花费的时间越来越长,无法满足下游数仓生产的时间要求。直接从MySQL中Select大量数据,对MySQL的影响非常大,容易造成慢查询,影响业务线上的正常服务。由于Hive本身的语法不支持更新、删除等SQL原语(高版本Hive支持,但是需要分桶+ORC存储格式),对于MySQ

  • MySQL集群搭建实现高可用

    本节所讲内容:lMySQL集群概述l实战:MySQL集群搭建1 MySQL集群概述和安装环境MySQLCluster是MySQL适合于分布式计算环境的高实用、高冗余版本。Cluster的汉语是“集群”的意思。它采用了NDBCluster存储引擎,允许在1个Cluster中运行多个MySQL服务器。MySQLCluster是一种技术,该技术允许在无共享的系统中部署“内存中”数据库的Cluster。通过无共享体系结构,系统能够使用廉价的硬件,而且对软硬件无特殊要求。此外,由于每个组件有自己的内存和磁盘,不存在单点故障。1.1 mysql集群架构SQL节点:给上层应用层提供sql访问。管理节点(MGM):管理整个集群。启动,关闭集群。通过ndb_mgmd命令启动集群存储/数据节点:保存cluster中的数据。数据节点,可以提供副本。实现数据冗余。NDB引擎:是一种“内存中”的存储引擎,它具有可用性高和数据一致性好的特点。拓展:NDB引擎介绍:NDB引擎MySQLCluster使用了一个专用的基于内存的存储引擎——NDB引擎,这样做的好处是速度快,没有磁盘I/O的瓶颈,但是由于是基于内存的,所

  • 我所经历的一次Dubbo服务雪崩,这是一个漫长的故事

    这周本来是要写一篇Dubbo源码分析的,被突发事件耽搁了,下周有时间再补上。 这周,笔者经历了一次服务雪崩。服务雪崩,听到这个词就能想到问题的严重性。是的,整个项目,整条业务线都挂了,从该业务线延伸出来的下游业务线也跟着凉了。笔者是连续三天两夜的忙着处理问题,加起来睡眠时间不足5小时,今天才得以睡个好觉。但事故之后还有很多问题等着去处理。其实这一天的到来我是有意料到的,但我以为会是数据量上升导致,实际却是并发量先上升,而严重程度超出我的预料。问题出现那天,我们还在进行每周的技术分享会,结果运营推开会议室的大门传来噩耗,顿时技术分享会变成了问题排查讨论会,场面像极了一起加班解决Bug。在一个处理用户点击广告的高并发服务上找到了问题。看到服务打印的日记后我完全蒙了,全是jedis读超时,Readtimeout!一直用的是亚马逊的Redis服务,很难想象Jedis会读超时。看了服务的负载均衡统计,发现并发增长了一倍,从每分钟3到4万的请求数,增长到8.6万,很显然,是并发翻倍导致的服务雪崩。服务的部署:处理广告点击的服务:2台2核8g的实例,每台部署一个节点(服务)。下文统称服务A规则匹配服

  • 数据分析-NumPy数组的数学运算

    背景介绍今天我们学习使用numpy的内置数学运算方法和基本的算术运算符两种方式对数组进行数学运算的学习,内容涉及到线性代数的向量矩阵的基本运算知识(不熟悉的童鞋回头自己补一下哈),接下来开始:入门示例以下为在JupyterNotebook中的执行过程:编码如下:####使用numpy数组进行数学运算 importnumpyasnp x=np.array([[1,2],[3,4]]) y=np.array([[5,6],[7,8]]) ####加法运算 #使用运算符数组相加 x+y ####使用np.add()方法进行相加 z=np.add(x,y) z ####减法运算 x-y np.subtract(x,y) ####乘法运算 x*y np.multiply(x,y) ###除法运算 x/y np.divide(x,y) ###取平方根 np.sqrt(x) v=np.array([9,10]) w=np.array([11,13]) ###使用np.dot()进行矩阵运算 ####他的函数返回两个数组的点积。对于二维向量,它等效于矩阵乘法。 ####对于1-D阵列,它是向量的内积。

  • Hive常用语法

    1、concat_wsSELECTCONCAT_WS('.',split('a.b.c.d','\\.')[0],split('a.b.c.d','\\.')[1],split('a.b.c.d','\\.')[2]);复制2、row_num()SELECTa.* FROM ( SELECTt.*,row_num()over(partitionBYpackage_name,orderBYrow)asrow_num fromt )a WHEREa.row_num=1复制3、加载jar包函数addjarpath/xxxxx.jar; createtemporaryfunctionfunction_nameas'com.company.function_name';复制4、中文UTF-8转码reflect('java.net.URLDecoder','decode',XXXXXX,"U

  • 边缘计算(三)——边缘计算的解决方案

    目前,市场上存在的边缘计算相关概念包括雾计算、边缘计算、多接入边缘计算/移动边缘计算、移动云计算等概念。这是边缘计算的第三篇,主要讲的内容是边缘计算的解决方案。 CloudFoundry平台CloudFoundry是一款使用Ruby开发的开源Paas平台,由VMware于2009年开发,并于2014年2月转交给CloudFoundry基金会管理,正式成为开源软件。遍布全球的财富500强企业中有一半以上(包括金融服务,政府办公室,汽车公司等等)都依赖CloudFoundry来提高速度,灵活性和效率。当然,相对于云计算、大数据等概念以及平台,CloudFoundry就显得不那么声名显赫了。CloudFoundry是VMware主导一款开源PaaS云计算平台。遵从OpenStack云计算平台规范。CloudFoundry作为目前最有活力的开源Paas平台,有效降低了工业物联网平台的准入门槛和开发周期。目前,基于CloudFoundry开发的工业IoT平台包括:GEPredix平台;西门子MindSphere;博世IoTCloud;霍尼韦尔Sentience。除此之外,还包括如下物联网平台等:

  • 不使用定时器实现的onhashchange

    之前看sparks345写的《不采用interval方式模仿onHashChange》后来自己又折腾了一把,完整的源码总共大小是1.66KB(2K不到)支持:FF3.0+、IE6+、Chrome主流的浏览器(IE6、IE7除外),基本上都支持onhashchange事件,而IE8也将支持。只有IE6、IE7不支持,而使用这两个浏览器的用户还是占有很大的一部分份额。网上流传的实现onhashchange方法基本上都采用setInterval来跑,这样做:第一:不切换也要去检测一次hash,总觉得别扭;第二:点击过快的时候容易出bug(曾经耿耿于怀这个)既然外面的轮子都不好用,还就自己造一个吧~其实造也不难,因需要专门针对ie做一些处理就好了。页面放个iframe,然后然后iframe里面的内容,比如加个表单元素input并监听其onload事件,然后回调。说明一下:这个方法不是我最先想到的,是我不经意见研究某站点的代码发现的,在这里先致谢一下。HistoryManager.js的源码:1:functionHistoryManager(){ 2:this.listener=null;

  • 如何手动配置WordPress浏览器缓存

    当我们提到如何配置Wordpress缓存的时候,可能大部分人的第一反应是:用插件啊,比如WPSUPERCACHE之类的,效果很好。但事实上目前的wordpress缓存类插件对网站的速度是有些影响的,虽然不是很大。那么有没有更为简单的手动配置wordpress浏览器缓存的方法呢?当然有!在讲到手动配置WP缓存的方法前,先简单科普下浏览器缓存的好处:1.减少了加载时间,提高站点的打开速度;2.有效的降低了跳出率,这是衡量网站是否优秀的重要指标;3.降低你的主机或者服务器的运载压力,这一点也非常重要。如何检查你的WordPress网站是否充分利用浏览器缓存:我们可以用GooglePageSpeedInsights或者Gtmetrix之类的网页工具去做一个测试,以我的博客为例,可以很清晰的看到网站各类文件缓存设置以及时间。如何手动配置WordPress浏览器缓存(两步)第一步:通过FTP访问你的网站我比较偏爱FileZilla,因为它包含了许多功能,使用起来相当简单。第二步:编辑  .htaccess 文件.htaccess 是一个WordPress核心文件,我们将使用  .htaccess 

  • 码云周一见 | 7 款不可错过的开源智能硬件架构

    近年来,不断有智能硬件产品刷新着我们对于未来生活的期待,从智能手机到智能手表,从智能手环到智能空气净化器,毫无疑问,智能硬件在互联网时代以一种令人惊异的速度飞速发展,并给我们生活带来了更多的方便和乐趣。今天,小一也带着满满的诚意,为大家带来十足的技术干货!来,为了码出新世界,干了这一碗“技术鸡汤”。一、项目名称:Cupkee智能硬件操作系统项目简介:Cupkee是一个C语言编写的智能硬件操作系统,它专门设计用于微控制器硬件板,并在其上构筑了类似nodejs的运行环境,同时在内部包含一个简化的javascript解释器作为shell。大多数硬件板不具备人机交互设施,而cupkee借用了板卡的usb作为console口,使用PC或Mac通过usb连接硬件板,使用常规的终端程序即可与cupkee进行交互,使得开发者可以随时对硬件编程并获得即时响应。它将板卡上的硬件资源抽象为设备,并定义了一组标准方法供开发者使用。项目地址:https://git.oschina.net/cupkee/cupkee二、项目名称:智能家居基础架构项目简介:智能家居的概念(smarthome,homeauto)很早

  • iphone如何导出微信聊天记录到电脑?

      有个小美眉买了个iphone,但发现自己就是一小白,很多功能都不会用,微信倒是用得挺上手的,可以晚上聊到三四点,流量直接飙升500MB。最近她说手机太卡了,问ytkah帮她整一下。拿起她的IPhone一看,微信聊天记录满满的都是,让她删了一些没用的消息记录又舍不得。好吧,那就折腾一下导出iphone微信聊天记录备份到电脑!这里要用到一个同步助手软件。  运行同步助手,并连接iPhone。切换页面至“更多功能”,点击资料分类的最后一个按钮【微信】,即可进入微信消息记录管理器查看聊天记录(支持微信3.5以上版本,微信5.0也能完美支持)  同步助手可直接查询微信聊天记录  1)只要点击左侧联系人,就会显示与他的聊天记录,包括文字,语音、图片等。  2)同步助手还提供了强大的搜索功能,可按具体日期精确查询,也可以按照时间段(最近一个月)来模糊搜索。还能根据关键字来定位某条信息,及查看前后消息  同步助手导出微信聊天记录(文本消息)  除了方便的查询功能,导出微信文本记录也很简单。点击左上角的【导出】按钮,可选择txt和Excel两种存储方式。相较而言,Excel方式更方便后期的查询。  

  • 教你一招 | Python装饰器的另类用法

    之前有比较系统介绍过Python的装饰器(请查阅《详解Python装饰器》http://betacat.online/posts/python-decorator/),本文算是一个补充。今天我们一起。 语法回顾开始之前我们再将Python装饰器的语法回顾一下。@decorate deff(...): pass复制等同于:deff(...): pass f=decorate(f)复制@语法的好处在于:相同的函数名只出现一次,避免了f=decorate(f)这样的语句。可读性更高,让读代码的人一眼就明白函数被装饰了哪些功能。@call()装饰器假设你要创建一个整数平方的列表,你可以这样写:>>>table=[0,1,4,9,16] >>>len(table),table[3] (5,9)复制也可以使用列表表达式,因为我们要实现比较简单。>>>table=[i*iforiinrange(5)] >>>len(table),table[3] (5,9)复制但是假如这个列表的逻辑比较复杂的时候,最好是写成一个方法,这样会更好

  • 动态调整日志级别思路&实现

    引言 上篇文章性能调优——小小的log大大的坑已将详细的介绍了高并发下,不正确的使用日志姿势,可能会导致服务性能急剧下降问题。文末也给各位留下了解决方案——日志级别动态调整。 本文将详细介绍“动态日志”的实现原理及源码,希望各位能在今后的生产环境中应对日志问题能“得心应手”! 背景 日志的重要性不言而喻,是我们排查问题,解决BUG的重要手段之一,但是在高并发环境下,又会存在悖论: 大量打印日志,消耗I/O,导致CPU占用率高;减少日志,性能是下来了,但是排查问题的链路断掉了。 痛点:一方面需要借助日志可快速排查问题,另一方面要兼顾性能,二者能否得兼? 那么本文的动态日志调整实现就是为了能解决这个痛点所构思开发的。 功能特性 低侵入,快速接入:以二方包(jar)的形式介入,只需要配置启用,对业务无感 及时响应,随调随改:应对研发不小心在大流量入口链路打印了大量INFO日志,能及时调整日志级别 阶梯配置支持:默认全局设置兜底,又可以支持局部Logger放/限流 人性化操作:与操作界面,方便修改 技术实现 如下,我将以log4j2为实例作讲解,其它日志实现大同小异,参照实现即可。 如下是

  • 什么是EDI?如何管理复杂、分层的数据?

    在帮助两家不同的医疗保险提供商进行功能测试自动化部署时,我发现了他们面临的来自EDI数据的挑战的一些共同点: 大多数EDI工作流程都是从实际文件投递开始的。模拟文件投递是一个挑战。 一个单一的交换可以是方言、版本和消息类型的组合。生成符合该特定模式的消息可能会很繁琐。 用数据驱动EDI消息是必要的。它可能会变得过于复杂,特别是在管理层次结构和数据类型时。 在这篇文章中,我将简单讲述测试人员在使用EDI时面临的这些挑战,以及如何开始用自动化测试来解决这些问题。 电子数据交换(EDI) 首先,让我们回到基础知识上来。EDI是一种消息格式标准,用于在商业实体之间沟通商业信息。企业过去使用纸张进行这些交易(即采购订单、发票,或者在医疗保健行业,例如,注册表格),这非常复杂,而且容易出错: 为了改善这一过程,EDI被设计成标准化的通信,并进行“无纸交易”: 不幸的是,虽然EDI改进了流程,允许公司以电子方式而不是用纸质方式发送信息,但EDI也带来了自己的挑战。最近,我已经能够使用一些软件测试工具来帮助解决这些问题,我也很高兴与你分享解决方案。 在EDI测试中(轻松!)管理数据 在最近的

  • 代码【注册】

    ;/*!/client/widget/login/login-form/login-form.js*/ define("passport:widget/login/login-form/login-form.js",function(require,exports,module){ "usestrict"; function_classCallCheck(instance,Constructor){ if(!(instanceinstanceofConstructor))thrownewTypeError("Cannotcallaclassasafunction") } var$=require("common:widget/lib/jquery/jquery"), handlebars=(require("common:widget/ui/utils/utils"),require("common:widget/lib/handlebars/handlebars")), MailSuggest=require("common:widget/ui/mailSuggest/mailSu

  • 排序算法总结及Java实现

    1.整体介绍 分类   排序大的分类可以分为两种,内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。主要需要理解的都是内排序算法:   内排序可以分为以下几类:   (1)、插入排序:直接插入排序、二分法插入排序、希尔排序。   (2)、选择排序:简单选择排序、堆排序。   (3)、交换排序:冒泡排序、快速排序。   (4)、归并排序   (5)、基数排序 性能对比 稳定性:就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。即如果A i==A j,A i 原来在 A j位置前,排序后 Ai  仍然是在 Aj 位置前。   不稳定:简单选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法   稳定:冒泡排序、直接插入排序、二分法插入排序,归并排序和基数排序都是稳定的排序算法。 时间复杂度:一个算法执行所耗费的时间。   O(nlogn):快速排序,归并排序,希尔排序,堆排序。   O

  • 【BZOJ】3160: 万径人踪灭 FFT+回文串

    【题意】给定只含'a'和'b'字符串S,求不全连续的回文子序列数。n<=10^5。 【算法】FFT+回文串 【题解】不全连续的回文子序列数=回文子序列总数-回文子串数。 回文子串数可以用回文串算法(Manacher,PAM,二分+hash)轻松计算。 设f[i]表示以i为对称中心的对称字符对数,那么i对答案的贡献是$2^{f[i]}-1$,同时容易列出f[i]的计算公式: $$f[i]=\sum_{j=0}^{i}[S_j=S_{2i-j}]$$ 令a=0,b=1,那么有: $$f[i]=\sum_{j=0}^{i}S_j*S_{2i-j}$$ 这是一个卷积的形式,将上届扩展到2*i就可以计算了,同理计算a=1,b=0。 同理计算以i和i+1中间为对称中心的答案。 也可以用manacher那种方式处理字符串。  

相关推荐

推荐阅读