五千年(敝帚自珍)

主题:【原创】我们不谈数学(3)(草稿) -- jungleford

共:💬29 🌺112
分页树展主题 · 全看首页 上页
/ 2
下页 末页
  • 家园 【原创】我们不谈数学(3)(草稿)

    这个系列本来是打算明年有空才开始写,昨天突然吃饱了撑的心血来潮就胡扯了一通,算是个草稿,先预览一下。之所以编号是(3),因为前面有两篇处于只码了几个字的烂尾阶段。

    声明几点,以下内容纯属低水平民科的粗制滥造作品,而且还是未完工的,未经认真考据,仅供娱乐八卦之用,千万不要传出去误人子弟。本版有好几位如“我爱莫扎特”等河友的比较严肃而出色的作品,请移步参观。

    ===================华丽的分割线===================

    集合、逻辑与悖论

    我注意到,西西河有个网友注册了个ID叫“肯定没有被注册”。这是个很有意思的现象。有意思在,一个本来没有任何实际意义,仅仅用来区别不同用户的ID,被赋予了“内容”:“肯定没有被注册”这是一个ID,就好比我在西西河或者的ID叫“jungleford”一样,本来应该是跟别的ID地位完全平等的符号,居然描述了这个ID的意义!我宣布,“肯定没有被注册”河友是河里的一条大鲨鱼,太可怕鸟……

    (下面开始跑题,省略1K字……)

    电影《黑客帝国》(The Matrix)描绘了“真相党”们所为之泪流满面的一个“真相世界”:我们看到的一切都是unreal,我们都被洗脑了,“信Neo,得真相;信真相,得永生”。然而另有一部知道的人可能远少于《黑客帝国》的电影,叫《第十三层楼》(The 13th Floor,港台翻译为《异次元骇客》),没看过的朋友请原谅jungleford稍微剧透一下下(因为刚看完马亲王的“再谈剧透的艺术”,1,2,3,大家跟我一起默念:“祥——瑞——御——免——”):某高科技实验室有一套无比牛B的虚拟现实系统(或者叫梦境系统,灵境系统),某天该实验室的一个科学家被杀,某帅哥成为嫌疑犯,帅哥发现科学家留下的字条说他发现了一个惊天秘密,他把秘密藏在实验室的虚拟系统当中,帅哥跑到装置中催眠,进入了虚拟系统,穿越到20世纪30年代,并且发现了两个人跟科学家及其老婆长得一模一样的两个人,经过多次穿越,帅哥知道了这个“惊天秘密”,他及其他所生活的这个世界也是虚拟出来的!帅哥绝望地开车来到了科学家“生前”所暗示的某个地点,在这个世界里,军方设置了一个障碍在这个地点说是“军事禁区”,任何人不得进入,然而当帅哥无视这一警告翻过去的时候,真的就看到了他所在的这个“世界”的边界!帅哥崩溃了,开始追杀科学家的老婆,当他就要得手的时候,突然穿越回了这个“世界”的创造者所在的那个高层世界,在这个高层世界里,他、科学家和科学家的老婆都活得好好的,就当一切尽在和谐中的时候,影片突然像显示器断电一般停止了,似乎在暗示这个“高层世界”也不过是另一个“更高层的世界”的虚拟作品而已。这个片我也大概是八九年前看的,细节记得不是很准确,请原谅。类似的故事还一再被小说家们演绎着,古龙在《萧十一郎》当中也构造了一个异曲同工的“玩偶世界”:萧十一郎在山庄的一个屋子里看到一个大型的盆景模型,有什么什么样的风景和人物,然后当他第二天醒过来推开房门一看傻眼了,外面的风景人物跟那个盆景模型一模一样,还以为自己真是格列佛到小人国来了,结果男猪脚经过冷静的分析,找到某个房间,推开门一看,盆景就原样摆在那儿,只不过是故意布置成外景的缩微罢了。

    点看全图

    外链图片需谨慎,可能会被源头改

    (《第十三层楼》的海报)

    按照这两部(或许还有其它若干部)片子,尤其是后一部片子的观点,所有“世界”都有一个超自然(这里的“自然”是指前面那个“世界”意义当中的自然)的“监视者世界”存在。类似地,对于一维空间(或者叫“一维世界”,“线世界”)中的没有大小“点生物”来说,它的意识里只有“前”“后”两个方向,“左”“右”对他们来说是无法理解的。如果这条“线”恰好位于某个二维空间上,一个不在这条线上的有长度的“线生物”或有面积但无厚度的“面生物”穿越这个“线空间”的时候,“点生物”将惊奇地宣布发现了一个超自然现象:有一个UFO如崂山道士般穿墙,对不起,应该是穿线而过,平白无故地出现,又平白无故地消失了!二维空间的“面生物”对着背后“点生物”窃笑,“嘿嘿,真是低等物种”,可是还没等它得意完,它又可能看到前方也出现了跟“点生物”看到的相似的景象:一个圆圈平白无故地出现了,慢慢变大,然后又慢慢变小,最后又平白无故地消失了!“面生物”惊呼:“哇靠!真的有UFO耶!”而一个“球生物”在这个二维世界的生物所不能理解的“上”方也在窃笑着……

    (跑题结束,开始言归正传)

    对于一个集合系统或者公理系统,数学家们也有类似的担忧:

    ※ 集合系统——“集合的集合”也被纳入(可数)集合的范畴,那么这么一直“集合”下去,到底有没有个头?有人说总有一个“所有集合的集合”,那么这个玩意算不算集合,如果算,那么它描述的内容和它自身是一个东西吗?有人说我要发疯再“集合”一次……NG!打住,你刚刚不是说了这是个头吗?都“所有集合的集合”了耶!哼哼,要你管,“集合”的定义没说不让我这么干,我偏就要来个

    {“所有集合的集合”}

    那这个玩意算什么,按照“所有集合的集合”的内容或者说意义,这个玩意应该也在里面呀,也就是这个玩意如果是个集合的话,它应该

    {“所有集合的集合”}∈“所有集合的集合”

    诶?各位河友应该都中学毕业了吧?(“哗啦——”,一框鸡蛋扔将上来,不带这么骂人滴)。收起雨伞,往地上甩了甩,像《我的团长我的团》里的阿译那样抬起右手把秀发往后一甩,继续——至少jungleford那会儿是在高一上学期学的集合基础知识,如果jungleford脑子还清醒的话,那么按照老师当年教的,明明应该是

    “所有集合的集合”∈ {“所有集合的集合”}

    才对口牙,集合的“包含”关系()可以交换(等集合的情况下),可还没听说“属于”关系可以交换;如果这玩意不是一个集合,那么更糟了,“集合”这个东西的定义就出了问题!苍天啊!分析(微积分之类)base在实数理论上,实数base在有理数基础上,有理数base在整数基础上,整数base在可数集合基础上,你tmd这会集合定义居然就出问题了,你还让偶们,哦对不起,不是偶们,是他们(包含真子集“她们”)数学家怎么混啊!以无懈可击的严密性和以“自然科学女王”自居的整个数学体系轰然倒塌ing~~~数学家们狠得牙根痒痒的,满脸杀气的问,“上面那个声称发疯的家伙是谁?”“康托尔,格奥尔格·康托尔,就是号称‘集合论之父’的那位。”座下一人答到。……一片寂静……“那么你又是谁?”数学家们又问。“伯兰特·罗素。”

    ※ 公理系统——数学家们又哆哆嗦嗦地来到了这里寻找安慰来了。前面那个小黑屋门虚掩着,上面挂了块牌匾,上书“公理”二字(靠,怎么看上去像国家信访局?),这个小黑屋看上去很结实,据说墙是纳米材料浇注的,大梁柱子的材质是自然界最硬的金刚石,躲在里面应该没什么可担心的。刚想推开门进去,从门里冲出一戴着眼镜身材可媲美骨感美女的哥们,冲大伙作了个揖,说:“大伙请回吧,这房子我看就一豆腐渣工程。”众怒!“我靠!你丫谁呀?!”“库尔特·哥德尔,25岁,维也纳大学博士。”

    其实后面这个段子说的并不准确,这个房子的牌匾不能笼统的写“公理系统”,而应该写“形式公理系统”,也就是说,按希尔伯特老先生所构想的“形式化路线”是有问题的,再说得自白一点,就是那种“纯而又纯”“抽象得不能再抽象”的“小白兔数学”(我给起的名字)是有问题的。从小学开始,老师就跟我们说数学是其它自然科学的基础,她是一种抽象的工具,但是“第三次数学危机”却告诉我们,这种“抽象”不能是无限度的,它的研究对象必须具有某种程度上的“内容”。

    回过头来看最开始那个“肯定没有被注册”网友,这个ID的“内容”可以作两种理解:一种是,描述这个ID被注册之前西西河的状态,即“肯定没有被注册”这个ID是肯定没有被注册的,那么,这个ID的意义在数理逻辑上来说就是一个重言式,也就是“废话”;相反的另一种理解,这个ID如果描述的是它被注册之后西西河的状态,那么麻烦就来了,“肯定没有被注册”明明已经存在了嘛,怎么能说是没有被注册呢?如果按照这种理解,就产生了逻辑意义上的悖论。偷偷瞟一眼铁老大,看到这里是不是也已经崩溃鸟?没准回家赶快把“肯定没有被注册”河友喀嚓了~~~

    关键词(Tags): #肯定没有被注册(善良的恶霸地主)通宝推:胡丹青,frnkl,苍野,史文恭,

    本帖一共被 5 帖 引用 (帖内工具实现)
    • 家园 真是摇钱树啊

      恭喜:你意外获得【通宝】一枚

      鲜花已经成功送出,可通过工具取消

      提示:此次送花为此次送花为【有效送花赞扬,涨乐善、声望】。

    • 家园 本想。。。

      上班有些断断续续地事情,没办法看太长时间

      本想送朵西西小红花,收藏回头再细看

      人算不如天算阿,看看得宝了拉

      恭喜:你意外获得【通宝】一枚

      鲜花已经成功送出,可通过工具取消

      提示:此次送花为此次送花为【有效送花赞扬,涨乐善、声望】。

    • 家园 【讨论】问题

      数学家怎么混啊!以无懈可击的严密性和以“自然科学女王”自居的整个数学体系轰然倒塌ing~~~数学家们狠得牙根痒痒的,满脸杀气的问,“上面那个声称发疯的家伙是谁?”“康托尔,格奥尔格·康托尔,就是号称‘集合论之父’的那位。”座下一人答到。……一片寂静……“那么你又是谁?”数学家们又问。“伯兰特·罗素。”

      我不清楚你这段话要说什么东西,但个人印象是,这个悖论让集合论之父康托尔发疯,而这个悖论是罗素提出来的。

      实际上,所有集合的集合导致的悖论,不是罗素提出的,也不可能让康托尔发疯,因为康托尔本人在1899年的信件中,就自己提出了这个悖论。

      罗素的确让很多数学家发疯,但不是用康托尔悖论,而是用罗素悖论。

      把所有集合分为2类,第一类中的集合以其自身为元素,第二类中的集合不以自身为元素,

      什么叫以自身为元素呢?

      举一个例子,我们规定一个集合A为

      A={B∣B 是一个集合,且其元素不是自然数}

      A是一个集合,而其元素都是集合,不是自然属,所以A是自身的元素,A∈A成立。

      而我们常见的集合如自然数集N,整数集Z等,就不是自身的元素。

      假令第一类集合所组成的集合为P,第二类所组成的集合为Q。

       P={A∣A∈A 成立}

        Q={A∣A∈A 不成立}

      问题是Q∈Q是否成立?

      如果Q∈Q成立,那么,它不满足集合Q的定义,所以Q∈Q不成立,

      而一旦Q∈Q不成立,它就满足了Q的定义,于是Q∈Q。

      这就是所谓的罗素悖论。

      A∈A 这里已经是属于关系的交换了。

      A∈{A}中的 交换,内涵虽然和这里不一样,但似乎也不能简单地说 属于关系不能交换。

      请楼主考虑一下。

      • 家园 呵呵,多虑了

        我不清楚你这段话要说什么东西,但个人印象是,这个悖论让集合论之父康托尔发疯,而这个悖论是罗素提出来的。

        俺不是这个意思,这段对话纯属一段调侃,如果一定要说有什么含义,我原本的意思就是简单的交代一下这两个人在集合论引出悖论这个问题上的地位。

        老兄的问题很中肯,我会在正式版本里重新考虑,花一个。

    • 家园 【原创】我们不谈数学(番外篇)

      前面提到了偏序关系的问题,又勾起了俺古老的回忆

      下面是俺五年前在blog上的涂鸦(那时候还是蜗在实验室里的青葱嫩小子),IT民工们可能会比较亲切,且作为一点补充的番外篇。

      ===================华丽的分割线===================

      外链出处

      关于集合框架的思考(2004-12-05)

      jungleford如是说

      对于Java集合框架(Java Collections Framework,JCF),Java玩家大概都不会陌生,在C++里面相似的概念是标准模板库(Standard Template Library,STL),主要是对一些数据结构和相关算法的封装。考虑到这是一个Java初学者将会经常接触的工具,所以有了以下的一些文字。主要是参考了IBM developerWorks上的一篇教程,它可能解释得更加清晰,这里算是浓缩了一下吧,真正的来龙去脉可以看看JDK文档里的“The Collections Framework”,说明更为详细。

      问题的源头

      * 集合:对象的容器与数据结构

      回忆一下我们在程序设计里头可能会面对一些什么,无非是两类:基本类型和复合类型,后者常见的组织方式就是类。和基本类型不同,类对象通常是需要以动态方式分配的,譬如在内存的堆空间里new一个对象,这个我们一写OO的程序就必然会用到。同时我们面对的不仅仅是单个的基本类型或对象,对多个这样的数据我们通常采用的组织方式是什么?不错,是数组,这是伴随程序设计的一个古老概念。数组的优点显而易见,像根据下标检索元素这样的操作不费吹灰之力,但缺点也很明显:空间固定而不能动态增长(像Java这样的强类型语言对数组越界是及其敏感的),插入或删除元素比较费劲。因此数组不是解决一切集合问题的方便工具。我们可能需要一些新的工具,研究这些工具常常就是研究数据结构,特别的,数组本身就是一种线性有序的数据结构。

      数据结构的数学基础是集合论,为什么这么说呢?上面说过,现在我们要研究的不是单个的基本类型或对象,多个对象的整体不就是集合吗?从OO的角度上看,集合也是一种对象,但它是一种特殊的对象:对象的容器(注意,我们这里没有继续讨论基本类型的集合,因为基本类型和存储分配方式与对象有着本质的差别)。集合论的一个根本问题就是:给定一个元素,集合必须能够回答该元素是或者不是属于这个集合。还有一个问题也很重要,就是:如果元素是属于一个集合,那该元素在集合中的地位应该是唯一的,或者说它是唯一确定的。当然还有其它问题,譬如查找、遍历、排序等等,这和具体的集合类型相关,后面将会讲到。

      * 无序集、有序集、映射

      谈到集合的类型,我们在高中所学的集合概念是其中的一种,叫做“无序集”,也就是说集合的各个元素都是平等的,没有先后的区别,于是在无序集当中就决不允许出现一模一样的元素,否则当取到这个元素的时候就不知道应该取哪一个,这就违反了上面的“唯一确定”原则。

      等到我们上了大学,开始知道了另一种集合类型,叫做“有序集” (或者叫“线性表”,区别于以后碰到的像“树”,“图”这样的非线性的数据结构),如果是计算机专业的,大概学过离散数学当中的“代数结构”,那你就更清楚的知道,“有序集”其实是一种“二元关系”,确切的说是“偏序关系”,它是可以包含相同元素的,因为两个的相同元素的“序号”可以不同,这样根据“序号”仍可以“唯一确定”一个元素,数组就是一种有序集,有序集的另一个特点就是任意两个元素可以确定他们的顺序。

      无序集,有序集,难道还有第三种可能?呵呵,它还是出现在我们的高中代数课本里,叫做“映射”。映射也是集合?其实自从康托尔以来,集合论就认为“万物皆集合”(但也就是这个断言导致了集合论以后的尴尬境地,有兴趣可以看看罗素或哥德尔的一些结论,或google“集合论 悖论”)。映射其实是一种“元素对”的集合,就像

      f(a)=b, f(c)=d, ...

      等效于集合(无序集)

      {(a, b), (c, d), ...}

      ,在“映射”中可以看作是(原象, 象)的集合,换一种说法就是(关键字key, 值value)的集合。所以我们可以在笛卡儿正交坐标平面上画出漂亮的函数图像,因为在集合论看来,函数(映射)就是二维平面上的一个个点,明白了?这样一来上面的“有序集”也好理解了,偏序关系

      a>b>c>d>...

      (不知道“偏序关系”就把它们看作是数组

      x[1]=a, x[2]=b, x[3]=c, x[4]=d ...

      好了)等效于无序集

      {(1, a), (2, b), (3, c), (4, d), ...}

      ,于是乎,所有的集合都等效于无序集!所以高中只教了我们一种集合,呵呵……

      JCF的全家福

      好啦好啦,这些我们都知道,又不是在上数学课,说了这么多废话,怎么还没扯到正题上来?JCF的影子我还没看见呢!列位看官别急,这就给您道来。其实上面的概念对理解JCF非常重要。

      JCF是个颇有点规模的家族,看看它的类层次关系图就知道了,下面这张图(图1)摘自著名的Thinking in Java

      点看全图

      外链图片需谨慎,可能会被源头改

      图1 JCF层次结构

      哇,这么多接口和类,真有点让人无从下手的感觉。其实我们真正需要记住的只是这么一个超超easy的结构(图2):

      点看全图

      外链图片需谨慎,可能会被源头改

      图2

      这张图看起来舒服多了吧?但它又能说明什么问题呢?它怎么就能够把握整个JCF呢?我们把Collection接口置于最顶上,意思是想说:Collection其实是整个JCF家族中的“祖宗”,几乎所有的JCF成员都源自该接口,或者和它有密切的关系,Collection提供关于集合的一些通用操作的接口,包括插入(add()方法)、删除(remove()方法)、判断一个元素是不是其成员(contains()方法)、遍历(iterator()方法)等等。注意了,前面的“废话”在这里将得到体现:Set接口体现的是“无序集”的概念,它是不允许有重复元素出现的;List接口代表“有序集”;而Map接口则是“映射”(在早期的Java版本中并不叫Map,我们在后面会看到),其实Map.Entry接口就是代表一个“元素对”我们可以通过Map的entrySet()方法得到这样一个由“元素对”组成的Set对象。我们注意到Set和List都是从“祖宗”Collection派生的,而Map不是,毕竟对一对元素的操作与对单个元素的操作还是有区别的,但是如果你仔细对照一下Collection和Map的源代码,以及它们的直接后代AbstractCollectionAbstractMap的源代码,你将会发现很多相似的地方,所以我们仍然可以把Map看成是和Collection有着血缘关系的接口,而和Set,List一起处于并列的位置。

      有了“无序集”,“有序集”和“映射”,我们就可以定义各种各样的抽象数据结构了,譬如图1所示的向量,链表,堆栈,哈希表,平衡二叉树等。但我们需要记住的,仅仅是图2,置于其它的成员,在用到的时候查一下API手册不就行了?不过一般初学者还是比较容易用到一些类,像Vector、ArrayList、 HashMap,我在这里列了一张表,显示了常见的JCF成员及其关系:

      Collection(集合框架的祖宗)

      |

      |_Set(无序集)

      | |

      | |_AbstractSet

      | | |

      | | |_HashSet

      | | |

      | | |_LinkedHashSet

      | |

      | |_SortedSet

      | |

      | |_TreeSet

      |

      |_List(有序集)

      | |

      | |_AbstractList

      | | |

      | | |_Vector(历史集合)

      | | | |

      | | | |_Stack

      | | |

      | | |_ArrayList(新集合)

      | |

      | |_AbstractSequentialList

      | |

      | |_LinkedList

      |

      |_(映射)

      |

      |_Dictionary(历史集合)

      | |

      | |_Hashtable

      | |

      | |_Propertie

      |

      |_Map(新集合)

      |

      |_AbstractMap

      | |

      | |_WeakHashMap

      | |

      | |_IdentityHashMap

      | |

      | |_HashMap

      | |

      | |_LinkedHashMap

      |

      |_SortedMap

      |

      |_TreeMap

      可能有的概念您还不是太了解,譬如什么叫“历史集合”,Hashtable、HashMap、TreeMap三者之间有什么区别和联系,怎样实现对一个特定集合的快速遍历、元素查找或者排序,没关系,我们在下面将逐一进行研究。

      细节考虑:目标与效率

      有了JCF的层次还不够,重要的是对集合所容纳的对象的具体操作,以前我们学数据结构的时候可能老师总会让你计算一个算法的时间复杂度,可能你会对这个O(f(n))很不耐烦,但事实上算法效率是一个重要的因素。

      1. 侧重点:遍历 vs. 查找

      对集合的有两个主要的应用:我需要知道集合有哪些元素;根据条件找到一个特定的元素。在算法上通常称为“遍历”和“查找”。不要以为我们生活中不常用哦!譬如CCTV的“幸运52”里面,李咏让参赛者报出一款PDA的准确价位,他会怎么做?“2000”“高了”“1000”“低了”“1500”“低了”……直到答对为止。可能有很多人都会选择这个策略,无论他是不是计算机专业出身的,也不知道他是不是了解“数据结构”和“折半查找”,更不用说他是不是知道还有比在无初始代价下O(log n)的时间复杂度更快的算法了,但我们经常会自然而然地用这样的方法,这和一个人的行业无关,除非这个人的rp超强,呵呵……

      又讲了一堆题外话了,遍历和修改似乎是一对矛盾,一个可以高效率插入删除元素的数据结构通常遍历的性能并不是最优。于是JCF在这里根据用户的目标实现了两种定制的数据结构:哈希表(包括HashSet和HashMap)和平衡二叉树(包括TreeSet和TreeMap)。由于可排序性是一种独特的要求,所以引入了SortedSet和SortedMap,它们分别是AbstractSet和AbstractMap的子接口,而TreeSet和TreeMap又分别是他们的一种实现。熟悉数据结构的人可能比较了解,哈希表在进行插入、删除、查找这样的操作是很快的,其时间复杂度是常数级O(1);平衡二叉树虽然插入、删除操作比较麻烦(需要O(log n)的代价),但进行遍历和排序却很快。选择完全在于用户的侧重点,但由于类型转换的方便性,通常我们用哈希表构造一个集合以后,再把它转换成相应的树集进行遍历,以获得较好的效果。

      Set set1 = new HashSet();

      set1.add(elem1);// 通过插入元素构造集合

      set1.add(elem2);

      set1.add(elem3);

      Set set2 = new TreeSet(set);

      Iterator all = set2.iterator();

      while (all.hasNext())

      {// 遍历集合

      all.next();

      ...

      }

      2. 历史实现 vs. 新实现

      历史实现(Legacy Implementations)是JCF的一个术语,准确的意义不是很清楚,但大致可以认为在Java 2(JDK 1.2)出现以前的老版本中JCF的一个雏形框架。在Java 2以后,JCF才开始完善健壮起来,新实现中出现了一些新的类用于替代老版本中的成员,但由于种种原因,老版本中很多类都代表了传统数据结构的精髓部分,以及一些安全原因,所以仍然被我们使用着。

      Enumeration vs. Iterator

      Enumeration是一个传统的集合遍历工具,在新的JCF中使用的是Iterator,Iterator同样具有遍历功能,还包含一个remove()方法来删除当前得到的元素。

      Dictionary vs. Map

      Dictionary 是一个现在已经被标记为deprecated的类,实现了老版本中的映射功能,现在已经完全被Map取代。它们的区别是:Dictionary中key和 value不能为null,但Map却允许空的关键字和值,这一点直接影响到它们的后代:Hashtable和HashMap。

      Vector vs. ArrayList

      Vector 和ArrayList是数组在JCF中的体现,还记得前面讲过的数组的缺点么?Vector和ArrayList就是一种可以动态增长的数组。 Vector是历史实现,它和ArrayList的主要区别在于,Vector是同步集合(或者说是线程安全的),但ArrayList并不是同步的,由于同步需要花一定的代价,所以ArrayList看起来要比Vector的存取访问效率更高。关于同步我们下面还将要谈到。

      Hashtable vs. HashMap

      Hashtable 是Dictionary的子类,属于历史实现,而HashMap是Map的子类,是新实现。它们的区别除了上面所说的key和value是否可以为空之外,也有同步的差别,Hashtable是同步的,但HashMap不是。HashMap的一个经典的例子就是JSP的内置对象session。不过不要因为Hashtable是“老前辈”而瞧不起它哦,它的一个著名的子类Propertie我们可是经常会用到的。

      3. 同步 vs. 不同步

      从上面的描述中我们似乎可以得出这么一个印象:历史实现好像都是同步的,但新实现中却没有。需要同步操作的理由是,可能存在多个线程对同一个集合进行操作的情况:譬如一个线程正在对某集合进行遍历,但与此同时,另一个线程又在对该集合进行插入或删除,那么第一个线程的遍历结果将是不可预测的,对于同步集合,它将会抛出一个ConcurrentModificationException异常,JCF把这种机制成为“fail-fast”。我们对比一下Vector和ArrayList的源代码就可以发现Vector的很多方法都是有synchronized关键字修饰的,但ArrayList没有。

      4. 容易遗忘的工具:CollectionArray

      在图1中右下角落里有两个类叫做Collections(注意,不是Collection!)和Arrays,这是JCF里面功能强大的工具,但初学者往往会忽视。按JCF文档的说法,这两个类提供了封装器实现(Wrapper Implementations)、数据结构算法和数组相关的应用。

      想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧,Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作:

      binarySearch:折半查找。

      sort:排序,这里是一种类似于快速排序的方法,效率仍然是O(n * log n),但却是一种稳定的排序方法。

      reverse:将线性表进行逆序操作,这个可是从前数据结构的经典考题哦!

      rotate:以某个元素为轴心将线性表“旋转”——哇,这个功能太酷了!

      swap:交换一个线性表中两个元素的位置。

      ……

      Collections还有一个重要功能就是“封装器”(Wrapper),它提供了一些方法可以把一个集合转换成一个特殊的集合:

      unmodifiableXXX:转换成只读集合,这里XXX代表六种基本集合接口:Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作,将会抛出UnsupportedOperationException异常。

      synchronizedXXX:转换成同步集合。

      singleton:创建一个仅有一个元素的集合,这里singleton生成的是单元素Set,singletonListsingletonMap分别生成单元素的List和Map。

      空集:由Collections的静态属性EMPTY_SETEMPTY_LISTEMPTY_MAP表示。

      此外,我们知道把集合转换成对象数组可以用Collection的toArray()方法,我们也可以方便地把一个对象数组转换成一个线性表(可不要告诉我你是一个一个地add哦):)]Arrays.asList()

      5. 泛型

      目前我们了解的JCF的一个重要特征是:所有加入到集合当中的对象都将在表面上失去它们自己的特性,而看上去仅仅只是一个Object对象而已,除非你把它强制类型转换成它们原来的对象。这一点很自然,集合嘛,对象的容器,它容纳的是各种各样的对象,而不仅仅是某种特定类型的对象。J2SE 5.0出现以后,JCF开始引入泛型的特性,譬如我们经常碰到这样的应用,就是把集合转换成特定的数组,虽然Collection有toArray()的方法,但可惜的是,这个数组的所有元素都是Object类型的,我们通常的做法是用一个for循环把数组的每个元素都进行强制类型转换,虽然可行,但看上去很笨拙,如果有了泛型,我们就可以预先指定要得到的类型,然后一次toArray就可以得到我们期望的数组,里面的元素全部都是指定类型了。惭愧的是,我对5.0还不是太了解,具体可以参考J2SE 5.0的JCF文档

      小结

      我这里走马观花一样把JCF的一些主要概念罗嗦了一下,Java的老手们可能比较厌烦,新手们可能更觉得像回顾了一下高中的数学课和大学的数据结构,呵呵。这只是一个小小的例子,可见基础知识对现实当中的应用还是蛮有指导意义的。大师们看数学,觉得那是很唯美很艺术的一样东西,西方一直都把数学区别于其它自然科学,而认为它更靠近于哲学,像我等这样整天还在为找工作烦得要死的俗人还是没法入道啊,sigh……

      参考资料

      * IBM developerWorks教程: Java 集合框架

      * J2SE Documentation: The Collections Framework

      * The Java Tutorial

      * JCF API

      • 家园 泛型大概和数理逻辑中的类型论有关

        类型论是罗素怀特海他们为了解决罗素悖论发展出来的。

        • 家园 MS计算机语言的类型系统也是类型论的应用

          这也就难怪国内很少有计算机语言创建出来了,理论基础与人相比太差了。不过中科院软件所的XYZ语言还是很有独创性的,其理论基础是时序逻辑。

      • 家园 我们不谈数学(番外的番外)

        还是一个老帖子

        外链出处

        2007/11/1

        5-1=巴掌?

        刚刚下班回家在农工商旁边的小摊上买花生,摊主是一对中年夫妇,一小dd,估计是他们的孩子,趴在方茶几上写作业。胡子拉碴的蜀熟在旁边盯着,突然劈头一顿落英神剑掌拍下:“五减一等于一?!五减一等于一?!”,小dd抽着鼻子都不敢哭出声,偶小声说了一句“怎么能这么对孩子呢”,估计周围太嘈杂,他们没听见。

        斗胆猜测这位蜀熟自己可能也未必能严格证明“五减一”为什么就不能等于一,可能未必学过近世代数,可能未必了解自然数和皮亚诺公理系统,可能未必清楚自然数群的性质,可能未必意识到“减”是二元函数而“等于”是二元关系……以上仅仅是说笑,不是xb,偶离散学得颇烂,把代数结构和数理逻辑课程也忘得差不多了。当年也被老豆暴扁过的,而且还是离满分差几分就揍几下的那种,不好过了若干年就来嘲笑所谓家庭暴力,只是“悟”到过了这若干年 “下雨天打孩子闲着也是闲着”的传统似乎没有多少改变。很多家长对孩子倒是挺严格,对自己反而不那么严格,没有形成健康的榜样,导致孩子成年以后缺乏纪律性和责任感,做事先想着后路,后果不好该怎么逃避追究,多年以来倒真是有点像雷海宗先生说的中国人养成了“一种文弱的气质”。

        BTW:这边的花生好像炒得比北京的苦一些……

    • 家园 请教

      所有集合的集合 的确会导致悖论,但并不是楼主这样论证的。

      设所有集合的集合为A,可由之构造幂集P(A),由于P(A)是A的子集(A的定义),则有| P(A) | ≤ | A |,

      根据Cantor定理,又有

      | P(A) | > | A |

      矛盾。

      楼主似乎没有论证出什么矛盾来,集合的定义没有禁止{A}的构造,也没有禁止{A}与A的对于属于关系的交换。

      • 请教
        家园 康托尔本人确实不是按俺那个方式论证的

        俺那就是一番心血来潮的瞎扯,主要目的就是对数学本质,主要是对数学“抽象性”方面的一点民科想法

        关于“∈”是不是可交换的,取决于“∈”是不是一种偏序二元关系。俺是想当然的觉得“∈”是偏序关系,不仅是偏序的,而且还是全序关系
        这个纯属胡说八道,请跳过

        • 家园 的确有点想当然了

          关于“∈”是不是可交换的,取决于“∈”是不是一种偏序二元关系。俺是想当然的觉得“∈”是偏序关系,不仅是偏序的,而且还是全序关系

          一般来说,元素之间和集合之间是没有“∈”关系的,这是集合与元素之间的关系。

          第一条自反性就不满足。

          你这个关系是定义在什么集合上的呢?

          • 家园 呃,讲序关系是不对

            讲关系首先要定义论域,这个在集合的各种关系里不好定,前面讲序关系是不对,只好笼统讲“属于关系”了

            • 家园

              你那个,有点怪,看不出明显的悖论。

              因为,属于关系定义在什么集合上你讲不清楚,你认为你构造出来的那个矛盾,实际上违反的是 反对称性,但是,自反性一早就不成立,传递性更是无从谈起。

              所以,在这个问题的讨论中,贸然把关系扯进来,不大适当。

    • 家园 【文摘】在数学的海洋中飘荡

      作者:Dahua

      在过去的一年中,我一直在数学的海洋中游荡,research进展不多,对于数学世界的阅历算是有了一些长进。

      为什么要深入数学的世界

      作为计算机的学生,我没有任何企图要成为一个数学家。我学习数学的目的,是要想爬上巨人的肩膀,希望站在更高的高度,能把我自己研究的东西看得更深广一些。说起来,我在刚来这个学校的时候,并没有预料到我将会有一个深入数学的旅程。我的导师最初希望我去做的题目,是对appearance和motion建立一个unified的model。这个题目在当今Computer Vision中百花齐放的世界中并没有任何特别的地方。事实上,使用各种Graphical Model把各种东西联合在一起framework,在近年的论文中并不少见。

      我不否认现在广泛流行的Graphical Model是对复杂现象建模的有力工具,但是,我认为它不是panacea,并不能取代对于所研究的问题的深入的钻研。如果统计学习包治百病,那么很多“下游”的学科也就没有存在的必要了。事实上,开始的时候,我也是和Vision中很多人一样,想着去做一个Graphical Model——我的导师指出,这样的做法只是重复一些标准的流程,并没有很大的价值。经过很长时间的反复,另外一个路径慢慢被确立下来——我们相信,一个图像是通过大量“原子”的某种空间分布构成的,原子群的运动形成了动态的可视过程。微观意义下的单个原子运动,和宏观意义下的整体分布的变换存在着深刻的联系——这需要我们去发掘。

      在深入探索这个题目的过程中,遇到了很多很多的问题,如何描述一个一般的运动过程,如何建立一个稳定并且广泛适用的原子表达,如何刻画微观运动和宏观分布变换的联系,还有很多。在这个过程中,我发现了两个事情:

      我原有的数学基础已经远远不能适应我对这些问题的深入研究。

      在数学中,有很多思想和工具,是非常适合解决这些问题的,只是没有被很多的应用科学的研究者重视。

      于是,我决心开始深入数学这个浩瀚大海,希望在我再次走出来的时候,我已经有了更强大的武器去面对这些问题的挑战。

      我的游历并没有结束,我的视野相比于这个博大精深的世界的依旧显得非常狭窄。在这里,我只是说说,在我的眼中,数学如何一步步从初级向高级发展,更高级别的数学对于具体应用究竟有何好处。

      集合论:现代数学的共同基础

      现代数学有数不清的分支,但是,它们都有一个共同的基础——集合论——因为它,数学这个庞大的家族有个共同的语言。集合论中有一些最基本的概念:集合(set),关系(relation),函数(function),等价(equivalence),是在其它数学分支的语言中几乎必然存在的。对于这些简单概念的理解,是进一步学些别的数学的基础。我相信,理工科大学生对于这些都不会陌生。

      不过,有一个很重要的东西就不见得那么家喻户晓了——那就是“选择公理”(Axiom of Choice)。这个公理的意思是“任意的一群非空集合,一定可以从每个集合中各拿出一个元素。”——似乎是显然得不能再显然的命题。不过,这个貌似平常的公理却能演绎出一些比较奇怪的结论,比如巴拿赫-塔斯基分球定理——“一个球,能分成五个部分,对它们进行一系列刚性变换(平移旋转)后,能组合成两个一样大小的球”。正因为这些完全有悖常识的结论,导致数学界曾经在相当长时间里对于是否接受它有着激烈争论。现在,主流数学家对于它应该是基本接受的,因为很多数学分支的重要定理都依赖于它。在我们后面要回说到的学科里面,下面的定理依赖于选择公理:

      拓扑学:Baire Category Theorem

      实分析(测度理论):Lebesgue 不可测集的存在性

      泛函分析四个主要定理:Hahn-Banach Extension Theorem, Banach-Steinhaus Theorem (Uniform boundedness principle), Open Mapping Theorem, Closed Graph Theorem

      在集合论的基础上,现代数学有两大家族:分析(Analysis)和代数(Algebra)。至于其它的,比如几何和概率论,在古典数学时代,它们是和代数并列的,但是它们的现代版本则基本是建立在分析或者代数的基础上,因此从现代意义说,它们和分析与代数并不是平行的关系。

分页树展主题 · 全看首页 上页
/ 2
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河