Mapping a list of lists containing index numbers to a standard index sequence after subsetting

user_3132960 0
Viewed 50

I'm working with a data structure that is stratified into by three levels. For example, suppose my structure D is

First  Second  Third  Value  Index (let's do 1-indexing)
    1       1      1      a      1
    1       1      2      a      2
    1       1      3      a      3
    1       2      1      a      4
    1       2      2      a      5
    2       1      1      a      6
    2       1      2      a      7

I formed a nested list structure to index components corresponding to each grouping structure:

[[1]]
[[1]][[1]]
1 2 3
[[1]][[2]]
4 5 

[[2]]
[[2]][[1]]
6 7

In reality, my structure D is enormous, and in my context I will perform operations on random subsets of D. The way I'm doing the random subsetting is stratified sampling of each of the different levels. For example, suppose the first level contains 1:1000, the second is 1:100, the third containing 1:50. I may subsample 50 of the first-level identifiers, 10 of the second-level identifiers, and 3 of the third-level identifiers, which may give me something like (call the below nested structure A)

[[1]]
[[1]][[1]]
2 27 49
[[1]][[2]]
61 80 95

....

[[1]][[10]]
2409  3509   5609

[[2]]
[[2]][[1]]
7092 8091 9039

...

After subsetting based on the above indices, say now with structure D', the indices for D' are no longer the above, but rather (call the below nested structure A')

[[1]]
[[1]][[1]]
1 2 3
[[1]][[2]]
4 5 6

....

[[1]][[10]]
28 29 30

[[2]]
[[2]][[1]]
31 32 33

...

What is the most efficient way to map A to A'? It would be nice for this to be efficient, since it appears I'll be doing this operation many times and could be a rate-limiting step in my entire program. I'm currently using Rcpp (C++) and it may be possible some subsets are smaller than the require sampling number (for example, some second-level indices could be less than 10, say 7, in which case we just take all 7 labels).

rcpp list c++
1 Answers

Before going straight to Rcpp I would encourage you to think about how we could do this in base R. List, subsetting, and indexing are the bread and butter of base R and can be quite efficient.

Below, we have a solution that attacks your problem. You will note, it could probably be more efficient, but for now, this is very straightforward approach and is easy to understand. We will test the efficiency later and address any concerns then.

A_prime <- function(A) {
    ## Generate index vector for all of A
    ind <- seq_len(sum(unlist(lapply(A, lengths))))
    
    ## Generate the ending index of each vector
    endInd <- cumsum(lengths(unlist(A, recursive = F)))
    
    ## Use the endInd to create the corresponding start index
    startInd <- c(1L, endInd[-length(endInd)] + 1L)
    
    ## Create a simple list with the appropriate index vector
    A_ind <- mapply(function(s, e) ind[s:e], startInd, endInd, SIMPLIFY = FALSE)
    
    ## Again, using the structure of A, we begin creating starting
    ## and ending indices to replicate the structure of A
    A_end <- cumsum(lengths(A))
    A_strt <- c(1L, A_end[-length(A_end)] + 1L)
    
    ## Create the desired result
    lapply(seq_along(A), function(x) A_ind[A_strt[x]:A_end[x]])
}

Let's test it on a similar problem that the OP has presented:

set.seed(35)
a <- sort(sample(10000, 60))

L1 <- lapply(seq.int(1, 60, 3), function(x) {
    a[x:(x + 2)]
})

A <- list(L1[1:10], L1[11:20])

str(A)
List of 2
$ :List of 10
..$ : int [1:3] 4 203 205
..$ : int [1:3] 710 1281 1515
..$ : int [1:3] 1605 1784 1846
..$ : int [1:3] 1904 1993 2425
..$ : int [1:3] 2468 2499 2630
..$ : int [1:3] 2910 2920 3210
..$ : int [1:3] 3360 3464 3469
..$ : int [1:3] 3689 3811 4002
..$ : int [1:3] 4053 4304 4358
..$ : int [1:3] 4433 5290 5862
$ :List of 10
..$ : int [1:3] 6017 6021 6155
..$ : int [1:3] 6250 6370 6414
..$ : int [1:3] 6447 6530 6656
..$ : int [1:3] 6706 6820 6977
..$ : int [1:3] 6986 7148 7338
..$ : int [1:3] 7515 7522 7666
..$ : int [1:3] 7755 7889 7891
..$ : int [1:3] 8071 8143 8487
..$ : int [1:3] 8625 8731 8945
..$ : int [1:3] 8957 9149 9770

And here is the output:

str(A_prime(A))
List of 2
$ :List of 10
..$ : int [1:3] 1 2 3
..$ : int [1:3] 4 5 6
..$ : int [1:3] 7 8 9
..$ : int [1:3] 10 11 12
..$ : int [1:3] 13 14 15
..$ : int [1:3] 16 17 18
..$ : int [1:3] 19 20 21
..$ : int [1:3] 22 23 24
..$ : int [1:3] 25 26 27
..$ : int [1:3] 28 29 30
$ :List of 10
..$ : int [1:3] 31 32 33
..$ : int [1:3] 34 35 36
..$ : int [1:3] 37 38 39
..$ : int [1:3] 40 41 42
..$ : int [1:3] 43 44 45
..$ : int [1:3] 46 47 48
..$ : int [1:3] 49 50 51
..$ : int [1:3] 52 53 54
..$ : int [1:3] 55 56 57
..$ : int [1:3] 58 59 60

That looks pretty good! A benefit of the function A_prime is that the nested list need not be uniform. Let's test this on a very large list with over 10Mb of data:

set.seed(123)
big_ind <- sort(sample(1e8, 1e6))

## generate random chunks
endIndBig <- sort(sample(1e6, 1e5))
startIndBig <- c(1L, endIndBig)
endIndBig <- c(endIndBig, 1e6)

A_big_init <- mapply(function(s, e) big_ind[s:e], startIndBig, endIndBig, SIMPLIFY = FALSE)

## generate random chunks for nested lists
A_big_ends <- sort(sample(length(A_big_init), 1e3))
A_big_strts <- c(1L, A_big_ends)
A_big_ends <- c(A_big_ends, length(A_big_init))

A_big <- lapply(seq_along(A_big_ends), function(x) A_big_init[A_big_strts[x]:A_big_ends[x]])

Here is some summary information on A_big. As you can see the length of each sub list is not uniform:

print(object.size(A_big), units = "Mb")
# 10.7 Mb

length(A_big)
# [1] 1001

head(lengths(A_big))
# [1] 159 175  59  69 175  38

tail(lengths(A_big))
# [1]  88   4 225  91  74  59

A_big[[1]][[1]]
# [1]    3   72  722  836  929 1014 1091 1127

A_big[[1]][[159]]
# [1] 170285 170370 170482 170763 170793 170913 170965 171066 171240 171397 171464 171572 171590 171722
# [15] 171898 171903 172196 172284 172298 172590 172696 172698

A_big[[1000]][[2]]
# [1] 99856337 99856415

A_big[[1000]][[74]]
# [1] 99938669 99938699 99938743 99939158 99939664 99939803

Now, for the moment of truth...

system.time(A_prime(A_big))
   user  system elapsed 
  0.201   0.003   0.203

A_big_prime <- A_prime(A_big)

A_big_prime[[1]][[1]]
# [1] 1 2 3 4 5 6 7 8

A_big_prime[[1]][[159]]
# [1] 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898
# [21] 1899 1900

A_big_prime[[1000]][[2]]
# [1] 1109671 1109672

A_big_prime[[1000]][[74]]
# [1] 1110583 1110584 1110585 1110586 1110587 1110588

That's not bad!!! As we can see, the mapping was performed correctly and quickly all with base R.

user_44085380
Related