g*****u 发帖数: 298 | 1 1. 美国免费电话都是800开始,现在有866,866,888并且还在增长。你只有1MB内存。如
何排序及检索?
排序:multi-pass
检索如何做?
2. 使用位图时,初始化要占用大量时间。如何通过某个技巧来绕开,以便首次访问某
向量时就将其初始化为0? |
r**u 发帖数: 1567 | 2 1. 先对all available phone numbers 构造一个bitmap,把这个bitmap写成文件
bitfile。
bitfile logical divided into pages of size of 1MB
检索的时候,给一个电话,e.g., 8008997654,找到这个number在bitfile的哪一个
page,
8008997654/1MB。然后move文件指针到这个page,读入这个page,check这个number
在不在
这page里。
2. 题目不明白,calloc?
【在 g*****u 的大作中提到】 : 1. 美国免费电话都是800开始,现在有866,866,888并且还在增长。你只有1MB内存。如 : 何排序及检索? : 排序:multi-pass : 检索如何做? : 2. 使用位图时,初始化要占用大量时间。如何通过某个技巧来绕开,以便首次访问某 : 向量时就将其初始化为0?
|
s*********t 发帖数: 1663 | 3 http://www.cs.bell-labs.caom/cm/cs/pearls/sol01.html
第九题应该就是他说的第二题
很tricky
number
【在 r**u 的大作中提到】 : 1. 先对all available phone numbers 构造一个bitmap,把这个bitmap写成文件 : bitfile。 : bitfile logical divided into pages of size of 1MB : 检索的时候,给一个电话,e.g., 8008997654,找到这个number在bitfile的哪一个 : page, : 8008997654/1MB。然后move文件指针到这个page,读入这个page,check这个number : 在不在 : 这page里。 : 2. 题目不明白,calloc?
|
m********g 发帖数: 692 | 4 take 8 out, when constructing the bitmap.
number
【在 r**u 的大作中提到】 : 1. 先对all available phone numbers 构造一个bitmap,把这个bitmap写成文件 : bitfile。 : bitfile logical divided into pages of size of 1MB : 检索的时候,给一个电话,e.g., 8008997654,找到这个number在bitfile的哪一个 : page, : 8008997654/1MB。然后move文件指针到这个page,读入这个page,check这个number : 在不在 : 这page里。 : 2. 题目不明白,calloc?
|
x***y 发帖数: 633 | 5 It's the same like fast memory initialization. Besides the original array,
keep 2 other arrays A B of the same length and an integer count(initialized as 0)that indicates how many elements have been initialized. When Array[i] is first initialized, A[i] = count, B[count] =i and count++ and return 0 ; when array[j] is accessed, we check whether A[j]
【在 g*****u 的大作中提到】 : 1. 美国免费电话都是800开始,现在有866,866,888并且还在增长。你只有1MB内存。如 : 何排序及检索? : 排序:multi-pass : 检索如何做? : 2. 使用位图时,初始化要占用大量时间。如何通过某个技巧来绕开,以便首次访问某 : 向量时就将其初始化为0?
|
y****w 发帖数: 3747 | 6 试着把800,866,888编码成0b00,0b01,0b10再有其他就用0b11,或增加位数,
【在 g*****u 的大作中提到】 : 1. 美国免费电话都是800开始,现在有866,866,888并且还在增长。你只有1MB内存。如 : 何排序及检索? : 排序:multi-pass : 检索如何做? : 2. 使用位图时,初始化要占用大量时间。如何通过某个技巧来绕开,以便首次访问某 : 向量时就将其初始化为0?
|
g*****u 发帖数: 298 | 7 这个链接不工作啊。。。
【在 s*********t 的大作中提到】 : http://www.cs.bell-labs.caom/cm/cs/pearls/sol01.html : 第九题应该就是他说的第二题 : 很tricky : : number
|
g*****u 发帖数: 298 | 8 这题问题不仅在于此,即使不考虑8xx,剩下也是10M个号码,主存只有8*2^20位,不够
的。只能按前面人的说法,放到硬盘上然后计算区间,查询一次需要一次random disk
access。
【在 y****w 的大作中提到】 : 试着把800,866,888编码成0b00,0b01,0b10再有其他就用0b11,或增加位数,
|
s*********t 发帖数: 1663 | 9 我发现了.caom。。。。
不知道为啥会出这个粘贴错误
lol
应该是这个
http://www.cs.bell-labs.com/cm/cs/pearls/sol01.html
【在 g*****u 的大作中提到】 : 这个链接不工作啊。。。
|
y****w 发帖数: 3747 | 10 也是,没数位数,呵呵,
disk
【在 g*****u 的大作中提到】 : 这题问题不仅在于此,即使不考虑8xx,剩下也是10M个号码,主存只有8*2^20位,不够 : 的。只能按前面人的说法,放到硬盘上然后计算区间,查询一次需要一次random disk : access。
|
w******1 发帖数: 520 | 11 raou , bitmap怎么建造, 能讲讲么? |
l*y 发帖数: 21010 | 12 google那本书的题目,有源代码
【在 w******1 的大作中提到】 : raou , bitmap怎么建造, 能讲讲么?
|
w******1 发帖数: 520 | 13 Thank you
I got it.
如果有这样的题。比如N 个数中有几对重复的数, 也可以用这个BITMAP来实现了。 第
一次出现, 这个数,设定值为一, 第二次出现, 就直接打印出来。
/* phase 1: initialize set to empty */
for i = [0, n)
bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file
bit[i] = 1
/* phase 3: write sorted output */
for i = [0, n)
if bit[i] == 1
write i on the output file
【在 l*y 的大作中提到】 : google那本书的题目,有源代码
|