Feeling

　　Spark簡介

　　Spark是整個BDAS的核心組件，是一個大數(shù)據(jù)分布式編程框架，不僅實現(xiàn)了MapReduce的算子map 函數(shù)和reduce函數(shù)及計算模型，還提供更為豐富的算子，如filter、join、groupByKey等。是一個用來實現(xiàn)快速而同用的集群計算的平臺。

　　Spark將分布式數(shù)據(jù)抽象為彈性分布式數(shù)據(jù)集（RDD），實現(xiàn)了應(yīng)用任務(wù)調(diào)度、RPC、序列化和壓縮，并為運行在其上的上層組件提供API。其底層采用Scala這種函數(shù)式語言書寫而成，并且所提供的API深度借鑒Scala函數(shù)式的編程思想，提供與Scala類似的編程接口

　　Sparkon Yarn

　　從用戶提交作業(yè)到作業(yè)運行結(jié)束整個運行期間的過程分析。

　　一、客戶端進(jìn)行操作

1. 根據(jù)yarnConf來初始化yarnClient，并啟動yarnClient

2. 創(chuàng)建客戶端Application，并獲取Application的ID，進(jìn)一步判斷集群中的資源是否滿足executor和ApplicationMaster申請的資源，如果不滿足則拋出IllegalArgumentException；

3. 設(shè)置資源、環(huán)境變量：其中包括了設(shè)置Application的Staging目錄、準(zhǔn)備本地資源（jar文件、log4j.properties）、設(shè)置Application其中的環(huán)境變量、創(chuàng)建Container啟動的Context等；

4. 設(shè)置Application提交的Context，包括設(shè)置應(yīng)用的名字、隊列、AM的申請的Container、標(biāo)記該作業(yè)的類型為Spark；

5. 申請Memory，并最終通過yarnClient.submitApplication向ResourceManager提交該Application。

　　當(dāng)作業(yè)提交到Y(jié)ARN上之后，客戶端就沒事了，甚至在終端關(guān)掉那個進(jìn)程也沒事，因為整個作業(yè)運行在YARN集群上進(jìn)行，運行的結(jié)果將會保存到HDFS或者日志中。

　　二、提交到Y(jié)ARN集群，YARN操作

1. 運行ApplicationMaster的run方法；

2. 設(shè)置好相關(guān)的環(huán)境變量。

3. 創(chuàng)建amClient，并啟動；

4. 在Spark UI啟動之前設(shè)置Spark UI的AmIpFilter；

5. 在startUserClass函數(shù)專門啟動了一個線程（名稱為Driver的線程）來啟動用戶提交的Application，也就是啟動了Driver。在Driver中將會初始化SparkContext；

6. 等待SparkContext初始化完成，最多等待spark.yarn.applicationMaster.waitTries次數(shù)（默認(rèn)為10），如果等待了的次數(shù)超過了配置的，程序?qū)顺觯环駝t用SparkContext初始化yarnAllocator；

7. 當(dāng)SparkContext、Driver初始化完成的時候，通過amClient向ResourceManager注冊ApplicationMaster

8. 分配并啟動Executeors。在啟動Executeors之前，先要通過yarnAllocator獲取到numExecutors個Container，然后在Container中啟動Executeors。

   　　那么這個Application將失敗，將Application Status標(biāo)明為FAILED，并將關(guān)閉SparkContext。其實，啟動Executeors是通過ExecutorRunnable實現(xiàn)的，而ExecutorRunnable內(nèi)部是啟動CoarseGrainedExecutorBackend的。

9. 最后，Task將在CoarseGrainedExecutorBackend里面運行，然后運行狀況會通過Akka通知CoarseGrainedScheduler，直到作業(yè)運行完成。

　　Spark節(jié)點的概念

　　一、Spark驅(qū)動器是執(zhí)行程序中的main()方法的進(jìn)程。它執(zhí)行用戶編寫的用來創(chuàng)建SparkContext(初始化)、創(chuàng)建RDD，以及運行RDD的轉(zhuǎn)化操作和行動操作的代碼。

　　驅(qū)動器節(jié)點driver的職責(zé)：

1. 把用戶程序轉(zhuǎn)為任務(wù)task(driver)

   　　Spark驅(qū)動器程序負(fù)責(zé)把用戶程序轉(zhuǎn)化為多個物理執(zhí)行單元，這些單元也被稱之為任務(wù)task(詳解見備注)

2. 為執(zhí)行器節(jié)點調(diào)度任務(wù)(executor)

   　　有了物理計劃之后，Spark驅(qū)動器在各個執(zhí)行器節(jié)點進(jìn)程間協(xié)調(diào)任務(wù)的調(diào)度。Spark驅(qū)動器程序會根據(jù)當(dāng)前的執(zhí)行器節(jié)點，把所有任務(wù)基于數(shù)據(jù)所在位置分配給合適的執(zhí)行器進(jìn)程。當(dāng)執(zhí)行任務(wù)時，執(zhí)行器進(jìn)程會把緩存的數(shù)據(jù)存儲起來，而驅(qū)動器進(jìn)程同樣會跟蹤這些緩存數(shù)據(jù)的位置，并利用這些位置信息來調(diào)度以后的任務(wù)，以盡量減少數(shù)據(jù)的網(wǎng)絡(luò)傳輸。（就是所謂的移動計算，而不移動數(shù)據(jù))。

