posts - 12, comments - 3, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2010年1月17日

快速排序介绍:
快速排序(Quicksort)是对冒泡法的一种改进。由C. A. R. Hoare在1962年提出。

基本思想是:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

 1 package my.sort;
 2 
 3 public class QuickSort {
 4 
 5     static int a[] = { 101113164325456 };
 6 
 7     public static void sort(int L, int R) {
 8         int i = L - 1;
 9         int j = R;
10         int tmp;
11         if (L < R) {
12             for (; i < R;) {
13                 while (a[++i] > a[R]) {// 从i开始,从前往后扫描,如果发现大于a[R](数组最后一个值),与之对换
14                     while (j > 0) {
15                         if (j <= i) {// 如果i == j结束跳出循环
16                             break;
17                         }
18                         if (a[--j] < a[R]) {// 从J开始,从后往前扫描,如果发现小于a[i],与之对换
19                             tmp = a[j];
20                             a[j] = a[i];
21                             a[i] = tmp;
22                         }
23                         
24                     }
25                     
26                     tmp = a[i];
27                     a[i] = a[R];
28                     a[R] = tmp;
29                     
30                     for(int b : a) {
31                         System.out.print(b + " ");//打印没一趟排序结果
32                     }
33                     System.out.println();
34                     
35                     //把数组分成两段排序
36                     sort(L, i-1);//基准数前面的数据进行排列
37                     sort(i, R);//基准数后面的数据排列
38                 }
39             }
40         }
41 
42     }
43 
44     public static void main(String[] args) {
45         System.out.println("排序前:");
46         for (int b : a) {
47             System.out.print(b + " ");
48         }
49         System.out.println("\n排序过程:");
50         sort(0, a.length - 1);
51         System.out.println("排序后:");
52         for (int b : a) {
53             System.out.print(b + " ");
54         }
55         System.out.println();
56     }
57 }
58 

posted @ 2010-01-17 16:14 创意恒动力 阅读(218) | 评论 (0)编辑 收藏

2010年1月4日

