x*****o
发帖数: 28 | 1 Hi.I just feel interesting on the underlying implmentation of the vector
class. Anyone knows some detail on these stuffs? Thanks! Appreciate!
For the vector, it is a growable array,
1. it can support dynamic insert and delete
2. it can be accessed by index
So I just wonder how they implement it?
(Just my guess) the vector is still actually an contiguous array, and when
insert and delete, just create a new modified copy of the array.?
I am interested in this, because my code is based on the vecto | w*******g
发帖数: 9932 | 2 if you really want efficiency, define your own vector.
moreover, jdk 1.5 now uses List and its concrete classes such as
ArrayList, LinkedList, etc.
underlying
【在 x*****o 的大作中提到】
: Hi.I just feel interesting on the underlying implmentation of the vector
: class. Anyone knows some detail on these stuffs? Thanks! Appreciate!
: For the vector, it is a growable array,
: 1. it can support dynamic insert and delete
: 2. it can be accessed by index
: So I just wonder how they implement it?
: (Just my guess) the vector is still actually an contiguous array, and when
: insert and delete, just create a new modified copy of the array.?
: I am interested in this, because my code is based on the vecto
| s***e
发帖数: 284 | 3 allocate some space in advance.
once it's not enough, allocate a larger memory space, copy all
existing data to new space, discard old space
underlying
【在 x*****o 的大作中提到】
: Hi.I just feel interesting on the underlying implmentation of the vector
: class. Anyone knows some detail on these stuffs? Thanks! Appreciate!
: For the vector, it is a growable array,
: 1. it can support dynamic insert and delete
: 2. it can be accessed by index
: So I just wonder how they implement it?
: (Just my guess) the vector is still actually an contiguous array, and when
: insert and delete, just create a new modified copy of the array.?
: I am interested in this, because my code is based on the vecto
| x*****o
发帖数: 28 | 4 many thanks. so, indeed a contiguous array.
if everytime i request an insert in the middle, say, at the 10th position.
everytime, it has to copy the existing data from 1 to 9th and insert
my new 10th and then copy the old 10th to the last. right?
if so, costy. I can not use the vector class. I have to write one.
【在 s***e 的大作中提到】
: allocate some space in advance.
: once it's not enough, allocate a larger memory space, copy all
: existing data to new space, discard old space
:
: underlying
| s***e
发帖数: 284 | 5 no. memory allocation only happens when your space is not enough for
new data. it may double each time. say initially its capacity is 10,
when you insert the 11th, it allocate 20 and copy. but later on, you
could insert another 9 numbers without memeory allocation. although
you have to move the second half numbers to the next position when you
insert a number into the middle position.
【在 x*****o 的大作中提到】
: many thanks. so, indeed a contiguous array.
: if everytime i request an insert in the middle, say, at the 10th position.
: everytime, it has to copy the existing data from 1 to 9th and insert
: my new 10th and then copy the old 10th to the last. right?
: if so, costy. I can not use the vector class. I have to write one.
| x*****o
发帖数: 28 | 6 thanks. isee.
【在 s***e 的大作中提到】
: no. memory allocation only happens when your space is not enough for
: new data. it may double each time. say initially its capacity is 10,
: when you insert the 11th, it allocate 20 and copy. but later on, you
: could insert another 9 numbers without memeory allocation. although
: you have to move the second half numbers to the next position when you
: insert a number into the middle position.
| w*******g
发帖数: 9932 | 7 actually, his question is different.
he wants to insert in the middle of the vector frequently,
in this case, the Vector object will compact if it is based on Array.
So to be sure, he might want to choose LinkedList class.
【在 s***e 的大作中提到】
: no. memory allocation only happens when your space is not enough for
: new data. it may double each time. say initially its capacity is 10,
: when you insert the 11th, it allocate 20 and copy. but later on, you
: could insert another 9 numbers without memeory allocation. although
: you have to move the second half numbers to the next position when you
: insert a number into the middle position.
| x*****o
发帖数: 28 | 8 exactly!!!
all the insertion happen in the middle.
But because I also need to access the array frequently.
Any good suggestions?
The access pattern is random, while the insertion or deletion is sequential
within one cycle. (means, e.g. I insert 4th, delete 8th, insert 10th....)
I just thinking of implementing a special class based on array to
handle it...
Previously I don't take a serious consideration on this issue, I just use the
vector, and the performance gains is just ok.
and this noon, I h
【在 w*******g 的大作中提到】
: actually, his question is different.
: he wants to insert in the middle of the vector frequently,
: in this case, the Vector object will compact if it is based on Array.
: So to be sure, he might want to choose LinkedList class.
| w*******g
发帖数: 9932 | 9 like I said.
In your case, it is more efficient to use a linked list.
So use the LinkedList class in JDK to do your job.
the
【在 x*****o 的大作中提到】
: exactly!!!
: all the insertion happen in the middle.
: But because I also need to access the array frequently.
: Any good suggestions?
: The access pattern is random, while the insertion or deletion is sequential
: within one cycle. (means, e.g. I insert 4th, delete 8th, insert 10th....)
: I just thinking of implementing a special class based on array to
: handle it...
: Previously I don't take a serious consideration on this issue, I just use the
: vector, and the performance gains is just ok.
| h****t
发帖数: 93 | 10 ever think a binary search tree? every insert will take O(log n) time,
but the good news is, every random access is also O(log n).
with a linklist, insert itself takes O(1), but before that you need to
locate the location, which take O(n) in worst case.
another though is to have a hash table if the data has a good distribution.
the
【在 x*****o 的大作中提到】
: exactly!!!
: all the insertion happen in the middle.
: But because I also need to access the array frequently.
: Any good suggestions?
: The access pattern is random, while the insertion or deletion is sequential
: within one cycle. (means, e.g. I insert 4th, delete 8th, insert 10th....)
: I just thinking of implementing a special class based on array to
: handle it...
: Previously I don't take a serious consideration on this issue, I just use the
: vector, and the performance gains is just ok.
| c*****t
发帖数: 1879 | 11 Why don't you just read the source code provided along with JDK?
underlying
【在 x*****o 的大作中提到】
: Hi.I just feel interesting on the underlying implmentation of the vector
: class. Anyone knows some detail on these stuffs? Thanks! Appreciate!
: For the vector, it is a growable array,
: 1. it can support dynamic insert and delete
: 2. it can be accessed by index
: So I just wonder how they implement it?
: (Just my guess) the vector is still actually an contiguous array, and when
: insert and delete, just create a new modified copy of the array.?
: I am interested in this, because my code is based on the vecto
| x*****o
发帖数: 28 | 12 oh. I never knew java is open source...
I will check it.
thx.
【在 c*****t 的大作中提到】
: Why don't you just read the source code provided along with JDK?
:
: underlying
| l***i
发帖数: 1309 | 13 Most likely it is a Binary search tree underlying, like what STL of C++ does
【在 s***e 的大作中提到】
: no. memory allocation only happens when your space is not enough for
: new data. it may double each time. say initially its capacity is 10,
: when you insert the 11th, it allocate 20 and copy. but later on, you
: could insert another 9 numbers without memeory allocation. although
: you have to move the second half numbers to the next position when you
: insert a number into the middle position.
|
|