　　二、執(zhí)行器節(jié)點

　　作用：

1. 負(fù)責(zé)運行組成Spark應(yīng)用的任務(wù)，并將結(jié)果返回給驅(qū)動器進(jìn)程；

2. 通過自身的塊管理器(blockManager)為用戶程序中要求緩存的RDD提供內(nèi)存式存儲。RDD是直接緩存在執(zhí)行器進(jìn)程內(nèi)的，因此任務(wù)可以在運行時充分利用緩存數(shù)據(jù)加快運算。

　　驅(qū)動器的職責(zé)：

　　所有的Spark程序都遵循同樣的結(jié)構(gòu)：程序從輸入數(shù)據(jù)創(chuàng)建一系列RDD，再使用轉(zhuǎn)化操作派生成新的RDD，最后使用行動操作手機(jī)或存儲結(jié)果RDD，Spark程序其實是隱式地創(chuàng)建出了一個由操作組成的邏輯上的有向無環(huán)圖DAG。當(dāng)驅(qū)動器程序執(zhí)行時，它會把這個邏輯圖轉(zhuǎn)為物理執(zhí)行計劃。

　　這樣 Spark就把邏輯計劃轉(zhuǎn)為一系列步驟(stage)，而每個步驟又由多個任務(wù)組成。這些任務(wù)會被打包送到集群中。

　　Spark初始化

1. 每個Spark應(yīng)用都由一個驅(qū)動器程序來發(fā)起集群上的各種并行操作。驅(qū)動器程序包含應(yīng)用的main函數(shù)，并且定義了集群上的分布式數(shù)據(jù)集，以及對該分布式數(shù)據(jù)集應(yīng)用了相關(guān)操作。

2. 驅(qū)動器程序通過一個SparkContext對象來訪問spark,這個對象代表對計算集群的一個連接。（比如在sparkshell啟動時已經(jīng)自動創(chuàng)建了一個SparkContext對象，是一個叫做SC的變量。(下圖，查看變量sc)

   　　

3. 一旦創(chuàng)建了sparkContext，就可以用它來創(chuàng)建RDD。比如調(diào)用sc.textFile()來創(chuàng)建一個代表文本中各行文本的RDD。（比如vallinesRDD = sc.textFile(“yangsy.text”),val spark = linesRDD.filter(line=>line.contains(“spark”),spark.count()）

   　　執(zhí)行這些操作，驅(qū)動器程序一般要管理多個執(zhí)行器,就是我們所說的executor節(jié)點。

4. 在初始化SparkContext的同時，加載sparkConf對象來加載集群的配置，從而創(chuàng)建sparkContext對象。

   　　從源碼中可以看到，在啟動thriftserver時，調(diào)用了spark- daemon.sh文件，該文件源碼如左圖，加載spark_home下的conf中的文件。

   　　

   　　（在執(zhí)行后臺代碼時，需要首先創(chuàng)建conf對象，加載相應(yīng)參數(shù)， val sparkConf = newSparkConf().setMaster("local").setAppName("cocapp").set("spark.executor.memory","1g"), val sc: SparkContext = new SparkContext(sparkConf))

　　RDD工作原理：

　　RDD(Resilient DistributedDatasets)[1] ,彈性分布式數(shù)據(jù)集，是分布式內(nèi)存的一個抽象概念，RDD提供了一種高度受限的共享內(nèi)存模型，即RDD是只讀的記錄分區(qū)的集合，只能通過在其他RDD執(zhí)行確定的轉(zhuǎn)換操作（如map、join和group by）而創(chuàng)建，然而這些限制使得實現(xiàn)容錯的開銷很低。對開發(fā)者而言，RDD可以看作是Spark的一個對象，它本身運行于內(nèi)存中，如讀文件是一個RDD，對文件計算是一個RDD，結(jié)果集也是一個RDD ，不同的分片、數(shù)據(jù)之間的依賴、key-value類型的map數(shù)據(jù)都可以看做RDD。

　　主要分為三部分：創(chuàng)建RDD對象，DAG調(diào)度器創(chuàng)建執(zhí)行計劃，Task調(diào)度器分配任務(wù)并調(diào)度Worker開始運行。

　　SparkContext(RDD相關(guān)操作)→通過(提交作業(yè))→(遍歷RDD拆分stage→生成作業(yè))DAGScheduler→通過（提交任務(wù)集）→任務(wù)調(diào)度管理(TaskScheduler)→通過（按照資源獲取任務(wù))→任務(wù)調(diào)度管理(TaskSetManager)

