Nameless Site

来源Leetcode第15题三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[

前略

计算机系统的性能评价

• 非时间指标
  • 机器字长
  • 总线宽度
  • 主存容量、存储带宽
  • CPU内核数
• 时间指标
  • 主频、周期、外频、倍频
  • CPI、IPC
  • MIPS、MFLOPS
  • CPU执行时间

非时间指标

机器字长：机器一次能处理的二进制位数

• 由运算器、寄存器的位数决定；
• 一般与内部寄存器的位数相等；
• 字长决定数据表示范围与精度；
• 目前常见的有32位和64位字长。

总线宽度：数据总线一次能并行传送的最大信息位数

• 运算器与存储器之间的数据总线位数。
• 有些计算机内部与外部数据总线宽度不一致：
• 8086、80286、80386内外数据总线等宽；
• Pentium外总线64位，内总线32位（两条32位流水线）

主存容量与存储带宽

• 主存容量：是指一台计算机主存所包含的存储单元总数。
• 存储带宽： 指单位时间内与主存交换的二进制信息量，单位Byte/s。
  (影响存储带宽的指标包括数据位宽和数据传输速率)。

时间指标

• 主频f
  • CPU工作的时钟频率，与CPU运算能力之间不是唯一的、直接关系；
• 时钟周期T = 1/f
  • 计算机中最基本的、最小的时间单位。一个时钟周期CPU仅完成一个最基本的动作；
• 外频
  • 系统总线的工作频率，CPU与主板之间同步运行的速度，标准外频66MHz、100MHz、133MHz、200MHz、400MHz
• 倍频
  • 主频=外频×倍频 ， Pentium 4 2.4G 主频 2400M = 133M (外频) × 18 (倍频)
  • 调整倍频可以获得较高的主频，486后出现的技术，使得外设低频，CPU高频

CPI (Clock cycles Per Instruction)

• 执行一条指令 (平均) 需要的时钟周期数
  • 单条指令CPI
  • 一段程序中所有指令的CPI
  • 指令系统CPI
    CPI = 一段程序中所有指令的时钟周期数之和 / 指令条数 //统计
    = 程序中各类指令的CPI * 程序中该类指令的比例 //加权

例1 假设一台计算机主频为1GHZ，在其上运行由2105条指令组成的目标代码，程序主要由4类指令组成，他们所占的比例和各自的CPI如下表所示，求程序的CPI和MIPS。
| 指令类型 | CPI | 指令比例 |
| :—————-: | :—: | :———: |
| 算术和逻辑 | 1 | 60% |
| Load/Store | 2 | 18% |
| 转移 | 4 | 12% |
| Cache缺失访存 | 8 | 10% |

解： CPI = 1*60% + 2*18% + 4*12% +8*10% = 2.24
MIPS = f/(CPI * 10^6) = 1*10^9/ (2.24 *10^6 ) = 446.4

MFLOPS (Million Floating-Point Operations Per Second)

• 计算机每秒钟执行浮点操作的次数
• MIPS：单位时间内执行的指令条数
• MFLOPS = 程序中的浮点运算次数 / (执行时间 * 10^6 ）
• MFLOPS (Mega) = 10^6 FLOPS GFLOPS (Giga) = 10^9 FLOPS
• TFLOPS (Tera) = 10^12 FLOPS PFLOPS (Peta) = 10^15 FLOPS
• EFLOPS (Exa) = 10^18 FLOPS

CPU执行

• 执行一段程序所需的时间
  ( CPU时间 + I/O时间 + 存储访问时间 + 各类排队时延等)
• CPU时间 = 程序中所有指令的时钟周期数之和 * T

     =程序中所有指令的时钟周期数之和 / f
  

  CPU 时间 = CPI * 指令条数 * 时钟周期
  CPU 时间 = 指令条数 / (MIPS * 10^6)

例1 假设一台计算机主频为1GHZ，在其上运行由2*10^5条指令组成的目标代码，程序主要由4类指令组成，他们所占的比例和各自的CPI如下表所示，求程序的CPI和MIPS，求程序执行时间？
| 指令类型 | CPI | 指令混合比例 |
| ——————- | —— | —————— |
| 算术和逻辑 | 1 | 60% |
| Load/Store | 2 | 18% |
| 转移 | 4 | 12% |
| Cache缺失访存 | 8 | 10% |

CPI = 2.24
MIPS = 446.4
CPU时间 = 2 *10^5 * CPI / f = (2 *10^5 * 2.24 / 10^9 ) = 4.48 *10^-4 (秒)
CPU时间 = 指令条数/MIPS*10^6 = 2 *10^5 / 446.44*10^6

关键时间指标

• 实际上频率和IPC真正决定CPU性能
• CPU性能=IPC × 频率 (MHz时钟速度)
  • 英特尔提出并被业界广泛认可

计算机性能测试

• 性能测试原理
  • 计算机中配置了大量传感器和状态寄存器
  • 通过读取相应寄存器的值得到系统运行的状况
  • 通过实际运行测试关键指标获取性能数据
• 性能测试工具分类
  • CPU测试工具
  • 显卡测试工具
  • 磁盘测试工具
  • 内存测试工具

来源Leetcode第14题最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:

来源Leetcode第12题整数转罗马数字

罗马数字包含以下七种字符：I，V，X，L，C，D和M。

来源Leetcode第11题盛最多的水

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
示例:

来源Leetcode第10题正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持’.’和’*‘的正则表达式匹配。
‘.’匹配任意单个字符
‘*‘匹配零个或多个前面的那一个元素
所谓匹配，是要 涵盖整个字符串s的，而 不是部分字符串s 。

来源Leetcode第80题删除排序数组中的重复项II

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

来源Leetcode第9题回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1: