博客榜—查看频道“hideto”

总排名： 8354

hideto

MSN/Skype/Gmail/AIM: hideto.bj@gmail.com

RSS地址： http://hideto.javaeye.com/rss
共有9篇文章被收藏推荐
收录于2008-01-03

认领

报错

最新文章

精华文章

13位订阅者

▶ CLRS笔记6：堆排序 2008-11-19 21:40

作者: hideto 链接：http://hideto.javaeye.com/blog/271004 发表时间: 2008年11月19日声明：本文系JavaEye网站发布的原创博客文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！终于搞明白堆排序了，汗一个先上代码： ...
作者: hideto 链接：http://hideto.javaeye.com/blog/271004 发表时间: 2008年11月19日

声明：本文系JavaEye网站发布的原创博客文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！

终于搞明白堆排序了，汗一个

先上代码：

def heapify(a, idx, size)
  left_idx = 2 * idx + 1
  right_idx = 2 * idx + 2
  bigger_idx = idx
  bigger_idx = left_idx if left_idx < size && a[left_idx] > a[idx]
  bigger_idx = right_idx if right_idx < size && a[right_idx] > a[bigger_idx]
  if bigger_idx != idx
    a[idx], a[bigger_idx] = a[bigger_idx], a[idx]
    heapify(a, bigger_idx, size)
  end
end

def build_heap(a)
  last_parent_idx = a.length / 2 - 1
  i = last_parent_idx
  while i >= 0
    heapify(a, i, a.size)
    i = i - 1
  end
end

def heap_sort(a)
  return a if a.size <= 1
  size = a.size
  build_heap(a)
  while size > 0
    a[0], a[size-1] = a[size-1], a[0]
    size = size - 1
    heapify(a, 0, size)
  end
  return a
end

a = [1,5,3,6,4,3,2,7,9,0,8,0,10]
p heap_sort(a)

算法原理：
利用二叉树，先将一个数组构建成一个“最大堆”，保证对每个节点i，它的相邻子节点left和right都<=i
这时根节点就是最大的数，将它和最后一个节点互换位置
然后从根节点开始与相邻的子节点比较大小，如果left或right比它大，则互换位置，称为“下移”，直到第n-1个节点，这一轮“下移”之后根节点成为除了最后一个节点之外最大的数，将它和倒数第二个节点互换位置
。。。
循环直到所有节点做完“下移”操作，这时数组已经从小到大排好序了

关键：
有两点：
1，先构建“最大堆”，从最后一个节点的父节点开始做“下移”，直到根节点
2，每次“下移”结束后不能将最大值根节点从数组中删除，只能跟最后一个节点互换位置，这样是为了保证二叉树的结构不变，即还是一个“最大堆”，所以堆排序又称为“in place sort”

时间复杂度：
一个长度为n的数组，用二叉树来表示的话共有lgn层
对节点i，比较它相邻的left节点和right节点并做“下移”操作的时间为Θ(1)
可以用数学归纳法来证明heapsort的时间复杂度为Θ(nlogn)
1，初始化构建“最大堆”的时间为O(nlgn)，不影响结果(实际上为O(n))
2，可以知道对n=3,6,f(n) < nlgn,
而f(2n) = f(n) + nlg(2n)
        < nlgn + n(1+lgn)
        = 2nlgn + n
        < 2n(lgn + 1)
        = 2nlg2n
所以fn = Θ(nlgn)

已有 0 人发表留言，猛击->>这里<<-参与讨论

JavaEye推荐

▶ 深入理解计算机系统13，并发编程 2008-11-14 16:16

作者: hideto 链接：http://hideto.javaeye.com/blog/267093 发表时间: 2008年11月14日声明：本文系JavaEye网站发布的原创博客文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！ ...

▶ 深入理解计算机系统10，虚拟存储器垃圾收集器 2008-11-14 16:16

作者: hideto 链接：http://hideto.javaeye.com/blog/266582 发表时间: 2008年11月13日声明：本文系JavaEye网站发布的原创博客文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！虚拟存储器是对主存的一个抽象...

▶ ECUG III -- Elrang中国用户组第三次活动 2008-11-06 11:50

作者: hideto 链接：http://hideto.javaeye.com/blog/263040 发表时间: 2008年11月06日声明：本文系JavaEye网站发布的原创博客文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！详情请见： http://ecug.org/ ...

▶ MySQL优化笔记 2008-10-28 18:36

作者: hideto 链接：http://hideto.javaeye.com/blog/259126 发表时间: 2008年10月28日声明：本文系JavaEye网站发布的原创博客文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！ MySQL 5.1参考手册 :: 7. 优化一、查询优化...
作者: hideto 链接：http://hideto.javaeye.com/blog/259126 发表时间: 2008年10月28日

声明：本文系JavaEye网站发布的原创博客文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！

MySQL 5.1参考手册 :: 7. 优化

一、查询优化
使用EXPLAIN

EXPLAIN tbl_name

返回Field、Type、Null、Key、Default、Extra这几列对应的表中每个字段的值
相当于DESCRIBE tbl_name或SHOW COLUMNS FROM tbl_name

EXPLAIN [EXTENDED] SELECT select_options

借助于EXPLAIN，可以知道什么时候必须为表加入索引以得到一个使用索引来寻找记录的更快的SELECT
EXPLAIN为用于SELECT语句中的每个表返回一行信息
EXPLAIN的每个输出行提供一个表的相关信息，并且每个行包括下面的列：

id
SELECT识别符。这是SELECT的查询序列号。

select_type
SELECT类型，可以为以下任何一种：
1, SIMPLE
简单SELECT(不使用UNION或子查询)
2, PRIMARY
最外面的SELECT
3, UNION
UNION中的第二个或后面的SELECT语句
4, DEPENDENT UNION
UNION中的第二个或后面的SELECT语句，取决于外面的查询
5, UNION RESULT
UNION的结果。
6, SUBQUERY
子查询中的第一个SELECT
7, DEPENDENT SUBQUERY
子查询中的第一个SELECT，取决于外面的查询
8, DERIVED
导出表的SELECT(FROM子句的子查询)

table
输出的行所引用的表。

type
联接类型。下面给出各种联接类型，按照从最佳类型到最坏类型进行排序：
1, system
表仅有一行(=系统表)。这是const联接类型的一个特例。
2, const
表最多有一个匹配行，它将在查询开始时被读取。因为仅有一行，在这行的列值可被优化器剩余部分认为是常数。const表很快，因为它们只读

取一次！
3, eq_ref
对于每个来自于前面的表的行组合，从该表中读取一行。这可能是最好的联接类型，除了const类型。它用在一个索引的所有部分被联接使用并

且索引是UNIQUE或PRIMARY KEY。
4, ref
对于每个来自于前面的表的行组合，所有有匹配索引值的行将从这张表中读取。如果联接只使用键的最左边的前缀，或如果键不是UNIQUE或

PRIMARY KEY（换句话说，如果联接不能基于关键字选择单个行的话），则使用ref。如果使用的键仅仅匹配少量行，该联接类型是不错的。
5, ref_or_null
该联接类型如同ref，但是添加了MySQL可以专门搜索包含NULL值的行。在解决子查询中经常使用该联接类型的优化。
6, index_merge
该联接类型表示使用了索引合并优化方法。
7, unique_subquery
该类型替换了下面形式的IN子查询的ref：
value IN (SELECT primary_key FROM single_table WHERE some_expr)
unique_subquery是一个索引查找函数，可以完全替换子查询，效率更高。
8, index_subquery
该联接类型类似于unique_subquery。可以替换IN子查询，但只适合下列形式的子查询中的非唯一索引：
value IN (SELECT key_column FROM single_table WHERE some_expr)
9, range
只检索给定范围的行，使用一个索引来选择行。key列显示使用了哪个索引。key_len包含所使用索引的最长关键元素。在该类型中ref列为NULL

。
10, index
该联接类型与ALL相同，除了只有索引树被扫描。这通常比ALL快，因为索引文件通常比数据文件小。
当查询只使用作为单索引一部分的列时，MySQL可以使用该联接类型。
11, ALL
对于每个来自于先前的表的行组合，进行完整的表扫描。

possible_keys
possible_keys列指出MySQL能使用哪个索引在该表中找到行。
如果该列是NULL，则没有相关的索引。
在这种情况下，可以通过检查WHERE子句看是否它引用某些列或适合索引的列来提高你的查询性能。
为了看清一张表有什么索引，使用SHOW INDEX FROM tbl_name。

key
key列显示MySQL实际决定使用的键（索引）。
如果没有选择索引，键是NULL。
要想强制MySQL使用或忽视possible_keys列中的索引，在查询中使用FORCE INDEX、USE INDEX或者IGNORE INDEX。

key_len
key_len列显示MySQL决定使用的键长度。如果键是NULL，则长度为NULL。

ref
ref列显示使用哪个列或常数与key一起从表中选择行。

rows
rows列显示MySQL认为它执行查询时必须检查的行数。