　　Transformation返回值還是一個RDD。它使用了鏈?zhǔn)秸{(diào)用的設(shè)計模式，對一個RDD進(jìn)行計算后，變換成另外一個RDD，然后這個RDD又可以進(jìn)行另外一次轉(zhuǎn)換。這個過程是分布式的。

　　Action返回值不是一個RDD。它要么是一個Scala的普通集合，要么是一個值，要么是空，最終或返回到Driver程序，或把RDD寫入到文件系統(tǒng)中

　　轉(zhuǎn)換(Transformations)(如：map, filter, groupBy, join等)，Transformations操作是Lazy的，也就是說從一個RDD轉(zhuǎn)換生成另一個RDD的操作不是馬上執(zhí)行，Spark在遇到Transformations操作時只會記錄需要這樣的操作，并不會去執(zhí)行，需要等到有Actions操作的時候才會真正啟動計算過程進(jìn)行計算。

　　操作(Actions)(如：count, collect, save等)，Actions操作會返回結(jié)果或把RDD數(shù)據(jù)寫到存儲系統(tǒng)中。Actions是觸發(fā)Spark啟動計算的動因。

　　它們本質(zhì)區(qū)別是：Transformation返回值還是一個RDD。它使用了鏈?zhǔn)秸{(diào)用的設(shè)計模式，對一個RDD進(jìn)行計算后，變換成另外一個RDD，然后這個RDD又可以進(jìn)行另外一次轉(zhuǎn)換。這個過程是分布式的。Action返回值不是一個RDD。它要么是一個Scala的普通集合，要么是一個值，要么是空，最終或返回到Driver程序，或把RDD寫入到文件系統(tǒng)中。關(guān)于這兩個動作，在Spark開發(fā)指南中會有就進(jìn)一步的詳細(xì)介紹，它們是基于Spark開發(fā)的核心。

　　RDD基礎(chǔ)

1. Spark中的RDD就是一個不可變的分布式對象集合。每個RDD都被分為多個分區(qū)，這些分區(qū)運行在集群的不同節(jié)點上。創(chuàng)建RDD的方法有兩種：一種是讀取一個外部數(shù)據(jù)集；一種是在群東程序里分發(fā)驅(qū)動器程序中的對象集合，不如剛才的示例，讀取文本文件作為一個字符串的RDD的示例。

2. 創(chuàng)建出來后，RDD支持兩種類型的操作:轉(zhuǎn)化操作和行動操作

   　　轉(zhuǎn)化操作會由一個RDD生成一個新的RDD。（比如剛才的根據(jù)謂詞篩選）

   　　行動操作會對RDD計算出一個結(jié)果，并把結(jié)果返回到驅(qū)動器程序中，或把結(jié)果存儲到外部存儲系統(tǒng)（比如HDFS）中。比如first()操作就是一個行動操作，會返回RDD的第一個元素。

   　　注：轉(zhuǎn)化操作與行動操作的區(qū)別在于Spark計算RDD的方式不同。雖然你可以在任何時候定義一個新的RDD，但Spark只會惰性計算這些RDD。它們只有第一個在一個行動操作中用到時，才會真正的計算。之所以這樣設(shè)計，是因為比如剛才調(diào)用sc.textFile(...)時就把文件中的所有行都讀取并存儲起來，就會消耗很多存儲空間，而我們馬上又要篩選掉其中的很多數(shù)據(jù)。

   　　這里還需要注意的一點是，spark會在你每次對它們進(jìn)行行動操作時重新計算。如果想在多個行動操作中重用同一個RDD，那么可以使用RDD.persist()或RDD.collect()讓Spark把這個RDD緩存下來。（可以是內(nèi)存，也可以是磁盤)

3. Spark會使用譜系圖來記錄這些不同RDD之間的依賴關(guān)系，Spark需要用這些信息來按需計算每個RDD，也可以依靠譜系圖在持久化的RDD丟失部分?jǐn)?shù)據(jù)時用來恢復(fù)所丟失的數(shù)據(jù)。(如下圖，過濾errorsRDD與warningsRDD,最終調(diào)用union()函數(shù))

   　　

　　RDD計算方式

　　RDD的寬窄依賴

　　窄依賴 (narrowdependencies) 和寬依賴 (widedependencies) 。窄依賴是指 父 RDD 的每個分區(qū)都只被子 RDD 的一個分區(qū)所使用 。相應(yīng)的，那么寬依賴就是指父 RDD 的分區(qū)被多個子 RDD 的分區(qū)所依賴。例如， map 就是一種窄依賴，而 join 則會導(dǎo)致寬依賴

　　這種劃分有兩個用處。首先，窄依賴支持在一個結(jié)點上管道化執(zhí)行。例如基于一對一的關(guān)系，可以在 filter 之后執(zhí)行 map 。其次，窄依賴支持更高效的故障還原。因為對于窄依賴，只有丟失的父 RDD 的分區(qū)需要重新計算。而對于寬依賴，一個結(jié)點的故障可能導(dǎo)致來自所有父 RDD 的分區(qū)丟失，因此就需要完全重新執(zhí)行。因此對于寬依賴，Spark 會在持有各個父分區(qū)的結(jié)點上，將中間數(shù)據(jù)持久化來簡化故障還原，就像 MapReduce 會持久化 map 的輸出一樣。

　　SparkExample

　　步驟 1 ：創(chuàng)建 RDD 。上面的例子除去最后一個 collect 是個動作，不會創(chuàng)建 RDD 之外，前面四個轉(zhuǎn)換都會創(chuàng)建出新的 RDD 。因此第一步就是創(chuàng)建好所有 RDD( 內(nèi)部的五項信息 ) 。

　　步驟 2 ：創(chuàng)建執(zhí)行計劃。Spark 會盡可能地管道化，并基于是否要重新組織數(shù)據(jù)來劃分 階段 (stage) ，例如本例中的 groupBy() 轉(zhuǎn)換就會將整個執(zhí)行計劃劃分成兩階段執(zhí)行。最終會產(chǎn)生一個 DAG(directedacyclic graph ，有向無環(huán)圖 ) 作為邏輯執(zhí)行計劃。

