f*********d
发帖数: 140 | 1 Describe a data structure for which
getValue(int index)
setValue(int index, int value)
setAllwalues(int value)
are all O(1)
题目来之MS |
z****e
发帖数: 54598 | 2 hashmap + private Integer allValues
如果setAllvalues的时候，记得clear map
get时候，先查hashmap，再看allValues是不是为空 |
f*********d
发帖数: 140 | 3 嗯，学习了!
对了，c++, java 里面各种clear 的复杂度(e.g., clear map)可以认为是O(1)的吧?
【在 z****e 的大作中提到】
: hashmap + private Integer allValues
: 如果setAllvalues的时候，记得clear map
: get时候，先查hashmap，再看allValues是不是为空
|
z****e
发帖数: 54598 | 4 如果不是的话
hashmap = new HashMap();
【在 f*********d 的大作中提到】
: 嗯，学习了!
: 对了，c++, java 里面各种clear 的复杂度(e.g., clear map)可以认为是O(1)的吧?
|
f*********d
发帖数: 140 | 5 嗯
合情合理
鞠躬致敬~
【在 z****e 的大作中提到】
: 如果不是的话
: hashmap = new HashMap();
|
s*******n
发帖数: 305 | 6
为啥setAllvalues 会是O（1）？
【在 z****e 的大作中提到】
: hashmap + private Integer allValues
: 如果setAllvalues的时候，记得clear map
: get时候，先查hashmap，再看allValues是不是为空
|
v****p
发帖数: 53 | 7 Hashmap 不支持index 吧. 应该用Vector?
【在 z****e 的大作中提到】
: hashmap + private Integer allValues
: 如果setAllvalues的时候，记得clear map
: get时候，先查hashmap，再看allValues是不是为空
|
r*********n
发帖数: 4553 | 8 显然不是，比如c++里面unordered_map clear，每个元素的destructor都要被调用一次。
我不熟悉java，但是我觉得下面这行
hashmap = new HashMap();
只是把destructor call的时间推迟到garbage collection的时候，但是应该还是
linear time吧。
【在 f*********d 的大作中提到】
: 嗯，学习了!
: 对了，c++, java 里面各种clear 的复杂度(e.g., clear map)可以认为是O(1)的吧?
|
b******7
发帖数: 92 | 9 clear应该做不到O(1)。
我的想法是加设置commonValue，并加入时间戳区别setValue与setAllValues的调用先
后关系，若setValue比setAllValues先调用则返回hashmap中的值，否则返回
commonValue。具体code见http://blog.sina.com.cn/s/blog_979956cc0101hs1a.html |
l******9
发帖数: 26 | 10 http://grepcode.com/file/repository.grepcode.com/java/root/jdk/
HashMap 的 clear() 复杂度是 O(n)
【在 f*********d 的大作中提到】
: Describe a data structure for which
: getValue(int index)
: setValue(int index, int value)
: setAllwalues(int value)
: are all O(1)
: 题目来之MS
|
r*********n
发帖数: 4553 | 11 赞...这个方法不错
【在 b******7 的大作中提到】
: clear应该做不到O(1)。
: 我的想法是加设置commonValue，并加入时间戳区别setValue与setAllValues的调用先
: 后关系，若setValue比setAllValues先调用则返回hashmap中的值，否则返回
: commonValue。具体code见http://blog.sina.com.cn/s/blog_979956cc0101hs1a.html
|
f*********d
发帖数: 140 | 12 牛，好方法！
学习了~
【在 b******7 的大作中提到】
: clear应该做不到O(1)。
: 我的想法是加设置commonValue，并加入时间戳区别setValue与setAllValues的调用先
: 后关系，若setValue比setAllValues先调用则返回hashmap中的值，否则返回
: commonValue。具体code见http://blog.sina.com.cn/s/blog_979956cc0101hs1a.html
|
z****e
发帖数: 54598 | 13 这贴很好滴说明了c程序员和java程序员的区别
就拿这题而言
这些内存的使用，如果要考虑gc的话
最好的方法就是在你需要clear时候，整块扔掉
然后到了gc的时候，jvm自动清空这一块
有什么问题，比如linear清空map
这里可以单独做优化
当初想clear的目的主要是复用代码，节省内存
不过这一块已经越来越不提倡使用了，new越来越好了
如果引入额外的标记
不仅使得内存使用增加，因为有额外的变量占用内存
而且使得gc机制不能很好的工作，因为该清空的map不会被gc
有map的引用，内部所有储存的变量都不会被gc
最后这个map会越来越大 |
x***y
发帖数: 633 | 14 Good idea.
Another way of avoiding timestamp is to use the 3-array approach of setting
values in memory, which has initial garbage values.
【在 b******7 的大作中提到】
: clear应该做不到O(1)。
: 我的想法是加设置commonValue，并加入时间戳区别setValue与setAllValues的调用先
: 后关系，若setValue比setAllValues先调用则返回hashmap中的值，否则返回
: commonValue。具体code见http://blog.sina.com.cn/s/blog_979956cc0101hs1a.html
|
