2
$\begingroup$

I am addressing an optimization problem involving a doubly linked list, where nodes are allocated within a contiguous memory block of fixed size $N$. Initially, the spatial locality of nodes in memory is not preserved, meaning that the next pointers of nodes might refer to any other node within the block.

The objective is to reorder the nodes such that for each node $i$, its successor node $j$ in the list is also its immediate successor in memory (i.e., memory[i] directly precedes memory[i + 1].

A trivial solution would involve traversing the linked list, storing the nodes in an auxiliary ordered container, and then copying them back into the memory block in order.

However, the goal is to reorder the nodes directly within the memory block, potentially using an auxiliary structure but performing the reordering through in-place swaps. Is such in-place reordering even feasible?

$\endgroup$

5 Answers 5

6
$\begingroup$

If you know all pointers to nodes, and you have enough free space for a single node, then you iterate through the nodes. For the I-th node, you copy the node stored at address I to the free space, copy the I-th node to address I, remember that the old location of the I-th node is now unused, and update all the pointers to those two nodes. You also need to check whether by coincidence the I-th node is already stored at address I; in that case you must do nothing for this node.

This takes time O(n), so massively faster than any O(n log n) sorting.

$\endgroup$
1
  • 1
    $\begingroup$ A way of breaking this idea done is to write a swap(t,i,j) function that swaps elements in t[i] and t[j] updating pointers accordingly to preserve the original linked list (which can be done since it is doubly linked)? Then just follow the list and when reading the ith element, get its index j (which can be done with some pointer arithmetic I guess) and call swap(t,i,j). $\endgroup$
    – holf
    Commented Jul 3 at 9:29
4
$\begingroup$

Take any in-place sorting algorithm and simply sort the nodes based on their next pointers.

$\endgroup$
3
  • $\begingroup$ Perhaps it's an under-specified question, but my interpretation is that the next pointer is to another position in the array. So every swap will involve changing the values you're sorting by, or breaking the links. This is not a complete solution. $\endgroup$ Commented Jul 3 at 19:44
  • $\begingroup$ An in-place sort is inefficient: you already know where each node belongs, so you can reorder in O(n) time, with just a single pass through the list. $\endgroup$
    – Mark
    Commented Jul 3 at 21:37
  • 2
    $\begingroup$ There’s the minor problem here that the sort key (the address of the node) changes throughout the sorting process. $\endgroup$
    – gnasher729
    Commented Jul 4 at 4:58
1
$\begingroup$

potentially using an auxiliary structure

The next and previous pointers of the double linked list can be used as the basis of the aux structure

Then after the reorder you update the pointers.

The most straightforward way would be selection sort where you don't need to search for the smallest (it's the next pointer of the last node) and on swap you update the pointers to the node you are moving out of the way:

int j = root - array[0];
array[0].prev->next = &array[j];
swap(array, 0, j);
for(int i = 1; i < array_len; i++) {
    int j = array[i-1].next - array[0];
    array[i].prev->next = &array[j];
    swap(array, i, j);
}
root = &array[0];
for(int i = 1; i < array_len; i++) {
    array[i-1].next = &array[i];
    array[i].prev = &array[i-1];
}

This is an O(n) operation.

$\endgroup$
1
$\begingroup$

O(n) but non-optimal:

You could just swap each node into the space it belongs as you traverse the list. Each swap will require 4 random accesses to the heap: Two read-writes for the nodes you're swapping, two writes to update the references on the prev and next nodes.

Better cache performance, with two passes:

Before you move anything, you know what the next/prev addresses will be as you traverse the list. So:

1: Traverse the nodes in list order, updating the next/prev of each node to its correct final address.

2: Traverse the space in memory order, with a pointer at the start of the block. Increment your pointer until you find another node in the wrong position (correct_address==prev+1==next-1). Otherwise, store a copy and mark the position in the list as deleted. Swap the stored copy with the one in its correct position, then swap the newly stored node with one in its correct position. Continue until you place a node in an empty position. Increment pointer and repeat.

Each node is updated once with its new address, then moved at most 1 time into its proper place. Each pass requires one random-access read-write per node. The second pass also includes a sequential read of the memory block as the pointer progresses, which could be significant if the list is much smaller than the block of memory it's in.

A further optimization to take advantage of existing sections of sequentially positioned nodes would be to store a small buffer - still small enough to keep in the stack - of multiple nodes instead of just one, and iterate through it, swapping contiguous chains of nodes, and replenishing any empty nodes that are swapped in from the pointer.

$\endgroup$
0
$\begingroup$

Inspired by @maybeWeCouldStealAVan, a one-pass algorithm. We're doing a forward pass through the list, so we don't try to keep node::prev up to date. We do need to keep node::next up to date as we swap values around

Let `Head` be the head of the list of unprocessed nodes (initially that's the whole list)
Let `N` be the number of nodes reordered so far (initially 0).
# This number is sufficient to define the list of processed nodes.
# The head of that list is memory[0], memory[x].next==x+nodesize,
# memory[x].prev==x-nodesize except for of course memory[0].prev==null.

To process one node, we 
* update memory[N].prev.next to Head
* swap memory[N].value and Head.value
* set memory[N].prev to N-nodesize and .next to N+nodesize 
* increment N
* set Head to Head.next

If it happens that Head=memory[N] at any given time, it means that that node is already in the right place. In that case, we could skip the value swap, but this is unlikely and the check is likely more expensive on average than the occasional unnecessary swap-with-self.

This involves O(N) read/writes in sequential order (cache-friendly) and O(N) random writes to move the remaining unordered values and keep their linked-list order. This will likely bottleneck on the random write speed, which is the fundamental architecture limit of this problem. To beat this, you have to be able to make assumptions about the list order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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