6
$\begingroup$

Description

Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to "B", my derived list looks like ["B"]. Next, if I change my source list's "d" to "D", the derived list should look like ["B","D"].

Is it possible to make the insertions and removals in the derived list, while maintaining order, in faster than $O(n)$ time, $n$ being the size of the list?

Finally, I'd like to be able to know the index of where the insertion or removal takes place in the derived list in faster than $O(n)$ time.

An idea that doesn't work

I could keep the derived list in a tree, sorted by the source index. This way, when I needed to insert my item in derived tree-list, it would take $O(log n)$. However, I would not be able to know that index of that insertion without walking the entire tree.

Thanks for your help!

Problem Statement

  • Let $S$ be an ordered list
  • Let $Si.filterProperty$ be $true$ for some elements in $S$
  • Let $F$ be an ordered list of all elements in $S$ where $Si.filterProperty$ is true

Let $T(i)$ be a function that:

  • Sets $Si.filterProperty$ to $true$
  • Inserts $Si$ into $F$, ordered in the same fashion as $S$
  • Returns the index in $F$ where $Si$ was inserted

Can $T$ and its side effects be faster than $O(n)$?

Any list-like data structures can be used within these constraints:

  • Insertion and side effects of insertion are faster than $O(n)$
  • We must know the index of the newly inserted item into $F$
$\endgroup$
  • 2
    $\begingroup$ I don't understand what you're trying to accomplish, or what task you are trying to make run fast. I also don't understand the filter (why isn't the derived list ["A","B","C","D"]? that's what you get after capitalizing every element of the input list -- so it sounds like you also have a selection operator you haven't told us about). Finally, what have you tried? For instance, do you know about balanced binary search trees? If you store the derived list in such a data structure, insertions and deletions take $O(\lg n)$ time. So: Can you edit the question to clarify? $\endgroup$ – D.W. Jun 9 '15 at 23:19
  • 2
    $\begingroup$ What is the underlying problem you are trying so solve? This has the smell of "actually, what you want to do is...". In particular, does $F$ do be exist explicitly? What properties does $F$ have to have, API-wise? $\endgroup$ – Raphael Jun 10 '15 at 11:05
  • 2
    $\begingroup$ If you keep $S$ in a balanced binary tree, you can do insertion in $\log n$ time. You can keep in each node of the tree a count of the number of elements below it so that the current rank of any element in $S$ can also be known in $\log n$ time. Finally we also keep in each node a count of the elements of $F$ below it, so that we can also compute the rank in $F$ in $\log n$ time. This seems to meet your requirement in a fairly standard way. So I am wondering whether you have more constraints regarding the use of $F$. In particular, I am not sure what $n$ is supposed to be. $\endgroup$ – babou Jun 10 '15 at 14:21
  • 2
    $\begingroup$ @JustinMeyer For each insertion, increment the count of any node that is traversed by one. $\endgroup$ – ramblinjan Jun 10 '15 at 20:13
  • 1
    $\begingroup$ => Justin Meyer : @jandjorgensen told me my answer was the right approach for your need, though you may want to adapt it to another kind of self ba;ancing binary search tree. Indeed, the choice of the type of tree depends on usage statistics, as AVL trees are faster when look-up dominates over tree modifications, while red-black trees are otherwise faster. So, did it solve your problem? $\endgroup$ – babou Jun 19 '15 at 21:29
3
$\begingroup$

At the time of writing I was not absolutely sure what the problem was. This lead to a more general second answer. See details in discussion at the end of this answer.

Apparently, the "idea that does not work" does not work because you do not know the index of an element $S_i$ in $F$ organized as a tree.

This is what is addressed here. The problem is restated for clarity, as your statement of it is a bit hard to follow.

Restatement of the problem:

Given a set $S$ with an order relation, maintain an ordered list $F$ where elements of $S$ can be inserted or removed, and such that the index of an element in $F$ is returned when the element is inserted.

Actually, the solution will do more, as it is possible to access any element of $F$ given its index, or to retrieve the index given an element of $F$. All operations are in time $\log n$.

Solution:

