-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
513 lines (366 loc) · 55.8 KB
/
index.html
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
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>All Make Easier</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description">
<meta property="og:type" content="website">
<meta property="og:title" content="All Make Easier">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="All Make Easier">
<meta property="og:description">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="All Make Easier">
<meta name="twitter:description">
<link rel="alternate" href="/atom.xml" title="All Make Easier" type="application/atom+xml">
<link rel="icon" href="/favicon.png">
<link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
<link rel="stylesheet" href="/css/style.css">
</head>
<body>
<div id="container">
<div id="wrap">
<header id="header">
<div id="banner"></div>
<div id="header-outer" class="outer">
<div id="header-title" class="inner">
<h1 id="logo-wrap">
<a href="/" id="logo">All Make Easier</a>
</h1>
</div>
<div id="header-inner" class="inner">
<nav id="main-nav">
<a id="main-nav-toggle" class="nav-icon"></a>
<a class="main-nav-link" href="/">Home</a>
<a class="main-nav-link" href="/archives">Archives</a>
</nav>
<nav id="sub-nav">
<a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
<a id="nav-search-btn" class="nav-icon" title="Search"></a>
</nav>
<div id="search-form-wrap">
<form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" results="0" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit"></button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
</div>
</div>
</div>
</header>
<div class="outer">
<section id="main">
<article id="post-RTEMS针对MPC8313开发板的移植" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2016/06/27/RTEMS针对MPC8313开发板的移植/" class="article-date">
<time datetime="2016-06-27T04:11:42.000Z" itemprop="datePublished">2016-06-27</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2016/06/27/RTEMS针对MPC8313开发板的移植/">RTEMS针对MPC8313开发板的移植</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="PowerPC-MPC8313开发板"><a href="#PowerPC-MPC8313开发板" class="headerlink" title="PowerPC MPC8313开发板"></a>PowerPC MPC8313开发板</h2><p>MPC8313系列套件是一套完整的基于摩托罗拉MPC8313系列处理器的嵌入式开发平台。MPC8313系列集成PowerPC 处理器适用于那些对成本、空间、功耗和性能都有很高要求的应用领域。该器件有较高的集成度，从而降低了系统的组成开销。高集成度的结果是简化了电路板的设计，降低了功耗和加快了开发调试时间。</p>
<p>这种低成本多用途的集成处理器的设计目标是使用PCI 接口的网络基础结构、电讯和其它嵌入式应用。它可用于路由器、接线器、网络存储应用和图像显示系统。智心胜达MPC8313系列套件集成摩托罗拉MPC8313系列处理器，256M的DDR1内存以及16M 的FLASH，为用户的软件研发提供了足够的空间。开发板上则提供非常丰富的外设接口：两个10M/100M/1000M自适应以太网接口、两个三线RS-232 串口等。</p>
<p>系统具有体积小、耗电低、处理能力强、网络功能强大等特点，能够装载和运行嵌入式Linux 操作系统。用户可以在这个系统平台上进行自主软件开发，并对MPC8313系列进行测试和评估。MPC8313系列套件中提供底板硬件电路图及硬件设计文档，极大的方便了用户进行系统设计开发。智心胜达MPC8313系列套件提供完备的嵌入式LINUX 开发环境及丰富的开发调测工具软件。</p>
<p>MPC8313概览图：<br><img src="/2016/06/27/RTEMS针对MPC8313开发板的移植/framework.png" alt="logo"></p>
<h2 id="MPC8313开发板设计特点"><a href="#MPC8313开发板设计特点" class="headerlink" title="MPC8313开发板设计特点"></a>MPC8313开发板设计特点</h2><ol>
<li>将CPU尽量多的资源通过接口引出，兼容更多的应用环境。</li>
<li>Boot部分同时支持PLCC32封装的小Flash启动和TSOP封装的大Flash启动。通过跳线配置从哪一片Flash启动。系统正常工作的时候，从大Flash启动。当系统由于误操作等其他原因而启动不起来的时候，可以从小Flash启动，恢复系统。</li>
<li>开发板的所有开发不需要昂贵的PowerPC仿真器。不需要担心误操作而造成的系统启动不了的麻烦。</li>
<li>适应更多的应用环境，大Flash同时兼容8MB/16MB/32M/64MB的Flash, SDRAM兼容64MB/128MB/256MB大小。</li>
<li>内存芯片根据需要可选民用级别和工业级别。同时兼容三星、现代、Micron等公司的内存芯片。</li>
<li>电源对外统一5V电源输入，板上所需要的3.3V I/O电压和1.5V核心电压都从这个电压分压而成。</li>
<li>电源提供允许宽范围电压，最低4.5V，最高18V都可以兼容。</li>
<li>板载CPU配置跳线，允许根据实际情况修改系统配置。使用电阻配置，支持开发板的抗震性能和稳定性能。</li>
</ol>
<p>开发板允许通过跳线配置(或者电阻配置)，使用单片大Flash直接允许，而不使用PLCC封装的小Flash，允许在有抗震性能要求的应用中使用。</p>
<h2 id="MPC8313开发板基本配置"><a href="#MPC8313开发板基本配置" class="headerlink" title="MPC8313开发板基本配置"></a>MPC8313开发板基本配置</h2><h3 id="根据开发板采用特定的BSP，-并重新编译RTEMS系统"><a href="#根据开发板采用特定的BSP，-并重新编译RTEMS系统" class="headerlink" title="根据开发板采用特定的BSP， 并重新编译RTEMS系统"></a>根据开发板采用特定的BSP， 并重新编译RTEMS系统</h3><p>由于我们采用MPC8313开发板，将使用rtems项目中的mpc8313erdb (路径：rtems/c/src/lib/libbsp/poerpc/gen83xx/startup/mpc8313erdb.cfg)的bsp。</p>
<p>对rtems重新配置和编译：<br>(rtems源码相同路径下)<br><strong><br>$ mkdir powerpcRun; cd powerpcRun<br>$ ../rtems/configure –target=powerpc-rtems4.11 –enable-rtemsbsp=mpc8313erdb –enable-tests=samples –prefix=${HOME}/opt/rtemsPowerpc<br>$ make<br>$ make install
</strong></p>
<h3 id="为可执行文件生成镜像"><a href="#为可执行文件生成镜像" class="headerlink" title="为可执行文件生成镜像"></a>为可执行文件生成镜像</h3><p>在上述步骤的powerpcRun路径下：</p>
<p><strong><br>$ cd powerpc-rtems4.11/c/mpc8313erdb/testsuites/samples/ticker<br>$ powerpc-rtems4.11-objcopy –O binary ticker.exe ticker.bin<br>$ gzip -9 ticker.bin<br>$ mkimage –A ppc –O rtems –T kernel –C gzip –a 100 –e 10000 –n “RTEMS TEST”-d ticker.bin.gz ticker.img
</strong></p>
<p>其中，mkimage是uboot的一个工具，Ubuntu下可以使用apt-get install u-boot-tools (Ubuntu 12.04) 安装</p>
<h3 id="使用Minicom连接开发板"><a href="#使用Minicom连接开发板" class="headerlink" title="使用Minicom连接开发板"></a>使用Minicom连接开发板</h3><p>我们在Ubuntu下使用minicom连接开发板，采用一跟pl2303的usb-to-db9转换线分别接入PC的usb接口和开发板的默认串口，同时为了采用tftp服务，用网线直接连接PC和开发板。</p>
<p>Minicom配置如下：</p>
<ul>
<li>Serial Device: /dev/ttyUSB0</li>
<li>Bps/Par/Bits : 115200 8N1</li>
<li>Hardware Flow Control： NO</li>
<li>Software Flow Control : NO</li>
</ul>
<h3 id="在开发板上使用uboot引导镜像，运行系统应用"><a href="#在开发板上使用uboot引导镜像，运行系统应用" class="headerlink" title="在开发板上使用uboot引导镜像，运行系统应用"></a>在开发板上使用uboot引导镜像，运行系统应用</h3><p>我们在电脑PC端配置的有线静态IP：192.168.1.1 。uboot联通后， 在uboot终端 </p>
<p>**</p>
<ol>
<li>setenv ipaddr 192.168.1.2</li>
<li>setenv serverip 192.168.1.1</li>
<li>tftp 1000000 ticker.img</li>
<li>bootm<br>**</li>
</ol>
<p>由此进入RTEMS操作，截图如下：</p>
<p><img src="/2016/06/27/RTEMS针对MPC8313开发板的移植/result.png" alt="logo"></p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2016/06/27/RTEMS针对MPC8313开发板的移植/" data-id="cipxiux3h00035g49aumd9n0r" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/RTEMS/">RTEMS</a></li></ul>
</footer>
</div>
</article>
<article id="post-Ubuntu下编译RTEMS" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2016/06/27/Ubuntu下编译RTEMS/" class="article-date">
<time datetime="2016-06-27T03:37:44.000Z" itemprop="datePublished">2016-06-27</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2016/06/27/Ubuntu下编译RTEMS/">Ubuntu下编译RTEMS</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="说明"><a href="#说明" class="headerlink" title="说明"></a>说明</h2><p>由于RTEMS 的最新版本4.12的使用信息并不完善，我们决定采用更加完善稳定的RTEMS 4.11版本，配套使用4.11的RTEMS Resource Builder。</p>
<h2 id="Linux下RTEMS工具链的安装"><a href="#Linux下RTEMS工具链的安装" class="headerlink" title="Linux下RTEMS工具链的安装"></a>Linux下RTEMS工具链的安装</h2><p>Linux下的RTEMS工具链包括gcc， gdb， python等，首先使用命令安装这些工具</p>
<p><strong> $ sudo apt-get build-dep binutils gcc g++ gdb unzip git python2.7-dev</strong></p>
<h2 id="RTEMS-Resource-Builder（RSB）的使用"><a href="#RTEMS-Resource-Builder（RSB）的使用" class="headerlink" title="RTEMS Resource Builder（RSB）的使用"></a>RTEMS Resource Builder（RSB）的使用</h2><p>RSB是帮助开发者在RTEMS项目中构建所需的项目包的重要工具。它有助于巩固你需要在一个可控的和可核查的方式配置和完善一个包的详细信息。RSB面对的不仅是RTEMS及其应用开发者，而是更多的嵌入式实时操作系统的开发者。我们的开发环境是 Ubuntu 12.04。</p>
<p>RSB的获取及编译主要分为以下步骤：<br>1）获取RSB,<br> <strong><br> $ cd<br> $ mkdir -p development/rtems/src<br> $ cd development/rtems/src
</strong></p>
<p>2）切换Branch<br> <strong><br> $ cd rtems-source-builder<br> $ git checkout –b 4.11 origin/4.11
</strong></p>
<p>3) 在Ubuntu下所需配置的环境<br> <strong><br> $ sudo apt-get build-dep binutils gcc g++ gdb unzip git python2.7-dev
</strong></p>
<p>4） 检查环境<br> <strong><br> $ cd $HOME/development/rtems/src/rtems-source-builder/rtems<br> $ ../source-builder/sb-set-builder –list-bsets
</strong></p>
<p>5) 编译工具链<br> <strong><br> $../source-builder/sb-set-builder –log=l-sparc.txt –prefix=$HOME/development/rtems/4.11 4.11/rtems-sparc
</strong></p>
<h2 id="RTEMS源码编译"><a href="#RTEMS源码编译" class="headerlink" title="RTEMS源码编译"></a>RTEMS源码编译</h2><p>下载RTEMS源码，并进行编译<br> <strong><br> $ git clone git://git.rtems.org/rtems.git<br> $ cd rtems<br> $ ./bootstrap
</strong></p>
<h2 id="虚拟环境下运行RTEMS应用程序"><a href="#虚拟环境下运行RTEMS应用程序" class="headerlink" title="虚拟环境下运行RTEMS应用程序"></a>虚拟环境下运行RTEMS应用程序</h2><p>此虚拟环境使用SPARC Instruction Simulator (SIS) BSP，真实硬件环境下，需要单独编译BSP。RTEMS的编译分为四个步骤：<br>1）在bootstrap阶段，我们使用configure.ac 和 Makefile.am 作为autoconf 和automake的输入来生成文件。<br>2）在配置阶段，根据特殊的配置，一系列文件被生成。其中包括了用来编译和安装的Makefile。<br>3）在编译阶段，源文件被编译成目标文件，各个依赖库也同时被编译。<br>4）在安装阶段，依赖库，头文件和其他的一些支持文件被拷贝到安装路径下。</p>
<p>具体对应如下操作：<br><strong><br>$ mkdir b-sis<br>$ cd b-sis<br>$ ../rtems/configure –target=sparc-rtems4.11 –enable-rtemsbsp=sis –enable-tests=samples –prefix=${HOME}/install_path<br>$ make<br>$ make install<br>$ sparc-rtems4.11-run `find . -name hello.exe`
</strong></p>
<p>当然也可以使用GDB：<br><strong><br>$ sparc-rtems4.11-gdb `find . -name hello.exe`<br>$ tar sim<br>$ load<br>$ r
</strong></p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2016/06/27/Ubuntu下编译RTEMS/" data-id="cipxiux3j00045g49tg0lu89t" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/RTEMS/">RTEMS</a></li></ul>
</footer>
</div>
</article>
<article id="post-Sublime-Compile-tex" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2016/05/24/Sublime-Compile-tex/" class="article-date">
<time datetime="2016-05-24T04:19:28.000Z" itemprop="datePublished">2016-05-24</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2016/05/24/Sublime-Compile-tex/">Sublime compile tex not working</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="Problem"><a href="#Problem" class="headerlink" title="Problem"></a>Problem</h2><p>When using Sublime Text 2 + MacTex + Skim for the tex editing on mac, after all the setting, the compile of the sublime not working(using cmd + B, not working)</p>
<h2 id="Solve"><a href="#Solve" class="headerlink" title="Solve"></a>Solve</h2><p>At sublime text, go to: Preferences -> Package Settings -> Settings - User, and reset the package to the default, then the compile works.</p>
<p><img src="/2016/05/24/Sublime-Compile-tex/solve.png" alt="logo"></p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2016/05/24/Sublime-Compile-tex/" data-id="cipxiux3l00065g4955r0xblm" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Latex/">Latex</a></li></ul>
</footer>
</div>
</article>
<article id="post-Grid-Growing-Clustering-Algorithm" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2016/04/23/Grid-Growing-Clustering-Algorithm/" class="article-date">
<time datetime="2016-04-22T16:10:55.000Z" itemprop="datePublished">2016-04-23</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2016/04/23/Grid-Growing-Clustering-Algorithm/">Grid Growing Clustering Algorithm</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>对于越来越大的数据量，数据挖掘算法的时间效率成为了一个新的挑战。Grid Growing（<a href="http://sse.tongji.edu.cn/zhaoqinpei/" target="_blank" rel="external">http://sse.tongji.edu.cn/zhaoqinpei/</a>）一种基于网格的聚类算法，它把数据空间量化为一定数量的单元，形成了网状结构，所有的聚类操作都是在分出的网格中进行的。它的特点是聚类过程都是基于每一个网格，而独立于数据集，处理速度有了很大的提高。</p>
<h2 id="基本思想"><a href="#基本思想" class="headerlink" title="基本思想"></a>基本思想</h2><p>将数据空间分成若干个大小相等的单元，则每个单元包含了一定数量的数据点，接着按照一定方式选取m个种子点，从每个种子点开始，选取与它们相邻的单元，如果那个单元的数据点数大于0，那么将这个单元和这个种子单元划分到相同的簇中，同时，考察这些相邻的单元，递归地将簇扩大，直到不能向外扩展。</p>
<ul>
<li>Grid Growing的输入参数</li>
</ul>
<ol>
<li>需要选取的初始种子单元的数量m</li>
<li>选取种子单元的方式 </li>
<li>需要将数据空间等分的参数(每个维度需要等分的数量)</li>
</ol>
<p>在二维空间中，我们可以输入参数Nx和Ny来决定将数据空间分成网格的数量，其中有部分网格是不包含数据的，下图显示了一个将一个二维数据空间分为2 * 2的情况: </p>
<p><img src="/2016/04/23/Grid-Growing-Clustering-Algorithm/GridGrowing1.png" alt="logo"></p>
<p>算法中，选取所有数据点中每个维度的最大值和最小值，并将其差值等分成若干等分。上图中x维度最大值和最小值分别是26和2，那么把x维度分为2个等分，则每个网格在x维度的长度为(26-2) / 2 = 12。</p>
<p>在将数据空间等分为若干网格后，需要这些网格中选取m (m小于网格数)个网格作为种子单元，选取的方式有三种：</p>
<ol>
<li>选取密度最大的(包含数据点最多)的m个网格，如图3-7中，如果m=1，那么则选取包含6个数据点的那个网格 </li>
<li>采取随机的方式选取m个网格 </li>
<li>在空间中分布均匀地选取m个网格</li>
</ol>
<p>在符合高斯分布的数据集中，第一种方法的效果最好，另外两种方法在特定的数据集中也能取得出较好的聚类结果，例如在一些分布整齐的数据集中，方法三的选取方式可能达到最好的效果。</p>
<p>Grid Growing算法最关键的步骤是从种子点开始向外扩展的过程，这也是每个簇形成的过程。下图中，数据空间被分为了8 * 4的32个网格，其中，密度最大的两个网格的编号为(3, 2)和(7, 4)，他们分别含有10和13个数据点。</p>
<p><img src="/2016/04/23/Grid-Growing-Clustering-Algorithm/GridGrowing2.png" alt="logo"></p>
<p>在二维网格中，从种子网格考察它周围的八个网格，如果那么网格的密度大于0，那么这个网格和这个种子网格就属于同一个区域(Region)，这个区域中的数据点就属于同一个簇，同时将这个网格也作为一个新的种子点进行考察它周围的八个网格，按照这样的方式递归地扩大这个区域，同时也就能扩大了这个簇。<br>图中，编号为(2, 2)的网格是种子网格(3, 2)的邻居网格，而编号为(1, 1)的网格又是网格(2, 2)的邻居网格，所以它们同属于一个区域。这样，最终的聚类结果:</p>
<p><img src="/2016/04/23/Grid-Growing-Clustering-Algorithm/GridGrowing2.png" alt="logo"></p>
<h2 id="算法伪代码"><a href="#算法伪代码" class="headerlink" title="算法伪代码"></a>算法伪代码</h2><pre><code class="java"> Input：数据集D，分割数据空间的大小Nx, Ny, Nz....., 种子网格的个数，选择种子网格的方式
Output： 所有数据所属簇的编号
GridGrowingClustering(D, Nx, Ny, random, m){
Grids = getGrids(D,Nx,Ny)
SeedGrids = getSeedByRandom(Grids)
ClusterNumber = <span class="number">1</span>
For each seed in SeedGrids{
<span class="keyword">if</span> seed is not visited
mark seed as visited
neighborhood = getNeighbors(seed, Grids)
qulifiedNeighborhood = notEmptyNeighors(neighborhood)
<span class="function">mark qulifiedNeighborhood as visited
mark ClusterNumber to seed and qulifiedNeighborhood
<span class="title">ExpandRegion</span><span class="params">(qulifiedNeighborhood, ClusterNumber,Grids)</span>
ClusterNumber </span>= ClusterNumber + <span class="number">1</span>
}
}
ExpandRegion(neighborhood, ClusterNumber,Grids){
For each grid in neighborhood{
neighborhood’ = getNeighbors(grid, Grids)
qulifiedNeighborbood’ = notEmptyNeighbors(neighborhood’)
mark qulifiedNeighborhood’ as visited
mark ClusterNumber to qulifedNeighborhood’.<span class="function">clusterNumer
<span class="title">ExpandRegion</span><span class="params">(qulifedNeighborhood’, ClusterNumber, Grids)</span>
}
}</span>
</code></pre>
<h2 id="复杂度"><a href="#复杂度" class="headerlink" title="复杂度"></a>复杂度</h2><p> Grid Growing算法在计算过程中需要遍历每一个网格点，因此它的时间复杂度和网格的个数有关，而网格的个数由输入参数决定。<br> 以二维数据考虑，若整个数据集大小为N，将数据空间等分为Nx <em> Ny的网格，那么计算过程花费的时间为 t = 2N + 9 </em> Nx <em> Ny，因此算法的时间复杂度为O(N + Nx </em> Ny)，而多数情况下，我们对Nx和Ny的取值时，都使得Nx * Ny 远小于 N，因此时间复杂可以是O(N)，相对于其他聚类算法，具有一定的时间效率优势。</p>
<h2 id="优缺点分析"><a href="#优缺点分析" class="headerlink" title="优缺点分析"></a>优缺点分析</h2><p>Grid Growing是基于网格的聚类算法，但兼有DBSCAN的一些特征，总体上，它的</p>
<ul>
<li>优点：</li>
</ul>
<ol>
<li>算法过程依赖于分割出来的所有网格，而不是所有的数据点，所以和其他聚类算法相比，它的处理速度非常快。</li>
<li>它扩展簇的方式和DBSCAN相同，均采用从种子点向外扩展的方法来发现簇，因此它可以发现任意形状的簇。</li>
<li>它对噪声点敏感，开始没有被选为种子网格或者之后没有被扩展到的网格都被认为是噪声，因此聚类结果不易受到噪声的干扰。</li>
</ol>
<ul>
<li>缺点：</li>
</ul>
<ol>
<li>输入参数较多，需要花比较长的时间在参数的选取上，一定程度上降低了算法的使用性：将数据空间分割成等分的网格的多少对最终的聚类结果有着很大影响，需要不断尝试，才能得到最优的分割方法。</li>
<li>种子网格的个数m需要认为指定，全凭个人经验，很多情况下，也需要不断地尝试，最后得到的类簇个数才能接近预期。针对不同类型的数据分布，可以采用不同种子网格的选取方案，但是某些情况下三种方式都不一定能够得到最优的选取。</li>
<li>综合上面的优缺点，总的说来，这个算法在性能上有好的表现，可以用来处理大规模的数据，同时，也需要不断地尝试不同的参数组从而获得最优解。</li>
</ol>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2016/04/23/Grid-Growing-Clustering-Algorithm/" data-id="cipxiux3600005g498fvjo8lb" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Data-Mining/">Data Mining</a></li></ul>
</footer>
</div>
</article>
<article id="post-3Sum-Java-Solution" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2016/04/22/3Sum-Java-Solution/" class="article-date">
<time datetime="2016-04-22T15:10:29.000Z" itemprop="datePublished">2016-04-22</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2016/04/22/3Sum-Java-Solution/">3Sum Java Solution</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>来自LeetCode的3Sum问题<br>Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?<br>Find all unique triplets in the array which gives the sum of zero.</p>
<p> Note:<br> Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)<br> The solution set must not contain duplicate triplets.<br> For example, given array S = {-1 0 1 2 -1 -4},</p>
<p> A solution set is:<br> (-1, 0, 1)<br> (-1, -1, 2)</p>
<h2 id="解决思路"><a href="#解决思路" class="headerlink" title="解决思路"></a>解决思路</h2><h3 id="2Sum-问题的解决"><a href="#2Sum-问题的解决" class="headerlink" title="2Sum 问题的解决"></a>2Sum 问题的解决</h3><p>2Sum解决的事情是：从一个数组中，找到相加的和为指定的某个数k的数值对。<br>一种解决思路是，先将数组进行排序，然后在利用两个指针p和q，分别指向数组的第一个和最后一个，每次比较指针指向的两个数，如果相加的和大于k，那么q往前移一位，如果小于k，那么p往后移一位。所以算法的时间复杂度有两部分:</p>
<ol>
<li>排序: O(NlogN)</li>
<li>指针遍历一遍: O(N)</li>
</ol>
<h3 id="3Sum-问题的解决"><a href="#3Sum-问题的解决" class="headerlink" title="3Sum 问题的解决"></a>3Sum 问题的解决</h3><p>利用2Sum的思想，我们首先将数据进行排序，然后对于数组中的每一个数a，我们只要找到数组中另外的两个数b和c，他们的和为b+c = -a。 在这情况下，算法的时间复杂度为:</p>
<ol>
<li>排序花费: O(NlogN)</li>
<li>针对每个a的2Sum查找: O(N*N)</li>
</ol>
<p>当然这个问题还要考虑取出重复三元组的情况，需要考虑两点：</p>
<ol>
<li>在考虑一个数过后，并不是简单地往后或者往前移动一位，而是需要移动到一个不同于之前的数的位置</li>
<li>为了避免重复，针对每个a，都可以在a的后面位置上寻找满足b+c=-a的两个数</li>
</ol>
<p>以下为java代码，</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> List<List<Integer>> threeSum(<span class="keyword">int</span>[] nums) {</span><br><span class="line"></span><br><span class="line"> List<List<Integer>> retVal = <span class="keyword">new</span> ArrayList<List<Integer>>();</span><br><span class="line"> <span class="keyword">if</span> (nums.length<<span class="number">3</span>) <span class="keyword">return</span> retVal;</span><br><span class="line"> <span class="keyword">int</span>[] clonedNums = nums.clone();</span><br><span class="line"> Arrays.sort(clonedNums);</span><br><span class="line"> <span class="keyword">int</span> length = nums.length;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>; i<length-<span class="number">2</span>;) {</span><br><span class="line"> outLoop:</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> start=i+<span class="number">1</span>, end=length-<span class="number">1</span>; start<end; ) {</span><br><span class="line"> inLoop:</span><br><span class="line"> <span class="keyword">if</span> (clonedNums[start] + clonedNums[end] > -clonedNums[i]) {</span><br><span class="line"> <span class="comment">//move backword the end pointer</span></span><br><span class="line"> <span class="keyword">if</span> (end > <span class="number">0</span>) {</span><br><span class="line"> <span class="keyword">int</span> moves = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> (end-moves>=<span class="number">0</span> && clonedNums[end]==clonedNums[end-moves]) moves++;</span><br><span class="line"> end -= moves;</span><br><span class="line"> }</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (clonedNums[start] + clonedNums[end] < -clonedNums[i]) {</span><br><span class="line"> <span class="comment">//move forward the start pointer</span></span><br><span class="line"> <span class="keyword">if</span> (start < length - <span class="number">1</span>) {</span><br><span class="line"> <span class="keyword">int</span> moves = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> (start + moves < length && clonedNums[start] == clonedNums[start + moves]) moves++;</span><br><span class="line"> start += moves;</span><br><span class="line"> }</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (start!=i && end!=i) {</span><br><span class="line"> <span class="comment">//save one triplet</span></span><br><span class="line"> Integer[] triplet = <span class="keyword">new</span> Integer[]{clonedNums[i], clonedNums[start], clonedNums[end]};</span><br><span class="line"> Arrays.sort(triplet);</span><br><span class="line"> retVal.add(Arrays.asList(triplet));</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//move backword the end pointer</span></span><br><span class="line"> <span class="keyword">if</span> (end > <span class="number">0</span>) {</span><br><span class="line"> <span class="keyword">int</span> backwordMoves = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> (end - backwordMoves>=<span class="number">0</span> && clonedNums[end] == clonedNums[end-backwordMoves]) backwordMoves++;</span><br><span class="line"> end -= backwordMoves;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">//move forward the start pointer</span></span><br><span class="line"> <span class="keyword">if</span> (start < length - <span class="number">1</span>) {</span><br><span class="line"> <span class="keyword">int</span> forwordMoves = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> (start+forwordMoves<length && clonedNums[start] == clonedNums[start + forwordMoves]) forwordMoves++;</span><br><span class="line"> start += forwordMoves;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (i < length - <span class="number">3</span>) {</span><br><span class="line"> <span class="keyword">int</span> moves = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> ((i + moves) < length && clonedNums[i] == clonedNums[i + moves]) moves++;</span><br><span class="line"> i += moves;</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> retVal;</span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2016/04/22/3Sum-Java-Solution/" data-id="cipxiux3b00015g49k1achmwi" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Algorithm/">Algorithm</a></li></ul>
</footer>
</div>
</article>
</section>
<aside id="sidebar">
<div class="widget-wrap">
<h3 class="widget-title">Tags</h3>
<div class="widget">
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Algorithm/">Algorithm</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Data-Mining/">Data Mining</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Latex/">Latex</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/RTEMS/">RTEMS</a></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Tag Cloud</h3>
<div class="widget tagcloud">
<a href="/tags/Algorithm/" style="font-size: 10px;">Algorithm</a> <a href="/tags/Data-Mining/" style="font-size: 10px;">Data Mining</a> <a href="/tags/Latex/" style="font-size: 10px;">Latex</a> <a href="/tags/RTEMS/" style="font-size: 20px;">RTEMS</a>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Archives</h3>
<div class="widget">
<ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/06/">June 2016</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/05/">May 2016</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/04/">April 2016</a></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Recent Posts</h3>
<div class="widget">
<ul>
<li>
<a href="/2016/06/27/RTEMS针对MPC8313开发板的移植/">RTEMS针对MPC8313开发板的移植</a>
</li>
<li>
<a href="/2016/06/27/Ubuntu下编译RTEMS/">Ubuntu下编译RTEMS</a>
</li>
<li>
<a href="/2016/05/24/Sublime-Compile-tex/">Sublime compile tex not working</a>
</li>
<li>
<a href="/2016/04/23/Grid-Growing-Clustering-Algorithm/">Grid Growing Clustering Algorithm</a>
</li>
<li>
<a href="/2016/04/22/3Sum-Java-Solution/">3Sum Java Solution</a>
</li>
</ul>
</div>
</div>
</aside>
</div>
<footer id="footer">
<div class="outer">
<div id="footer-info" class="inner">
© 2016 Rambot Zhong<br>
Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
</div>
</div>
</footer>
</div>
<nav id="mobile-nav">
<a href="/" class="mobile-nav-link">Home</a>
<a href="/archives" class="mobile-nav-link">Archives</a>
</nav>
<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>
<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
<script src="/fancybox/jquery.fancybox.pack.js"></script>
<script src="/js/script.js"></script>
</div>
</body>
</html>