Extra
该列包含MySQL解决查询的详细信息。下面解释了该列可以显示的不同的文本字符串：
1, Distinct
MySQL发现第1个匹配行后，停止为当前的行组合搜索更多的行。
2, Not exists
MySQL能够对查询进行LEFT JOIN优化，发现1个匹配LEFT JOIN标准的行后，不再为前面的的行组合在该表内检查更多的行。
3, range checked for each record(index map: #)
MySQL没有发现好的可以使用的索引，但发现如果来自前面的表的列值已知，可能部分索引可以使用。
4, Using filesort
MySQL需要额外的一次传递，以找出如何按排序顺序检索行。
5, Using index
从只使用索引树中的信息而不需要进一步搜索读取实际的行来检索表中的列信息。当查询只使用作为单一索引一部分的列时，可以使用该策略

。
6, Using temporary
为了解决查询，MySQL需要创建一个临时表来容纳结果。典型情况如查询包含可以按不同情况列出列的GROUP BY和ORDER BY子句时。
7, Using where
WHERE子句用于限制哪一个行匹配下一个表或发送到客户。
8, Using sort_union(...), Using union(...), Using intersect(...)
这些函数说明如何为index_merge联接类型合并索引扫描。
9, Using index for group-by
类似于访问表的Using index方式，Using index for group-by表示MySQL发现了一个索引，可以用来查询GROUP BY或DISTINCT查询的所有列，

而不要额外搜索硬盘访问实际的表。

MySQL优化器会对JOIN、INDEX、GROUP BY、ORDER BY做一些优化

二、MySQL锁
对WRITE，MySQL使用的表锁定方法原理如下
* 如果在表上没有锁，在它上面放一个写锁。
* 否则，把锁定请求放在写锁定队列中。
对READ，MySQL使用的锁定方法原理如下：
* 如果在表上没有写锁定，把一个读锁定放在它上面。
* 否则，把锁请求放在读锁定队列中。

可以通过检查table_locks_waited和table_locks_immediate状态变量来分析系统上的表锁定争夺：

SHOW STATUS LIKE 'Table%'

三、数据库结构优化
1, 使数据尽可能小
尽可能地使用最有效(最小)的数据类型
尽可能使用较小的整数类型使表更小
如果可能，声明列为NOT NULL
对于MyISAM表，如果没有任何变长列(VARCHAR、TEXT或BLOB列)，使用固定尺寸的记录格式
在MySQL/InnoDB中，InnoDB表使用更紧凑的存储格式
紧凑的InnoDB格式也改变了包含UTF-8数据的CHAR列的保存方式
每张表的主索引应该尽可能短
只创建你确实需要的索引
如果很可能一个索引在头几个字符上有唯一的前缀，仅仅索引该前缀比较好

使用列索引和多列索引
索引用于快速找出在某个列中有一特定值的行。
不使用索引，MySQL必须从第1条记录开始然后读完整个表直到找出相关的行。
表越大，花费的时间越多。
如果表中查询的列有一个索引，MySQL能快速到达一个位置去搜寻到数据文件的中间，没有必要看所有数据。
索引用于下面的操作：
1，快速找出匹配一个WHERE子句的行。
2，删除行。如果可以在多个索引中进行选择，MySQL通常使用找到最少行的索引。
3，当执行联接时，从其它表检索行。
4，对具体有索引的列key_col找出MAX()或MIN()值。由预处理器进行优化，检查是否对索引中在key_col之前发生所有关键字元素使用了WHERE

key_part_# = constant。

四、优化MySQL服务器
这个命令生成所有mysqld选项和可配置变量的列表：

mysqld --verbose --help

如果有一个mysqld服务器正在运行，通过连接它并执行这个命令，可以看到实际上使用的变量的值：

SHOW VARIABLES;

还可以通过下面的语句看到运行服务器的统计和状态指标：

SHOW STATUS;

通常情况若给MySQL更多的内存性能会更好。
当调节MySQL服务器时，要配置的两个最重要的变量是key_buffer_size和table_cache：

mysqld_safe --key_buffer_size=64M --table_cache=256 \
            --sort_buffer_size=4M --read_buffer_size=1M &

不同的机器硬件上使用不同的编译器性能也会有不同的提高

已有 1 人发表留言，猛击->>这里<<-参与讨论

JavaEye推荐

收录该频道的主题秀

原子菌个人收藏(36)

原子菌创建于2008-02-26

搜索不到您的频道？
>立即加入
想与您的读者互动？快来认领您的频道
>立即认领
想知道您的博客详细订阅数据么？
>到FeedSky查看
想体验专业的博客托管服务么？
>注册BlogBus

推荐频道：
已打标签：
添加标签：
	别人打过的标签：我使用过的标签：