Re: Suitable Data Structure?

On 2005-12-02 05:58:15 -0400, "J.M." <jm_jm@xxxxxx> said:

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 


After a quick scan, before morning coffee, this looks like a priority
queue, also known as a heap (one of many usages of heap!), where you
want to modify some elements in the heap. Keep two structures, one
is just an array and the other is a heap where both know the position
on any object in the other. Modifying an array is simple. Modifying a
heap usually goes by the names of sift-up or sift-down.



.

Relevant Pages

  • Re: Suitable Data Structure?
    ... need to find a suitable data structure for a vector v of dimension n to ... update seems to be too expensive if a linear data structure is used. ... I need an algorithm that ... course, O, which could be obtained if a binary tree could be used. ...
    (sci.math.num-analysis)
  • Re: Genealogical evidence and data model
    ... a heap file was just that -- an unsorted ... A heap is a specialized tree-based data structure that satisfies the ... do with biology and more to do with a political decision (much like ... It sounds like it is a relational database that has a table ...
    (soc.genealogy.computing)
  • Re: Lisp data structures repository?
    ... and generally only one data structure. ... I was looking for a heap. ... > least like to submit it with a BSD license and unit tests (probably ... > Lisp style/conventions very well. ...
    (comp.lang.lisp)
  • Re: Need some help understanding array definitions
    ... For example I can define a data structure called 'node'. ... For heap-like problems, I would actually use the Forth heap (ALLOCATE/ ... the dictionary space often has lower memory limits than the heap ...
    (comp.lang.forth)
  • Re: a tool for debugging memory leaks? for ARM and OS-Linux
    ... You could have an ever-expanding data structure, or heap ... yes an ever expanding data structure, i know i do not have. ... but what is heap fragmentation? ...
    (comp.unix.programmer)