[R] Seeking a more efficient way to find partition maxima

[Talbot Katz]

Hi Marc.

Thank you for the swift response!  I should have explained more about the partitions, I hoped it would be clear from the code.  I am supplying an index vector to create the partitions.  In my original example of v = c(1,4,2,6,7,5) with v1 = v[1:3], v2 = v[4], v3 = v[5:6], I would specify this partition with the index vector c(1,4,5), giving the first indices of each subvector; the implicit assumption is that the last index of partition i is the first index of partition (i + 1) minus 1, except for the last partition, which ends at the end of the original vector being partitioned.  Here are the results of this example from the two functions I defined:

> partiCmax(c(1,4,2,6,7,5),c(1,4,5))
[1] 4 6 7
> partiMax(c(1,4,2,6,7,5),c(1,4,5))
[1] 4 6 7
>


However, if I use an example in which the maxima are not non-decreasing:

> partiCmax(6:1,c(1,4,5))
[1] 6 6 6
> partiMax(6:1,c(1,4,5))
[1] 6 3 2
>

partiMax gives the sought result, but partiCmax doesn't.  Your function is like a cleaner version of partiMax, using the fact that you have the partition in a list.  This begs the question of what is the most efficient way to create the partition list from the original vector and the index vector that specifies the partition.  But I am also wondering whether we can find something even more efficient than the use of the apply family of functions.  Thanks!


--  TMK  --
212-460-5430	home
917-656-5351	cell
t o p k a t z @ m s n . c o m



> Date: Mon, 7 Jan 2008 10:44:20 -0600
> From: marc_schwartz at comcast.net
> To: topkatz at msn.com
> CC: r-help at stat.math.ethz.ch
> Subject: Re: [R] Seeking a more efficient way to find partition maxima
>
> Talbot Katz wrote:
>> Hi.
>>
>> Suppose I have a vector that I partition into disjoint, contiguous
>> subvectors. For example, let v = c(1,4,2,6,7,5), partition it into
>> three subvectors, v1 = v[1:3], v2 = v[4], v3 = v[5:6]. I want to
>> find the maximum element of each subvector. In this example, max(v1)
>> is 4, max(v2) is 6, max(v3) is 7. If I knew that the successive
>> subvector maxima would never decrease, as in the example, I could do
>> the following:
>>
>> partiCmax <- function( values, seriesIdx ) { # assume seriesIdx is
>> increasing integer sequence beginning with 1, ending at less than or
>> equal to length(values) parti <- cbind( seriesIdx, c( ( seriesIdx[ -1
>> ] - 1 ), length( values ) ) ) return( cummax( values )[ parti[ , 2 ]
>> ] ) }
>>
>>
>> The use of cummax makes that pretty efficient, but if the subvector
>> maxima are not non-decreasing, it doesn't work. The following
>> function works (at least it did on the examples I tried):
>>
>> partiMax <- function( values, seriesIdx ) { # assume seriesIdx is
>> increasing integer sequence beginning with 1, ending at less than or
>> equal to length(values) parti <- cbind( seriesIdx, c( ( seriesIdx[ -1
>> ] - 1 ), length( values ) ) ) return( sapply( ( 1:length(seriesIdx)
>> ), function ( i ) {return( max( values[ parti[ i, 1 ]:parti[ i, 2 ] ]
>> ) ) } ) ) }
>>
>>
>> but I figured someone out there could come up with something
>> cleverer. Thanks!
>
> It is not clear how you are creating the partitions, but if you are
> (hopefully) ending up with a list, such as:
>
>> Vec.List
> $v1
> [1] 1 4 2
>
> $v2
> [1] 6
>
> $v3
> [1] 7 5
>
>
> Then you can use:
>
>> sapply(Vec.List, max, na.rm = TRUE)
> v1 v2 v3
> 4 6 7
>
>
> See ?sapply for more information.
>
> HTH,
>
> Marc Schwartz
>