　　步驟 3 ：調(diào)度任務(wù)。 將各階段劃分成不同的 任務(wù) (task) ，每個任務(wù)都是數(shù)據(jù)和計算的合體。在進(jìn)行下一階段前，當(dāng)前階段的所有任務(wù)都要執(zhí)行完成。因為下一階段的第一個轉(zhuǎn)換一定是重新組織數(shù)據(jù)的，所以必須等當(dāng)前階段所有結(jié)果數(shù)據(jù)都計算出來了才能繼續(xù)。

　　假設(shè)本例中的 hdfs://names 下有四個文件塊，那么 HadoopRDD 中 partitions 就會有四個分區(qū)對應(yīng)這四個塊數(shù)據(jù)，同時 preferedLocations 會指明這四個塊的最佳位置。現(xiàn)在，就可以創(chuàng)建出四個任務(wù)，并調(diào)度到合適的集群結(jié)點上。

　　Spark數(shù)據(jù)分區(qū)

1. Spark的特性是對數(shù)據(jù)集在節(jié)點間的分區(qū)進(jìn)行控制。在分布式系統(tǒng)中，通訊的代價是巨大的，控制數(shù)據(jù)分布以獲得最少的網(wǎng)絡(luò)傳輸可以極大地提升整體性能。Spark程序可以通過控制RDD分區(qū)方式來減少通訊的開銷。

2. Spark中所有的鍵值對RDD都可以進(jìn)行分區(qū)。確保同一組的鍵出現(xiàn)在同一個節(jié)點上。比如，使用哈希分區(qū)將一個RDD分成了100個分區(qū)，此時鍵的哈希值對100取模的結(jié)果相同的記錄會被放在一個節(jié)點上。

   　　（可使用partitionBy(newHashPartitioner(100)).persist()來構(gòu)造100個分區(qū))

3. Spark中的許多操作都引入了將數(shù)據(jù)根據(jù)鍵跨界點進(jìn)行混洗的過程。(比如：join(),leftOuterJoin(),groupByKey(),reducebyKey()等)對于像reduceByKey()這樣只作用于單個RDD的操作，運行在未分區(qū)的RDD上的時候會導(dǎo)致每個鍵的所有對應(yīng)值都在每臺機(jī)器上進(jìn)行本地計算。

　　SparkSQL的shuffle過程

　　Spark SQL的核心是把已有的RDD，帶上Schema信息，然后注冊成類似sql里的”Table”，對其進(jìn)行sql查詢。這里面主要分兩部分，一是生成SchemaRD，二是執(zhí)行查詢。

　　如果是spark-hive項目，那么讀取metadata信息作為Schema、讀取hdfs上數(shù)據(jù)的過程交給Hive完成，然后根據(jù)這倆部分生成SchemaRDD，在HiveContext下進(jìn)行hql()查詢。

　　SparkSQL結(jié)構(gòu)化數(shù)據(jù)

1. 首先說一下ApacheHive，Hive可以在HDFS內(nèi)或者在其他存儲系統(tǒng)上存儲多種格式的表。SparkSQL可以讀取Hive支持的任何表。要把Spark SQL連接已有的hive上，需要提供Hive的配置文件。hive-site.xml文件復(fù)制到spark的conf文件夾下。再創(chuàng)建出HiveContext對象(sparksql的入口)，然后就可以使用HQL來對表進(jìn)行查詢，并以由行足證的RDD的形式拿到返回的數(shù)據(jù)。

2. 創(chuàng)建Hivecontext并查詢數(shù)據(jù)

   　　importorg.apache.spark.sql.hive.HiveContext

   　　valhiveCtx = new org.apache.spark.sql.hive.HiveContext(sc)

   　　valrows = hiveCtx.sql(“SELECT name,age FROM users”)

   　　valfitstRow – rows.first()

   　　println(fitstRow.getSgtring(0)) //字段0是name字段

3. 通過jdbc連接外部數(shù)據(jù)源更新與加載

   　　Class.forName("com.mysql.jdbc.Driver")

   　　val conn =DriverManager.getConnection(mySQLUrl)

   　　val stat1 =conn.createStatement()

   　　stat1.execute("UPDATE CI_LABEL_INFO set DATA_STATUS_ID = 2 , DATA_DATE ='" + dataDate +"' where LABEL_ID in ("+allCreatedLabels.mkString(",")+")")

   　　stat1.close()

   　　//加載外部數(shù)據(jù)源數(shù)據(jù)到內(nèi)存

   　　valDIM_COC_INDEX_MODEL_TABLE_CONF =sqlContext.jdbc(mySQLUrl,"DIM_COC_INDEX_MODEL_TABLE_CONF").cache()

   　　val targets =DIM_COC_INDEX_MODEL_TABLE_CONF.filter("TABLE_DATA_CYCLE ="+TABLE_DATA_CYCLE).collect

　　SparkSQL解析

