博文

目前显示的是 2022的博文

真正的高手,都具備高度抽象能力

在之前的《编程究竟难在哪? 》,我们谈过编程思维,其实就是“理解问题——找出路径”的思维过程,它由分解—识别模式—抽象—算法四个步骤组成。 今天,想和大家探讨的是这其中最重要的一步——抽象能力。 (一)什么是抽象能力? 人们在实践中认识到,在现实世界中一定事物、状态或过程之间,总存在某些相似的方面,即共性。 把这些相似的方面集中和概括起来,暂时忽略它们之间的差异,这就是抽象。 比如,我们将10只十分熟悉的猫咪放入100只陌生的猫咪中,一开始仅靠形象记忆,就可轻而易举找到这10只猫咪,但如果把这10只熟悉的猫放入一千只、一万只、十万只陌生的猫群中,我们仅靠形象记忆找到猫的困难会越来越大,大到不可能。 如果在10只猫身体上都打上记号,事情立即会变得很简单。 这个打记号的过程,是抽象思维。 抽象思维在理解概念时,就是在给所指事物寻找记号,不过这个记号不是人为的,而是事物本身固有的,指的是事物的规律和本质。 当我们遇到从未见过的事物时,如果能够运用“抽象思维”去寻找记忆中的知识——现有的事物之间的联系,作为解决过程的关键要素,那么我们解决问题的效率将会大大上升。 《北大逻辑课》一书中,就讲了一个运用“抽象思维”解决现实问题的例子。 在大宋提刑官中,有这么一桩有名的案子: 有一天衙门接到报案,发现一民居失火,男主人与房屋都惨遭不幸,而女主人因为刚好有事离家,因此幸免于难。 正在女主人为丈夫的逝去而哭泣的时候,法医宋慈发现了尸体的异样:死者虽表层皮肤被烧毁,但口中十分干净,并无烟灰。于是断定这个案件并非意外事故,而是另有凶手隐瞒真相,死者是先被谋杀、后尸体被烧毁。 宋慈的推理过程是这样的: 取一活猪、一死猪一起放在火中烧着,取出后发现活猪被烧毁后口中有大量烟灰,而死猪口中十分干净,并无烟灰。 宋慈解释道:“之所以会如此,是因为动物在被火烧会发出激烈的自救运动,而剧烈运动会大量的呼吸氧气,同时,就必然会把烟灰吸入口中、肺中,例如我们过年烧的猪头,由于是死猪,口中就十分干净。” “同理,本案中死者的口中并无烟灰,因此可以推断,他在火灾发生前,就已经被人杀害了!” 宋慈之所以能做出这段推理,就是灵活运用抽象,从“猪遇火灾的反映”抽象出“口中有无烟灰是生物遇火时,是死或生的唯一标准”这一定理,并加以证明的结果。 一个抽象能力强的人,往往能从复杂的现象中直击事物的本质。也就是我们生活中常...

原码、反码、补码

图片
  关于补码的由来和作用 最近在读《深入理解计算机系统》(CSAPP),第二章中关于补码的描述很有意思,在书中并没有详细叙述补码的由来和为什么要使用补码来表示有符号数,而不是用原码和反码。相反这本书详细的叙述了补码的数学表示,以及公式的推导!对补码的由来却一笔带过,甚至原码和反码只是简单的在后面的篮框提示中提了一下,根本没有出现在正文。 这在一定程度上造成了我的阅读困难,于是在搜索引擎的帮助下,我查了很多资料,了解到补码的更多细节,以及这个神奇的编码方式如何帮助人们设计CPU时节省大量的精力和金钱。这里我把他记录下来。 计算机中的信息都是用二进制表示的,在表示无符号数时并没有什么问题,但是在表示有符号整数时就出现了问题,如何在二进制中区分正数与负数呢? 区分正数和负数的另一个意义在于如果能够准确的表示出、负数,我们就可以化减法为加法,如5-4就可以表示为5+(-4),至于为什么那么多先辈要执着于把减法化为加法,原因很简单,对计算机的电路而言,计算加法要比计算减法方便的多。 很多人提出了有符号整数的编码方式,其中有: 原码 (Sign-Magnitude)、 反码 (ones' Complement)、 补码 (two's Complement)。 原码 原码的英文为sign-magnitude,第一个单词为符号的意思,第二个单词经过查询有“大小”的意思,大意应该为 符号-数值 的组合,在原码中,第一个数字代表符号位,1代表负数,0代表正数,余下的为数值位,用来表示具体的数值。这种编码方式最 简洁易懂 ,也最 符合人的思维 。比如:-5用4位二进制原码来表示就是1101。 CSAPP中给出的原码数学公式为: 由此我们能推断出SMAX w =2 w-1 -1,SMIN w =-(2 w-1 -1)。如八位二进制原码的范围应该为[-127,127]。 实际上目前我们很少用原码来做运算,原码目前常常用来作为我们求补码的一个过渡。 反码 反码的英文为ones'complement,乍看之下有些迷惑,翻译过来是“很多个1的补”,似乎更迷惑了。。。 其实反码确实可以用“ 很多1的补 ”来理解,我们都知道w位二进制数表示的最大范围是2 w -1,用位向量来表示就是[111111....11111],就是很多个1。假设x是正数,求-x的补码的含义实际上就是求[...

