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. : 思路到是有,比如参照合并排序,但是具体怎么实现?内存也太小了点。 : 再就是参照快速排序。但是递归式的快速排序是要不少空间的。
|