The problem

I have been playing with one of my toy projects and ended up having to shuffle text many times in a file that is around 10MB long. A naïve implementation chopping a string and gluing it together again ended up being painfully slow:

where n is the length of the string and k is the number of shuffling operations.

A solution

It turns out that the problem can be efficiently solved using splay trees, where each node holds:

• the starting offset in the source string
• the length of the substring it represents
• the offset from the beginning of the substring taking into account all of the children on the left-hand-side
• total length of the substring taking into account all the children on the right-hand side

The find operation looks for a node containing the offset and splits it in two, if the node does not start with the offset.

 1static Node *Find(uint32_t offset, Node *root)
 2{
 3  if(!root)
 4    return 0;
 5  if(offset >= root->offset && offset < (root->offset + root->length))
 6    return root;
 7  if(offset < root->offset)
 8    return Find(offset, root->left);
 9  return Find(offset-root->offset-root->length, root->right);
10}
11
12static Node *STFind(uint32_t offset, Node *root)
13{
14  Node *n = Find(offset, root);
15  Splay(n);
16
17  if(n->offset < offset) {
18    Node *newNode = new Node();
19    newNode->start  = n->start;
20    newNode->length = offset - n->offset;
21    n->start  = newNode->start + newNode->length;
22    n->length -= newNode->length;
23    newNode->left = n->left;
24    update(newNode);
25    n->left = newNode;
26    update(n);
27  }
28  return n;
29}

The actual shuffling boils down to splitting and merging sub-trees and producing the result to traversing the whole tree in-order.

 1void process(int i, int j, int k)
 2{
 3  Node *n, *t, *left, *right = 0;
 4  STSplit(left, n, i, pRoot);
 5  if(j+1 < pS.length())
 6    STSplit(n, right, j+1-i, n);
 7  t = STMerge(left, right);
 8  if(k < (t->offset + t->total_length))
 9    STSplit(left, right, k, t);
10  else {
11    right = 0;
12    left = t;
13  }
14  pRoot = STMerge(left, n);
15  pRoot = STMerge(pRoot, right);
16}

The amortized complexity is:

See rope-splay.cpp.

A test

It all runs pretty nicely for a test case with 10M characters and 100k shuffle operations:

]==> ./testgen 10000000 100000 > test
]==> time ./rope-naive < test > test-o-naive
./rope-naive < test > test-o-naive  386.17s user 66.19s system 99% cpu 7:32.86 total
]==> time ./rope-splay < test > test-o-splay
./rope-splay < test > test-o-splay  0.71s user 0.04s system 99% cpu 0.752 total
]==> diff test-o-splay test-o-naive