Best Algorithm

[rachitagrawal]

I have a following kind of data(~10^10) in a file

<instruction num> <Memory address accessed>

Data are in ascending order of instruction num in the file.

I want to know the median of difference of instruction num..

For e.g.

1 100
2 345
3 100
4 342
5 645
6 100
7 345

for address 100 -> difference of instruction num are: (3-1), (6-3) = 2, 3 ->median = 2.5
for address 100 -> difference of instruction num are: (7-2) = 5 ->median = 5

So, the overall median is = median{median(100), median(345)} = 3.75
This has to be done for all possible address.

At the same time, number of unique addresses accessed between two access of an address is to be found.

For e.g. in this case
for address 100 -> unique address accessed are:1, 2 ->median = 1.5
for address 345 -> unique address accessed are: 3 -> median = 3

overall median = 2.25.

The way I have done is taking a huge amount of time and huge amount of time. Can someone tell me a better way to do it?