Archive for the ‘Uncategorized’ Category

Shellsort

十二月 6, 2014

Shell是人名,不是bash这种shell。

事先确定一个单调递减且以1为终点的步长序列,以每个步长做一次插入排序。

计算量小于n^2,大概为n^{4/3}n^{6/5},与步长序列有关。

至今仍不知道最优步长选择是什么样的。

Advertisements

水塘抽样 (reservoir sampling)

十一月 21, 2014

题目:从n个物品中等概率取出k个。

最直接的想法:先把n个物品乱序,然后取出前k个。缺点是需要n个随机数,且需要排序,太复杂。实际上完全不需要这么复杂。

进一步需求:在不知道n的时候怎么办(比如数据来自一个数据流)?

答案:

设想数据不断传来。当数据个数不超过k时,当然应该直接把所有数据都选中。

第k+1个数据传来时,我们需要做个操作,使得这个新数据以及所有已有的数据被选中的几率为k/(k+1);换句话说,已有的数据有1/(k+1)的几率被踢掉。具体做法是,只需要生成1到k+1之间的整型随机数,如果这个随机数不超过k,就把相应位置的数据替换成新数据,否则不操作。

进一步,假设当收到第n个数后我们的操作满足题目的要求,即每个数被选中的几率为k/n,问第n+1个数到来时应该怎么操作。同样,生成1到n+1之间的随机整数,如果这个整数不超过k,则把相应位置的数据替换成新数据,否则不操作。新数据被选中的几率是k/(n+1),而旧数据不被替换的几率是n/(n+1),考虑到旧数据已被选中的几率本身是k/n,于是旧数据继续呆在那里的几率是k/(n+1)。正确。

所以,不需要知道总共有多少数据,只需要知道当前收到了多少数据就可以了。

一维格子,间隔为等比级数,且比例分级

一月 6, 2014

设区间为(x_1, x_2),总格点数为N,比例等级数为m,每级格点数为nN = m\times n。  假定比例的比例已知,为\xi。问题是需要找个算法来确定第一个格子的宽度\Delta x_0和每级内格子宽度之间的比例\eta

我们有 \displaystyle \Delta x_0 \frac{\xi^m-1} {\xi-1} \frac{\eta^n-1} {\eta-1} = x_2 - x_1.

恒星照耀下黑体墙温度的简单计算

一月 6, 2014

\displaystyle T = \left( \frac{L}{ 4\pi r^2 \sigma} \right)^{1/4} = (393~\text{K}) \left(\frac{L} {L_\odot} \right)^{1/4} \left(\frac{r} {\text{AU}} \right)^{-1/2}.

宇宙线主导区域的化学

八月 25, 2011

http://arxiv.org/pdf/1102.2996v1

并和或星暴星系中宇宙线强度可以比银河系的高万倍。

以前的一些计算是针对固定温度的。

需要自洽地考虑到热和化学过程。

UCL_PDR code,密度是常数。跑1e8年,达到稳恒态。

实际上1e6年就差不多达到了稳恒态。

把原子C转变成CO的时标随着宇宙射线强度的增加而减小,但中性物质之间的反应限制了反应速度。

一维半无限平板,温度是深度和时间的函数。深度达到Av=20.

各种分子冷却机制。高消光的时候这么做会更精确。

逃逸概率描述。

使用LAMDA分子数据库。

还有OI亚稳能级冷却,以及O与H+和E-碰撞激发机制。

H2自屏蔽;Lee et al. 1996.

131 species, 1834 reactions.

除H2的形成之外无任何尘埃过程。

适用于温度为几千度的环境。但上万度的就不适合了。

于是只用于宇宙线电离率小于1e-12/s的环境。

不考虑二次电离的物质。

金属丰度0.1-4倍于太阳丰度。其它一些参数假定正比于金属丰度。

外部辐射场1000Habing。

OH+, CH+, H2O+, H3O+; AGN

Orion-KL and W49N

H3+,O2丰度与宇宙线强度的关系。