All those moments will be lost in time,
like tears in the rain.
Found in FFFFOUND!
月度归档： 2009年1月
计算机科学中的O(logn)
在计算机科学中我们经常说类似这样的话：
“基于交换的排序算法的时间复杂度至少是O(nlogn)的。”
但是这里从来不说所谓logn，是以几为底数的logn？
实际上，我们有：
[singlepic=18396]
所以在计算机科学中谈论的对数logn，其底数是无所谓的。但是默认情况，如果写成logn，一般认为是以2为底的n的对数。
都是系统管理员，差距咋就这么大呢…
Sun工程师惊天发现:大吼可致硬盘潜伏期激增
Sun Microsystems Fishworks实验室的工程师Brendan Gregg公布了他的惊天发现：如果你对着硬盘大吼，会导致其潜伏期出现瞬间激增。
从这位仁兄公布的视频上看，他在一个吵杂的数据中心里使用相关软件监测硬盘的IO/s和潜伏期，然后对着RAID JBOD硬盘阵列的某一处大吼，这时候就可以发现一个很陡峭的瞬间波峰，而检查标明，出现变化的硬盘正是被他大叫的那一块。
现在还不确认为什么会有这么诡异的变化。考虑到硬盘是机械部件，有可能是高声引起的震动所致。不管怎么说，Brendan Gregg显然对他的这一发现感到非常得意。
无论如何，以后再生气也不要冲着你的硬盘大喊大叫了，最好把你的电脑放置在一个相对比较安静的环境里，别吓着里边的零件。
所谓潜伏期(Latency)，又称等待时间，是指当硬盘磁头移动到数据所在的磁道后，等待所要的数据块继续转动(半圈或多些、少些)到磁头下的时间，单位为毫秒(ms)。平均潜伏期(Average latency)就是盘片转半圈的时间。
全周期线性同余随机数生成器
全周期线性同余随机数生成器(Full period linear congruential random generator)：
[singlepic=18395]
其中如果前两项的和为非负数，则δ(Xi)=0，否则δ(Xi)=1。
研究发现取素数M=2147483647，A=48271可以取得不错的随机性。鉴于这样的取值被仔细研究过并广泛应用，因此一般不要改这两个取值。
算法实现
[code=’cpp’]
class RandomFactory
{
public:
RandomFactory();
long LinerCongruentialRandom();
private:
static const long A = 48271;
static const long M = 2147483647;
static const long Q = M / A;
static const long R = M % A;
long lastValue;
};
[/code]
[code=’cpp’]
#include “stdafx.h”
RandomFactory::RandomFactory()
{
this->lastValue = 1;
}
long RandomFactory::LinerCongruentialRandom()
{
long temp = this->A * (this->lastValue % this->Q) –
R * (this->lastValue / this->Q);
if(temp < 0)
{
temp += this->M;
}
this->lastValue = temp;
return temp % 10;
}
[/code]
测试代码
[code=’cpp’] [code=’sh’] 我们还是可以发现不错的随机性。
RandomFactory *random = new RandomFactory();
int *statistics = new int[10];
for(long i = 0; i < 10; ++i)
{
statistics[i] = 0;
}
for(long i = 0; i < 1000; ++i)
{
int thisRandom = random->LinerCongruentialRandom();
statistics[thisRandom]++;
//cout<<"["<
[0]:94
[1]:114
[2]:105
[3]:90
[4]:98
[5]:101
[6]:91
[7]:105
[8]:91
[9]:111
[/code]
C#读取任意charset网页
[code=’c#’]
private string GetPageContent(string address)
{
try
{
string result = null;
HttpWebRequest req = (HttpWebRequest)HttpWebRequest.Create(address);
req.Method = “GET”;
using (WebResponse wr = req.GetResponse())
{
// 请求网页内容
Stream stream = wr.GetResponseStream();
StreamReader sr = new StreamReader(stream, Encoding.Default);
result = sr.ReadToEnd();
// 获取网页编码
int charsetIndex = result.IndexOf(“charset”);
string charset = “utf-8”;
if (charsetIndex != -1)
{
int right = result.IndexOf(“>”, charsetIndex);
charset = result.Substring(
charsetIndex + 7, right – charsetIndex – 7).Trim();
charset = charset.Replace(“=”, “”);
charset = charset.Replace(“\r”, “”);
charset = charset.Replace(“\n”, “”);
charset = charset.Replace(“\””, “”);
charset = charset.Replace(“‘”, “”);
charset = charset.Replace(“/”, “”);
charset = charset.Replace(” “, “”).ToLower();
}
// 将字符串转换成网页中指定的编码类型
result = Encoding.GetEncoding(charset).GetString(
Encoding.Convert(Encoding.Default,
Encoding.GetEncoding(charset),
Encoding.Default.GetBytes(result)));
sr.Close();
stream.Close();
}
return result;
}
catch
{
return null;
}
}
[/code]