sourabhforu
BAN USEROk. But my overall algorithm seems to be O(kn). Which looks better than O(k*n*logn). Isnt it?
- sourabhforu September 15, 2013I dont understand why people are bent on using a heap here?
Wouldn't it be more efficient to just keep track of the current ptr (named curPtr) in each of the K lists.
1.) All the K curptr are initialized to 0. We find the minimum element from the set of K elements formed by (list1[curPtr1], list2[curptr2], etc)
2.) We output the corresponding minimum element and hence increase the corresponding curPtr
3.) We need to make sure that once the curPtr for some list reaches the "n" we ignore it in the next iteration
4.) Since we will output one element in each iteration. The function will run in O(K*n) time.
Maybe I have missed something or committed some grave blunder. So, please feel free to comment.
UPDATE: Here is some quick code:
int _tmain(int argc, _TCHAR* argv[])
{
int k, n, mat[100][100];
printf("Enter K:");
scanf("%d", &k);
printf("Enter N:");
scanf("%d", &n);
for(int i = 0; i < k; i++)
{
for(int j = 0; j < n; j++)
{
scanf("%d", &(mat[i][j]));
}
}
int ptr[100], min = 0, index;
int done = 0;
for(int i = 0; i < k; i++)
{
ptr[i] = 0;
}
index = 0;
for(int i = 0; done == 0; i++)
{
min = mat[index][ptr[index]];
for(int j = 0; j < k; j++)
{
if ((ptr[j] < n) && (min > mat[j][ptr[j]]))
{
min = mat[j][ptr[j]];
index = j;
}
}
printf("%d\n", min);
ptr[index]++;
done = 1;
for(int j = 0; j < k; j++)
{
if (ptr[j] < n)
{
done = 0;
index = j;
break;
}
}
}
return 0;
}
This will result in a deadlock:-
1.) Assume Reader R1 and Writer W1 are blocked on while(wcount) spinlock while W0 is writing data in the structure. (I am assuming that you have a typo in the function init_read, where you actually meant to write "while(wcount)")
2.) As soon as W0 leaves, either W1 or R1 will get chance to exit the spin lock. Assume that W1 gets out first.
3.) Now, W1 will get blocked on while(rcount) since R1 has already taken this rcount++ when it entered the read
4.) R1 can never leave and decrement rcount since W1 is holding the writer's lock.
A possible solution I can think of is- modify init_read() and exchange the order of while(wcount_ and rcount++. Also make sure that they are executed atomically as a group.
As always, feel free to comment and point out any issues or mistakes I have done. Thanks in advance!
Ohh! I got it! I was confused by the other comments that the particular algo being discussed was O(K *n * Logn). Thanks!
- sourabhforu September 15, 2013