　　首先說下傳統(tǒng)數(shù)據(jù)庫的解析，傳統(tǒng)數(shù)據(jù)庫的解析過程是按Rusult、Data Source、Operation的次序來解析的。傳統(tǒng)數(shù)據(jù)庫先將讀入的SQL語句進(jìn)行解析，分辨出SQL語句中哪些詞是關(guān)鍵字（如select,from,where)，哪些是表達(dá)式，哪些是Projection，哪些是Data Source等等。進(jìn)一步判斷SQL語句是否規(guī)范，不規(guī)范就報錯，規(guī)范則按照下一步過程綁定（Bind)。過程綁定是將SQL語句和數(shù)據(jù)庫的數(shù)據(jù)字典(列,表,視圖等）進(jìn)行綁定，如果相關(guān)的Projection、Data Source等都存在，就表示這個SQL語句是可以執(zhí)行的。在執(zhí)行過程中，有時候甚至不需要讀取物理表就可以返回結(jié)果，比如重新運行剛運行過的SQL語句，直接從數(shù)據(jù)庫的緩沖池中獲取返回結(jié)果。在數(shù)據(jù)庫解析的過程中SQL語句時，將會把SQL語句轉(zhuǎn)化成一個樹形結(jié)構(gòu)來進(jìn)行處理，會形成一個或含有多個節(jié)點(TreeNode)的Tree,然后再后續(xù)的處理政對該Tree進(jìn)行一系列的操作。

　　Spark SQL對SQL語句的處理和關(guān)系數(shù)據(jù)庫對SQL語句的解析采用了類似的方法，首先會將SQL語句進(jìn)行解析，然后形成一個Tree，后續(xù)如綁定、優(yōu)化等處理過程都是對Tree的操作，而操作方法是采用Rule,通過模式匹配，對不同類型的節(jié)點采用不同的操作。SparkSQL有兩個分支，sqlContext和hiveContext。sqlContext現(xiàn)在只支持SQL語法解析器（Catalyst)，hiveContext支持SQL語法和HiveContext語法解析器。

原文地址：http://mt.sohu.com/20160522/n450849016.shtml

spark中有partition的概念（和slice是同一個概念，在spark1.2中官網(wǎng)已經(jīng)做出了說明），一般每個partition對應(yīng)一個task。在我的測試過程中，如果沒有設(shè)置spark.default.parallelism參數(shù)，spark計算出來的partition非常巨大，與我的cores非常不搭。我在兩臺機(jī)器上（8cores *2 +6g * 2）上，spark計算出來的partition達(dá)到2.8萬個，也就是2.9萬個tasks，每個task完成時間都是幾毫秒或者零點幾毫秒，執(zhí)行起來非常緩慢。在我嘗試設(shè)置了 spark.default.parallelism 后，任務(wù)數(shù)減少到10，執(zhí)行一次計算過程從minute降到20second。

參數(shù)可以通過spark_home/conf/spark-default.conf配置文件設(shè)置。

eg.

spark.master                  spark://master:7077 

spark.default.parallelism     10 

spark.driver.memory           2g 

spark.serializer              org.apache.spark.serializer.KryoSerializer 

spark.sql.shuffle.partitions  50

下面是官網(wǎng)的相關(guān)描述：

from:http://spark.apache.org/docs/latest/configuration.html

from:http://spark.apache.org/docs/latest/tuning.html

Level of Parallelism

Clusters will not be fully utilized unless you set the level of parallelism for each operation high enough. Spark automatically sets the number of “map” tasks to run on each file according to its size (though you can control it through optional parameters to SparkContext.textFile, etc), and for distributed “reduce” operations, such as groupByKey and reduceByKey, it uses the largest parent RDD’s number of partitions. You can pass the level of parallelism as a second argument (see the spark.PairRDDFunctions documentation), or set the config propertyspark.default.parallelism to change the default. In general, we recommend 2-3 tasks per CPU core in your cluster.


原文地址：http://www.cnblogs.com/wrencai/p/4231966.html

1 歸并排序（MergeSort）

歸并排序最差運行時間是O(nlogn)，它是利用遞歸設(shè)計程序的典型例子。

歸并排序的最基礎(chǔ)的操作就是合并兩個已經(jīng)排好序的序列。

假設(shè)我們有一個沒有排好序的序列，那么首先我們使用分割的辦法將這個序列分割成一個一個已經(jīng)排好序的子序列。然后再利用歸并的方法將一個個的子序列合并成排序好的序列。分割和歸并的過程可以看下面的圖例。



從上圖可以看出，我們首先把一個未排序的序列從中間分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一個一個的數(shù)據(jù)，再把這些數(shù)據(jù)兩兩歸并到一起，使之有序，不停的歸并，最后成為一個排好序的序列。

如何把兩個已經(jīng)排序好的子序列歸并成一個排好序的序列呢？可以參看下面的方法。

假設(shè)我們有兩個已經(jīng)排序好的子序列。
序列A：1 23 34 65
序列B：2 13 14 87
那么可以按照下面的步驟將它們歸并到一個序列中。

（1）首先設(shè)定一個新的數(shù)列C[8]。
（2）A[0]和B[0]比較，A[0] = 1，B[0] = 2，A[0] < B[0]，那么C[0] = 1
（3）A[1]和B[0]比較，A[1] = 23，B[0] = 2，A[1] > B[0]，那么C[1] = 2
（4）A[1]和B[1]比較，A[1] = 23，B[1] = 13，A[1] > B[1]，那么C[2] = 13
（5）A[1]和B[2]比較，A[1] = 23，B[2] = 14，A[1] > B[2]，那么C[3] = 14
（6）A[1]和B[3]比較，A[1] = 23，B[3] = 87，A[1] < B[3]，那么C[4] = 23
（7）A[2]和B[3]比較，A[2] = 34，B[3] = 87，A[2] < B[3]，那么C[5] = 34
（8）A[3]和B[3]比較，A[3] = 65，B[3] = 87，A[3] < B[3]，那么C[6] = 65
（9）最后將B[3]復(fù)制到C中，那么C[7] = 87。歸并完成。

