CODEWITHSUNDEEP
arraysalgorithmsorting
Farveaz
Farveaz

Reputation: 608

Algorithm to find 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 quickest algorithm to group all the 0s and represent them as their starting and ending index?

(ie) Output of this should be (0,5),(10,17)...

Upvotes: 4

Views: 414

Answers (3)

dotNET
dotNET

Reputation: 35400

Let me write multithreaded approach in pseudo-code form:

Function ZeroHunter()
  Split the array into N segments (where N is multiple of number of threads available)
  Create a Dictionary<SegmentNumber, Result>. Let's 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

Thing to note is that while this algorithm will beat non-threaded algorithms for very large arrays, you should not use it for smaller arrays because the overhead of creating threads and joining the results will outweigh the potential benefit of threading.

Upvotes: 0

Kishan Oza
Kishan Oza

Reputation: 1735

try this buddy...!! hope its fine :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);
     }    
}
}

Upvotes: 0

Kaidul
Kaidul

Reputation: 15875

Pseudo-code will 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 is O(n) where n is array length. Space complexity is constant.

Upvotes: 1

Related Questions