Python海象运算符

 Python海象运算符号实在 PEP 572 中提出来的,并且在Python3.8版本引入。 英文名称是Assignment Expresions,即赋值表达式, 符号是  :=   我们称之为海象运算符(walrus operator)。 语法格式如下: variable_name := expression  或者 variable_name := value 就是变量名后跟一个表达式或者值,可以看成Python的新的赋值表达式(=也是Python的赋值表达式)。 用法: if else语句中 常规写法 a=15 if a>10:     print("hello world") 海象运算符写法: if a:=15>10:      print("hello world") while语句中: 常规写法: n=6 while n:      print("hello world")     n -=1 海象运算符写法: n=6 while (n:=n-1)+1:  #需要加1是因为在执行输出前n就减1了      print("hello world") 读取文件中 常规写法: fp=open("test.txt","r") while True:     line=fp.readline()     if not line: break     print(line.strip()) fp.close() 海象运算符写法: fp=open("test.txt","r") while line:=fp.readline():      print(line.strip()) 用于列表推导: nums = [16, 36, 49, 64] def f(x):     print('运行了函数f(x)1次。')     return x ** 0.5 print([f(i) for i in nums if f(i) > 5]) 一共...

搜索引擎和Lucene基础(第54天)

图片
 搜索引擎组件及其组件之间的关系: 搜索引擎如何搜索图片,或者pdf文件等二进制对象? 文档是由key-value组成的,key也叫做域。 文档分析本质就是切词。 Lucene 著名的搜索引擎中关于索引链的实现方案是Lucene Lucene可以把原始数据构建成文档,并作文档分析,创建出索引。 Lucene前端的著名实现有Elastic Search Lucene中的文档(document) 文档是包含了一个或多个域的容器。域在Lucene中称为field(field:value就是键值对)。 在搜索的时候,其实搜索的对象是value 域: 域有很多选项,包括索引选项、存储选项、域向量使用选项; 索引选项用于通过倒排索引来控制文本是否可被搜索:索引选项可取值有: Index:ANYLYZED:分析(切词)并单独作为索引项; ndex.Not_ANYLYZED:不分析(不切词),把整个内容当一个索引项; Index.ANYLYZED_NORMS:类似于Index:ANALYZED,但不存储token的Norms(加权基准)信息; Index.Not_ANYLYZED_NORMS:类似于Index:Not_ANALYZED,但不存储值的Norms(加权基准)信息; Index.NO: 不对此域的值进行索引;因此不能被搜索; 存储选项:是否需要存储域的真实值; title:This is a Notebook. store.YES:存储真实值 store.NO:不存储真实值 域向量选项用于在搜索期间该文档所有的唯一项都能完全从文档中检索时使用; 文档和域的加权操作:加权计算标准 搜索: 查询Lucene索引时,它返回的是一个有序的scoreDoc对象;查询时,Lucene会为每个文档计算出其score(评分,评分是根据加权计算来的); Lucene  提供的API有: IndexSearcher:搜索索引入口; Query及其子类: QueryParser:查询分析器 TopDocs :前几个 scoreDoc对象 ScoreDoc: Lucene的多样化查询: IndexSearcher类中的search方法;将输入的关键词封装成query对象,传递给search方法,具体的搜索方式有:TermQuery, TermRangeQuery,Nu...