如果我們清楚了上面的分割和歸并過程，那么我們就可以用遞歸的方法得到歸并算法的實現(xiàn)。

歸并排序算法是一種O(nlogn)的算法。它的最差，平均，最好時間都是O(nlogn)。但是它需要額外的存儲空間，這在某些內(nèi)存緊張的機(jī)器上會受到限制。

歸并算法是又分割和歸并兩部分組成的。對于分割部分，如果我們使用二分查找的話，時間是O(logn)，在最后歸并的時候，時間是O(n)，所以總的時間是O(nlogn)。

2 堆排序（HeapSort）

堆排序?qū)儆诎偃f俱樂部的成員。它特別適合超大數(shù)據(jù)量（百萬條記錄以上）的排序。因為它并不使用遞歸（因為超大數(shù)據(jù)量的遞歸可能會導(dǎo)致堆棧溢出），而且它的時間也是O(nlogn)。還有它并不需要大量的額外存儲空間。

堆排序的思路是:

(1)將原始未排序的數(shù)據(jù)建成一個堆。
(2)建成堆以后，最大值在堆頂，也就是第0個元素，這時候?qū)⒌诹銈€元素和最后一個元素交換。
(3)這時候?qū)?到倒數(shù)第二個元素的所有數(shù)據(jù)當(dāng)成一個新的序列，建一個新的堆，再次交換第一個和最后一個元素，依次類推，就可以將所有元素排序完畢。

建立堆的過程如下面的圖所示:


堆排序的具體算法如下：

Eclipse 是一個集成開發(fā)環(huán)境，同時又是一個產(chǎn)品平臺。這樣有時候我們就會碰到一個問題，在開發(fā)Debug項目的時候沒有問題，打包發(fā)布的時候就有問題了，這可如何是好？由于Debug時候和發(fā)布后plugin的ClassLoader機(jī)制不盡相同，出現(xiàn)這個問題的幾率還有會有的。

Java 在這一點上為我們提供了方法，那就是遠(yuǎn)程Debug。遠(yuǎn)程Debug一般用于Web開發(fā)，或者客戶端無法負(fù)載大規(guī)模的應(yīng)用時才會運用到，所以Desktop developer 很少會涉及到這個概念。不過Eclipse 的產(chǎn)品平臺卻讓我再次體會到了Java的強(qiáng)大。

關(guān)于Eclipse Remote Debug的文章，大家可以從此處學(xué)習(xí)：

http://www.ibm.com/developerworks/cn/opensource/os-eclipse-javadebug/index.html

Remote Debug 需要2方面的設(shè)置，一個是產(chǎn)品平臺JVM啟動參數(shù)的設(shè)置，需要讓平臺以遠(yuǎn)程Debug的模式啟動。然后是在開發(fā)端監(jiān)聽產(chǎn)品平臺的運行狀態(tài)。當(dāng)產(chǎn)品平臺運行到斷點代碼時，Eclipse開發(fā)端就會進(jìn)入Debug界面，像普通debug一樣正常debug了。

網(wǎng)上關(guān)于Eclipse Fragment的資料比較少，引用Eclipse Wiki的一段話：