自我理解java linkedlist插入数据的算法:
首先看一下,linkedlist插入源代码:

 1 public class LinkedList
 2     extends AbstractSequentialList
 3     implements List, Deque, Cloneable, java.io.Serializable
 4 {
 5     private transient Entry header = new Entry(nullnullnull);//初始化时先实例一个header,链表头
 6 
 7 
 8     /**
 9      * Constructs an empty list.//构造一个空链表
10      */
11     public LinkedList() {
12         header.next = header.previous = header; //把链表头和尾先连到自己(1)
13         addBefore(e, header);(2
14 
15     }
16 
17 .
18 
19  public boolean add(E e) {//插入链表方法
20             return true;
21     }
22 .
23 
24 private static class Entry {//每个数据存放,所要用到的静态内部类
25      E element;
26      Entry next;//后一个节点
27      Entry previous;//接一个节点
28 
29      Entry(E element, Entry next, Entry previous) {
30          this.element = element;
31          this.next = next;
32          this.previous = previous;
33      }
34 }
35 
36 
37 //插入操作方法
38     private Entry addBefore(E e, Entry entry) {
39          Entry newEntry = new Entry(e, entry, entry.previous);(3
40          newEntry.previous.next = newEntry;(4
41          newEntry.next.previous = newEntry;(5
42          size++;(6
43          modCount++;
44          return newEntry;
45     }
46 
47 
48 /*其他方法~~*/
49 
50 

以上部分就是算法所在:(一个简单的公式替换过程)

算法步骤(对应上面的编号):

(1)实例化一个header (Entry)

header.next = header

header.previous = header

当有第一条数据插入链表:

(3)实例化一个 Entry newEntry (以下简称E1)

E1.next = header

E1.previous = header.previous

E1.previous.next = header.previous.next = header.next

(4)由上面可得:

newEntry.previous.next = newEntry;

作用:

相当于 E1.previous.next = header.next = E1

其实就是,让上一个节的next指向下一个节点数据

所以header.next 的下一个节点就是E1

(5)E1.next.previous = header.previous = E1(这里用得巧妙)

其实这个用法单从E1.next.previous= E1单这么看,很直观因为E1的下一个节点数据的上一个节点就应该是E1

从上面可知,E1.next == header,为什么要把header.previous = E1呢?

其实包含着一个递归在里面。

如果再新增一个数据 Entry E2 :

从上面的代码可以看出,E2的实例化过程是:(其实linkedlist每次新增一个数据,都通过header传值)

Entry E2 = new Entry(data, header, header.previous);

注意代码部分的负值。关键就是这里,实例化的时候,E2.previous = header.previous = E1
简单得完成了负值过程。

然后 E2.previous.next = E1.next = E2
E2.next.previous = header.previous = E2 .......(接着插入下一条数据,如此递归)

(6)记录链表位数


涉及到了一个小小的递归算法。

linkedlist记录一。完毕。。


posted @ 2010-01-04 19:23 创意恒动力 阅读(2393) | 评论 (0)编辑 收藏

2009年12月29日

弄了一段时间的tokyocabinet btree结构数据库。
存储的时候发现,tokyocabinet sync同步时,先让数据存放在内存,然后对比同步文件和内存的数据,使数据达到一直。
sync()这个tc方法易用,但不好控制。
稍有不慎就会使持久化文件容量以几何级数递增。

之前自己用mina框架做了一个btree的网络链接端口,起初内存一直飙升。弄了很久都不明白。
开始以为是mina造成的,而且cpu占用率居高不下。

后来拆分测试。发现单独mina的数据传输,内存并不高,非常低。
但是tc的单独测试发现,写文件的cpu占用率特高,多线程写入的情况下,会有明显阻塞。
初步了解了jvm gc的算法,如果cpu占用率搞,gc回收内存的能力会明显下降。
为了解决这一点,修改了一下网络端口的框架结构。

把数据接受端跟数据处理端分开:
1.接受端可以接受多个socket多线程传输,而数据处理端锁定只接受从接收端的一个或不超过5个scoket传输数据。
对tc的操作,单线程写入,感觉上比多线程处理流畅,特别在同步优化文件那一刻。
优化文件,需要的cpu和内存都比较厉害。
2.tc接受数据以后,不要马上写文本。等接受一批(100-10000)数据后,再使用同步方法。
3.参照第2条,定期优化文件,这样不至于文件过大。但是数据量增大,文件虽然优化了,写入速度不会怎么改变。
4.优化同步文件后,特别在数据量在不断增大的情况下。不要以为没有回收内存,其实gc已经很努力回收(长时间观察jprofiler的统计数据证明了这一点)当你向tc取数据的时候,你会发现,内存会逐级递减。


经过一番调整,用jprofiler测试,自己搭建的网络框架,内存锁定在250m左右。
可能到实际运行的时候,内存占用量会增加,但是只会达到一个相当的稳定值。
现用于公司的队列系统,内存总量不超过600m,偶尔超过是由于同步文件造成的,等数据稳定后,内存会回到稳定值。以后再作优化,希望能把内存压制200m左右。

初学nio,以此为记。

posted @ 2009-12-29 10:22 创意恒动力 阅读(615) | 评论 (0)编辑 收藏

2009年9月30日

     摘要: 不同方式的比较TC引擎,有利于开发高速的数据缓存

近日比较了一下TC中,HDB和BDB的速度,挺有意思的。  阅读全文

posted @ 2009-09-30 00:11 创意恒动力 阅读(805) | 评论 (0)编辑 收藏

一位语文老师的告白

http://docs.google.com/present/view?id=ddpwddzp_10j7xb9dgj

 

以前有看过,不过回味下,挺搞笑的

 

============================



文章来源:http://henry2009.javaeye.com/blog/479384

posted @ 2009-09-30 00:11 创意恒动力 阅读(123) | 评论 (0)编辑 收藏

SVNKit是一个纯Java开源Subversion客户端库,SVNKit支持Java
API控制和操作Subversion工作拷贝和资源,支持http,https,svn和svn+ssh连接协议等。

Subversion is a leading and fast growing Open Source version control system.
          SVNKit brings Subversion
closer to the Java world! SVNKit is a pure Java toolkit
          - it implements all Subversion features and provides APIs to work with
          Subversion working copies, access and manipulate Subversion repositories
          - everything within your Java application.

通过SVNKit,用户可以很容易地操作控制Subversion。
SVNKit 1.3.1发布,可以在http://svnkit.com/ 上下载

下载地址:
http://svnkit.com/download.php

svnkit文档地址:
http://svnkit.com/documentation.html

(有了这个东东,就不用在linux下安装这个库,那个c编译包了~~~呵呵)


文章来源:http://henry2009.javaeye.com/blog/474715

posted @ 2009-09-30 00:11 创意恒动力 阅读(328) | 评论 (0)编辑 收藏

     摘要:   阅读全文

posted @ 2009-09-30 00:11 创意恒动力 阅读(305) | 评论 (0)编辑 收藏

     摘要:   阅读全文

posted @ 2009-09-30 00:11 创意恒动力 阅读(124) | 评论 (0)编辑 收藏

     摘要: Sphinx :Sphinx是一个基于SQL的全文检索引擎,可以结合MySQL,PostgreSQL做全文搜索,它可以提供比数据库本身更专业的搜索功能,使得应用程序更容易实现专业化的全文检索。Sphinx特别为一些脚本语言设计搜索API接口,如PHP,Python,Perl,Ruby等,同时为 MySQL也设计了一个存储引擎插件。  阅读全文

posted @ 2009-09-30 00:11 创意恒动力 阅读(889) | 评论 (0)编辑 收藏

     摘要: 近期闹得火红的小日本B+数据库tokyocabinet(以下简称tc),性能确实不容置疑,但是安装却老是出问题,问题都出自于一大堆的依赖错误。要搞定确实折腾!主要问题是tc要依赖bzip2,还有libbz2这个linux常规压缩工具。说是常规,但是ubuntu,opensuse常规是不会安装的。搞不懂,哪来常规。
也许常规是对Radhat而言的,我用5.3企业版的radhat不会出现这种麻烦事。  阅读全文

posted @ 2009-09-30 00:11 创意恒动力 阅读(6372) | 评论 (1)编辑 收藏