Algorithm for finding a range of data in an array
Given an array
$array = [ 0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0];
What is the fastest algorithm for grouping all 0s and representing them as their start and end indices?
(i.e. the output of this should be (0.5), (10.17) ...
The pseudocode would be something like this:
for(int i = 0; i < array.length; i++) {
if(array[i] == 0) {
int left = i;
while(i + 1 < array.length && array[i + 1] == 0) {
i++;
}
// print range [left, i]
}
}
Time complexity O(n)
, where n
is the length of the array. The complexity of space is constant.
Let me write a multi-threaded approach in pseudocode form:
Function ZeroHunter()
Split the array into N segments (where N is multiple of number of threads available)
Create a Dictionary<SegmentNumber, Result>. Let call it DicResults.
For i = 0 to Number of segments
Result = ProcessSegmentOnNewThread(S)
DicResults.Add(i, Result)
Next
Wait for all threads to complete
ConcatResults(DicResults)
End Function
Code for ProcessSegmentOnNewThread:
Function ProcessSegmentOnNewThread(Segment S)
Create a new thread
List<int, int> lst;
while i < S.Length
if S[i] == 0 Then
NewEntry = lst.Add(i, i)
while i < S.Length and S[i] == 0
NewEntry.End++;
i++
end while
end if
i++
end while
Return the results in the form of List<int, int>
End Function
Code for ConcatResults ():
Function ConcatResults(DicResults)
Sort the input dictionary on segment number (the dictionary key that is)
For i = 0 to DicResults.Count - 1
If DicResult[i].End = DicResult[i+1].Start - 1
Set DicResult[i].End = DicResult[i+1].End
Remove DicResult[i+1] from the dictionary
End If
Next
Return DicResult
End Function
It should be noted that while this algorithm will beat non-streaming algorithms for very large arrays, you shouldn't use it for smaller arrays because the overhead of creating streams and combining the results will outweigh the potential benefit of streaming.
try this buddy ... !! hope it works well: D
#include <stdio.h>
int main()
{
int a[12] = {0,0,0,0,1,1,1,1,0,0,0,0};
int i;
int t = 0;
for( i = 0; i < (int)( sizeof(a) / sizeof(a[0])); i++) {
if(a[i] == t) {
int k = i;
while(i + 1 < (int)( sizeof(a) / sizeof(a[0])) && a[i + 1] == 0) {
i++;
}
printf("range(%d,%d)\n",k,i);
}
}
}