请问一个有关选择数据结构的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Java - 爪哇娇娃

请问一个有关选择数据结构的问题

请问一个有关选择数据结构的问题# Java - 爪哇娇娃

r*t2005-03-29 08:03

1 楼

在java程序中需要用到一个布尔数组，它的大小是可变的（从0开始，可能会增加到
1K到1M）。我的要求是尽可能地节省空间。我可以想到这些办法：
直接用数组。但是数组一旦初始化，就不可以改变长度，这种情况下我很难选择初
始化的数组大小。
初始化一定大小的布尔数组，用满了以后，产生一个更大的新数组，再把原来的数
据copy进去。我不知道这种情况下，java的内存管理机制会不会完全释放原来的数
组？如果内存资源不能完全回收，出来的performance会有问题。
用java已有的类，比如vector或者arraylist。以前没有用过这两个，不知道哪个更
好。也不知道有没有更合适的。
请各位大侠指点！！
多谢多谢！！！！

o*e2005-03-29 08:03

2 楼

then look again at java.util package.

【在 r**t 的大作中提到】

: 在java程序中需要用到一个布尔数组，它的大小是可变的（从0开始，可能会增加到
: 1K到1M）。我的要求是尽可能地节省空间。我可以想到这些办法：
: 直接用数组。但是数组一旦初始化，就不可以改变长度，这种情况下我很难选择初
: 始化的数组大小。
: 初始化一定大小的布尔数组，用满了以后，产生一个更大的新数组，再把原来的数
: 据copy进去。我不知道这种情况下，java的内存管理机制会不会完全释放原来的数
: 组？如果内存资源不能完全回收，出来的performance会有问题。
: 用java已有的类，比如vector或者arraylist。以前没有用过这两个，不知道哪个更
: 好。也不知道有没有更合适的。
: 请各位大侠指点！！

g*g2005-03-29 08:03

3 楼

check BitSet

【在 o***e 的大作中提到】

:
: then look again at java.util package.

m*t2005-03-29 08:03

4 楼

I'd go with ArrayList unless your project is on J2ME.
Just remember to use Boolean.valueOf(value) rather than new Boolean(value)
everytime when you insert an element. That way you won't end up with
a bunch of different Boolean objects.

【在 r**t 的大作中提到】

m*t2005-03-29 08:03

5 楼

Good idea. The only caveat though is that it doesn't implement
any collection interface, which may or may not matter depending on
how big of an abstraction freak you are. 8-)
BTW, don't you find it strange that it's called BitSet while
it's essentially a sequence of bits?
到
更

【在 g*****g 的大作中提到】

: check BitSet

g*g2005-03-29 08:03

6 楼

It's performance issue that holded the designers back from implementing any
collection interface.
Boolean value is stored as a bit in integer and it will be very expensive to
implement method like remove(int index).
The BitSet is only good for store large array of boolean values with trading
performance for space in mind.

加
初
数
数
个

【在 m******t 的大作中提到】

:
: Good idea. The only caveat though is that it doesn't implement
: any collection interface, which may or may not matter depending on
: how big of an abstraction freak you are. 8-)
: BTW, don't you find it strange that it's called BitSet while
: it's essentially a sequence of bits?
: 到
: 更

m*t2005-03-29 08:03

7 楼

I understand. That's why I said "depending on how big of an abstraction
freak you are." 8-)
Although one might argue that performance issues should only hold back
the *usage* of an API, rather than the *implementation* of it. Removing
a bit is expensive doesn't mean it can't/shouldn't be implemented. As
long as it's clearly documented, the user should be allowed to make a
conscious decision to still use the API.
E.g., if a BitSet occasionally
needs to be passed to an API taking Collection inte

【在 g*****g 的大作中提到】

: It's performance issue that holded the designers back from implementing any
: collection interface.
: Boolean value is stored as a bit in integer and it will be very expensive to
: implement method like remove(int index).
: The BitSet is only good for store large array of boolean values with trading
: performance for space in mind.
:
: 加
: 初
: 数