`
小玩子
  • 浏览: 22940 次
  • 性别: Icon_minigender_2
  • 来自: 北京
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

浅谈一下java API设法的一个错误带来的后果引以为戒

阅读更多
java从出台以来有十二年的历史了,我们从未知到现在被广大程序员所接受 正是说明了它有其存在与发展的空间
但是人无完人 java在设计上也有自身的缺点,举个例子:从API里可以看到java.util.Stack类,stack 的特点是后进先出 且不能查找 array的特点是易于查找但是增删比较难
这个一般的程序员都很清楚 这个类是java.util.Vector的子类,Vector底层实现是用array且线程安全,这就与statck本身的特点不符合,再者由于是继承,stack就会将父类的所有方法都继承过来
如:add(int index,E element)这与stack是根本就不能实现的 但是SUN公司对于这个错误是没办法挽回了 以至于这个错误就一直错了十多年 最后SUN公司给出的解释就是不要轻易用这个类
从这件小事上来说明 一个设计者小小的失误对代码或者一个应用会起到为意想不到的结果 所以我们要努力再努力去完善自己

分享到:
评论
20 楼 sunsy 2007-07-25  
那大家是否介绍几种比较好的stack实现。
19 楼 小玩子 2007-07-25  
好激烈的争论啊 不过就喜欢这种气氛
18 楼 JAVA_ED 2007-07-25  
netpcc 写道
1.C++ stl 里stack的实现类是可以通过第二个模板参数选择的。并非一定是deque。
2.C++的数据结构通常保存Value,而不是Reference。这样的话(a)Copy的成本比较高,(b)vector要求连续内存,所以对于size比较大的Value,以及大数据量不适合。而java只能是Reference,所以Copy的成本并不高。
3.我想说明的是做为stack的底层结构,vector比linkedlist好,不是和deque做比较。通常deque比vector更适合。但有些情况vector更好。但是我找不出来在什么情况下linkedlist比较好。
4.我的前提条件是对stack的push和pop的操作次数远大于stack的最大元素数量的情况。也就是不停的push和pop。这是stack的典型情况。
5.能不能具体说说把vector的methods暴露出来有什么缺点。

对于CPP的情况 你可以GOOGLE一下
JAVA的vector暴露了本不应该属于其具有的API
17 楼 netpcc 2007-07-24  
1.C++ stl 里stack的实现类是可以通过第二个模板参数选择的。并非一定是deque。
2.C++的数据结构通常保存Value,而不是Reference。这样的话(a)Copy的成本比较高,(b)vector要求连续内存,所以对于size比较大的Value,以及大数据量不适合。而java只能是Reference,所以Copy的成本并不高。
3.我想说明的是做为stack的底层结构,vector比linkedlist好,不是和deque做比较。通常deque比vector更适合。但有些情况vector更好。但是我找不出来在什么情况下linkedlist比较好。
4.我的前提条件是对stack的push和pop的操作次数远大于stack的最大元素数量的情况。也就是不停的push和pop。这是stack的典型情况。
5.能不能具体说说把vector的methods暴露出来有什么缺点。
16 楼 JAVA_ED 2007-07-24  
netpcc 写道
小玩子 写道
或者用Linkedlist也可以嘛
就是不知道为啥要选用vector


用Linkedlist实现stack完全没有道理。
stack只能从一头增删数据。如果不考虑shink和海量数据的话,vector还是很适合的。

linkedlist辅助空间极大,而且添加删除也比较慢。并不适合用来实装stack.

另外C++的STL的STACK的内部存储结构是可选的。并不局限于deque。


为什么CPP里用dequeue而不用vector
因为用Vector有个无法逃避的问题
当size大于预先分配时 会首先申请空间 然后拷贝构造
再释放原有空间
如果你的stack确定大小 的确可以自定义你自己的stack实现

vector的优点在于平均时间复杂度最小
看看STL的代码
Dequeue:
void  push_back(const value_type& __x)
      {
	if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1)
	  {
	    std::_Construct(this->_M_impl._M_finish._M_cur, __x);
	    ++this->_M_impl._M_finish._M_cur;
	  }
	else
	  _M_push_back_aux(__x);
      }


List:
void  push_back(const value_type& __x)
      { this->_M_insert(end(), __x); }


Vector:
void
      push_back(const value_type& __x)
      {
	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
	  {
	    std::_Construct(this->_M_impl._M_finish, __x);
	    ++this->_M_impl._M_finish;
	  }
	else
	  _M_insert_aux(end(), __x);
      }

_M_insert_aux(end(), __x) 是个很费力气的函数 会分配内存再copy再插入
所以用Dequeue虽然不是最优 但还是适合普遍情况

JAVA里为什么不适合用vector 就是LZ说的原因

Vector is poor choice for stack implementation as all Vector methods are accessible
http://72.14.235.104/search?q=cache:c2JsFWrru2UJ:higheredbcs.wiley.com/legacy/college/koffman/0471467561/ppt/ch05.ppt+stack+linkedlist+or+vector&hl=en&ct=clnk&cd=16&gl=sg

15 楼 netpcc 2007-07-23  
jindw 写道
netpcc 写道
首先,辅助空间的消耗是按照空间复杂度来计算的。vector的情况比较复杂,但是通常可以按照O(1)来计算。而linkedlist是O(n)。

这个你还是看一下JDK源码再说吧。

我看了一下JDK1.5的源代码,没什么太大的问题。我已经说过了,vector的空间复杂度比较复杂,确实有可能比linkedlist大。按照JDK1.5的实现,按照O(1)计算可能不太合理,但是平均情况是linkedlist的1/4(linkedlist是双向链表)。如果开放出Vector(int initialCapacity, int capacityIncrement)构造函数或者从Stack在继承一下,修改capacityIncrement的话,空间复杂度几乎就是O(1)了。但是Push的时间复杂度会上升。
如有疑义,请详细说明。
jindw 写道

netpcc 写道

第三,linkedlist才会在Pop,push中反复分配,清理每个节点。vector的情况要好得多。

也是,但是相对于vector那样可能整个数组的从新分配、复制、清理,要好的多。小块的内存声请开销更低。

同上,反复Pop,Push中,vector并没有反复分配内存。
对于最大size是n,Pop/Push m次的情况来说,基于vector的stack。内存的分配次数为O(log (n))。和Pop/push次数无关。
linkedlist的内存分配次数为O(m)。
m>=n,且通常m远大于n。孰优孰劣很清楚了。
如有疑义,详细说明。
jindw 写道

netpcc 写道

第四,对于JAVA这样的纯引用Stack来说,vector在绝大多数情况下是最优解。

就凭Vector的同步特征,就可以让它在很多情况下被剔除出局。

如果是同步的问题的话,应该引入非同步的vector,比如ArrayList。

jindw 写道

netpcc 写道

第五,不存在一种数据结构在所有情况中都是最优的。C++大量使用value stack,所以deque适用于大多数情况。Java只有Reference stack,选择vector没有任何问题。而linked list只在极少数极端情况才适用。

不觉得,只要没有随机访问的需求,看不出linked list的致命缺陷。

linked list每次Push/Pop都要重新分配内存这点已经够致命了,而且还有巨大辅助空间的消耗。

14 楼 jindw 2007-07-23  
netpcc 写道
首先,辅助空间的消耗是按照空间复杂度来计算的。vector的情况比较复杂,但是通常可以按照O(1)来计算。而linkedlist是O(n)。

这个你还是看一下JDK源码再说吧。

netpcc 写道

第二,我已经说明过是在不考虑Shrink的情况。绝大多数stack是不shrink的,并且对于java来说Shrink的成本并不是很高。虽然时间复杂度是O(n),但是常数非常小。

不懂

netpcc 写道

第三,linkedlist才会在Pop,push中反复分配,清理每个节点。vector的情况要好得多。

也是,但是相对于vector那样可能整个数组的从新分配、复制、清理,要好的多。小块的内存声请开销更低。

netpcc 写道

第四,对于JAVA这样的纯引用Stack来说,vector在绝大多数情况下是最优解。

就凭Vector的同步特征,就可以让它在很多情况下被剔除出局。

netpcc 写道

第五,不存在一种数据结构在所有情况中都是最优的。C++大量使用value stack,所以deque适用于大多数情况。Java只有Reference stack,选择vector没有任何问题。而linked list只在极少数极端情况才适用。

不觉得,只要没有随机访问的需求,看不出linked list的致命缺陷。

netpcc 写道

讨论数据结构及算法时,请不要泛泛而谈。“几个”,“未必”这样的词不能说明任何问题。具体说明时间复杂度和空间复杂度才有说服力。

我是经验主义,仅供参考,不想去说服每一个人。
13 楼 netpcc 2007-07-23  
首先,辅助空间的消耗是按照空间复杂度来计算的。vector的情况比较复杂,但是通常可以按照O(1)来计算。而linkedlist是O(n)。

第二,我已经说明过是在不考虑Shrink的情况。绝大多数stack是不shrink的,并且对于java来说Shrink的成本并不是很高。虽然时间复杂度是O(n),但是常数非常小。

第三,linkedlist才会在Pop,push中反复分配,清理每个节点。vector的情况要好得多。

第四,对于JAVA这样的纯引用Stack来说,vector在绝大多数情况下是最优解。

第五,不存在一种数据结构在所有情况中都是最优的。C++大量使用value stack,所以deque适用于大多数情况。Java只有Reference stack,选择vector没有任何问题。而linked list只在极少数极端情况才适用。

讨论数据结构及算法时,请不要泛泛而谈。“几个”,“未必”这样的词不能说明任何问题。具体说明时间复杂度和空间复杂度才有说服力。
12 楼 jindw 2007-07-22  
netpcc 写道
linkedlist的优点是在中间插入,删除元素的时间复杂度为O(1)。而缺点是消耗大量辅助空间。
这个优点对Stack没有用。因此就只有缺点而没有优点了。

而且对stack提供除Push,Pop之外其他的操作也不是什么大问题。毕竟对栈里的数据进行查找,排序是常用操作。需要在栈中间插入或者删除一些元素的需求也不是特别奇怪。像表达式解析经过大幅优化后经常需要这么干。



linkedlist缺点是随机访问慢。现在的硬件环境还有谁会在乎几个引用的空间。
再说,linkedlist之外,用数组实现的有序集合,同样要让费空间,这个让费,未必比linkedlist小,而且,增删时还需要反复的从新分配、清理。。。。
11 楼 netpcc 2007-07-20  
linkedlist的优点是在中间插入,删除元素的时间复杂度为O(1)。而缺点是消耗大量辅助空间。
这个优点对Stack没有用。因此就只有缺点而没有优点了。

而且对stack提供除Push,Pop之外其他的操作也不是什么大问题。毕竟对栈里的数据进行查找,排序是常用操作。需要在栈中间插入或者删除一些元素的需求也不是特别奇怪。像表达式解析经过大幅优化后经常需要这么干。

10 楼 小玩子 2007-07-20  
netpcc 写道
小玩子 写道
或者用Linkedlist也可以嘛
就是不知道为啥要选用vector


用Linkedlist实现stack完全没有道理。
stack只能从一头增删数据。如果不考虑shink和海量数据的话,vector还是很适合的。

linkedlist辅助空间极大,而且添加删除也比较慢。并不适合用来实装stack.

另外C++的STL的STACK的内部存储结构是可选的。并不局限于deque。



你为什么说用linkedlist实现stack完全没有道理呢?
9 楼 netpcc 2007-07-20  
小玩子 写道
或者用Linkedlist也可以嘛
就是不知道为啥要选用vector


用Linkedlist实现stack完全没有道理。
stack只能从一头增删数据。如果不考虑shink和海量数据的话,vector还是很适合的。

linkedlist辅助空间极大,而且添加删除也比较慢。并不适合用来实装stack.

另外C++的STL的STACK的内部存储结构是可选的。并不局限于deque。

8 楼 jindw 2007-07-18  
小玩子 写道
好像1.6StringBuffer还有一个类似的类 StringBuilder 速度要比StringBuffer快 但是线程不安全

集合需要同步的情况还是比较常见,不过也没必要在实现类里面实现,后来jdk4的Collections工具类的一些同步包装方法就比较漂亮。

很难想象StringBuffer需要同步的情景。
7 楼 Godlikeme 2007-07-17  
集合操作线程同步意义不大,只能保证操作的原子性,不能保证数据的完整性。StringBuffer得不偿失。
6 楼 小玩子 2007-07-17  
晕 应该是1.5 咋打错了呢
5 楼 小玩子 2007-07-17  
好像1.6StringBuffer还有一个类似的类 StringBuilder 速度要比StringBuffer快 但是线程不安全
4 楼 歆渊 2007-07-17  
Stack 是从1.0就有了, 那时候还不是 Collections Framework, java.util.* 的设计也就没有那么成体系, 看看 Properties, Hashtable 也差不多.

Java 在 1.0 的时代还挣扎在生存斗争里, 主要精力还是在 安全, 网络, 跨平台 等等那些亮点上, 细节上感觉没有顾得上精雕细琢. 到了1.1好像底气才比较足起来, 做了很多重大改进.

其实像 StringBuffer 也是类似, 程序里 String s = "Hello, " + "World" 这样的语句是编译为 String s = new StringBuffer().append("Hello,").append("World").toString(); 的, 这种用法用户代码根本得不到那个StringBuffer的引用, 也就不可能在多个线程间共享, 所以也就根本不可能出现并发访问, 用不着同步的.

但是StringBuffer从头到尾都是同步实现的, 当然也是考虑给不注意同步问题的程序员预先买单, 而且牺牲的只是大约30%的性能, Java一开始的时候自己已经慢得够呛了, 这点性能损失虽然没有必要, 但是很不明显.

另外一个可能的部分原因是Java的同步机制太有创意了, 最初大家都很兴奋, 喜欢把它用在各种看起来需要的地方.

不过现在Java的性能问题已经是本质性的改善了, 也确立了自己的地位, 类似的历史问题也到了回过头去追求完美的时候了. 所以从5.0开始, 引入了 StringBuilder, 不需要同步的时候就用它, 而接口和实现逻辑与StringBuffer完全相同, 只是简单去掉了一些synchronized关键字.
3 楼 小玩子 2007-07-17  
或者用Linkedlist也可以嘛
就是不知道为啥要选用vector
2 楼 JAVA_ED 2007-07-17  
<br/>
<strong>小玩子 写道:</strong><br/>
<div class='quote_div'><font>java从出台以来有十二年的历史了,我们从未知到现在被广大程序员所接受 正是说明了它有其存在与发展的空间<br/>
但是人无完人 java在设计上也有自身的缺点,举个例子:从API里可以看到java.util.Stack类,stack 的特点是后进先出 且不能查找 array的特点是易于查找但是增删比较难<br/>
这个一般的程序员都很清楚 这个类是java.util.Vector的子类,Vector底层实现是用array且线程安全,这就与statck本身的特点不符合,再者由于是继承,stack就会将父类的所有方法都继承过来<br/>
如:add(int index,E element)这与stack是根本就不能实现的 但是SUN公司对于这个错误是没办法挽回了 以至于这个错误就一直错了十多年 最后SUN公司给出的解释就是不要轻易用这个类<br/>
从这件小事上来说明 一个设计者小小的失误对代码或者一个应用会起到为意想不到的结果 所以我们要努力再努力去完善自己<br/>
</font>
<p><font><img src='/javascripts/fckeditor/editor/images/smiley/msn/regular_smile.gif' alt=''/></font></p>
</div>
<br/>
的确 我猜测可能是因为STL里一般用dequeue adapt stack, 但是JAVA没有dequeue 所以选择了vector<br/>
可以选择用LinkedList实现 也可以封装JDK的stack<br/>
<br/>
1 楼 baallee 2007-07-17  
不知道是不是作者偷懒,哈哈,继承Vector实在是匪夷所思。无依无靠实现个stack也不是什么难事吧。

相关推荐

    《java程序调试》的一些方法

    程序错误类型按照发现难度的不同可以分为三类:编译错误、运行时错误和逻辑错误(这里描述为“没有错误的错误”)。这三类错误在调试过程中都需要采取不同的策略来处理。 1. **编译错误**:这类错误是最容易发现的...

    浅谈C语言函数的递归调用.pdf

    "浅谈C语言函数的递归调用.pdf" 本文主要讲述了C语言函数的递归调用,包括递归函数的定义、类型、应用实例和执行过程的分析。 递归函数是一种特殊的函数调用方式,它允许函数调用自身,使得问题可以被简化和解决。...

    浅谈“C语言程序设计”教学体会 (1).pdf

    本文为浅谈“C语言程序设计”教学体会,讨论了C语言课程的教学经验和体会。该课程是高等院校计算机专业基础课程之一,其教学效果直接影响学生在计算机方面的应用。本文结合三年来的教学实践,浅谈了几点对该课程的...

    基于Java的异常处理技术与应用.pdf

    Java将程序中的错误分为两类:一类是程序本身的代码存在问题,导致程序不能简单地恢复执行,这就是错误;另一类是不可以预测的异常情况,通过某种修正后程序还可以继续执行,这类错误称为异常(如内存不足、找不到所...

    浅谈小学生如何写好作文.doc

    【标题】: "浅谈小学生如何写好作文.doc" 的主要知识点 【描述】: 本文探讨了如何帮助小学生提高作文水平,强调了激发学生兴趣、选材的重要性、选取写作角度以及培养写作方法的总结与应用。 【标签】: 小学生作文...

    浅谈微分方程模型在经济学中的应用.doc

    浅谈微分方程模型在经济学中的应用 微分方程模型在经济学中的应用是经济学研究的重要工具之一。经济问题的处理和决策的产生都离不开数学经济模型的应用。数学经济模型可以按变量的性质分成两类,即概率型和确定型。...

    JAVA 五子棋人机对战

    【JAVA五子棋人机对战】是一种基于JAVA编程实现的智力游戏,它结合了基本的计算机算法与玩家之间的互动,让玩家可以与计算机进行五子棋比赛。在这个项目中,开发者采用了一些简单的人工智能策略,通过分析棋盘上不同...

    通信与网络中的浅谈梭子鱼安全负载均衡机

     梭子鱼安全负载均衡机是一个强大的TCP/UDP 4-7层流量管理设备,功能强大、易用且适用于所有规模的企业。除了强大的负载均衡功能之外,梭子鱼安全负载均衡机还内置入侵检测(IPS)系统。即使有人已经设法突破了你...

    浅谈新理念下幼儿园美术活动的开展.docx

    【标题】:浅谈新理念下幼儿园美术活动的开展 【描述】:本文探讨了在新的教育理念下,如何有效地开展幼儿园美术活动,以促进幼儿的全面发展。 【标签】:幼儿美术教学,观察分析法,范例教学法,启发联想法,情境...

    达内 coreJava 习题答案

    12、输入一个数据n,计算斐波那契数列(Fibonacci)的第n个值 1 1 2 3 5 8 13 21 34 规律:一个数等于前两个数之和 //计算斐波那契数列(Fibonacci)的第n个值 public class Fibonacci{ public static void main...

    Java程序员面试宝典:数字的智力测试

    Java程序员在面试中经常面临各种智力测试,这些测试旨在评估候选人的逻辑思维、问题解决能力和数学技巧。以下是一些解答智力测试的关键策略: 1. **排除法**:这是最基本也是最常用的策略,通过排除明显不相关或不...

    JAVA性能瓶颈和漏洞检测

    JProbe Suite是一种能节省开发时间、降低开发费用、改善Java应用运行速度及和扩展能力的强大工具套件,在全球各地拥有大量用户。通过JProbe Suite,开发和测试小组可以全面诊断应用性能、内存使用、线程及代码覆盖等...

    教育精品资料浅谈信息技术在培养小学数学创新思维能力的有效运用.doc

    【教育精品资料浅谈信息技术在培养小学数学创新思维能力的有效运用】 信息技术的快速发展为教育领域带来了革命性的变化,尤其在小学数学教学中,它已成为激发学生创新思维的重要工具。本文探讨了如何通过信息技术的...

    浅谈思想政治教育.docx

    面对这一挑战,教师需要转变教育理念,注重情感投入,建立与学生的深厚联系。 【关爱学生,理解其需求】 教师对学生的关爱是教育成功的关键。通过深入理解学生的想法,关注他们的心理变化,可以及时发现并解决问题...

    如果应用系统是面向多种语言的,编程时就不得不设法解决国际化问题

    如果应用系统是面向多种语言的,编程时就不得不设法解决国际化问题,包括操作界面的风格问题、提示和帮助语言的版本问题、界面定制个性化问题等。由于Java语言具有平台无关、可移植性好等优点,并且提供了强大的类库...

    如果应用系统是面向多种语言的,编程时就不得不设法解决国际化问题、

    如果应用系统是面向多种语言的,编程时就不得不设法解决国际化问题,包括操作界面的风格问题、提示和帮助语言的版本问题、界面定制个性化问题等。由于Java语言具有平台无关、可移植性好等优点,并且提供了强大的类库...

    浅谈提高小学数学课堂效率的途径.docx

    教师应设法打破这种定势,通过“一题多问”、“一题多解”和“一题多变”等方法,激发学生的创新思维。例如,对于同一道题,教师可以从不同角度提问,鼓励学生寻找多种解法。在解题过程中,学生应该学会从不同角度...

    三年级奥数用假设法解题PPT教案.pptx

    三年级奥数用假设法解题PPT教案.pptx

    浅谈小学数学教材中“数学广角”.doc

    【数学广角】是人教版小学数学教材中设置的一个特色单元,旨在向小学生逐步渗透数学思维方法。这个单元的设计不仅是教材的亮点,也是教育创新的体现,它针对学生的数学思维训练,旨在培养学生的数学兴趣、欣赏数学美...

    Java专业课程设计点小游戏.docx

    本课程设计的目标是通过设计和实现一个 21 点小游戏,来加深学生对面向对象程序设计理论、方法和基础知识的了解,掌握使用 Java 语言进行面向对象设计的基础方法,提升利用面向对象知识分析实际问题、处理实际问题...

Global site tag (gtag.js) - Google Analytics