Janusz Waligóra Janusz Waligóra - 19 days ago 8
C Question

Random access cyclical data structure with two defined operations

As input I recive a list of natural integers.
I have to store them inside a structure that enables me to go from the last element to the first without much problem.

The task is to perform t (number given from the start) operations on this data structure. Starting from the first number given as input (i=0):

If data[i] % 2 == 0 -> perform operation R

else -> perform operation X

operation R: remove element with index position i+1, and move to the right as many times as was the value of removed element.

operation X: take the value of data[i] element and insert new element in front of that one with value data[i]-1. Then move data[i] times to the right.

example (i->n means that i points to el. with value n):

input: 3 1 2 3

t = 3

data = [ 1, 2, 3 ]

1.
i->1
operation X,
result: [ 1, 0, 2, 3 ]

2.
i->0
operation R,
result: [ 1, 0, 3 ]

3.
i->1
operation X,
result: [ 1, 0, 0, 3 ]


The real problem occurs when the value of t is very large.
I tried two implementations:


  • One based on linked list. I know it works because the result is correct, but execution time is close to 2-3 minutes.

  • One based on an array but the execution time is just a little faster.



Here is the fragment that takes 99,99% of execution time:

while(t--){
c = current -> value;
if(c % 2 == 0){
c = current -> next -> value;
Node* n = current -> next -> next;
free(current -> next);
current -> next = n;

--size;
}
else{
Node* n = getNode(current -> next);
current -> next = n;
n -> value = c-1;

++size;
}

c %= size;
while(c--){
current = current->next;
}
}


getNode(Node* n) returnes new node with node -> next = n.

Any insight into optimalization method/ other approach appreciated.

*edit:

Node* getNode(Node* nxt){
Node* first = (Node*)malloc(sizeof(Node));
first -> value = -1;
first -> next = nxt;
return first;
}

Answer

Thinking in terms of the algorithm run-time (where n is the length of elements):

  • You need t operations, so outside loop is O(n)
  • If you use linked lists, finding ith element is O(n) and moving the ith element around is Theta(1) as you are just changing the pointers making your inner while loop O(n) so total runtime of O(n^2)
  • With array, finding ith element is Theta(1) but moving them around is O(n), so inner loop is again O(n), total being O(n^2)

Can you use a hashmap with integer index as the key and value working as if it's a linked list? Hashmaps will make both the search and move Theta(1) making the total O(n)