An Eclipse Fragment is a way of putting your own classes into the "class loader" of another package (basically, it's as though your class was actually in the other package). If you combine this ability of a Fragment with the notion of a plugin's classpath ordering, then you can force your class to load before a like-named class in the original package.

簡而言之，F(xiàn)ragment可以利用Eclipse平臺的ClassLoader機(jī)制替換原有Plugin的某些文件，以便實現(xiàn)自己的功能。如果僅僅是因為Plugin擴(kuò)展，而需要替換自己項目的某些Plugin，可以參考文章：

http://wiki.eclipse.org/Steps_to_use_Fragments_to_patch_a_plug-in  （來之不易，感興趣的可以收藏下）

讀完這篇文章，你大概就應(yīng)該能夠了解到Fragment的實現(xiàn)分為兩部分：Host 和 Patch。這兩部分對應(yīng)的plugin的manifest.mf文件都需要做特殊處理，對于Patch的build方式也要特殊處理，那就是build出來的plugin jar里放置的不是松散的class文件，而是一個特殊的jar文件，這個 jar 文件定義在Host plugin的manifest.mf 的classpath里面。

通常情況下，按照這篇文章的做法是沒有問題的。但是在開發(fā)階段，有一種情況可能無法實現(xiàn)class的替換。

我公司的項目是使用perforce進(jìn)行項目版本控制的，但是perforce比較傻，有些重要的功能沒有實現(xiàn)，而又很關(guān)鍵，因此我想自己針對perforce的eclipse plugin做一個fragment，添加自己想要的功能。但是這個plugin沒有source code，而我自己的hack也是反編譯class文件進(jìn)行的。所以在我的work space里，并沒有Host plugin的 project。結(jié)果按照這篇文章的做法，始終不能在workbench debug的狀態(tài)下，正確load我hack過的class。因為在代碼模式下面是可以正確load的，而現(xiàn)在沒有代碼，在數(shù)次檢驗無果之后，只能針對ClassLoader去思考了。Host文件里要求一個jar文件，我就用PDE 將 fragment export出來，把Fragment plugin jar 包里包含的那個 jar 文件解壓出來，放到 patch project 里，然后重新Debug， OK，這次果然沒問題了。一個小小的Class Loader問題，真的能夠要人命呀……這應(yīng)當(dāng)算是Eclipse的一個bug吧，除非是對一個Plugin進(jìn)行hack，否則一般也不會碰到這種情況。普通的項目開發(fā)，肯定會包含Host Plugin的Project。

我的經(jīng)歷權(quán)且當(dāng)做飯后談資，不足為慮。我這兒想說的是Fragment機(jī)制非常好用，也易于Plugin擴(kuò)展。比如你的項目分為Open Source 和 Commercial 2種的話， Commercial 部分也可以通過Fragment來實現(xiàn)，不一定需要走Extension Point路線。由于網(wǎng)上相關(guān)文章不多，還需要自己多多研究，了解其機(jī)制。

Have you tried running your application elevated? (Right Click->Run As Administrator) If this doesn't work try applying an XP SP2 Compatibility shim from the Compatibility Tab in the properties dialog. (Right Click->Properties | Compatibility).

Let me know if this works.

Thanks!

沉寂了一段時間，現(xiàn)在繼續(xù)SWT Win32 Extension的開發(fā)，說實話，最近的進(jìn)展挺失敗的。Black Glossy效果我發(fā)現(xiàn)在某些機(jī)器上的顯示效果非常的卡，我自己的機(jī)器卻沒有任何問題。另外就是我最近在XP下實現(xiàn)了Window Mixer API，用來管理系統(tǒng)聲音。Win98，2000，XP都沒有問題，結(jié)果Vista讓我郁悶了，Vista居然取消了Mixer，我哭呀。以下是微軟員工給出的答案：

That's because the mixer APIs are virtualized on Windows Vista - you don't get to see the real audio hardware by default, only a virtualized version.  We did this because the vast majority of applications that used the mixer APIs were using them to control their own volume, which is quite rude (it says "I own the box, no other sounds on the system matter").

 You have two choices.  The first is to run your application in XP compatibility mode, in which case you'll be able to access the real audio hardware (please note: you'll see exactly what the hardware provides, which may lead to surprising results).

 The other choice is to use the new Vista audio engine APIs.  either the IAudioEndpointVolume API which allows you access to the master volume for each of the audio endpoints on the machine.  If you really need to access the actual audio controls the IDeviceTopology interface will allow you direct access to the various controls on the audio hardware.

通過打開Birt透視圖，然后Reset至缺省的Layout，我們能夠看到基本的一些View和一個主要的報表可視化編輯器。

先來說一下View，Birt主要的View包含7塊：

左上角包含3個視圖，Palette，Data Explorer和Resource Explorer，Palette里放置了報表常用的可視化組件，直接將這些組件拖到報表設(shè)計器的時候，這些組件并沒有作特殊的初始化處理，而從Data Explorer里向設(shè)計器拖入一個Dataset會自動生成一個Table，拖入一個Cube會生成一個Crosstab，拖入一個Dataset Column會生成一個DataItem。Data Explorer主要是用來管理和顯示數(shù)據(jù)源。Resource Explorer 老版本里是Library Explorer，新版本則變更為了Resource Explorer，用來特別顯示Library，CSS文件，其他文件則不進(jìn)行特殊處理。

左下角有2個視圖，包含Navigator視圖和Online視圖，Navigator視圖是用來建立Birt項目用的，如果是Birt Rcp版本，我們則看不到這個視圖，這是IDE版本專有的一個視圖，在Rcp版本里沒有Project這個概念，直接以文件的形式進(jìn)行管理。Outline是Birt里較為重要的視圖，所有的報表部件都會在這個View里顯示并會隨著報表的變化實時刷新。

右下角包含了Property Editor 和 Problems兩個視圖， Property Editor 用來編輯每個可視化報表元素的屬性，一般比較常用的屬性都會在前幾個Tab頁里，但是有些屬性前幾個Tab頁里都沒有，這時候需要選擇Advanced這個Tab頁，它里面包含了這個元素所有可用的屬性，如果連這兒也沒有，那么說明該元素不存在你想要的屬性。Problems視圖則用來顯示報表收集到的一些問題，如果報表校驗的時候發(fā)生錯誤，會在此處顯示出來。

以上的那些視圖屬于缺省視圖，但還有幾個視圖也比較有用，一個是Error log視圖，一個是Example視圖。Error log視圖主要是開發(fā)用的，當(dāng)你使用Birt進(jìn)行二次開發(fā)的時候，難免會碰到一些bug，當(dāng)你感覺有問題的時候，不妨打開error log視圖，只要Birt捕捉到了異常，一般都會顯示在這個視圖里。而Example視圖里提供了各種各樣的視圖，可以O(shè)pen 和 Save， Open的時候會自動幫你在workspace里建立一個項目，以便你瀏覽該項目文件。Save則是把這個Example保存到本地某個目錄。

說完視圖，再來看看Birt可視化的報表設(shè)計器，這個設(shè)計器包含了五個部分：Layout，Master Page，Script，XML Source，Preview。

