精华内容
下载资源
问答
  • 存储器的层次关系

    2020-12-15 22:56:54
    一、前言 自己在复习校招时候由于...JVM中类加载三个步骤加载、链接、初始化,深入到底什么意思?等等问题,想要回答更加准确和深入,就需要一定计组基础了。其实很知识面试我也是背下来,只不过学时候,

    一、前言

    自己在复习校招时候由于转行,时间有限,计组并没有完整的学过,我的策略是学到哪个需要的知识点就回头看一下。当时我还不太懂计组的意义,感觉软件工程师只要能顺利coding就好了,校招过程直截了当地问计组的情况其实并不多。但是当面试官很多问题深入追问的时候,比如,为什么用吞吐率和响应时间考量程序的性能?volitale关键字是什么作用?JVM中类加载的三个步骤加载、链接、初始化,深入到底什么意思?等等问题,想要回答的更加准确和深入,就需要一定的计组基础了。其实很多知识面试我也是背下来的,只不过学的时候,知识没成体系,没有感触而已。到后面学了一定计组的知识,回想曾经学的,才感觉到豁然开朗。

    实习时候的leader强烈推荐我,好好学一学计组的知识。现在回头来看,其实计组确实相当有意义的课程之一,现在也在逐渐学习的过程中,我的感受是,这门课完全可以用一个词来概括,就是“抽象”。在我看来“抽象”一词,这也是整个计算机设计中所蕴含的的灵魂。计算机组成原理,就是围绕着计算机是如何组织运作展开的。也许当妹子咨询你电脑问题的时候,答案就藏在这门课程里面(大雾)。

    计算机,显式来看是有CPU,内存,主板等硬件组成的设备。但是我们从事的软件开发工作。显然,计算机组成原理就是隔离了软件和硬件,并且提供了软件硬件接口。实际上计算机内部的晶体管和电路,完全不知道自己做了什么,人们把他们不同的状态抽象成0和1的概念,进行逻辑运算,然后用这些逻辑运算我们可以用二进制的形式表示数值运算,再结合这些运算,就产生了一条条指令,最后把这些电路统一成CPU,实际上都是一层一层的抽象。最上一层的抽象可以轻松供我们使用,而不需要每次都关注0或者1。层层抽象的过程中,每一层完成自己的任务,同时又提供更高层次的抽象。

    学完计组后,对之前学的一些知识的细节确实有一种豁然开朗的感觉。不过计组的知识体系很庞大,我也在逐渐学习的过程中。应对校招的话,如果时间有限,可能也并不需要学习那么全面。

    接下来我准备记录一下自己关于计组的学习笔记和思考。主要是CPU篇,内存篇等,最后会总结成一个面向校招的笔记~敬请期待

    二、计算机主要的硬件组成

    CPU(Central Processing Unit)

    CPU即中央处理器(Central Processing Unit),可以说是计算机中最重要的配件之一,因为计算机所有的计算都是由CPU来完成的。

    而硬件层面上来看,CPU就是一个超级精细的印刷电路板。

    内存(Memory)

    内存(Memory)也是学习和面试中经常出现的字眼。我们运行的程序,比如跑的代码,玩的游戏,看的视频,都要加载到内存中,才能正常运行。总而言之,计算机所有程序的运行都在内存中运行

    从硬件层面来看,内存就是我们所说的内存条,由内存芯片,电路板等元件组成。

    存放在内存里的程序和数据,需要被 CPU 读取,CPU 计算完之后,还要把数据写回到内存。那么CPU究竟是如何和内存进行数据交换的呢?两块单独的电路板是无法直接交换数据的。因此,有了另外一个重要的硬件——主板

    主板(Motherboard)

    主板是一个有着各种各样,有时候多达数十乃至上百个插槽的配件。我们的 CPU 要插在主板上,内存也要插在主板上。主板的芯片组(Chipset)和总线(Bus)解决了 CPU 和内存之间如何通信的问题。芯片组控制了数据传输的流转,也就是数据从哪里到哪里的问题。总线则是实际数据传输的高速公路。因此,总线速度(Bus Speed)决定了数据能传输得多快。

    有了这些,再加上曾经大计基学过的,一些IO设备,显卡,GPU等就可以组成一台完整的计算机了。

    三、存储器层次结构

    CPU的寄存器

    从硬件角度来看,寄存器就是 CPU 内部,由多个触发器(Flip-Flop)或者锁存器(Latches)组成的简单电路。(触发器和锁存器,其实就是两种不同原理的数字电路组成的逻辑门,这是数电的概念,简单了解即可)

    一个 CPU 里面会有很多种不同功能的寄存器。给你介绍三种比较特殊的。

    1. PC 寄存器(Program Counter Register),它就是用来存放下一条需要执行的计算机指令的内存地址。(学过JVM的小伙伴是不是看到这里很亲切,JVM中的程序计数器和这个一模一样,因为JVM就是是一种利用软件方法实现的,抽象的计算机基于下层的操作系统和硬件平台)

    2. 指令寄存器(Instruction Register),用来存放当前正在执行的指令。

    3. 条件码寄存器(Status Register),用里面的一个一个标记位(Flag),存放 CPU 进行算术或者逻辑计算的结果。

    也就是说,寄存器实际上也是一种存储器,但是它更像是CPU的一部分,只能存放有限的信息,但是它的速度十分快,几乎与CPU同步

    CPU缓存(面试经常问)

    首先,缓存只是一种非常快速的内存类型,小伙伴们应该不陌生了。面试用经常问到如何加快数据库热点数据访问速度,我们一定绕不开Redis这个缓存中间件。而计算机内部有多种内存类型,比如缓存,比如主存储(常说的硬盘或者SSD)用于存储大量数据(操作系统和所有程序)。

    那么缓存是怎么来的呢?

    按照摩尔定律,CPU 的访问速度每 18 个月便会翻一番,相当于每年增长 60%。内存的访问速度虽然也在不断增长,却远没有这么快,每年只增长 7% 左右。长此以往导致CPU和内存的速度差异越来越大。为了弥补两者之间的性能差异,更好的利用CPU性能,我们在现代 CPU内部引入了高速缓存,也就是CPU Cache。

    从硬件角度看,CPU Cache 用的是一种叫作SRAM(Static Random-Access Memory,静态随机存取存储器)的芯片。

    SRAM

    SRAM(Static Random-Access Memory,静态随机存取存储器),之所以是静态的,是因为只要通电,内部的数据就可以存在。而一旦断电,数据也就丢失了。是不是看起来不太安全?但是设计简单的好处就是用起来更方便。在SRAM中,数据存储密度并不高,而且存储的数据有限。但是正是由于SRAM的结构简单,所以数据访问速度十分快。

    那么既然有静态随机存取存储器是否也有动态随机存储器呢?接着往后看

    CPU缓存如何工作?

    我们已经知道,程序被设计为一组指令,最终由CPU运行。当我们运行程序的时候,这些指令必须从主存储器取指令到CPU。这是内存层次结构起作用的地方。

    由于内存和CPU运行速度差异过大,所以数据需要首先被加载到SRAM中,然后被发送到CPU。因为CPU每秒都能够执行大量指令。为了充分利用其功能,CPU需要访问超高速内存,这是缓存的来源。

    高速缓存在CPU内执行数据的来回传输。内存和缓存不断进行交互。

    CPU缓存级别:L1,L2和L3

    CPU缓存分为三个主要的级别,即L1,L2和L3

    • L1 的 Cache 往往就嵌在 CPU 核心的内部。
    • L2 的 Cache 同样是每个 CPU 核心都有的,不过它往往不在 CPU 核心的内部。所以,L2 Cache 的访问速度会比 L1 稍微慢一些。
    • L3 Cache,则通常是多个 CPU 核心共用的,尺寸会更大一些,访问速度自然也就更慢一些。

    内存

    DRAM

    之前说了CPU内部高速缓存用的SRAM,结构简单,数据存储量小,但是速度十分快。而内存就是用的**DRAM(Dynamic Random Access Memory,动态随机存取存储器)**的芯片,比起 SRAM 来说,它的密度更高,有更大的容量,而且它也比 SRAM 芯片便宜不少。DRAM 被称为“动态”存储器,是因为 DRAM 需要靠不断地“刷新”。所以,DRAM 在同样的物理空间下,能够存储的数据也就更多,也就是存储的“密度”更大。但是,因为数据是存储在电容里的,电容会不断漏电,所以需要定时刷新充电,才能保持数据不丢失。DRAM 的数据访问电路和刷新电路都比 SRAM 更复杂,所以访问延时也就更长。

    这样,各个存储器只和相邻的一层存储器打交道,并且随着一层层向下,存储器的容量逐层增大,访问速度逐层变慢,而单位存储成本也逐层下降,也就构成了我们日常所说的存储器层次结构。

    外部存储(外存)

    SSD(Solid-state drive 或 Solid-state disk,固态硬盘)、HDD(Hard Disk Drive,硬盘)这些被称为硬盘的外部存储设备

    SSD 固态硬盘是基于NAND 芯片的高速硬盘。而 HDD 硬盘则是一种完全符合“磁盘”这个名字的传统硬件。“磁盘”的硬件结构,决定了它的访问速度受限于它的物理结构,是最慢的。

    因此,一般我们装电脑时候,都是用固态硬盘来装系统盘,用机械硬盘来存储其他数据,也是同样的道理。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wOodNVCz-1608043614501)(../../AppData/Roaming/Typora/typora-user-images/image-20201213225410655.png)]

    四、总结

    ​ 我画了一张金字塔图,大家可以对照着看一下,从CPU 、内存,到 SSD 和 HDD 硬盘。其中,容量越小的设备速度越快,而且,CPU 并不是直接和每一种存储器设备打交道,而是每一种存储器设备,只和它相邻的存储设备打交道

    这样,各个存储器只和相邻的一层存储器打交道,并且随着一层层向下,存储器的容量逐层增大,访问速度逐层变慢,而单位存储成本也逐层下降,也就构成了我们日常所说的存储器层次结构。

    展开全文
  • 程序员十大层次

    2011-08-23 08:57:28
    觉得这篇文章写的还蛮意思,全篇很长我简要的把该文改写一下,以突出十个层次的区别: 中国的程序员水平比西方程序员水平差,还是中国有许多优秀的程序员达到或超过了西方程序员 同等水平呢?要解决这个问题,必须...

     程序员的十个层


    觉得这篇文章写的还蛮意思,全篇很长我简要的把该文改写一下,以突出十个层次的区别:
    中国的程序员水平比西方程序员水平差,还是中国有许多优秀的程序员达到或超过了西方程序员
    同等水平呢?要解决这个问题,必须先知道程序员有多少种技术层级,每个层级需要什么样的技
    术水平,然后再比较中国和西方在各个技术层级的人数,就可以知道到底有没有差距,差距有多
    大。
    当然,对于如何划分程序员的技术层级,不同公司或不同人会有不同的划分标准,下面的划分仅
    代表个人的观点,如有不当之处,还请砸板砖予以纠正。
    一、菜鸟
    第1 层楼属于地板层,迈进这层楼的门槛是很低的。基本上懂计算机的基本操作,了解计算
    机专业的一些基础知识,掌握一门基本的编程语言如C/C++,或者Java,或者JavaScript,...,
    均可入门迈进这层。
    二、大虾
    从第1 层爬到第2 层相对容易一些,以C/C++程序员为例,只要熟练掌握C/C++编程语言,
    掌握C 标准库和常用的各种数据结构算法,掌握STL 的基本实现和使用方法,掌握多线程编程
    基础知识,掌握一种开发环境,再对各种操作系统的API 都去使用一下,搞网络编程的当然对
    socket 编程要好好掌握一下,然后再学习一些面向对象的设计知识和设计模式等,学习一些测
    试、软件工程和质量控制的基本知识,大部分人经过2~3 年的努力,都可以爬到第2 层,晋升
    为"大虾"。
    三、牛人
    由于"大虾"们经常被一些疑难问题给卡住,所以有了"大虾"们只好继续学习,他们需要将原
    来所学的知识进一步熟练掌握,比如以熟练掌握C++编程语言为例,除了学一些基础性的C++
    书籍如《C++ Primer》,《Effective C++》,《Think in C++》,《Exception C++》等之外,更重要
    的是需要了解C++编译器的原理和实现机制,了解操作系统中的内部机制如内存管理、进程和
    线程的管理机制,了解处理器的基础知识和代码优化的方法,此外还需要更深入地学习更多的数
    据结构与算法,掌握更深入的测试和调试知识以及质量管理和控制方法,对各种设计方法有更好
    的理解等。
    学习上面说的这些知识不是一挥而就的,不看个三五十本书并掌握它是做不到的。以数据结
    构算法来说,至少要看个5~10 本这方面的著作;以软件设计来说,光懂结构化设计、面向对
    象设计和一些设计模式是不够的,还要了解软件架构设计、交互设计、面向方面的设计、面向使
    用的设计、面向数据结构算法的设计、情感化设计等,否则是很难进到这个楼层的。
    四、大牛
    从第3 层爬到第4 层可不像上面说过的那几层一样容易,要成为大牛的话,你必须要能做
    牛人们做不了的事情,解决牛人们解决不了问题。比如牛人们通常都不懂写操作系统,不会写编
    译器,不懂得TCP/IP 协议的底层实现,如果你有能力将其中的任何一个实现得象模象样的话,
    那么你就从牛人升级为"大牛"了。
    当然,由于各个专业领域的差别,这里举操作系统、编译器、TCP/IP 协议只是作为例子,
    并不代表成为"大牛"一定需要掌握这些知识,以时下热门的多核编程来说,如果你能比牛人们更
    深入地掌握其中的各种思想原理,能更加自如的运用,并有能力去实现一个象开源项目TBB 库
    一样的东西,也可以成为"大牛",又或者你能写出一个类似Apache 一样的服务器,或者写出一
    个数据库,都可以成为"大牛"。
    当"牛人"晋升为"大牛",让"牛人们"发现有比他们更牛的人时,对"牛人"们的心灵的震撼是可
    想而知的。由于牛人们的数量庞大,并且牛人对大虾和菜鸟阶层有言传身教的影响,所以大牛们
    通常能获得非常高的社会知名度,几乎可以用"引无数菜鸟、大虾、牛人竞折腰"来形容,看看前
    面提过的Linus Torvalds 等大牛,应该知道此言不虚。
    虽然成为"大牛"的条件看起来似乎很高似的,但是这层楼并不是很难爬的一层,只要通过一定的
    努力,素质不是很差,还是有许多"牛人"可以爬到这一层的。由此可知,"大牛"这个楼层的人数
    其实并不像想像的那么少,例如比尔·盖茨之类的人好像也是属于这一层的。
    五、专家
    当大牛们真正动手做一个操作系统或者类似的其他软件时,他们就会发现自己的基本功仍然有很
    多的不足。以内存管理为例,如果直接抄袭Linux 或者其他开源操作系统的内存管理算法,会被
    人看不起的,如果自动动手实现一个内存管理算法,他会发现现在有关内存管理方法的算法数量
    众多,自己并没有全部学过和实践过,不知道到底该用那种内存管理算法。
    看到这里,可能有些人已经明白第5 层楼的奥妙了,那就是需要做基础研究,当然在计算机里,
    最重要的就是"计算"二字,程序员要做基础研究,主要的内容就是研究非数值"计算"。
    非数值计算可是一个非常庞大的领域,不仅时下热门的"多核计算"与"云计算"属于非数值计算范
    畴,就是软件需求、设计、测试、调试、评估、质量控制、软件工程等本质上也属于非数值计算
    的范畴,甚至芯片硬件设计也同样牵涉到非数值计算。如果你还没有真正领悟"计算"二字的含义,
    那么你就没有机会进到这层楼来。
    六、学者
    当"专家"们想继续往上一层楼爬时,他们几乎一眼就可以看到楼梯的入口,不过令他们吃惊的是,
    楼梯入口处竖了一道高高的门槛,上面写着"创新"二字。不幸的是,大多数人在爬到第5 层楼时
    已经体能消耗过度,无力翻过这道门槛。
    以查找为例,并不是去天天盯着那些复杂的查找结构和算法进行研究,你需要做的是将二分查找、
    哈希查找、普通二叉树查找等基础性的知识好好地复习几遍。
    以哈希查找为例,首先你需要去将各种冲突解决方法如链式结构、二次哈希等编写一遍,再试试
    不同种类的哈希函数,然后还需要试试在硬盘中如何实现哈希查找,并考虑数据从硬盘读到内存
    后,如何组织硬盘中的数据才能快速地在内存中构建出哈希表来,...,这样你可能需要将一个哈
    希表写上十几个不同的版本,并比较各个版本的性能、功能方面的区别和适用范围。
    总之,对任何一种简单的东西,你需要考虑各种各样的需求,以需求来驱动研究。最后你将各种
    最基础性的查找结构和算法都了然于胸后,或许某天你再看其他更复杂的查找算法,或者你在散
    步时,脑袋里灵光一现,突然间就发现了更好的方法,也就从专家晋升为"学者"了。
    七、大师
    从第6 层楼爬到第7 层楼,并没有多少捷径可走,主要看你有没有足够的能量。你如果能象Hoare
    一样设计出一个快速排序的算法;或者象Eugene W. Myers 一样设计出了一个用编辑图的最短
    路径模型来解决diff 问题的算法;或者象M.J.D. Powell 一样提出了一个能够处理非线性规划问
    题的SQP 方法;或者你发现基于比较的排序算法,它的复杂度下界为O(NLogN);或者你发现
    用栈可以将递归的算法变成非递归的;或者你设计出一个红黑树或者AVL 树之类的查找结构;
    或者你设计出一个象C++或Java 一样的语言;或者你发明了UML;...,你就爬到了第7 层,晋
    升为"大师"了。
    八、科学家
    科学家向来都是一个神圣的称号,因此我把他放在了“大师”之上。要成为科学家,你的贡献必须
    超越大师,不妨随便举一些例子。
    如果你象Dijkstra 一样设计了ALGOL 语言,提出了程序设计的三种基本结构:顺序、选择、循
    环,那么你可以爬到第8 层楼来。顺便说一下,即使抛开这个成果,Dijkstra 凭他的PV 操作和
    信号量概念的提出,同样可以进到这层楼。
    如果你象Don Knuth 一样,是数据结构与算法这门学科的重要奠基者,你也可以进到这层楼来。
    当然,数据结构和算法这门学科不是某个人开创的,是许多大师和科学家集体开创的。
    如果你象巴科斯一样发明了Fortran 语言,并提出了巴科斯范式,对高级程序语言的发展起了重
    要作用,你也可以进到这层楼来。
    九、大科学家
    进入这层楼的门槛通常需要一些运气,比如某天有个苹果砸到你头上时,你碰巧发现了万有引力,
    那么你可以进到这层楼来。当然,万有引力几百年前就被人发现了,如果你现在到处嚷嚷着说你
    发现了万有引力,恐怕马上会有人打110,然后警察会把你送到不正常人类的聚集地去。因此,
    这里举万有引力的例子,只是说你要有类似的成就才能进到这层楼来。
    当然,程序员们最关心的是自己有没有机会变成大科学家。既然计算机这门大学科的开创性成果
    早就被冯·诺伊曼、图灵等人摘走了,那么程序员们是不是没有机会变成大科学家了呢?我们的
    古人说得好:“江山代有才人出,各领风骚数百年”,现在在计算机这门学科下面诞生了许多非常
    重要的大的分支,所以你还是有足够的机会进到这层楼的。
    如果你能够彻底解决自然语言理解(机器翻译)这门学科中的核心问题, 或者你在人工智能或
    者机器视觉(图像识别)方面有突破性的发现,那么你同样可以轻易地晋升为“大科学家”。这
    样当某天你老了去世时,或许那天国人已经觉醒,你也能享受到如Dijkstra 一样的待遇,有满城
    甚至全国的人去为你送葬。
    十、大哲
    看了这层楼的名字“大哲”,可能不少人已经猜到了这层楼的秘密,那就是你的成果必须要上升到
    哲学的高度,你才有机会能进到这层来。
    当然,上升到哲学高度只是一个必要条件,牛顿的万有引力似乎也上升到了哲学的高度,因为不
    知道引力到底是怎么来的,但是牛顿没有被划到这一层,因为进到这层还有另外的条件,那就是
    你的成果必须引起了哲学上的深度思考,并能让人们的世界观向前跨进一大步。窃以为牛顿、爱
    因斯坦等人的成就还达不到让人们世界观向前跨进一大步的程度。
    所以,这层楼中的人的成就对我们普通人认识世界非常重要,你可以不学相对论,但是你不可以
    不对这层楼的人所作出的成就不了解,否则你的世界观就是极其不完整的,会犯许多认识上的错
    误。不幸的是,中国的科普知识普及还不够到位,知道这层楼成就的人好像并不多,程序员中恐
    怕更少。下面就来看看这些用一只手的手指数得清的大哲们,到底有什么成就,能比万有引力定
    律和相对论还重要。
    1、希尔伯特(1862~1943)
    第1 位进到此楼层是一位名叫“希尔伯特”的大数学家,如果你学过《泛函分析》,那么你在学
    习希尔伯特空间时可能已经对这位大数学家有所了解;如果你不是学数学出身的,又对数学史不
    感兴趣的话,恐怕你从来没有听说过这个名字。不过如果我问一下,知不知道二次世界大战前世
    界数学中心在那里,你肯定会有兴趣想知道。
    不妨说一下,二战前整个世界的数学中心就在德国的哥廷根,而我们这位大数学家希尔伯特便是
    它的统帅和灵魂人物。即使在二战期间,希特勒和丘吉尔也有协定,德国不轰炸牛津和剑桥,作
    为回报,英国不轰炸海德堡和哥廷根。
    2、哥德尔(1906~1978)
    这位大哲的名字叫“哥德尔(G?del) ”,你可能从来也没有听说过这个名字,即使你读了一个数
    学系的博士学位,如果你的研究方向不和这位大哲对口的话,你也不一定了解这位大哲的成就,
    更不知道他的成果对我们这个世界有何意义。
    简单地说,这位大哲20 多岁时就证明了两个定理,一个叫做“哥德尔完全性定理”,另一个更
    重要的叫做“哥德尔不完全性定理”。你也许会觉得奇怪,第9 层楼的成就就已经上升到了公理
    的高度,这种证明定理的事情不是学者和大师们做的事情吗?怎么能比第9 层楼的成就还高呢?
    下面就来简单说一下这两个定理的含义,你就会明白这属于系统级的定理,绝不是普通的定理和
    公理所能比拟的。
    “哥德尔完全性定理”证明了逻辑学的几条公理是完备的,即任何一个由这些公理所产生出的问
    题,在这个公理系统内可以判定它是真的还是假的,这个结论表明了我们人类所拥有的逻辑思维
    能力是完备的。这条定理并不能将其带入这层楼来,带其进入这层楼的是另一条定理。
    可能你看过《未来战士》、《黑客帝国》、《I,Robot》之类的科幻电影,于是你产生制造一个和人
    一样或者比人更高一级的智能机器人的想法,这就引入了一个达到哲学高度的问题,“人到底能
    不能制造出具有和人一样的思维能力的机器来?”。
    我只能告诉你,“你的愿望是良好的,但现实是残酷的”。如果你仔细思考一下不完全性定理的含
    义,并结合现代计算机所具有的能力分析一下,你会发现这个问题的答案暂时是否定的。如果你
    想造出和人一样思维能力的机器,那么你需要去好好学习这位大哲及其后续研究者的成果,并在
    他们的基础上有新的突破才行。
    3、海森堡(1901~1976)
    海森堡这个名字相信没有几个人不知道的,大部分人在学习物理时都学过他的“测不准关系”,
    也就是因为这个“测不准关系”,海森堡爬到了第十层楼。
    如果你看过《时间简史》和《霍金讲演录-黑洞、婴儿宇宙及其他》,你也许已经了解测不准关
    系的威力,所以这里不想做过多的讨论,只谈一些和本土产生的哲学思想相关的东西。
    十一、超越第十层的上帝
    看了上面的小标题,你可能会觉得奇怪,这篇文章不是讲“程序员的十层楼”吗?怎么冒出了第
    11 层来了?
    其实这并不矛盾,程序员确实只有十层楼,因为爬到第11 层时,已经变成上帝,不再是程序员
    了;所以超出10 层楼本身并不重要,关键的问题是看你有没有能力变成上帝。
    1、谁是上帝?
    菜鸟们认为Linus Torvalds 是程序员中的上帝,看完了前面各层楼的介绍,此时再看到这句话,
    相信你要忍不住在心里笑起来。当然,你会不会笑起来是事先注定的。Don Knuth 也不是上帝,
    他离上帝还有三层楼的距离。即使是大哲们,他们离天堂也还差一层楼,因此这个世界上有史以
    来还没有任何一个人变成过上帝。
    我们感兴趣的是,将来会不会有人爬到比大哲们更高的楼层上,变成了上帝。
    要变成上帝,你得有上帝一样的能力,上帝会造人,你会吗?
    你也许会怯生生地问:“我可以和爱人生小孩,算不算造人?”,你可能还会理直气壮地说:“现
    在生物学上都可以克隆人了,早就有人掌握了造人的方法”。
    事实上克隆人需要有人的体细胞,必须要先有人才会有体细胞。上帝造人时,这个世界上并没有
    人,是从无生命的物质“尘土”中创造出的人。因此,用最原始的方法生人和克隆人都是从有生
    命信息的物质中生人,不能算作造人。
    读后感:
    终于轮到我来发表一下看法了,这也是我为什么要把这篇文章摘抄下来的原因。可以看出本文作
    者是为C/C++程序员并且受过良好的教育,以及高于编程以外的思考。要说作者参透了一切,
    看破了红尘。那到未必,不过作者的十个层次分级对一名程序员来说一个很好的指导性意见。最
    后用《天道》中的《自嘲》做为结束:
    卜算子·自嘲
    本是后山人,偶做前堂客,醉舞经阁半卷书,坐井说天阔。
    大志戏功名,海斗量福祸,论到囊中羞涩时,怒指乾坤错。

    展开全文
  • 程序员10个层次

    2012-02-13 10:54:25
     觉得这篇文章写的还蛮意思,全篇很长我简要的把该文改写一下,以突出十个层次的区别:  中国的程序员水平比西方程序员水平差,还是中国有许多优秀的程序员达到或超过了西方程序员 同等水平呢?要解决这个问题,必须先...
    程序员的10个层次
    
       觉得这篇文章写的还蛮意思,全篇很长我简要的把该文改写一下,以突出十个层次的区别:
      中国的程序员水平比西方程序员水平差,还是中国有许多优秀的程序员达到或超过了西方程序员 同等水平呢?要解决这个问题,必须先知道程序员有多少种技术层级,每个层级需要什么样的技 术水平,然后再比较中国和西方在各个技术层级的人数,就可以知道到底有没有差距,差距有多 大。
    当然,对于如何划分程序员的技术层级,不同公司或不同人会有不同的划分标准,下面的划分仅 代表个人的观点,如有不当之处,还请砸板砖予以纠正。
    一、 菜鸟
      第 1 层楼属于地板层,迈进这层楼的门槛是很低的。基本上懂计算机的基本操作,了解计算 机专业的一些基础知识,掌握一门基本的编程语言如 C/C++,或者 Java,或者 JavaScript,或者O-C..., 均可入门迈进这层。
    二、 大虾 
      从第 1 层爬到第 2 层相对容易一些,以 C/C++程序员为例,只要熟练掌握 C/C++编程语言,
    掌握 C 标准库和常用的各种数据结构算法,掌握 STL 的基本实现和使用方法,掌握多线程编程 基础知识,掌握一种开发环境,再对各种操作系统的 API 都去使用一下,搞网络编程的当然对 socket 编程要好好掌握一下,然后再学习一些面向对象的设计知识和设计模式等,学习一些测 试、软件工程和质量控制的基本知识,大部分人经过 2~3 年的努力,都可以爬到第 2 层,晋升 为"大虾"。
    三、 牛人 
      由于"大虾"们经常被一些疑难问题给卡住,所以有了"大虾"们只好继续学习,他们需要将原
    来所学的知识进一步熟练掌握,比如以熟练掌握 C++编程语言为例,除了学一些基础性的 C++ 书籍如《C++ Primer》,《Effective C++》,《Think in C++》,《Exception C++》等之外,更重要 的是需要了解 C++编译器的原理和实现机制,了解操作系统中的内部机制如内存管理、进程和 线程的管理机制,了解处理器的基础知识和代码优化的方法,此外还需要更深入地学习更多的数 据结构与算法,掌握更深入的测试和调试知识以及质量管理和控制方法,对各种设计方法有更好 的理解等。
    学习上面说的这些知识不是一挥而就的,不看个三五十本书并掌握它是做不到的。以数据结 构算法来说,至少要看个 5~10 本这方面的著作;以软件设计来说,光懂结构化设计、面向对 象设计和一些设计模式是不够的,还要了解软件架构设计、交互设计、面向方面的设计、面向使 用的设计、面向数据结构算法的设计、情感化设计等,否则是很难进到这个楼层的。
    四、 大牛
      从第 3 层爬到第 4 层可不像上面说过的那几层一样容易,要成为大牛的话,你必须要能做
    牛人们做不了的事情,解决牛人们解决不了问题。比如牛人们通常都不懂写操作系统,不会写编 译器,不懂得 TCP/IP 协议的底层实现,如果你有能力将其中的任何一个实现得象模象样的话, 那么你就从牛人升级为"大牛"了。当然,由于各个专业领域的差别,这里举操作系统、编译器、TCP/IP 协议只是作为例子, 并不代表成为"大牛"一定需要掌握这些知识,以时下热门的多核编程来说,如果你能比牛人们更 深入地掌握其中的各种思想原理,能更加自如的运用,并有能力去实现一个象开源项目TBB 库 一样的东西,也可以成为"大牛",又或者你能写出一个类似 Apache 一样的服务器,或者写出一 个数据库,都可以成为"大牛"。
    当"牛人"晋升为"大牛",让"牛人们"发现有比他们更牛的人时,对"牛人"们的心灵的震撼是可 想而知的。由于牛人们的数量庞大,并且牛人对大虾和菜鸟阶层有言传身教的影响,所以大牛们 通常能获得非常高的社会知名度,几乎可以用"引无数菜鸟、大虾、牛人竞折腰"来形容,看看前 面提过的 Linus Torvalds等大牛,应该知道此言不虚。
    虽然成为"大牛"的条件看起来似乎很高似的,但是这层楼并不是很难爬的一层,只要通过一定的 努力,素质不是很差,还是有许多"牛人"可以爬到这一层的。由此可知,"大牛"这个楼层的人数 其实并不像想像的那么少,例如比尔·盖茨之类的人好像也是属于这一层的。
    五、 专家
      当大牛们真正动手做一个操作系统或者类似的其他软件时,他们就会发现自己的基本功仍然有很 多的不足。以内存管理为例,如果直接抄袭 Linux 或者其他开源操作系统的内存管理算法,会被 人看不起的,如果自动动手实现一个内存管理算法,他会发现现在有关内存管理方法的算法数量 众多,自己并没有全部学过和实践过,不知道到底该用那种内存管理算法。
    看到这里,可能有些人已经明白第5 层楼的奥妙了,那就是需要做基础研究,当然在计算机里, 最重要的就是"计算"二字,程序员要做基础研究,主要的内容就是研究非数值"计算"。
    非数值计算可是一个非常庞大的领域,不仅时下热门的"多核计算"与"云计算"属于非数值计算范 畴,就是软件需求、设计、测试、调试、评估、质量控制、软件工程等本质上也属于非数值计算 的范畴,甚至芯片硬件设计也同样牵涉到非数值计算。如果你还没有真正领悟"计算"二字的含义, 那么你就没有机会进到这层楼来。
    六、 学者
      当"专家"们想继续往上一层楼爬时,他们几乎一眼就可以看到楼梯的入口,不过令他们吃惊的是, 楼梯入口处竖了一道高高的门槛,上面写着"创新"二字。不幸的是,大多数人在爬到第 5 层楼时 已经体能消耗过度,无力翻过这道门槛。
    以查找为例,并不是去天天盯着那些复杂的查找结构和算法进行研究,你需要做的是将二分查找、 哈希查找、普通二叉树查找等基础性的知识好好地复习几遍。
    以哈希查找为例,首先你需要去将各种冲突解决方法如链式结构、二次哈希等编写一遍,再试试 不同种类的哈希函数,然后还需要试试在硬盘中如何实现哈希查找,并考虑数据从硬盘读到内存 后,如何组织硬盘中的数据才能快速地在内存中构建出哈希表来,...,这样你可能需要将一个哈 希表写上十几个不同的版本,并比较各个版本的性能、功能方面的区别和适用范围。
    总之,对任何一种简单的东西,你需要考虑各种各样的需求,以需求来驱动研究。最后你将各种 最基础性的查找结构和算法都了然于胸后,或许某天你再看其他更复杂的查找算法,或者你在散
    步时,脑袋里灵光一现,突然间就发现了更好的方法,也就从专家晋升为"学者"了。
    七、 大师
      从第 6 层楼爬到第 7 层楼,并没有多少捷径可走,主要看你有没有足够的能量。你如果能象 Hoare 一样设计出一个快速排序的算法;或者象Eugene W. Myers 一样设计出了一个用编辑图的最短 路径模型来解决 diff 问题的算法;或者象 M.J.D. Powell 一样提出了一个能够处理非线性规划问 题的 SQP 方法;或者你发现基于比较的排序算法,它的复杂度下界为O(NLogN);或者你发现 用栈可以将递归的算法变成非递归的;或者你设计出一个红黑树或者 AVL 树之类的查找结构; 或者你设计出一个象C++或 Java 一样的语言;或者你发明了UML;...,你就爬到了第7 层,晋 升为"大师"了。
    八、科学家
      科学家向来都是一个神圣的称号,因此我把他放在了“大师”之上。要成为科学家,你的贡献必须 超越大师,不妨随便举一些例子。
    如果你象 Dijkstra 一样设计了 ALGOL 语言,提出了程序设计的三种基本结构:顺序、选择、循 环,那么你可以爬到第 8 层楼来。顺便说一下,即使抛开这个成果,Dijkstra 凭他的 PV 操作和 信号量概念的提出,同样可以进到这层楼。
    如果你象DonKnuth一样,是数据结构与算法这门学科的重要奠基者,你也可以进到这层楼来。 当然,数据结构和算法这门学科不是某个人开创的,是许多大师和科学家集体开创的。 如果你象巴科斯一样发明了Fortran 语言,并提出了巴科斯范式,对高级程序语言的发展起了重 要作用,你也可以进到这层楼来。
    九、大科学家
      进入这层楼的门槛通常需要一些运气,比如某天有个苹果砸到你头上时,你碰巧发现了万有引力, 那么你可以进到这层楼来。当然,万有引力几百年前就被人发现了,如果你现在到处嚷嚷着说你 发现了万有引力,恐怕马上会有人打110,然后警察会把你送到不正常人类的*****地去。因此, 这里举万有引力的例子,只是说你要有类似的成就才能进到这层楼来。
    当然,程序员们最关心的是自己有没有机会变成大科学家。既然计算机这门大学科的开创性成果 早就被冯·诺伊曼、图灵等人摘走了,那么程序员们是不是没有机会变成大科学家了呢?我们的 古人说得好:“江山代有才人出,各领风骚数百年”,现在在计算机这门学科下面诞生了许多非常 重要的大的分支,所以你还是有足够的机会进到这层楼的。
    如果你能够彻底解决自然语言理解(机器翻译)这门学科中的核心问题,或者你在人工智能或 者机器视觉(图像识别)方面有突破性的发现,那么你同样可以轻易地晋升为“大科学家”。这 样当某天你老了去世时,或许那天国人已经觉醒,你也能享受到如 Dijkstra 一样的待遇,有满城 甚至全国的人去为你送葬。
    十、 大哲
      看了这层楼的名字“大哲”,可能不少人已经猜到了这层楼的秘密,那就是你的成果必须要上升到 哲学的高度,你才有机会能进到这层来。
    当然,上升到哲学高度只是一个必要条件,牛顿的万有引力似乎也上升到了哲学的高度,因为不 知道引力到底是怎么来的,但是牛顿没有被划到这一层,因为进到这层还有另外的条件,那就是 你的成果必须引起了哲学上的深度思考,并能让人们的世界观向前跨进一大步。窃以为牛顿、爱 因斯坦等人的成就还达不到让人们世界观向前跨进一大步的程度。
    所以,这层楼中的人的成就对我们普通人认识世界非常重要,你可以不学相对论,但是你不可以 不对这层楼的人所作出的成就不了解,否则你的世界观就是极其不完整的,会犯许多认识上的错 误。不幸的是,中国的科普知识普及还不够到位,知道这层楼成就的人好像并不多,程序员中恐 怕更少。下面就来看看这些用一只手的手指数得清的大哲们,到底有什么成就,能比万有引力定 律和相对论还重要。
    1、希尔伯特 (1862~1943)
      第 1 位进到此楼层是一位名叫“希尔伯特”的大数学家,如果你学过《泛函分析》,那么你在学 习希尔伯特空间时可能已经对这位大数学家有所了解;如果你不是学数学出身的,又对数学史不 感兴趣的话,恐怕你从来没有听说过这个名字。不过如果我问一下,知不知道二次世界大战前世 界数学中心在那里,你肯定会有兴趣想知道。
    不妨说一下,二战前整个世界的数学中心就在德国的哥廷根,而我们这位大数学家希尔伯特便是 它的统帅和灵魂人物。即使在二战期间,希特勒和丘吉尔也有协定,德国不轰炸牛津和剑桥,作 为回报,英国不轰炸海德堡和哥廷根。
    2、哥德尔 (1906~1978)
      这位大哲的名字叫“哥德尔 (G?del) ”,你可能从来也没有听说过这个名字,即使你读了一个数 学系的博士学位,如果你的研究方向不和这位大哲对口的话,你也不一定了解这位大哲的成就, 更不知道他的成果对我们这个世界有何意义。
    简单地说,这位大哲 20 多岁时就证明了两个定理,一个叫做“哥德尔完全性定理”,另一个更 重要的叫做“哥德尔不完全性定理”。你也许会觉得奇怪,第 9 层楼的成就就已经上升到了公理 的高度,这种证明定理的事情不是学者和大师们做的事情吗?怎么能比第 9 层楼的成就还高呢? 下面就来简单说一下这两个定理的含义,你就会明白这属于系统级的定理,绝不是普通的定理和 公理所能比拟的。
    “哥德尔完全性定理”证明了逻辑学的几条公理是完备的,即任何一个由这些公理所产生出的问 题,在这个公理系统内可以判定它是真的还是假的,这个结论表明了我们人类所拥有的逻辑思维 能力是完备的。这条定理并不能将其带入这层楼来,带其进入这层楼的是另一条定理。
    可能你看过《未来战士》、《黑客帝国》、《I,Robot》之类的科幻电影,于是你产生制造一个和人 一样或者比人更高一级的智能机器人的想法,这就引入了一个达到哲学高度的问题,“人到底能 不能制造出具有和人一样的思维能力的机器来?”。
    我只能告诉你,“你的愿望是良好的,但现实是残酷的”。如果你仔细思考一下不完全性定理的含 义,并结合现代计算机所具有的能力分析一下,你会发现这个问题的答案暂时是否定的。如果你
    想造出和人一样思维能力的机器,那么你需要去好好学习这位大哲及其后续研究者的成果,并在 他们的基础上有新的突破才行。
    3、海森堡 (1901~1976) 海森堡这个名字相信没有几个人不知道的,大部分人在学习物理时都学过他的“测不准关系”,
      也就是因为这个“测不准关系”,海森堡爬到了第十层楼。
    如果你看过《时间简史》和《霍金讲演录-黑洞、婴儿宇宙及其他》,你也许已经了解测不准关 系的威力,所以这里不想做过多的讨论,只谈一些和本土产生的哲学思想相关的东西。
    十一、超越第十层的上帝 
    看了上面的小标题,你可能会觉得奇怪,这篇文章不是讲“程序员的十层楼”吗?怎么冒出了第 11 层来了?
    其实这并不矛盾,程序员确实只有十层楼,因为爬到第 11 层时,已经变成上帝,不再是程序员 了;所以超出 10 层楼本身并不重要,关键的问题是看你有没有能力变成上帝。
    1、谁是上帝?
      菜鸟们认为 Linus Torvalds是程序员中的上帝,看完了前面各层楼的介绍,此时再看到这句话, 相信你要忍不住在心里笑起来。当然,你会不会笑起来是事先注定的。Don Knuth 也不是上帝, 他离上帝还有三层楼的距离。即使是大哲们,他们离天堂也还差一层楼,因此这个世界上有史以 来还没有任何一个人变成过上帝。
    我们感兴趣的是,将来会不会有人爬到比大哲们更高的楼层上,变成了上帝。 要变成上帝,你得有上帝一样的能力,上帝会造人,你会吗?
    你也许会怯生生地问:“我可以和爱人生小孩,算不算造人?”,你可能还会理直气壮地说:“现 在生物学上都可以克隆人了,早就有人掌握了造人的方法”。
    事实上克隆人需要有人的体细胞,必须要先有人才会有体细胞。上帝造人时,这个世界上并没有 人,是从无生命的物质“尘土”中创造出的人。因此,用最原始的方法生人和克隆人都是从有生 命信息的物质中生人,不能算作造人。
    读后感: 终于轮到我来发表一下看法了,这也是我为什么要把这篇文章摘抄下来的原因。可以看出本文作 者是为 C/C++程序员并且受过良好的教育,以及高于编程以外的思考。要说作者参透了一切, 看破了红尘。那到未必,不过作者的十个层次分级对一名程序员来说一个很好的指导性意见。
    最 后用《天道》中的《自嘲》做为结束: 
    卜算子·自嘲 
    本是后山人,偶做前堂客,醉舞经阁半卷书,坐井说天阔。 
    大志戏功名,海斗量福祸,论到囊中羞涩时,怒指乾坤错。(转)
    展开全文
  • Chamelon的英文单词的意思是变色龙,所以这个算法又称之为变色龙算法,变色龙算法的过程如标题所描绘的那样,是分为2个主要阶段的,不过他可不是像BIRCH算法那样,是树的形式。继续看下面的原理介绍。 算法原理

    算法介绍

    本篇文章讲述的还是聚类算法,也是属于层次聚类算法领域的,不过与上篇文章讲述的分裂实现聚类的方式不同,这次所讲的Chameleon算法是合并形成最终的聚类,恰巧相反。Chamelon的英文单词的意思是变色龙,所以这个算法又称之为变色龙算法,变色龙算法的过程如标题所描绘的那样,是分为2个主要阶段的,不过他可不是像BIRCH算法那样,是树的形式。继续看下面的原理介绍。

    算法原理

    先来张图来大致了解整个算法的过程。

    \

    上面图的显示过程虽然说有3个阶段,但是这其中概况起来就是两个阶段,第一个是形成小簇集的过程就是从Data Set 到k最近邻图到分裂成小聚餐,第二个阶段是合并这些小聚簇形成最终的结果聚簇。理解了算法的大致过程,下面看看里面定义的一些概念,还不少的样子。

    为了引出变色龙算法的一些定义,这里先说一下以往的一些聚类算法的不足之处。

    1、忽略簇与簇之间的互连性。就会导致最终的结果形成如下:

    \

    2、忽略簇与簇之间的近似性。就会导致最终的聚类结果变成这样“:

    \

     

    为什么提这些呢,因为Chameleon算法正好弥补了这2点要求,兼具互连性和近似性。在Chameleon算法中定义了相对互连性,RI表示和相对近似性,RC表示,最后通过一个度量函数:

    function value = RI( Ci, Cj)× RC( Ci, Cj)α,α在这里表示的多少次方的意思,不是乘法。

    来作为2个簇是否能够合并的标准,其实这些都是第二阶段做的事情了。

    在第一阶段,所做的一件关键的事情就是形成小簇集,由零星的几个数据点连成小簇,官方的作法是用hMetic算法根据最小化截断的边的权重和来分割k-最近邻图,然后我网上找了一些资料,没有确切的hMetic算法,借鉴了网上其他人的一些办法,于是用了一个很简单的思路,就是给定一个点,把他离他最近的k个点连接起来,就算是最小簇了。事实证明,效果也不会太差,最近的点的换一个意思就是与其最大权重的边,采用距离的倒数最为权重的大小。因为后面的计算,用到的会是权重而不是距离。

    我们再回过头来细说第二阶段所做的事情,首先是2个略复杂的公式(直接采用截图的方式):

    相对互连性RI=\

    相对近似性RC=\

    Ci,Cj表示的是i,j聚簇内的数据点的个数,EC(Ci)表示的Ci聚簇内的边的权重和,EC(Ci,Cj)表示的是连接2个聚簇的边的权重和。

    后来我在查阅书籍和一些文库的时候发现,这个公式还不是那么的标准,因为他对分母,分子进行了部分的改变,但是大意上还是一致的,标准公式上用到的是平均权重,而这里用的是和的形式,差别不大,所以就用这个公式了。

    那么合并的过程如下:

    1、给定度量函数如下minMetric,

    2、访问每个簇,计算他与邻近的每个簇的RC和RI,通过度量函数公式计算出值tempMetric。

    3、找到最大的tempMetric,如果最大的tempMetric超过阈值minMetric,将簇与此值对应的簇合并

    4、如果找到的最大的tempMetric没有超过阈值,则表明此聚簇已合并完成,移除聚簇列表,加入到结果聚簇中。

    4、递归步骤2,直到待合并聚簇列表最终大小为空。

    算法的实现

    算法的输入依旧采用的是坐标点的形式graphData.txt:

     

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    0 2 2
    1 3 1
    2 3 4
    3 3 14
    4 5 3
    5 8 3
    6 8 6
    7 9 8
    8 10 4
    9 10 7
    10 10 10
    11 10 14
    12 11 13
    13 12 8
    14 12 15
    15 14 7
    16 14 9
    17 14 15
    18 15 8
    算法坐标点数据Point.java
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    package DataMining_Chameleon;
     
     
     
    /**
     * 坐标点类
     * @author lyq
     *
     */
    publicclass Point{
        //坐标点id号,id号唯一
        intid;
        //坐标横坐标
        Integerx;
        //坐标纵坐标
        Integery;
        //是否已经被访问过
        boolean isVisited;
         
        publicPoint(String id, String x, String y){
            this.id = Integer.parseInt(id);
            this.x = Integer.parseInt(x);
            this.y = Integer.parseInt(y);
        }
         
        /**
         * 计算当前点与制定点之间的欧式距离
         *
         * @param p
         *            待计算聚类的p点
         * @return
         */
        publicdouble ouDistance(Point p) {
            doubledistance = 0;
     
            distance = (this.x - p.x) * (this.x - p.x) + (this.y - p.y)
                    * (this.y - p.y);
            distance = Math.sqrt(distance);
     
            returndistance;
        }
         
        /**
         * 判断2个坐标点是否为用个坐标点
         *
         * @param p
         *            待比较坐标点
         * @return
         */
        publicboolean isTheSame(Point p) {
            boolean isSamed = false;
     
            if (this.x == p.x && this.y == p.y) {
                isSamed = true;
            }
     
            returnisSamed;
        }
    }

    簇类Cluster.java:

     

     

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    package DataMining_Chameleon;
     
    import java.util.ArrayList;
     
    /**
     * 聚簇类
     *
     * @author lyq
     *
     */
    publicclass Cluster implements Cloneable{
        //簇唯一id标识号
        intid;
        // 聚簇内的坐标点集合
        ArrayList<Point> points;
        // 聚簇内的所有边的权重和
        doubleweightSum = 0;
     
        publicCluster(intid, ArrayList<Point> points) {
            this.id = id;
            this.points = points;
        }
     
        /**
         * 计算聚簇的内部的边权重和
         *
         * @return
         */
        publicdouble calEC() {
            intid1 = 0;
            intid2 = 0;
            weightSum = 0;
             
            for(Point p1 : points) {
                for(Point p2 : points) {
                    id1 = p1.id;
                    id2 = p2.id;
     
                    // 为了避免重复计算,取id1小的对应大的
                    if (id1 < id2 && ChameleonTool.edges[id1][id2] == 1) {
                        weightSum += ChameleonTool.weights[id1][id2];
                    }
                }
            }
     
            returnweightSum;
        }
     
        /**
         * 计算2个簇之间最近的n条边
         *
         * @param otherCluster
         *            待比较的簇
         * @param n
         *            最近的边的数目
         * @return
         */
        publicArrayList<int[]> calNearestEdge(Cluster otherCluster, intn){
            intcount = 0;
            doubledistance = 0;
            doubleminDistance = Integer.MAX_VALUE;
            Point point1 = null;
            Point point2 = null;
            ArrayList<int[]> edgeList = new ArrayList<>();
            ArrayList<Point> pointList1 = (ArrayList<Point>) points.clone();
            ArrayList<Point> pointList2 = null;
            Cluster c2 = null;
             
            try {
                c2 = (Cluster) otherCluster.clone();
                pointList2 = c2.points;
            } catch (CloneNotSupportedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
     
            int[] tempEdge;
            // 循环计算出每次的最近距离
            while (count< n) {
                tempEdge = new int[2];
                minDistance = Integer.MAX_VALUE;
                 
                for(Point p1 : pointList1) {
                    for(Point p2 :  pointList2) {
                        distance = p1.ouDistance(p2);
                        if (distance < minDistance) {
                            point1 = p1;
                            point2 = p2;
                            tempEdge[0] = p1.id;
                            tempEdge[1] = p2.id;
     
                            minDistance = distance;
                        }
                    }
                }
     
                pointList1.remove(point1);
                pointList2.remove(point2);
                edgeList.add(tempEdge);
                count++;
            }
     
            returnedgeList;
        }
     
        @Override
        protected Object clone() throws CloneNotSupportedException {
            // TODO Auto-generated method stub
             
            //引用需要再次复制,实现深拷贝
            ArrayList<Point> pointList = (ArrayList<Point>) this.points.clone();
            Cluster cluster = new Cluster(id, pointList);
             
            returncluster;
        }
         
         
     
    }

    算法工具类Chameleon.java:

     

     

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    338
    339
    340
    341
    342
    343
    344
    345
    346
    347
    348
    349
    350
    351
    352
    353
    354
    355
    356
    357
    358
    359
    360
    361
    362
    363
    364
    365
    366
    367
    368
    369
    370
    371
    372
    373
    374
    375
    376
    377
    378
    379
    380
    381
    382
    383
    384
    385
    386
    387
    388
    389
    390
    391
    392
    393
    394
    395
    396
    397
    398
    399
    400
    401
    402
    403
    404
    405
    406
    407
    408
    409
    410
    411
    412
    413
    414
    415
    416
    417
    418
    419
    420
    421
    422
    423
    424
    425
    package DataMining_Chameleon;
     
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileReader;
    import java.io.IOException;
    import java.text.MessageFormat;
    import java.util.ArrayList;
     
    /**
     * Chameleon 两阶段聚类算法工具类
     *
     * @author lyq
     *
     */
    publicclass ChameleonTool {
        // 测试数据点文件地址
        private String filePath;
        // 第一阶段的k近邻的k大小
        privateintk;
        // 簇度量函数阈值
        privatedoubleminMetric;
        // 总的坐标点的个数
        privateintpointNum;
        // 总的连接矩阵的情况,括号表示的是坐标点的id号
        publicstatic int[][] edges;
        // 点与点之间的边的权重
        publicstatic double[][] weights;
        // 原始坐标点数据
        private ArrayList<Point> totalPoints;
        // 第一阶段产生的所有的连通子图作为最初始的聚类
        private ArrayList<Cluster> initClusters;
        // 结果簇结合
        private ArrayList<Cluster> resultClusters;
     
        publicChameleonTool(String filePath, intk, doubleminMetric) {
            this.filePath = filePath;
            this.k = k;
            this.minMetric = minMetric;
     
            readDataFile();
        }
     
        /**
         * 从文件中读取数据
         */
        private void readDataFile() {
            File file = new File(filePath);
            ArrayList<String[]> dataArray = new ArrayList<String[]>();
     
            try {
                BufferedReaderin= new BufferedReader(new FileReader(file));
                String str;
                String[] tempArray;
                while ((str = in.readLine()) != null) {
                    tempArray = str.split(" ");
                    dataArray.add(tempArray);
                }
                in.close();
            } catch (IOException e) {
                e.getStackTrace();
            }
     
            Point p;
            totalPoints = new ArrayList<>();
            for(String[] array : dataArray) {
                p = new Point(array[0], array[1], array[2]);
                totalPoints.add(p);
            }
            pointNum = totalPoints.size();
        }
     
        /**
         * 递归的合并小聚簇
         */
        private void combineSubClusters() {
            Cluster cluster = null;
     
            resultClusters = new ArrayList<>();
     
            // 当最后的聚簇只剩下一个的时候,则退出循环
            while (initClusters.size() > 1) {
                cluster = initClusters.get(0);
                combineAndRemove(cluster, initClusters);
            }
        }
     
        /**
         * 递归的合并聚簇和移除聚簇
         *
         * @param clusterList
         */
        private ArrayList<Cluster> combineAndRemove(Cluster cluster,
                ArrayList<Cluster> clusterList) {
            ArrayList<Cluster> remainClusters;
            doublemetric = 0;
            doublemaxMetric = -Integer.MAX_VALUE;
            Cluster cluster1 = null;
            Cluster cluster2 = null;
     
            for(Cluster c2 : clusterList) {
                if (cluster.id == c2.id) {
      &n