libvrit管理kvm虚拟机和虚拟化网络(第52天)

 libvirt工具栈: libvirt支持管理的的虚拟化技术:KVM, XEN, VMWARE, Qemu,LXC, OpenVZ;  libvirt是一套用于管理硬件虚拟化的开源API、守护进程与管理工具。[3]此套组可用于管理KVM、Xen、VMware ESXi、QEMU及其他虚拟化技术。libvirt内置的API广泛用于云解决方案开发中的虚拟机监视器编排层(Orchestration Layer)。 支持管理本地和远程主机上的虚拟机。 所有被管理的Hypervisor都必须安装libvirtd服务 libvirt中的术语: node: 指物理节点 domain: vm instances(虚拟机实例),所以在libvirt中,域就是虚拟机实例 Hypervisor 安装: virt-manager(图形化管理工具)virt-install (cli程序)和libvirt-client(提供virsh,用于管理虚拟机) # yum install libvirt libvirt-client virt-install virt-manager 安装完后:查看 rpm -ql libvirt-daemon   (libvirt-daemon是主程序) libvirt和libvirtd的配置文件: libvirt配置文件:/etc/libvirt/libvirt.conf 守护进程libvirtd配置文件:/etc/libvirt/libvirtd.conf systemctl start libvirtd.service   启动服务 客户端工具: 服务启动之后可以使用客户端工具查看或管理虚拟机: 此处安装的客户端工具有(virt-manager和virsh和virt-install): virt-manager &    图形界面 virsh list (virsh是受欢迎的虚拟机管理工具) virsh --help  查看virsh帮助信息 virt-install的使用方法: virt-install 类似于qemu-kvm 使用virt-install创建虚拟机并安装GuestOS: virt-install是一个命令行工具,它能够为KVM、Xen...

KVM(第51天)

图片
 KVM:Kernel-based Virtual Machine 基于内核的虚拟机,依赖于HVM(比如intel VT-x, amd ADM-V),KVM寄宿于内核中。所以,把加载KVM模块的内核称之为Hypervisor,由此可知该Hypervisor直接运行于硬件平台之上,内核之上的用户空间还是原来的用户空间。创建出来的虚拟机运行于Hypervisor之上,有自己的内核和用户空间 KVM加载后的系统的运行模式: 内核模式:执行GuestOS的IO类操作,或者其他的特殊指令的操作,称为来宾的内核模式 来宾模式:执行GuestOS的非IO类操作,称为来宾的用户模式 用户模式:代表GuestOS请求IO类操作 KVM Hypervisor:加载KVM模块的内核 KVM的组件: /dev/kvm:工作于Hypervisor,在用户空间可通过ioctl()系统调用来完成VM创建,启动管理功能,他是一个字符设备,功能包括为VM分配内存,读写VCPU的寄存器,向VCPU注入中断,运行VCPU等等 qemu进程:工作于用户空间,kvm需要借助qemu模拟IO设备 KVM的特性: 内存管理:      支持将分配给VM的内存交换至SWAP      支持使用Huge Page      支持使用INTEL EPT和AMD RVI技术完成内存地址的映射:Guest虚拟地址到guest物理地址到宿主机物理地址     支持KSM(Kernel Same-page Merging) KVM继承了Linux系统管理内存的诸多特性,比如,分配给虚拟使用的内存可以被交换至交换空间、能够使用大内存页以实现更好的性能,以及对NUMA的支持能够让虚拟机高效访问更大的内存空间等。 KVM基于Intel的EPT(Extended Page Table)或AMD的RVI(Rapid Virtualization Indexing)技术可以支持更新的内存虚拟功能,这可以降低CPU的占用率,并提供较好的吞吐量。 此外,KVM还借助于KSM(Kernel Same-page Merging)这个内核特性实现了内存页面共享。KSM通过扫描每个虚拟机的内存查找各虚拟机间相同的内存页,并将这些内存...

