CODEWITHSUNDEEP
arraysalgorithm
Goatt
Goatt

Reputation: 121

Array Moves Chunks Of Neighboring Elements To A New Index

The Question

The question is simple, Imagine I have a list or an array (not linkedList)

list = [1, 2, ... 999999]

Now I wanna move elements from index 3000 to 600000 to index 100. The result should be easy to imagine

[1, 2,... 99, 100, 3000, 3001, ... 6000000, 101, 102, ...2999, 600001, 600002, ... 999999]

How to do those operations efficiently?

Judge My Thinking

Disclaimer: You can say this operation is exactly same as moving 101 to 2999 to index 600000. Which seems a more efficient operation. But that's not the algorithm my question is about, my question is about how to move more efficiently, so let's do the original question.

I can think of several ways:

  1. Just do delete and insert for element 3000 to 600000. (What's the time complexity?)
  2. Save elements from [3000, 600000] to a temporary space, then use delete insert to move everything from [101 to 2999] down to [597192, 600000] to make space to transfer [3000, 600000] back into index 100. Temporary holding data from [3000, 600000] will cost some memory, but does the copying make the whole operation slower? (Time complexity?)
  3. is an attempt to improve 2. Same idea, but the move operation is not done by delete insert, but by manually copy [101,2999] to [597192, 600000]. (Time complexity? does it improve speed compared to delete insert)?
  4. is an attempt to improve 2 or 3. Same idea, but no delete insert, but using many copying. But not copying everything from [3000, 600000], but only hold 1 element at a time in temporary memory, and move / copy everything in a complicated way. (Is this faster than others? Is it possible to implement? Can you show me the code / pseudo-code)

Is there better ideas?

Thank you for reading and thinking.

Upvotes: 1

Views: 126

Answers (3)

user58697
user58697

Reputation: 7923

The algorithm you are after is known as rotate. There are two common ways to implement it. Both are running in O(length) time and O(1) space.

One, which is attributed to Dijkstra, is ultimately efficient in a sense that every element is moved just once. It is kind of tricky to implement, and requires a non-obvious setup. Besides, it may behave in a very cache-unfriendly manner. For details, see METHOD 3 (A Juggling Algorithm).

Another is very simple, cache-friendly, but moves each element twice. To rotate a range [l, r) around a midpoint m do

    reverse(l, m);
    reverse(m, r);
    reverse(l, r);

Upvotes: 2

Chad
Chad

Reputation: 23

Let [l, r] be the segment you want to move, and L = r-l+1, the length of segment. N is total count of elements.

  1. Delete and Insert at arbitrary position in array takes O(N), and delete and insert occurs O(L). So total time complexity is O(NL).

  2. Same as #1. It takes O(NL) because of delete and insert.

3, 4. Copy and move takes O(L). Simply we can say it takes O(N)

Now, some fancy data structure for better complexity. You can use tree data structure to store linear array. Especially, self-balancing binary search tree(BBST). It takes O(logN) to insert and delete one element. Time complexity of moving segment to arbitrary position could be O(L logN), delete and insert each element. You can find this data strcuture std::map in C++.

O(L logN) does not seem to be better. But, it can be better with BBST, to amortized O(log N) You can gather elements in [l, r] to one subtree. Then cut this subtree from BBST. It is delete. Insert this subtree at position you want. For example, gather [3000, 600000] to one subtree and cut it from its parent. (Delete segment at once) Make this subtree right child of 100th element in inorder, or left child of 101th element in inorder. (Insert segment at once) Then, tree contains elements in order what you want.

Splay Tree would be good choice.

Upvotes: 1

Jan Christoph Terasa
Jan Christoph Terasa

Reputation: 5935

I split the list at the "breakpoints", and reassembled the pieces. Creating a slice should be O(n), with n being the length of the slice. The longest slice is up to len(a) elements, so the storing of the list pieces should be O(n), with n being len(a). Reassembling the list pieces is O(n) as well, so this should be O(n) in total. The memory requirement is 2*len(a), since we store the slices as well, which sum up to the same length as a.

def truck(a, start, end, to):
    a = list(a)

    diff = end - start
    to_left = to < start
    
    split_save = a[to:to+diff]
    split_take = a[start:end]
    
    if to_left:
        split_first = a[:to]
        split_second = a[to+diff:start]
        split_third = a[end:]
        res = split_first + split_take + split_second + split_save + split_third
    else:
        split_first = a[:start]
        split_second = a[end:to]
        split_third = a[to+diff:]
        res = split_first + split_save + split_second + split_take + split_third
        
    return res

print(truck(range(10), 5, 8, 2))
# [0, 1, 5, 6, 7, 2, 3, 4, 8, 9]
print(truck(range(10), 2, 5, 8))
# [0, 1, 8, 9, 5, 6, 7, 2, 3, 4]

Upvotes: 1

Related Questions