1
$\begingroup$

I have a sorted (by key) sequence of key value pairs:

< (1,"A"),(1,"C"),(1,"G"),(1,"B"),(2,"D"),(2,"F"),(3,"E") >

And I have to produce a sequence of tuples like this:

< (1,< "A","C","G","B" >),(2, <"D","F">),(3, <"E">) >

Where the second element of the tuple is a sequence with the values corresponding to the key.

I am working on haskell, under the hood I have a Seq that is a Vector, but a pseudocode solution is OK.

I have this algorithm that will run in parallel in $O(\lg n)$, but cost of work is too high (more than $O(n)$):

comb :: Seq s => ((a, s b) -> (a, s b) -> Bool) -> s (a, s b) -> s (a, s b) -> s (a, s b)
comb f sl sr | lengthS sr == 0 = sl
             | lengthS sl == 0 = sr
             | f (nthS sl ((lengthS sl) - 1)) (nthS sr 0) =  let 
                                                                 (cl, vl) = (nthS sl ((lengthS sl) - 1))
                                                                 (cr, vr) = (nthS sr 0)
                                                                 union = singletonS (cr, appendS vl vr)
                                                             in appendS (appendS (takeS ((lengthS sl) - 1) sl) union) (dropS 1 sr)
             | otherwise = appendS sl sr

groupDyC :: Seq s => ((a, s b) -> (a, s b) -> Bool) -> s (a, b) -> s (a, s b)
groupDyC f seq = reduceS (comb (f)) emptyS (mapS (\x -> singletonS x) (mapS (\(c, v) -> (c, singletonS v)) seq))

Where lengthA, nthS are $O(1)$ and appendS is linear to the size of both sequences.

My problem is that the solution has to have work in $O(n)$ and parallel cost (S) $O(lg n)$. How could I create an algorithm that runs on that cost with these operations:

enter image description here

Thank you very much.

$\endgroup$
2
  • $\begingroup$ What's your question? I don't see a question here. We are a question-and-answer site, so we ask you to articulate a specific question. Is there a reason to believe your requirements are achievable? Did you see this question asked somewhere as an exercise, for example? What's the computation model? Can we index into the sequence in $O(1)$ time? Please note that coding questions are off-topic here, so asking us for a solution in Haskell is out of scope for this site, but if you're asking about general algorithms, that is on-topic here. $\endgroup$
    – D.W.
    Jul 2 '21 at 8:02
  • $\begingroup$ @D.W. I tried my best to create a question that is more easily answered. Is the question now ok? $\endgroup$ Jul 2 '21 at 17:13
1
$\begingroup$

Since the input is sorted, the elements are essentially already grouped, you just need to find the "boundaries" between the groups. By boundary, I mean the index where a run of the same key starts.

You can find the boundaries by filtering the indices where adjacent keys don't match. For example on input < (1,"A"),(1,"C"),(1,"G"),(1,"B"),(2,"D"),(2,"F"),(3,"E") > the boundary indices are 0, 4, and 6.

The boundary indices tell you how big each group is (by subtracting adjacent boundaries). Now, you just have to construct the output groups. For each group, do a tabulate, where you offset the index by the boundary. Specifically, the $i$th element of the $j$th group is input[boundary[j] + i].

In total, that's $O(n)$ work for the filter and maps/tabulates. The parallel time is dominated by the filter, costing $O(\log n)$.

$\endgroup$
2
  • $\begingroup$ how do I find the boundry in $O(1)$ if I have to check every entry until I find the entry where the keys didn't match? In other words, if the entire list has a single key, does the algorithm run in parallel in O(log n)? $\endgroup$ Jul 15 '21 at 0:43
  • 1
    $\begingroup$ Yes, the whole algorithm runs in O(log n) parallel time, where n is number of input pairs. Finding the boundaries takes O(1) parallel time: in parallel for each i, if element at i is different from at i-1, then it is a boundary. And then you can filter out the non-boundaries in O(log n) parallel time. $\endgroup$ Jul 15 '21 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.