主题：【原创】新时代新潮流WebOS 【1】 -- 邓侃
家园 好，俺正在倒着慢慢看。
家园 这条线越来越有意思了。围绕 着浏览器和WEBOS的讨论也越来越深入，可喜可贺。
最近在国内一路看来，感触很多。
我估计4月20号后在北京住一段时间，不知道在北京（附近）的IT(?)河友是否有意小聚一次？
家园 【讨论】有几点看法 1. 只要有风吹草动的事件发生，XML DOM Tree就要不厌其烦地一遍又一遍搜索发生事件的节点。如果XML DOM Tree结构比较大，那么搜索的成本就很高。2. 在确定谁去处理事件，什么时候处理的过程中，需要从根节点沿capture path一路访问到目标节点，再沿bubbling path一路返回根节点，事件处理的过程很长。
如果换用链表结构，执行效率会提高很多。
邓兄此处的结论有点绝对了。
第一、数据结构方面，树搜索O(logN)要比链表搜索O(N)快将近一个数量级
第二、树状结构能够更有效的组织UI的各个元素。管理起来综合成本其实是偏低的
第三、链表不过是树结构的一种特例（单叉树），很多毛病还是继承下来了。
譬如在Figure 1中，共有5个characters。在浏览器渲染页面的时候，可以同时生成一个bitmap。页面中每个character对应bitmap中一个剪影，这样bitmap中有5个剪影。当用户移动鼠标时，鼠标所在剪影的光素的值，对应着这个character的depth。这样只需要O（1）的成本，就可以确定事件发生在哪一个character上。这里似乎概念不太清晰。前面的种种讨论都是局限于Object Model，这里讨论的其实是Presentation Layer。Tree一样可以照此办理，而且结果只会比List快，因为可以砍掉完全无关的子树，最终得到的bitmap只怕还要薄上两分。
当然，速度提高的代价是占用更多内存空间，也就是bitmap占用的空间。不过减少 bitmap尺寸的办法很多，譬如一个简单的办法是把原图像中相邻的四个光素合并成一个光素，这样就缩小了3/4的空间占用，如Figure 1中右图所示。这样做的后果，是当鼠标移动到characters边缘时，事件触发的精度不够高，但是对于绝大用户而言，事件触发的精度可能不需要太高。为了优化UI而引入Bitmap, 为了减小内存的占用反而又去牺牲UI的可用性，这个Tradeoff不划算啊。
2. 链表可以支持多个characters处理同一个事件。譬如事件发生于Figure 1中左边人物，但是作为响应，不仅左边人物有相应动作，而且脚下阴影也随之变化。实现这个关联动作的办法很简单，在左边人物处理完事件以后，主动调用阴影的相关动作，而不需要沿capture path和bubbling path访问一圈。这个并不是List带来的好处，而是Bitmap Z轴带来的好处，可以跟上面的观点合并。
我觉得现在的UI系统已经在各个方面做了很大的优化，考虑了方方面面的情况。既要易用，又要防止WCET爆炸，还要兼顾扩展性。这里扩展性既是extensible也是scalable。想要进一步优化不动动用户的奶酪(用户体验)怕是不行啊。
家园 树结构vs链表 假设有N个characters，每个character都是一个卡通图像，图像与图像之间有重叠。对于这种情形，树结构的表述很麻烦。链表的搜索效率是O（N)，但是树结构的搜索效率不是O（logN），而是几乎要遍历整个树，也就是O（N logN)。
但是兄台的分析也没有错。如果是文字为主的页面，每段文字之间不存在重叠，树的搜索的确是O（logN）。
所以，树结构和链表结构哪一个更好，取决于页面的主要内容是什么。但是，总体上来讲，我觉得链表结构更通用，更节省计算和存储开销。
引入Bitmap不是为了优化UI和图像的展示，而是为了方便捕捉鼠标移动等等事件。换句话说，假设要展示一个有图像的页面，需要两套frames，一套是专供graphics显示用的，另一套是bitmap。用户看到的是第一套frame，bitmap frame是看不见的，只是为了方便捕捉事件。
我是不是说清楚了？
我前面说的想法，不是常规的思路。我也觉得纳闷，为什么业界不去用我描述的这个简单易行的办法，而是用XML-DOM树结构。我不是想推销什么新构想，而是拿它来和XML-DOM比较，说明XML-DOM的弱点。肯定XML-DOM有什么强有力的优点，但是究竟是什么，至今没有看到有说服力的解释。
- 复 树结构vs链表
家园 问题是对requirement的理解 是含有一大堆卡通图像characters的html网页多，还是含有一大堆互相不重叠的文字的html网页多呢？
邓侃兄所说的这种“假设有N个characters，每个character都是一个卡通图像，图像与图像之间有重叠”的网页特例能够占当前所有的html网页的百分之几？我怀疑小于0.1%.屠龙之技当然好，可也要考虑是否市场上有龙给你屠呀。
其实，我理解你所说的那种特例。我见过一个这种类型的应用，就是用在手持设备例如手机上。用服务器来解析网页，转化成图像发给用户的手机/手持设备。客户端 截获用户对图片的点击，发给服务器端翻译成相应的用户操作。这种方法可以加速手机/手持设备的上网浏览。但也有不少弊端，我个人是不太看好这种设计的。其中一个理由就是你想要找的XML-DOM相对于这种方式的优点。
那个优点就是压缩，图片的压缩比远远不如文字。假设图片本身就已经是jpg了，那么再压缩的可能性就不大了。早期internet不是宽带，寸bit寸金，压缩传送可以大量节约带宽和提高用户体验。今天，在3G还没有普及的情况下，对于手机，带宽也是一个瓶颈，因此xml-dom的这种数据结构的浏览速度可能反倒比你的这种图片结构更快，因为可以在服务器端定制压缩。
家园 像PPT那样的手机页面 如前文所述，我关心的不是Internet网页，而是手机页面。Internet网页无论历史沉积，还是当今应用的广度，都太复杂，碰不得。手机页面设计基本上还算年轻，有可能考虑全盘重来。
我想象中理想的手机页面是类似于PPT那样的页面。文字不多，图片多，间或有点动画效果。PPT是什么结构？我觉得没必要用XML-DOM。
家园 问题是 是否有必要为了手机而专门设计网页？
wap现在还活着吗？
硬件发展是很快的，手机上也有类似于摩尔定律之类的规则。每6个月手机硬件就会升级一次。照这样的速度，很快其处理和计算能力就会和pc差不多，那么还有必要专门为了它而重新设计数据结构吗？当手机拥有4g内存以及cpu过2g时，xml-dom的排序和查找再慢能慢到哪里？
纵观it技术发展史，功能的丰富和可扩展性要远远重要于数据结构的设计。
sgi图形工作站当年多牛，从操作系统到硬件都是专门为了图形显示而设计的，更别说优化数据结构了，现在呢？硬生生被廉价的开放的pc给灭了。
做设计最怕的是什么？是不从用户的角度出发。邓侃兄干嘛不找几个专业的网页设计人员，问问他们是否用兴趣去用你的倡议的这种网页结构呢？坦白的说，你的这种结构虽然可能在某些情况下性能上会有优势，但设计者很难掌握。没有用户，再好的数据结构又有什么用呢？
另外,ppt的结构，here you are.
http://msdn.microsoft.com/en-us/library/cc313106.aspx
- 复 树结构vs链表
家园 最早的HTML也是很简单的，结果..... 事实上最早的HTML既没有DOM也没有CSS更没有Javascript。BODY下面就是<h1><p><table>等纯粹的内容标签。这里面只有table繁琐了点，但是对付单列表还是有简单的ol ul等标签。可以说设计者根本也没准备让大家拿网页当报纸排。
结果“伟大的”web工作者们抓住了唯一一个可以自定义结构的标签-------TABLE，这一通发挥。当年俺作为菜鸟都苦练过TABLE框架，TABLE拼图，TABLE画竖线等大招。当年哪个网页不是7-8个TABLE套在一起。
你说这结构化、非链表化的DOM是设计者拍脑瓜子拍出来的，还是被广大开发者逼出来的呢？
-------------------------------
再讨论点题外话
假设有N个characters，每个character都是一个卡通图像，图像与图像之间有重叠。对于这种情形，树结构的表述很麻烦。链表的搜索效率是O（N)，但是树结构的搜索效率不是O（logN），而是几乎要遍历整个树，也就是O（N logN)。
这个例子不完整，我们到底要在DOM上找什么？
找对鼠标所在位置负责的那个character？则是树搜索，O(logN)
找对鼠标所在位置负责的所有character？则是树遍历，O(N)
如果我们规定有效元素只是叶子点，内部点都算overhead。那树结构也不过是把O(N)的问题复杂化为O(N+logN)，还是O(N)。
家园 在DOM上定位事件发生的leaf 这个例子不完整，我们到底要在DOM上找什么？找对鼠标所在位置负责的那个character？则是树搜索，O(logN)
设想，browser现在知道鼠标的位置（X，Y），如何定位鼠标移动这个事件发生在哪个character上？
如果characters之间有重叠，那么就不能简单地从DOM树的根节点一路向叶子节点找，因为中间节点占据的区域有重叠。所以，成本不是O（logN）。
也就是说，用DOM树来表述2D图像是不方便的。对于这种情形，R-Tree或许更强有力。
但是假设我们要做的仅仅是简单页面的结构处理，还不如简单遍历，也就是链式结构。
如果我们规定有效元素只是叶子点，内部点都算overhead。那树结构也不过是把O(N)的问题复杂化为O(N+logN)，还是O(N)。如果想遍历树的叶子节点，成本是O（N），但是这里有个前提，必须事先用链表把所有树的叶子节点串联起来。如果没有叶子链表，那么要访问每个叶子节点，成本等同于遍历树，也就是O（N logN）。
这样分析对不对？
家园 DOM树来表述2D图像是不方便的,这句话需要商量的 二维图形，比如说SVG，还有那个微软出的什么WCF。都是树形结构.好处是，层次分明，比较直观，对象操作，修改起来比较方便。但是在渲染的时候，还是需要转成堆栈方式。
鼠标是否在当前节点.渲染的时候，已经确定节点的外围矩形。可以很方便的通过外围矩形来确定鼠标是否在当前节点.
遍历树,有几种规则（深度优先，广度优先），可以设计数据结构,在插入（删除）节点时，按照遍历规则排好序.遍历时，复杂度可以为线性O（N），不过，改变树结构的时候，需要花点时间.
