| « | may 2026 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 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 | | | | | | | |
|
公告 |
| 暂无公告... |
| Blog信息 |
|
blog名称:
日志总数:32
评论数量:9
留言数量:-1
访问次数:112965
建立时间:2008年12月3日 |
| |
|
 矩阵运算引起的换页错误，大家有什么方案
原创空间
liangbin 发表于 2008/12/3 23:40:20 |
|
发信人: pennyliang (pennyliang), 信区: SearchEngineTech标 题: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jun 29 11:03:37 2008), 站内 问题如下，比如一个boolean矩阵，为term*doc。即行表示term.列表示doc. 1 2 3 4 5 6 0 | 0 0 0 0 0 1 1 | 0 1 0 1 0 0 2 | 1 0 1 0 1 1 表示doc1包含term2,doc2包含term1,...doc6包含term0,term2 在访问的时候，希望由term,取doclist,因此希望是按行读取. 例如取term2,取出1 0 1 0 1 1 但是在创建这个矩阵时就必须按列存储，如果矩阵的列足够大，几乎在创建的时候每存一个值都可能是一个page fault，也就是一个n*m的矩阵，如果m足够大，则可能会造成m*n次page fault。大家有何高见，进来探讨一下? --硕士要啥自行车啊 ※ 修改:·pennyliang 于 Jun 29 20:53:23 2008 修改本文·[FROM: 58.30.83.*]※ 来源:·水木社区 newsmth.net·[FROM: 58.30.83.*]
[本篇全文] [回复文章] [本篇作者：shuke] [回信给作者] [进入讨论区] [返回顶部]
2
发信人: shuke (小白), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jun 29 13:34:44 2008), 站内batch一下？一次读m1个文档，得到一个n*m1的小矩阵，再一次性拷贝到你的大矩阵里,只有n次page fault。总共是n*m/m1次page fault.【 在 pennyliang (pennyliang) 的大作中提到: 】: 问题如下，比如一个boolean矩阵，为term*doc。即行表示term.列表示doc.: 1 2 3 4 5 6 : 0 | 0 0 0 0 0 1: ...................-- 小白是小新的宠物狗。over.※ 来源:·水木社区 http://newsmth.net·[FROM: 65.57.245.*]
[本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部]
3
发信人: pennyliang (pennyliang), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Mon Jun 30 12:26:56 2008), 站内 小白同学曹冲称象的方法不错【 在 shuke (小白) 的大作中提到: 】: batch一下？一次读m1个文档，得到一个n*m1的小矩阵，再一次性拷贝到你的大矩阵里,只有n次page fault。总共是n*m/m1次page fault.--硕士要啥自行车啊 ※ 来源:·水木社区 newsmth.net·[FROM: 211.99.222.*]
[本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部]
4
发信人: pennyliang (pennyliang), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Tue Jul 15 12:31:35 2008), 站内如果那位同学面试遇到这个题目答这三点，可以堪称完美(1)sort(2)compress (3)partition【 在 shuke (小白) 的大作中提到: 】: batch一下？一次读m1个文档，得到一个n*m1的小矩阵，再一次性拷贝到你的大矩阵里,只有n次page fault。总共是n*m/m1次page fault.--硕士要啥自行车啊 ※ 来源:·水木社区 newsmth.net·[FROM: 211.99.222.*]
[本篇全文] [回复文章] [本篇作者：houzhijiang] [回信给作者] [进入讨论区] [返回顶部]
5
发信人: houzhijiang (算法+编程+口语), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jul 20 10:08:13 2008), 站内详细解释一下？【 在 pennyliang (pennyliang) 的大作中提到: 】: 如果那位同学面试遇到这个题目答这三点，可以堪称完美: (1)sort: (2)compress : ...................--※ 来源:·水木社区 http://newsmth.net·[FROM: 221.131.61.*]
[本篇全文] [回复文章] [本篇作者：ignace] [回信给作者] [进入讨论区] [返回顶部]
6
发信人: ignace (心茫然-坚持,信任), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jul 20 10:15:54 2008), 站内page fault是啥意思出题目的人知道么?而且,这个也不是系统的主要瓶颈,热点..【 在 pennyliang (pennyliang) 的大作中提到: 】: 问题如下，比如一个boolean矩阵，为term*doc。即行表示term.列表示doc.: 1 2 3 4 5 6 : 0 | 0 0 0 0 0 1: ...................--心若在灿烂中死去爱会在灰烬里重生※ 来源:·水木社区 newsmth.net·[FROM: 211.99.222.*]
[本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部]
7
发信人: pennyliang (pennyliang), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jul 20 17:45:48 2008), 站内内存和对换区来回换。如果虚拟的页不再内存中，则发生一次从磁盘调页的工作。称这个为一次page-fault.如果虚拟的页在内存中，则直接用之。一般小数据集的计算，工作集很快就能达到稳定，因此page-fault的机会很少，但是海量数据处理，这种局部性就差。不知道我理解的对不对。【 在 ignace (心茫然-坚持,信任) 的大作中提到: 】: page fault是啥意思出题目的人知道么?: 而且,这个也不是系统的主要瓶颈,热点..--硕士要啥自行车啊 ※ 来源:·水木社区 newsmth.net·[FROM: 58.30.83.*]
[本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部]
8
发信人: pennyliang (pennyliang), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jul 20 18:02:05 2008), 站内MG一书的作者花了一章来解释这个问题。。。排序，就是变随机访问为顺序访问。做过索引的人应该懂，我就不展开了。压缩，索引项不同分量压缩方法是不同的，d-gap,occur-gap,压缩后可以降低大量磁盘IO。切分，这个就更容易了，把大任务分解成若干小任务。如果我们想像一下有这样的机器，问题就简单了。（1）内存足够大，不需要对换区，完全不可能出现page-fault（2）内存不分页，采用早期的内存管理方法，比如可变分区方法等。【 在 houzhijiang (算法+编程+口语) 的大作中提到: 】: 详细解释一下？--硕士要啥自行车啊 ※ 来源:·水木社区 newsmth.net·[FROM: 58.30.83.*]
[本篇全文] [回复文章] [本篇作者：duckyaya] [回信给作者] [进入讨论区] [返回顶部]
9
发信人: duckyaya (女人们的咖啡), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jul 20 18:16:25 2008), 站内看来并行是王道【 在 pennyliang (pennyliang) 的大作中提到: 】: MG一书的作者花了一章来解释这个问题。。。: 排序，就是变随机访问为顺序访问。做过索引的人应该懂，我就不展开了。: 压缩，索引项不同分量压缩方法是不同的，d-gap,occur-gap,压缩后可以降低大量磁盘IO。: ...................--自动对联机：床前明月光枕上有美女床前明月光案上青春色※ 来源:·水木社区 newsmth.net·[FROM: 202.106.180.35]
[本篇全文] [回复文章] [本篇作者：ignace] [回信给作者] [进入讨论区] [返回顶部]
10
发信人: ignace (心茫然-坚持,信任), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jul 20 23:07:23 2008), 站内有内存不够这个前提,那是对的我开始没想到这茬【 在 pennyliang (pennyliang) 的大作中提到: 】: 内存和对换区来回换。如果虚拟的页不再内存中，则发生一次从磁盘调页的工作。称这个为一次page-fault.: 如果虚拟的页在内存中，则直接用之。: 一般小数据集的计算，工作集很快就能达到稳定，因此page-fault的机会很少，但是海量数据处理，这种局部性就差。: ...................--心若在灿烂中死去爱会在灰烬里重生※ 来源:·水木社区 newsmth.net·[FROM: 211.99.222.*]
[本篇全文] [回复文章] [本篇作者：ignace] [回信给作者] [进入讨论区] [返回顶部]
11
发信人: ignace (心茫然-坚持,信任), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Sun Jul 20 23:09:57 2008), 站内排序过程必然也会有大量的page fault啊,如果工作集很大的话如何计算带来的好处呢? MG里应该有说明, 不过,在这里能不能简单解释一下,让我们能快点理解这个问题MG书是啥.有空学习学习去.【 在 pennyliang (pennyliang) 的大作中提到: 】: MG一书的作者花了一章来解释这个问题。。。: 排序，就是变随机访问为顺序访问。做过索引的人应该懂，我就不展开了。: 压缩，索引项不同分量压缩方法是不同的，d-gap,occur-gap,压缩后可以降低大量磁盘IO。: ...................--心若在灿烂中死去爱会在灰烬里重生※ 来源:·水木社区 newsmth.net·[FROM: 211.99.222.*]
[本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部]
12
发信人: pennyliang (pennyliang), 信区: SearchEngineTech标 题: Re: 矩阵运算引起的换页错误，大家有什么方案发信站: 水木社区 (Mon Jul 21 06:48:28 2008), 站内排序分为，内排和外排两部。内排尽可能用已有内存，排出有序归并段，sorted merge runs.外排通过原地的多路归并排除最后的顺序。内排不会有page fault的。外排在堆中完成，也都是在可用内存内完成,所以也不会有page fault【 在 ignace (心茫然-坚持,信任) 的大作中提到: 】: 排序过程必然也会有大量的page fault啊,如果工作集很大的话: 如何计算带来的好处呢? MG里应该有说明, 不过,: 在这里能不能简单解释一下,: ...................--硕士要啥自行车啊 ※ 修改:·pennyliang 于 Jul 21 06:48:50 2008 修改本文·[FROM: 58.30.83.*]※ 来源:·水木社区 newsmth.net·[FROM: 58.30.83.*]http://www.newsmth.net/bbstcon.php?board=SearchEngineTech&gid=7799 |
|
|