The Art Gallery Guardian

Sum of sparse array in linear time


Let n=(n1,,nd)\vec{n}=(n_1,\ldots,n_d). Define xmod  n=(x1mod  n1,,xdmod  nd)\vec{x}\mod \vec{n} = (x_1 \mod n_1,\ldots,x_d\mod n_d). We want to represent an dd-dimensional array. Assume AA and BB are both dd-dimensional arrays of size n\vec{n} and one have mm non-zero elements one have mm' non-zero elements. The following operations should be supported.

  1. circshift(A,r)circshift(A,\vec{r}) creates a new sparse array CC, such that C((i+r)mod  n)=A(i)C((\vec{i}+\vec{r}) \mod \vec{n})=A(\vec{i}). This is the circshift operation in matlab. Running time should be O(m)O(m).
  2. Similarly, we can define shift(A,t)shift(A,\vec{t}), such that C(i+t)=A(i)C(\vec{i}+\vec{t})=A(\vec{i}), if i+t\vec{i}+\vec{t} is outside the range, we have 00 instead.
  3. A+BA+B returns a sparse array CC such that C(i)=A(i)+B(i)C(\vec{i})=A(\vec{i})+B(\vec{i}) in O(m+m)O(m+m') time.
  4. elements(A)elements(A) output all elements with associated coordinates in AA in O(m)O(m) time.
  5. initialize(x,n)initialize(x,\vec{n}) create a new sparse array with size n\vec{n} and one element xx initialized at 0\vec{0} position.

We create a sparse list with d1d-1 dimension slices, and the lower dimension slices can be handled inductively. All we need to do is to implement sparse list. The list should store the position and value pairs ordered by position. Sum can be done with a merge operation. circshift go though all elements one by one and update the position, and then rotate the list so the smallest position is in the beginning.

This data structure can be useful output sensitive dynamic programming problems. For example, multidimensional subset sum have a simple recursive solution.

  1. Input S={s1,,sn}S=\{s_1,\ldots,s_n\}
  2. X{0}X\gets \{0\}.
  3. For ii from 11 to nn, XX{x+sixX}X\gets X \cup \{x+s_i|x\in X\}.
  4. Return XX

The running time is O(SX)O(|S||X|), where XX is the final output, since {x+sixX}\{x+s_i|x\in X\} is a shift, and union is just a sum. Using circshift, it can produce a output sensitive algorithm for subset sums in finite abelian groups.

Posted by Chao Xu on .
Tags: Algorithm.