You keep the ordered derived list $F$ in a self-balancing binary tree. I checked with AVL trees, but other types (such as red-black trees) should work as well. In each node $N$ of the tree you keep a count $\text{weight}(N)$ of the number of elements of $F$ in the subtree rooted in $N$, node $N$ included.

This can be done by updating weight counts as you walk down from the root of the AVL tree for $F$ to reach the place for the insertion or deletion. Then, during the retracing phase that rebalances the tree, when needed, you also update the weight counts according to the rebalancing. That only add constant cost to each elementary step, thus does not change the $\log n$ time complexity of the algorithm.

Hence it is easy to use this weight to compute in $\log n$ time the index of an element of the list $F$ when accessing it, either on the way down from the AVL tree root, or by walking up to the root when accessing the element directly.

The index is computed on the fly by adding the weights of all the immediate siblings on the left of the path from the AVL tree root to the concerned element of $F$.

Conversely, it is easy to find in $\log n$ time an element of $F$ from its (left to right) index by walking down from the root and leaving enough elements on the left.

Computing the index of $S_i$ in $F$ using weights:

Recall that the weight of a node $N$ is the number of nodes in the subtree rooted at $N$, node $N$ included.

Computing the index of $S_i$ from the weights in the tree is precisely done as follows: you simply do a search for $S_i$ in the standard way of binary search trees, with a modification to compute the index. Below is a pseudo-code recursive version, adapted from the searching algorithm in wikipedia. It raises an exception if $S_i$ is not in the AVL tree, and the index count start at 0 for the first element. To have the count start at 1, the first return statement should be return node.left.weight+1.

function Find-recursive(S_i, node):  // call initially with node = root
    if node = Null then
        raise Key_Not_Found
    else if node.key = S_i then
        if node.left = Null then return 0
        else return node.left.weight
    else if key < node.key then
        return Find-recursive(key, node.left)
    else
        if node.left = Null then return Find-recursive(key, node.right)+1
        else return Find-recursive(key, node.right)+node.left.weight+1

When the path from the root goes to the right daughter, that means that all nodes in the left daugther subtree, plus the current node, precede $S_i$, and have to be added to whatever other predecessors will be found while searching in the right daughter subtree.

I do not give here the modifications of the insertion and deletion code necessary to update the weight count, as this is a bit too long for an answer here, and not so hard to do.

About the question, and the two proposed answers

The precise specification of the problem took some time to agree upon.

This first answer to the question was written on the basis of an initial specification that did not mention explicitly that the source list $S$ could be modified dynamically, by insertion or deletion, thus possibly inducing a similar modification in the filtered list $F$.

The elements of list $S$ are mutable objects and have a filter-property $P_F$ that may be true or false depending on operations performed on an element. The purpose of the question is to maintain a sublist $F$ of elements $s\in S$ such that $P_F(s)$, similarly ordered, such that the rank in $F$ of an element $s\in S$ is known when it in inserted in $F$ due to a mutation.

I assume in this first answer here that the list $S$ is constant, except for changes to its mutable elements. Thus on may see the list $S$ as a set (of list elements), totally ordered by the order of the list, and that relative order of two elements can be checked in constant time $O(1)$, for example by attaching its $S$-list rank to each element.

In a much later comment to this answer, the author of the question made it clear that he also wanted to be able to modify the list $S$ with insertion or deletion of elements. This more complex question is addressed separately in a second answer.

Why keep both answers? The first algorithm here is slightly more efficient as all operations can be performed in time $O(\log|F|)$, while the more general algorithm (second answer) requires time $O(\log|S|)$. With a constant ratio $|F|/|S|$, the difference is only an additive constant $\log|S|-\log|F|$. However this constant is to be compared to a logarithmic complexity $\log|F|$, which may not be very large itself. And this complexity is that of elementary operations on a data structure, to be repeated often in larger algorithms. So this apparently negligible difference may have a measurable impact on performance of a larger algorithm using the structure.

To see it numerically, assume that $|S|=256$ and $|F|=16$. Then $\log|S|=8$ and $\log|F|=4$, which give a performance ratio of $2$, to which one should add that the structure of the more general algorithm may be more costly to maintain.

