Re: Suitable Data Structure?
- From: John_W_Herman@xxxxxxxxx (John Herman)
- Date: Mon, 05 Dec 2005 17:35:46 GMT
I'm a little confused. Are you talking about n items with one key or m items
with n keys for each item?
Skip lists are very fast for this operation though I've only used them for a
single key. I think that they could be extended to multiple keys without
significant effort.
In article <dmp5ro$kv8$1@xxxxxxxxxxxxxxxxxxxxxxxxx>, "J.M." <jm_jm@xxxxxx>
wrote:
>Perhaps this is slightly off-topic: if it is, could someone suggest a better
>group?
>
>I have the following problem, and would certainly appreciate some help. I
>need to find a suitable data structure for a vector v of dimension n to
>implement the following algorithm effectively:
>
>v=0
>for i=1..n
> for j=1..m
> Update j components of v: v_(j(i)) = v_(j(i))+d_(j(i)) (1)
> end for j
> determine I such that v_I = max(v_i: i=1,..n). (2)
> v_I =0
>end for i
>
>The difficulty is the following: The precise components j(i) of v that will
>be updated in (1) and the values of d_(j(i)) are unknown in advance. (They
>are calculated in the i-loop elsewhere.) In any case, n is quite large
>(often n>10^5), whereas m is usually quite small (m<100).
>
>Simply selecting the largest element in (2) requires O(n) operations, for a
>total of O(n^2) operations in the entire algorithm, which is too high for
>my application. Keeping v sorted and updating the order of v after every
>update seems to be too expensive if a linear data structure is used. The
>actual amount of work needed would also be too unpredictable. Ideally, a
>binary tree could be used to keep the elements in order, but to my
>knowledge, once an element is inserted in the tree, it cannot be updated,
>so this is not suitable either. Essentially, I need an algorithm that
>requires significantly less than O(n^2) operations. Ideal would be, of
>course, O(n*log n), which could be obtained if a binary tree could be used.
>Any ideas?
>
>For the sake of completeness, I should add that all d_(j(i)) are positive,
>so that all components of v are also positive. Furthermore, once v_I has
>been selected and set to zero, it will definitely not be updated and can be
>discarded.
>
>Thanks in advance
>
>Jan
>
>
>
.
- References:
- Suitable Data Structure?
- From: J.M.
- Suitable Data Structure?
- Prev by Date: Re: differential calculus
- Next by Date: Re: Gauss-Newton, nonlinear function and curve fitting
- Previous by thread: Re: Suitable Data Structure?
- Next by thread: Re: Suitable Data Structure?
- Index(es):
Relevant Pages
|
Loading
