最近开心上狂算24点，于是贝壳搞了一个24点计算程序，并且说明原理。
我们将24点问题一般化，变成一个搜索问题。假定从一个初始表开始，里面有一些原子。我们定义一个操作，结合。每次操作任意从中选择出两个(或者以上)原子，使用算符连接，成为一个新的原子。那么，一般来说，24点就是计算所有可能的路径，从初始表开始，持续进行结合，直到只剩下一个原子，并且对这个原子求值得24。
有人可能在算符优先级上想不开，其实不用考虑这个问题，每次求值的时候，按照求值顺序优先就可以。你想到的另外一种优先级可能，会在穷举的时候被列举出来算掉，不用担心遗漏。
同时，算子必须是两目以上算子，因为单目算子可以持续作用于同一个对象，因此原子表中的原子个数并不严格单调减少，造成无法肯定路径收敛于有限步骤上。并且，如果允许单目算子，那么我只需要求导和阶乘就可以对任何数字求24点。
((a')!+(b')!+(c')!+(d')!)!=24
因此，单目算符是没有意义的。
另外，注意算符分可交换和非可交换的。例如：a+b=b+a，但是a-b!=b-a。如果不注意这点，倒是不会漏算，但是会造成搜索空间增大，并且有重复结果。
以下是24点计算程序，python版本的。有兴趣的朋友可以用scheme重写，相信会更简洁有效。回头会用django封装一下，做成网页给大家玩玩。
#!/usr/bin/python
import sys
symbol_list = [
("%s+%s", True), ("%s-%s", False),
("%s*%s", True), ("%s/%s", False), ("%s**%s", False),
# ("min (%s,%s)", True), ("max (%s,%s)", True),
];
def diff_seq (length):
for i in range (0, length):
for j in range (i + 1, length):
yield (i, j);
def get_less_state (input_state):
for i, j in diff_seq (len (input_state)):
temp = input_state[:];
del temp[j];
del temp[i];
for s in symbol_list:
rslt = s[0] % (input_state[i], input_state[j]);
rslt = "(%s)" % rslt;
temp.append (rslt);
yield temp;
temp.remove (rslt);
if s[1]:
continue;
rslt = s[0] % (input_state[j], input_state[i]);
rslt = "(%s)" % rslt;
temp.append (rslt);
yield temp;
temp.remove (rslt);
def do_node (input_state, output):
for i in get_less_state (input_state):
if len (i) > 1:
do_node (i, output);
continue;
try:
rslt = eval (i[0]);
except:
continue;
if rslt == 24.0:
output.add (i[0].replace (".0", ""));
if __name__ == "__main__":
rslt = [];
for i in sys.argv[1:]:
rslt.append (float (i));
output = set ([]);
do_node (rslt, output);
for i in list (output):
print "%s=24" % i;
2009年1月19日星期一
2009年1月11日星期日
论同时的双系统－－准虚拟对双系统的进一步扩充
熟悉贝壳的人都知道，贝壳是个linux爱用者，不过因为工作关系，经常要使用windows。贝壳在自己的笔记本上使用了linux/windows混合双系统，并通过共用磁盘的方式共享数据，解决这个问题。但是长期的使用表明，这种解决方案存在几个巨大的瑕疵。首先是系统切换时间常，因此长期在一个系统中工作，而很少触及另外一个系统。其次是稳定性差，windows下一旦崩溃，进入linux后就需要检测数据盘，80G的数据慢慢扫描，感觉晕到死。那么是否有一种方案，能够同时使用两个工作级系统（注意，不是实验级，贝壳成功的在windows下的vmware里跑了一个oracle，这个可以说是实验级的典范。然而工作级系统的要求和实验级完全不同）。
从系统发展史的角度来说，我们可以预见，将来的系统将是脱离硬件的。首要的原因就是和硬件不相匹配的各个层级的计算能力需求。现在系统发展有两个极端，一个是虚拟机，试图将一个硬件整体分离，运行多个系统。另一个是高性能集群，试图将多个硬件合并，运行一个系统。从根本上说，这是因为高性价比的硬件集中在了一个性能区间，而实际的性能需求却是完全分离的，因此我们才会出现如此两类完全背离的需求。而现在有大量宝贵的人力浪费在了系统和硬件结合，系统稳定性问题上，这无疑是对将来发展的一个巨大瓶颈。虽然无法预知将来的技术发展会以何种方式解决这个问题，然而可以预见的是，解决硬件和性能的背离将是人类计算机发展史上一个重要的里程碑，解决这个问题的人必定会在计算机历史上留下重重的一笔。
同时，更进一步，贝壳揣测，将来的解决方案将是系统硬件调度/驱动和系统软件管理分离。一个软系统拥有一个用户表和一个硬件表，硬件表上写他可能有10个键盘，两个显示器，或者一堆其他设备。系统借助某个可信方案，管理了一系列虚拟抽象设备和真实设备形成的映射。作为系统层以上的软件，我们只要关心如何操作这个虚拟设备即可。而实际上，我们可以通过管理参数和对应关系实现各种需要。例如我们可以将多个机器的硬件管理核心加入一个系统，形成集群。或者我们可以在一个机器的硬件管理核心上加入多个系统，形成虚拟机。这个基本是分布系统的观点。如此一来，系统层软件就无法得知也无需得知自己是在到底运行在什么环境下。只是这个系统设计方案对高性能要求的子系统（主要是显卡）相当不利。
从揣测回到现实，为了实现一个工作级系统（幸好，还不是工业级），我们需要为系统制定一些评判标准，以判别各个方案的优劣。我们首先能想到的评判标准就是速度，一个慢吞吞的系统解决方案是没有任何实用价值的。当然，这个速度是有差异的，可能是linux快一些，windows慢一些，或者相反。我们假定实际的需要是windows快一些，因为linux可以通过定制进行加速。
我们的第二个评判标准就是稳定性，经常会崩溃的系统不比慢吞吞的系统好到哪里去，甚至会更加让人讨厌。虽然工作级系统并没有工业级那样高的要求，然而高负荷稳定，宕机平均频率低于3天/次还是要保证的。而后我们还希望两个系统可以做到数据互通，即两个系统间的数据尽可能的共享，至少要做到文件和邮件的共享。最后，我们希望解决方案简单易用，便于实施和维护。
而后，我们列出了一个原始方案，和以下几个改进解决方案，并给出优劣评价，谨供大家参考借鉴。同时我们在其中还补充了一些无法实际解决问题的虚拟化解决方案，并且说明无法使用的原因，供适合的人自行选用。
原始方案，windows+linux+数据分区。此种方案是最中规中矩的，性能最高的方案。具有对硬件最好的支持，最容易的维护。如果需要运行游戏（尤其是魔兽，WOW），这也是唯一可行的工作级方案。稳定性评价属于尚可，主要由于ntfs在linux的稳定性并不好，ext3在windows需要使用非官方驱动，和某些（就是avast）驱动不兼容。数据互通比较方便，通过数据分区可以轻松的共享文件和邮件。
windows虚拟方案，vmware+虚拟分区。这种方案是改进方案中唯一可以跑游戏的，因为虚拟机随时可以关上。性能上满足windows快 linux慢的要求，虚拟系统显示性能良好，也可以通过文件共享部分的解决数据共享问题（文件共享方便，邮件共享困难）。稳定性很好，基本没有什么不稳定的问题出现，操作和维护都不困难。然而之所以一开始这种方案就被排除在外，主要是因为这种方案无法让linux驱动实体硬件，无法通过机器启动。这样也许对一些跑起来玩玩的人或者是内核工程师/测试员比较有用，然而如果要在linux里面进行大量工作，编译程序，运行服务，这种方案就力有未逮。因此这个方案可以说是一个实验级方案，而非工作级。
windows虚拟方案，vmware+实体硬盘。速度一般，windows快linux慢，基本和上面一个方案一样，唯一的区别就是linux也可以被实际驱动。然而这也成了整个方案的最大败笔，因为linux的驱动灵活性不如windows，因此无法经受这种系统切换的动作。举例来说，真实的机器上，硬盘是sata的，作为sda识别和使用。而虚拟机上则是IDE的，被识别成了hda。于是启动环境一变，就需要修改大量配置来调和这个问题。又例如，在真实机器上，X使用fglrx驱动，而虚拟机下面要用mesa。如果我在/etc/xorg.conf中不指定驱动，那么真实机器的驱动也会变成 mesa，导致性能下降。如果指定驱动，又会导致虚拟机内X无法运行。诸如此类的问题林林总总，需要大量细节修正，因此维护复杂，稳定性差，不建议正式使用。在贝壳机器上更严重的，出现了虚拟机内和虚拟机外争抢数据分区的状况，这种情况下数据分区实质是被当做盘阵用了。使用非专用的磁盘作为底层共享存储，并在上面运行ext3系统，这是及其危险和愚蠢的。
linux虚拟方案，xen。速度超快，但是上来就在贝壳的机器上暴出几个问题，因而没有继续测试。首先是安装xen后x无法启动，出现fglrx驱动无法加载的状况。其次是xen要求使用虚拟盘启动，可贝壳经常需要跑到windows下面打游戏。因此在简单测试后被剔除出局。感觉这种方案的最大问题在于配置管理太过复杂，debian下面已经很轻松了，只需要安装对应内核，使用工具建立虚拟机，但是依旧感觉麻烦到一塌糊涂。相信这种方案在专业级服务器领域应当有不俗表现。
linux虚拟方案，openvz。这种方案压根就不适合贝壳的状况，因为这个虚拟方案要求宿主和客户必须是同一CPU同一系统（不要求同一linux发行）。主要用于希望将一个主机切分成多个独立的同构主机，以达到分离管理的目的（例如业务服务器和数据库服务器分离）。需要做大型网络管理/虚拟主机业务的人可能会对这个虚拟方案感兴趣。
linux虚拟方案，vmware。速度一般，linux快windows慢，视频效果不错。vmware毕竟是商业公司，视频驱动挺齐全的。但是内核驱动的编译麻烦到死，首先是要求编译器版本和主内核编译器版本一致，于是贝壳去搞了个gcc-4.1，然后连接了上去。下面又是内核头定义出现版本差异，搞到现在还没有搞定。谁能搞的定的给个参考，最好是debian上的解决方案。
linux虚拟方案，kvm。这个是贝壳目前使用的方案，基本比较理想。速度很快，和xen基本差不多，显示速度不如vmware（理论上说装好显卡驱动应该会好点，不过贝壳找不到CLDC5446的XP驱动，那是Win32和Win95时代的显卡）。linux快windows慢，但是还在可忍受范围内。稳定性很好，只要测试通过，运行中到目前为止没有死机（当然很多参数是加了之后开机即死机）。数据可以通过samba互通，邮件也同样可以互通。然而使用samba无疑复杂很多，而且性能并不太好。只是从稳定性上说，让linux自己去驱动ext3总比半吊子的windows驱动更好，同时也不会出现争抢的问题。易用性上还算可以，无论是内核编译还是系统使用都不太难，最大的麻烦就是网络配置。根据贝壳的测试，在真实机器上superpi运行100W 位需要45秒，虚拟机内需要54-60秒，尤其在换用kvm-72.2后反而更慢了（54下降到60，折合真实机器83.3％下降到75％）。
总体来说，贝壳更倾向于使用全开源的准-全虚拟解决方案kvm，主要因为他简便易行，对系统影响小，不改变现有系统。同时性能高，稳定性好。主要需要解决显卡效率问题。如果以上问题无法彻底解决，贝壳打算换用linux下的vmware，想办法搞定他的内核模块。
从系统发展史的角度来说，我们可以预见，将来的系统将是脱离硬件的。首要的原因就是和硬件不相匹配的各个层级的计算能力需求。现在系统发展有两个极端，一个是虚拟机，试图将一个硬件整体分离，运行多个系统。另一个是高性能集群，试图将多个硬件合并，运行一个系统。从根本上说，这是因为高性价比的硬件集中在了一个性能区间，而实际的性能需求却是完全分离的，因此我们才会出现如此两类完全背离的需求。而现在有大量宝贵的人力浪费在了系统和硬件结合，系统稳定性问题上，这无疑是对将来发展的一个巨大瓶颈。虽然无法预知将来的技术发展会以何种方式解决这个问题，然而可以预见的是，解决硬件和性能的背离将是人类计算机发展史上一个重要的里程碑，解决这个问题的人必定会在计算机历史上留下重重的一笔。
同时，更进一步，贝壳揣测，将来的解决方案将是系统硬件调度/驱动和系统软件管理分离。一个软系统拥有一个用户表和一个硬件表，硬件表上写他可能有10个键盘，两个显示器，或者一堆其他设备。系统借助某个可信方案，管理了一系列虚拟抽象设备和真实设备形成的映射。作为系统层以上的软件，我们只要关心如何操作这个虚拟设备即可。而实际上，我们可以通过管理参数和对应关系实现各种需要。例如我们可以将多个机器的硬件管理核心加入一个系统，形成集群。或者我们可以在一个机器的硬件管理核心上加入多个系统，形成虚拟机。这个基本是分布系统的观点。如此一来，系统层软件就无法得知也无需得知自己是在到底运行在什么环境下。只是这个系统设计方案对高性能要求的子系统（主要是显卡）相当不利。
从揣测回到现实，为了实现一个工作级系统（幸好，还不是工业级），我们需要为系统制定一些评判标准，以判别各个方案的优劣。我们首先能想到的评判标准就是速度，一个慢吞吞的系统解决方案是没有任何实用价值的。当然，这个速度是有差异的，可能是linux快一些，windows慢一些，或者相反。我们假定实际的需要是windows快一些，因为linux可以通过定制进行加速。
我们的第二个评判标准就是稳定性，经常会崩溃的系统不比慢吞吞的系统好到哪里去，甚至会更加让人讨厌。虽然工作级系统并没有工业级那样高的要求，然而高负荷稳定，宕机平均频率低于3天/次还是要保证的。而后我们还希望两个系统可以做到数据互通，即两个系统间的数据尽可能的共享，至少要做到文件和邮件的共享。最后，我们希望解决方案简单易用，便于实施和维护。
而后，我们列出了一个原始方案，和以下几个改进解决方案，并给出优劣评价，谨供大家参考借鉴。同时我们在其中还补充了一些无法实际解决问题的虚拟化解决方案，并且说明无法使用的原因，供适合的人自行选用。
原始方案，windows+linux+数据分区。此种方案是最中规中矩的，性能最高的方案。具有对硬件最好的支持，最容易的维护。如果需要运行游戏（尤其是魔兽，WOW），这也是唯一可行的工作级方案。稳定性评价属于尚可，主要由于ntfs在linux的稳定性并不好，ext3在windows需要使用非官方驱动，和某些（就是avast）驱动不兼容。数据互通比较方便，通过数据分区可以轻松的共享文件和邮件。
windows虚拟方案，vmware+虚拟分区。这种方案是改进方案中唯一可以跑游戏的，因为虚拟机随时可以关上。性能上满足windows快 linux慢的要求，虚拟系统显示性能良好，也可以通过文件共享部分的解决数据共享问题（文件共享方便，邮件共享困难）。稳定性很好，基本没有什么不稳定的问题出现，操作和维护都不困难。然而之所以一开始这种方案就被排除在外，主要是因为这种方案无法让linux驱动实体硬件，无法通过机器启动。这样也许对一些跑起来玩玩的人或者是内核工程师/测试员比较有用，然而如果要在linux里面进行大量工作，编译程序，运行服务，这种方案就力有未逮。因此这个方案可以说是一个实验级方案，而非工作级。
windows虚拟方案，vmware+实体硬盘。速度一般，windows快linux慢，基本和上面一个方案一样，唯一的区别就是linux也可以被实际驱动。然而这也成了整个方案的最大败笔，因为linux的驱动灵活性不如windows，因此无法经受这种系统切换的动作。举例来说，真实的机器上，硬盘是sata的，作为sda识别和使用。而虚拟机上则是IDE的，被识别成了hda。于是启动环境一变，就需要修改大量配置来调和这个问题。又例如，在真实机器上，X使用fglrx驱动，而虚拟机下面要用mesa。如果我在/etc/xorg.conf中不指定驱动，那么真实机器的驱动也会变成 mesa，导致性能下降。如果指定驱动，又会导致虚拟机内X无法运行。诸如此类的问题林林总总，需要大量细节修正，因此维护复杂，稳定性差，不建议正式使用。在贝壳机器上更严重的，出现了虚拟机内和虚拟机外争抢数据分区的状况，这种情况下数据分区实质是被当做盘阵用了。使用非专用的磁盘作为底层共享存储，并在上面运行ext3系统，这是及其危险和愚蠢的。
linux虚拟方案，xen。速度超快，但是上来就在贝壳的机器上暴出几个问题，因而没有继续测试。首先是安装xen后x无法启动，出现fglrx驱动无法加载的状况。其次是xen要求使用虚拟盘启动，可贝壳经常需要跑到windows下面打游戏。因此在简单测试后被剔除出局。感觉这种方案的最大问题在于配置管理太过复杂，debian下面已经很轻松了，只需要安装对应内核，使用工具建立虚拟机，但是依旧感觉麻烦到一塌糊涂。相信这种方案在专业级服务器领域应当有不俗表现。
linux虚拟方案，openvz。这种方案压根就不适合贝壳的状况，因为这个虚拟方案要求宿主和客户必须是同一CPU同一系统（不要求同一linux发行）。主要用于希望将一个主机切分成多个独立的同构主机，以达到分离管理的目的（例如业务服务器和数据库服务器分离）。需要做大型网络管理/虚拟主机业务的人可能会对这个虚拟方案感兴趣。
linux虚拟方案，vmware。速度一般，linux快windows慢，视频效果不错。vmware毕竟是商业公司，视频驱动挺齐全的。但是内核驱动的编译麻烦到死，首先是要求编译器版本和主内核编译器版本一致，于是贝壳去搞了个gcc-4.1，然后连接了上去。下面又是内核头定义出现版本差异，搞到现在还没有搞定。谁能搞的定的给个参考，最好是debian上的解决方案。
linux虚拟方案，kvm。这个是贝壳目前使用的方案，基本比较理想。速度很快，和xen基本差不多，显示速度不如vmware（理论上说装好显卡驱动应该会好点，不过贝壳找不到CLDC5446的XP驱动，那是Win32和Win95时代的显卡）。linux快windows慢，但是还在可忍受范围内。稳定性很好，只要测试通过，运行中到目前为止没有死机（当然很多参数是加了之后开机即死机）。数据可以通过samba互通，邮件也同样可以互通。然而使用samba无疑复杂很多，而且性能并不太好。只是从稳定性上说，让linux自己去驱动ext3总比半吊子的windows驱动更好，同时也不会出现争抢的问题。易用性上还算可以，无论是内核编译还是系统使用都不太难，最大的麻烦就是网络配置。根据贝壳的测试，在真实机器上superpi运行100W 位需要45秒，虚拟机内需要54-60秒，尤其在换用kvm-72.2后反而更慢了（54下降到60，折合真实机器83.3％下降到75％）。
总体来说，贝壳更倾向于使用全开源的准-全虚拟解决方案kvm，主要因为他简便易行，对系统影响小，不改变现有系统。同时性能高，稳定性好。主要需要解决显卡效率问题。如果以上问题无法彻底解决，贝壳打算换用linux下的vmware，想办法搞定他的内核模块。
订阅：
博文 (Atom)