Layout為設(shè)計器的主要部分，只要通過可視化的拖拽，一個報表就會被自動生成出來，當(dāng)然要想靈活運用報表設(shè)計器，就必須對各個組件的屬性了如指掌，Birt提供了豐富靈活的屬性供用戶選擇。MasterPage主要用來設(shè)置頁眉頁腳，以及打印顯示之類的功能。Script頁面，當(dāng)你在Layout頁面里選中一個元素之后，切換到Script頁面，就可以對這個元素進(jìn)行腳本編碼，主要用來監(jiān)聽各種事件，使用Javascript，在采用Web顯示里，這些腳本會生效。XML Source則是將這張報表背后的XML source顯示出來，用戶如果覺得自己對Birt很熟，可以直接在這兒手工修改代碼。Preview則是預(yù)覽Birt報表，Birt會啟動Tomcat顯示W(wǎng)eb運行效果。

基本上Birt還是比較強(qiáng)大的，基本的功能一應(yīng)俱全。可能你會發(fā)現(xiàn)缺少一些更高級花哨的功能，比如flash之類的，其實怎么說呢，不是Birt沒有，而是開源版的沒有，這個功能在Birt商業(yè)版里，可以在 http://www.actuatechina.com/download.php 下載專業(yè)版試用。如同IBM，這是這類公司特有的策略，免費上面做收費。喜歡的話，可以試一下專業(yè)版，呵呵，可惜網(wǎng)上找不到破解版。

Eclipse3.4馬上就要Release了，相信Eclipse的fans都已經(jīng)開始翹首以待，望穿秋水了。不過現(xiàn)在的RC版本用得很不爽呀，性能非常差，Eclipse的慣例就是最后一個月的工作基本上就是對性能做優(yōu)化，以達(dá)到最佳使用效果。

隨著Plugin的增多，Eclipse采用了特殊的策略，增加了一個子目錄dropins，用來放用戶新增加的plugin，而原有的plugins目錄，則基本用于系統(tǒng)基本功能，2者的區(qū)別就是，前者可以任意添加刪除，后者則基本上是一個ReadOnly的狀態(tài)，添加了就不能再作修改了，Eclipse會將每一個添加的plugin記錄下來，以后啟動就不再檢查這些plugin了。

不過對于我來說，我一直都習(xí)慣于使用plugins目錄，下了一個插件直接解壓，就直接覆蓋安裝到plugins目錄了，而且有一些plugin不支持dropins目錄，必須在plugins目錄下才能正常工作。不過一旦插件安裝失敗，想再reset就比較麻煩了。Eclipse不會自動恢復(fù)到初始安裝狀態(tài)，經(jīng)過測試，找到了一個解決方案，用原始的eclipse的文件替代2個目錄：configuration和p2目錄。plugins文件位置記錄在configuration\org.eclipse.equinox.simpleconfigurator\bundles.info里，p2目錄里則記錄了更多的初始化信息。要想Reset Eclipse3.4，這兩個目錄必須被恢復(fù)到初始化狀態(tài)，然后就可以正常使用了。

就我所知，目前把Java程序編譯成本機(jī)可執(zhí)行程序的方法有兩種，一種是GCJ，免費的，一種是Excelsior JET，商業(yè)的。我已經(jīng)很久沒有碰過GCJ了，因為當(dāng)初用起來實在是非常麻煩，現(xiàn)在的版本如何，我不太清楚。我自己使用的是Excelsior JET，版本為3.7。有一點要注意的的是，Excelsior JET的后續(xù)版本好像已經(jīng)不支持這個功能了，3.7是我所知的最后一個版本，能支持當(dāng)前所有的Win32平臺和早期的Linux（當(dāng)前比較流行的Ubuntu不支持，因為內(nèi)核版本過高，不過企業(yè)版Redhat沒有問題）。不過我是很久以前從0day當(dāng)下來的，由于0day倉儲只保留一年，故現(xiàn)在已經(jīng)找不到了，我自己的機(jī)器上也沒有安裝包了（有一次大意之下，把整個Download目錄全給刪掉了，事后悔之晚矣）。

Excelsior JET無非就是用自己的Runtime來代替JRE，只是比JRE更加靈活，根據(jù)Java程序具體的依賴來生成對應(yīng)的Runtime。其實這個Runtime也挺大的，通常10M左右，不過比起JRE，那要小很多了。SWT Extension上的那個例子只有6M，是因為我用ASPack把所有的DLL文件全部壓縮過了，體積小了一半。

就我的感覺，Excelsior JET比GCJ更加靈活，也更好用，畢竟是商業(yè)版的東西，它的網(wǎng)站上曾經(jīng)有例子將Eclipse 3.0編譯成本機(jī)程序，不過我當(dāng)初照著例子試了一遍，沒有成功。Excelsior JET的編譯過程極為耗時，我上大學(xué)的時候，當(dāng)時機(jī)器只有128M內(nèi)存，編譯了一天JRE也沒有完成，后來找同學(xué)借了根256的內(nèi)存，這才得以完成。

把JAVA代碼編譯成本機(jī)程序的弊端也是有的，那意味著你將無法在線升級，GCJ也許可以，但是Excelsior JET是絕對不行的，這是因為它最后一步要對所有DLL進(jìn)行鏈接，如果更換了DLL文件，它會檢測出來并報錯。

各位看官如果哪位有興趣，可以自行在網(wǎng)上查找Excelsior JET3.7或其他版本。由于安裝包我自己也沒有，故無法提供下載，見諒。