$\endgroup$
  • $\begingroup$ You restated the problem very well. Think you could write out how the index is computed from the weight? If I beat you to it I'll just propose an edit--just probably best for a beta SE site to state everything in detail where possible. $\endgroup$ – ramblinjan Jun 11 '15 at 22:26
  • $\begingroup$ @jandjorgensen I have stuff to finish right now. If you want to give it a try. I wish the OP would react as it is not clear that he does not want more. $\endgroup$ – babou Jun 11 '15 at 22:54
  • $\begingroup$ I'm working with him on this--this is a good approach. $\endgroup$ – ramblinjan Jun 11 '15 at 22:58
  • $\begingroup$ I see. So talking to you or him is about same. Well, as you wish. I was waiting for reactions. It is too often the case that I do some time consuming work on a question and the poster never shows up again. What is important too is updating weight on insertion and deletion (if you change your mind about completion of a "todo"). $\endgroup$ – babou Jun 11 '15 at 23:05
  • $\begingroup$ I'm going to put in another answer using a RB-tree approach with pseudocode, unless you'd like to community wiki your post and I can organize it into a larger collaborative solution. $\endgroup$ – ramblinjan Jun 11 '15 at 23:07
1
$\begingroup$

What you're describing is a data structure for a set of integers with a rank operation. There are a number of published solutions with performance as good as O(1) on both queries and updates, for instance this recent paper.

These structures are fairly intricate, but generally they break the elements into blocks and maintain a summary rank for each block to use as a starting point. It's not much different from using a tree with leaf counts, but the space can be considerably smaller.

This blog post describes the basic ideas.

$\endgroup$
1
$\begingroup$

I have an answer that seems to work in O(log N x log N) time. However, I'm betting there's an answer in O(log N) time.

In short, I keep a T self-balancing tree that reflects the source list S. It keeps track of indexes using the "left count" approach @babou suggested. Every node also knows about its parent.

I also keep an F self-balancing tree that represents the filtered result, but with references to its symmetric nodes in T. This also uses "left count" on each node.

Together, it works as follows. Say S looks like:

S = [Z,b,c,e, f, G]

T might look like:

                   {v: c,LC: 2}
{v: Z, LC: 0}                      {v: f, LC: 1}
      {v: b, LC: 0}         {v: e, LC: 0}   {v: G, LC: 0}

where v is the value, LC is the left count.

And the output F would look like:

{v: Z, LC: 0, NR: Z}
     {v: G, LC: 0, NR: G}

where NR is a reference to it's parallel node in T. At this point, F has all the capitalized letters [Z, G] and we know the indexes of each.

Now lets see what happens if I insert D in-between c and e.

First, we know the index 3 at which this happens and can insert it into and rotate T accordingly. T will look like:

                        {v: D,LC: 3}
        {v: c,LC: 1}                    {v: f, LC: 1}
{v: Z, LC: 0}   {v: b, LC: 0}       {v: e, LC: 0}   {v: G, LC: 0}

Once T has been set, I can do a binary search and insert in F. I'd start at the root node {v: Z, LC: 0, NR: Z}, use the node reference to find the corresponding node in T and use the node in T to calculate the index in O(log n) time. I'd have to repeat this O(log n) times.

$\endgroup$
1
$\begingroup$

An $O(\log n)$ solution for dynamically changing source list

The problem

In a previous answer, I assumed that $S$ was a fixed list of elements, considered as a set ordered by the place of elements in the list. Only some property of the elements was supposed to be modifiable. The problem was to maintain another ordered list $F$ where elements of $S$, filtered for that property, could be inserted or removed, and such that the rank index of an element in $F$ was returned when the element was inserted.

Assuming the list to be fixed was essential because, by precomputing the rank index of each element in the list, if was possible to check the order of two elements in unit time $O(1)$ by comparing their ranks.

In a later comment, the poster of the question indicated that in addition to the stated specification of the problem, the list $S$ itself can be modified by insertion and deletion. Then there may no longer be a way to check the order of two elements in unit time. It is possible to maintain a rank index dynamically, as shown below, but computing it has a cost $O(\log|S|)$, so that the whole complexity of each operation is multiplied by that value, thus having a complexity $O(\log|F|\times\log|S|)$, or, to simplify in $O(\log^2 n)$ where $n=|S|$ is the size of the source list.

