2012.10 颜然/韩富晟 yanran.hfs@taobao.com @韩富晟 如何赢一个机械键盘 2012.10 颜然/韩富晟 yanran.hfs@taobao.com @韩富晟.

Slides:



Advertisements
Similar presentations
定 格 入 格 破 格 —— 新诗仿写复习训练 仿照下列句子,再把 “ 人生 ” 比喻成 “ 大海 ”“ 天空 ” , 造两个句子。 如果说人生是一首优美的乐曲,那么痛苦则 是其中一个不可或缺的音符。 参考答案: 1 、如果说人生是一望无际的大海,那么挫折则 是其中一个骤然翻起的浪花。 2 、如果说人生是一片湛蓝的天空,那么失意则.
Advertisements

《微型计算机技术 及应用》 ( 第 4 版) —— 戴梅萼 史嘉权. 目标 深刻理解 牢固掌握 灵活应用.
大學甄選入學 個人申請面試技巧 黃仁竑 教授 中正大學資工系. 大綱 面試目的 面試流程 面試技巧 ( 注意事項 ) 結語.
勞動檢查常見違法案例說明 臺中市政府勞工局.
两岸文化 迷你剧 《我们恋爱吧》.
从永磁体谈起.
有关“政治课”与“政治”.
国外住房保障制度 比较及对我国的启示 石运玲 延边州委党校公共管理教研部教授.
指導教授: 黃淑卿 教授 組員: 4980P018 黃梓婷 4980P011 薛琇萍 4980P077 陳佳蓉 4991P025 池靜怡
說明單位:實習暨就業輔導組 地點:延平技術大樓1樓109教室 時間:105/6/1,中午12:10
獨角仙&樹木銀行 生態之旅 製作人:陳芳玲 蔡維其 樹木銀行 獨角仙農場.
中央预算单位公务卡 产品介绍.
电磁铁.
3-3電磁鐵的運用.
计算机组装与维护 项目一 个人计算机的合理配置 任务三 CPU识别与选购(内存、硬盘).
第四章 存储系统 计算机科学技术系 2006 年 4 月.
Q&A 百萬小學堂.
安 全 維 護 臺 東 林 區 管 理 處 消費安全 詐騙防範宣導 健康生活 毒家新聞 杜絕不明匯款及金融轉帳操作
第5章 排序与查找 PART A 《可视化计算》.
网络教育(综合类)本学期教学工作 网络教育办公室:周学斌.
第2章:企業組織 張緯良 世新大學資訊管理系.
第8章 机床操作 主讲:臧红彬 博士.
第四章 存储体系.
親職學習多面體 中學篇 第四課 管教之道 (二) 1 1.
第九章 排序 插入排序 交换排序 选择排序 归并排序 基数排序.
基隆市立八斗高中 102 學年度第二學期 402 班『親師座談』
5.1 存储器的层次结构 从单级存储器到多级存储器 第五章 存储层次 1. 从用户的角度来看,存储器的三个主要指标是:
陋室铭 刘禹锡 P 173.
Chapter 13 輸入/輸出系統 (I/O Systems)
臺北市天主教光仁小學 103學年度 上學期學校日 六年級教學團隊製作.
幼儿园教学工作会议精神执行 ING…… 虹 口.
寫 作 教 學 6 電腦與我 時代改變,科技進步,電腦成為日常生活不可或缺的設備。我是二十一世紀的E世代少年,一隻滑鼠在手,樂趣無窮。
長者日 每年 11月第三個星期日 表達對長者的敬意 宣傳關懷長者的訊息.
課程名稱:資料結構 授課老師:_____________
陋室铭 作者:刘禹锡.
陋室铭 作者:刘禹锡.
計算機概論 第4章 從主機板看電腦的世界.
數位邏輯的基礎.
淘宝核心系统数据库组 余锋 利用新硬件提升数据库性能 淘宝核心系统数据库组 余锋
本节我们结合AD5724驱动时序给大家介绍一下状态机在实际工程中的使用。
第五章 存储系统 半导体存储器概述 系统内存扩充 高速缓冲存储器 虚拟存储器 PC系列机中的主存储器 习题与思考 上一章 目 录 帮助
排序 Sorting.
快速排序法 (Quick Sort).
第9章 排序.
第十章 排序與搜尋.
作業系統 第八章 記憶體管理.
Data Structure(資料結構) 授課老師: 蕭志明 助理教授 Ext:6779
华南理工大学 陈虎 博士 CUDA编程模型 华南理工大学 陈虎 博士
单片机应用技术 项目一 循环彩灯装置 第2讲 51单片机的结构与引脚 《单片机应用技术》精品课程组 湖北职业技术学院机电工程系.
第8章 記憶體管理的概念.
第二章 電腦硬體知識 2-1 電腦的組成與架構 2-2 處理器 2-3 記憶體 2-4 輸入與輸出裝置 2-5 電腦的操作與保養.
基數排序法.
Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort
組合語言和程式範例.
計算機概論 第3章 計算機組織與結構概觀.
探討台灣保險業公益活動之效益 -以國泰人壽與安泰人壽為例
第8章 資料排序 資料結構設計與C++程式應用
第一章.
计算机系统结构(2012年春) ----存储层次: Cache基本概念
第九章 排序 概述 插入排序 快速排序 交换排序(起泡排序) 选择排序 归并排序.
第六章 記憶體.
GPU based online noise filtering algorithm in LHASSO-WCDA
核心系统数据库组 了解应用服务器 核心系统数据库组
陣列 東海大學物理系‧資訊教育 施奇廷.
北一女中 資訊選手培訓營 遞迴、河內塔與merge sort Nan.
墨水瓶、油漆桶 Flash 提供了墨水瓶工具 (Ink Bottle Tool) 和油漆桶工具 (Paint Bucket Tool) 2 種填色工具, 一個用來填筆畫顏色, 另一個則是用來填填色區域。 使用鉛筆工具 (Pencil Tool)、線段工具 (Line Tool) 所繪製的筆畫,
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
資料結構 老師:李崇明 助教:楊斯竣.
知识点4---向量的线性相关性 1. 线性相关与线性无关 线性相关性的性质 2..
县级支中心 乡镇基层服务点的建设 朱 庆 华.
Presentation transcript:

2012.10 颜然/韩富晟 yanran.hfs@taobao.com @韩富晟 如何赢一个机械键盘 2012.10 颜然/韩富晟 yanran.hfs@taobao.com @韩富晟

题纲 什么样的比赛 解决问题的步骤 影响程序性能的因素 优化实践

什么样的比赛 排序267751个单词 单词存储在文件中,每行一个单词 运行结果输出到文件中 不限制运行环境 不限制语言 以运行时间短作为获胜标准

解决问题的步骤 从文件读取数据 切分单词 排序 合并单词 输出结果到文件

影响程序性能的因素 影响程序性能的因素: 选择好的算法 利用多核并发处理 让程序与机器架构更友好

排序算法的选择 考虑时间复杂度和能否多线程化 思考:多种算法的组合 数据结构 时间复杂度 多线程化 Quicksort O(NlogN) 是 Merge sort Heapsort 否 Bubble sort O(N^2) Bucket sort O(N + K)* * K是元素的长度

并发 CPU核数越来越多

并发 尽可能将所有步骤并行化,充分利用CPU的计算资源 注意阿姆达定律所给的启示 一端单核运行1分钟的程序,有30秒可以被并行优化,另外30秒不能并行优化,那么并行优化的极限,运行时间也不能小于30秒

认识CPU Cache CPU与内存之间巨大的速度鸿沟 访问内存有时间上和空间上的局部性 一些数据 Cache Line Size: 64Bytes L1 Cache Lentency: ~1ns Memory Lentency: 60~100ns

认识CPU Pipeline Branch Predication 一条指令分成多个步骤执行 CPU内部指令级别的并行 不确定的分支,虚函数等损伤性能 一次分支预测误判: 5ns

优化程序性能的步骤 正确地测量程序的性能是最基础,同时也是最容易被忽视的步骤 设计测试场景(排除环境干扰,固化测试场景) 测量优化前程序的性能 优化ing 测量优化后程序的性能

排序程序并行化 … 并行化 从文件读取数据 切分单词 排序 合并单词 输出结果到文件 从文件读取数据 切分单词 快速排序 输出结果到文件 若干次归并排序* 合并单词 * 并行化

排序程序耗时分布

数据结构的优化 267751个单词里最长的16个字符 两个8字节的整形可以存下 极大的提高比较操作的性能:最重要的优化之一

数据结构的优化

数据结构的优化-计算长度 这个算法的优点和缺点?

归并排序的优化 不使用通用的算法,针对两路归并做优化,减少比较次数

颜然/韩富晟 yanran.hfs@taobao.com @韩富晟 谢谢