Xen(第50天)

 Xen Xen属于type-I虚拟化类别,Xen hypervisor直接运行于硬件平台上,运行于Xen hypervisor之上的操作系统都属于guest . 但是Xen仅仅虚拟化了CPU和内存,IO设备并没有虚拟化,Xen hypervisor上第一个guest有管理其他guest的权限和操作接口,第一个guest的内核管理硬件上的IO设备,支持网络设备和块设备,对于这些IO设备的访问支持半虚拟化,设备被抽象成net-frond,net-backend, block-frond, block-backend,其中前端存在于各guest中。 第二个,第三个等等的guest需要使用CPU和内存时向Xen hypervsior申请,需要使用IO设备时向第一个guest申请,该guest必须借助于qemu模拟出IO设备 第一个guest被称为Domain0(Privilleged Domain ),其他的成为DomainU(Unprivilleged Domain) ,有各自的ID。 Dom0提供管理其他DomU的工具栈,用于实现对虚拟机进行添加,启动,快照,停止,删除等操作。 DomU属于非特权域,支持PV(半虚拟化),HVM(硬件辅助虚拟化)和PV on HVM 3种虚拟技术。 Xen的PV技术:不依赖于CPU的hvm特性,但是要求GuestOS的内核做出修改以知晓自己运行于PV环境,运行于DomU中的OS有linux(2.6.24+),NetBSD,FreeBSD, OpenSolaris Xen的HVM技术,依赖于Intel VT或AMD-V,还要依赖于Qemu来模拟IO设备,运行于DomU中的OS有,几乎所有支持此X86平台的操作系统 PV on HVM:CPU为HVM模式运行,IO设备为PV模式运行,运行于DomU的OS有,只要OS能驱动PV接口类型的IO设备,net-front, block-front Xen的工具栈: xm/xend:在Xen Hypervisor的Dom0中要启动xend服务 xm:是命令行工具,有诸多子命令,比如creat, destroy,stop,pause xl:基于libxenlight提供的轻量级的命令行工具栈 xe/xapi:提供了对xen管理的api,因此用于cloud环境:比如Xen Server, XCP...

Linux虚拟化技术(第49天)

操作系统原理 系统调用:操作系统提供的调用接口 库:库是对系统调用的封装 用户态和内核态 x86指令分4层:ring0,ring1,ring2, ring3 MMU:内存管理单元,主要用于内存分页 寄存器:cpu内部保持数据的元器件 cpu缓存:一级缓存,二级缓存,三级缓存 IO设备:包括控制器和设备 控制器:集成在主板上的芯片 驱动程序:通常由设备生产商提供 每个控制器都集成少量的用于通信的寄存器:内核调用驱动程序进行读写操作,驱动程序会操作控制器对设备进行读写。 IO端口空间:所有IO设备的控制器上的寄存器集合,每一个寄存器表现为一个IO端口,被映射到内存中,每一个IO端口的都有一个独立的地址 中断:主板上的可编程中断控制器 中断号:IO设备的控制器在系统启动时要向中断控制器注册一个中断号,当IO设备有读写请求时,向中断控制器发出中断请求,中断控制器通知CPU,CPU发起中断切换。 中断分为中断上部,中断下部。 中断上部:将IO设备缓存中的内容copy到内核内存中 DMA:直接内存访问,完成中断上部。 虚拟地址 物理地址 虚拟化技术: 将计算机资源分割 cpu的虚拟化的技术:模拟和虚拟 模拟:软件模拟,emulation,宿主机架构和guest架构可以不一样,必须模拟出来ring0, ring1, ring2,ring3 虚拟:virtualization,guest并不知自己运行于虚拟机中,必须模拟出来一个特权环境,各guest内核运行于宿主机的ring1,当guest主机运行特权指令时候可以进行二进制翻译,把指令翻译为宿主机的特权指令运行之。 HVM:硬件辅助虚拟化技术:intel vt技术 宿主机运行于ring-1级,各guest用户态进程运行于ring3, guest内核态运行于ring0。 半虚拟化技术:para-virtualization 在硬件上运行hypervisor,也就是vm monitor,hypervisor直接管理硬件,hypervisor虚拟一层hyper call, 各guest的内核进程可以直接调用hyper call。各guest的内核必须做相应的调整,才能适配对hyper call的调用,所以guest是知道hyper call的存在的 Memory的虚拟: intel EPT技术:extended page table,M...