c**********e
发帖数: 2007 | 1 3. what does it look like if we plot: floating variable against the
actual value assigned to the variable?
这个问题答案显然是一个阶梯函数样子。但是更具体应该怎么样？
4. Given a sample of 100000000 data, how do we approximate the mean and
variance of the underlying random variable. How to avoid round off
error.
先猜一个均值，然后对余数相加吗？怎么避免舍入误差？
5. Given a machine of memory 10Mb, sort data of 10GB stored in a file.
思路到是有，比如参照合并排序，但是具体怎么实现？内存也太小了点。
再就是参照快速排序。但是递归式的快速排序是要不少空间的。
57. Given an array of size 4 billion which stores integers. Is it
possible to cover all integer expressed by 32 bit?
4 billion 大概就是从-2^31 -> 2^31-1, 也就是长整数的范围吧。但这个 32 bit
有是个什么概念？
往计算机大牛多多指点。不胜感激。 |
S*********g
发帖数: 5298 | 2 4是要严格计算？
严格计算的话，分块算平均.
譬如说，每10000个算一个平均，这样就有10000个平均值
再算这10000个平均值的平均值。
variance因为其实也是算平均值，所以也可以类似的这么求
【在 c**********e 的大作中提到】
: 3. what does it look like if we plot: floating variable against the
: actual value assigned to the variable?
: 这个问题答案显然是一个阶梯函数样子。但是更具体应该怎么样？
: 4. Given a sample of 100000000 data, how do we approximate the mean and
: variance of the underlying random variable. How to avoid round off
: error.
: 先猜一个均值，然后对余数相加吗？怎么避免舍入误差？
: 5. Given a machine of memory 10Mb, sort data of 10GB stored in a file.
: 思路到是有，比如参照合并排序，但是具体怎么实现？内存也太小了点。
: 再就是参照快速排序。但是递归式的快速排序是要不少空间的。
|
k*******d
发帖数: 1340 | 3 5就是merge sort吧，内存太小。 可以每10M的数据用quick sort排好存回到盘上，然
后就是merge sort
57照这个意思是可以了？32位整数就是从-2^31 -> 2^31-1吧
3. 要注意的是在浮点数格式下，有效数字是固定的，也就是说，越大的数，每个浮点
数对应的真实数的范围是越大的 |
s****n
发帖数: 1237 | 4 或者如果data是顺序读入的用online mean/var calculation，是stable不会overflow
的。
【在 S*********g 的大作中提到】
: 4是要严格计算？
: 严格计算的话，分块算平均.
: 譬如说，每10000个算一个平均，这样就有10000个平均值
: 再算这10000个平均值的平均值。
: variance因为其实也是算平均值，所以也可以类似的这么求
|
S*********g
发帖数: 5298 | 5 不会overflow，但是如果是一个一个读入的话，到一定的数目之后，就需要考虑精度问
题了。我提的这个其实就是你说的这种算法的一个变形
overflow
【在 s****n 的大作中提到】
: 或者如果data是顺序读入的用online mean/var calculation，是stable不会overflow
: 的。
|
o******e
发帖数: 74 | 6 5. 合并排序的话好像比较耗空间。 可以先分段读入数据并排序（如快速排序），再输
出到n个文件，再去从每个文件里挑最小的出来建立min-heap, 一次输出最小的数并从
最小数的来源文件取下一个数，插入到heap里。如此循环。
【在 c**********e 的大作中提到】
: 3. what does it look like if we plot: floating variable against the
: actual value assigned to the variable?
: 这个问题答案显然是一个阶梯函数样子。但是更具体应该怎么样？
: 4. Given a sample of 100000000 data, how do we approximate the mean and
: variance of the underlying random variable. How to avoid round off
: error.
: 先猜一个均值，然后对余数相加吗？怎么避免舍入误差？
: 5. Given a machine of memory 10Mb, sort data of 10GB stored in a file.
: 思路到是有，比如参照合并排序，但是具体怎么实现？内存也太小了点。
: 再就是参照快速排序。但是递归式的快速排序是要不少空间的。
|
