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那本书的题目，有源代码
|
