The Art Gallery Guardian

Speed up incremental computation with two stacks


1 Introduction

Problem1

Consider a knapsack of capacity and a empty sequence of objects. One can update the sequence by add or delete objects from either end of the sequence. Construct a data structure, such that we can output the maximum possible value of the knapsack after every update if we pack the knapsack using the objects in the sequence.

This is a generalization of the online knapsack problem, which is an generalization of a hard offline knapsack problem used by Quora.

A naive algorithm just recompute the knapsack each time using a dynamic programming algorithm. This would take time, where is the total number of updates, is the maximum number of objects in the sequence. The rest of the article describe the idea of decomposable function, which lead to an solution that solves this problem in time.

2 Decomposable function

Definition2

A function is called -decomposable, if for all , where

1. $\triangleright:X\times Y_{\triangleright}\to Y_{\triangleright}$ is right associative.
2. $\triangleleft:Y_{\triangleleft} \times X\to Y_{\triangleleft}$ is left associative. 
3. $\bowtie:Y_{\triangleright}\times Y_{\triangleleft}\to Y$.
Problem3

Let be a -decomposable function. Let be a finite sequence of elements, such that is in the domain of . Dynamically output after every deque operation on , such that we call and amortized constant number of times per operation.

We will use to mean , and to mean .

is called decomposable if there exist such that it’s decomposable.

The intuition is the function can be decomposed into solving two pieces of problems. Each piece of the problem has a incremental nature.

, the maximum value possible given objects and a knapsack of capacity is a decomposable function. If produces the last row of the common dynamic programming algorithm for the knapsack, then we can let to be an operation that combine the last rows to output a value.

3 Implement the data structure

Intuitively, and produces two stacks. combines the information on the stack to produce the solution to .

3.1 , a stack

Problem4

We have a stack of elements , dynamically maintain in per operation.

Say . We store for all , and whenever there is an insertion, we compute in one monoid operation. Deletion can be handled by discarding a value. In the worst case, gets called only once.

But this requires us to store values after the fold. We can decrease the extra space to store only prefix sums.

Let . Originally we store for all . We show how we store only when is a perfect square and around other elements. If , we make sure we store for all between and , and do not store any non perfect square smaller than (this means we actively clean them up as grows large). Assume we are deleting, we can delete around elements before we hit a perfect square, in that case we would need to recompute the sums from the previous perfect square. It’s not hard to see some amortized analysis, the extra space can be made into .

Actually, there is a entire range of space/time trade-offs possible. amortized time per operation and extra space [1].

3.2 , combine two stacks to simulate a deque

First, let’s consider we are allowed to add on both side of the sequence, but deletion is only at the beginning of the sequence.

The idea is to build this through two stacks. This is a very common problem, and we can see the solutions here. One thing to remember is that the left stack uses , the right stack uses .

We can try to simulate the deque with 3 stacks(where deque operation maps to stack operations) [2], but that is just an interesting exercise. We just need to use our two stack set up as in the queue and occasionally rebuild everything. When our front stack become empty and we remove an element in front of our sequence, we just rebuild the structure with two stacks of the same size. There are ways to do the rebuilding without use extra space. The case on the other side is handled symmetrically. Therefore we still maintain amortized monoid time per operation and extra space. Finally, we combine the result through .

Remark

There exist worst case constant time simulation of deque using a few stacks [2]. Thus it is conceivable to make everything from amortized to worst case, with obvious increase in space.

4 Examples

I have the code sample for the entire framework along with the examples. There are only functions.

emptyDecomposableDequeue initialize the data structure with the corresponding functions. pushFront, pushBack, popFront and popBack manipulates the sequences. measure returns the result after apply our decomposable function to the sequence.

4.1 Knapsack

Our common dynamic programming formulation is to sequentially compute tables , such that contains the maximum value picking objects from with knapsack capacity .

Usually, we order the objects as , and . We compute table from in time. This should be the operation for and . To get the particular entry , time suffice if we are given table for and . This would be the operation.

This implies if the sequence size is at most , then for any sequence of operations, we can dynamically compute all in time using only space. Notice once we convert the general algorithm to work in this special case, it is essentially the solution by Lei Huang. In fact, this general data structure is inspired by his solution.

4.2 Maximum subarray sum

The common dynamic programming problem of finding the maximum sum in an array(or, here we consider as a sequence) with both negative and positive numbers. One can compute it in linear time with Kadane’s algorithm. This is a decomposable function, too.

Let , where is the maximum sum using the beginning, is the sum of all elements from the beginning, is the maximum using the current element and is the maximum seen so far. is defined similarly. One can see that .

4.3 Dynamic sum of a sequence of elements

Problem5

Let be a finite sequence of elements from a monoid . Dynamically maintain the sum of all element in the sequence if we can add and delete element in both end of the sequence.

A simpler version of this problem is asked in CS theory, where we are allowed to add in one end and delete in another.

Let be the sum of elements in the sequence, then is -decomposable. There is a more general statement:

Theorem6

is a homomorphism, then it is decomposable.

Of course, there is already a data structure support this–a finger tree [3]. Because of the monoid structure, we can even allow concatenations.

References

[1]
S. Swamy, JohnE. Savage, Space-time tradeoffs for linear recursion, Mathematical Systems Theory. 16 (1983) 9–27 10.1007/BF01744566.
[2]
H. Petersen, Stacks versus deques, in: J. Wang (Ed.), Computing and Combinatorics, Springer Berlin Heidelberg, 2001: pp. 218–227 10.1007/3-540-44679-6_24.
[3]
R. Hinze, R. Paterson, Finger trees: A simple general-purpose data structure, J. Funct. Program. 16 (2006) 197–217 10.1017/S0956796805005769.
Posted by Chao Xu on .
Tags: algorithmic toolkit.