So I propose here a structure for implementing both lists $S$ and $F$ in such a way that:

  • the order in $S$ is preserved for both,

  • elements can be inserted or removed anywhere in $S$,

  • any element of $S$ that is modified to satisfy a property $P_F$ can be inserted in $F$, or removed if it no longer satisfies $P_F$,

  • for any element, it is possible to find its rank index in $S$ and in $F$

  • all operations being executed with a cost $O(\log |S|)$.

Furthermore the technique can be extended to handle simultaneously several lists $F_1, \ldots F_i\ldots$ each corresponding to a different property $P_i$.

Finally, I propose a technique to maintain a simple linked list of the elements in $F$, so that they can be listed in time $O(|F|)$ independently of the size of the source list $S$.

The base structure

The idea is to use a unique self-balancing binary search tree (BST) such as an AVL tree or a red-black tree). This tree is first used to implement the list $S$. This may seem strange as there is no a priori order to the elements of the list, and their order is determined only by arbitrary insertions and deletions. So the insertion procedure has to be changed, in a fairly trivial way, as you choose to insert a new node after some given node of the existing structure (inducing the order as a consequence, since there is none a priori) and rebalance the tree accordingly.

To every node $N$, you add a weight $W_S$ which is the number of elements of $S$ in the subtree rooted in $N$, actually the number of nodes of that subtree. This weight can be updated when inserting of deleting a node without changing the $O(\log |S|)$ cost of the operation. Furthermore, the weight can be used to compute the rank index of a node in $O(\log |S|)$ time, or to retrieve a node from its rank in the same time.

The rank index is computed on the fly by adding the weights of all the immediate siblings on the left of the path from the tree root to the concerned element of $S$. Their number is $O(\log |S|)$.

Conversely, it is easy to find in logn time an element of F from its (left to right) index by walking down from the root and leaving enough elements on the left.

Implmenting the list $F$

To implement the list $F$, one simply marks as such the nodes of the tree that contain an element of $F$. Actually they can be simply identified by testing he property $P_F$, when that test is cheap (i.e. at worst $O(1)$)

To be able to compute the index of an element in the list $F$, we add to each node $N$ a second weight $W_F$, which is the number of elements of $F$ in the subtree rooted in $N$. This weight is updated exactly like the previous one $W_S$. It is also used in the same way to get the index of a node in $F$ or to find a node in $F$ from its rank. There is a little subtlety in the latter, as, after leaving enough nodes on the left, we may have to search for the next subtree with a non zero weight $W_F$, since that weight can be zero for some nodes.

All this can be achieved in time $O(\log|S|)$ for each operation.

Enumerating $F$

If you want to enumerate in order all the elements of the list $F$, this can be done by enumerating the elements of $S$ by walking the tree, and filtering out those that are not in $F$. That take time $O(|S|)$.

But, it may be the case that the list $S$ is much larger than $F$, and it would be convenient to enumerate easily the elements of $F$ without this overhead, in time $O(|F|)$.

This can be done by maintaining in each node a link $L_F$, which is NIL if the node is not in $F$, or is the last node in $F$, and which points to the next node in $F$ when it is a node in $F$ other than the last one.

These pointers have to be maintained every time a node is inserted in $F$ or removed from it. But it is easily done in time $O(\log|S|)$ like other operations, thus not modifying the complexity. It is obviously possible since we can find the rank $r$ of a node $N$ inserted in $F$, and we can find the nodes preceeding and following $N$ from their rank $r-1$ and $r+1$, each in time $O(\log|S|)$. But there are faster ways to do it.

Using several filtered lists

The means for implementing the filtered list $F$ are built on top of the self-balancing binary search tree representing the list $S$, but they interfere in no way with the operations on that tree concerning $S$. Thus it is possible to implement in the same way as many filtered lists as may be needed, corresponding to different filtering predicate.

Note: The above sketches the algorithmic technique. Writing the whole thing is pseudo-code is far beyond what could be considered reasonable in a normal answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.