POSIXct 列表的列表列表中的高内存消耗
High memory consumption in unlist of list-of-lists of POSIXct
我有大约 500-2000 个 POSIXct 日期列表，列表如下所示：
ts <- lapply(c(1:500), function(x) seq(as.POSIXct("2000/1/1"), as.POSIXct("2017/1/1"), "hours"))
我需要一个唯一日期列表。我尝试了几件事：
t <- unique(do.call("c", ts))
这保留了 POSIXct class，但需要很长时间并使用 7-8GB 内存；尽管他的整个列表列表大约有 500MB。
t <- as.POSIXct(unique(unlist(ts, use.names = FALSE)), origin = "1970-01-01")
虽然消耗的内存大致相同，但速度要快得多。所以我试着把它和这个分开：
t <- lapply(split(ts, ceiling(seq_along(ts)/30)), function(x) {
return(unique(unlist(x, use.names = FALSE)))
})
t <- unique(unlist(x, use.names = FALSE))
相同的消耗，在我看来，内存来自 unlist() 或 unique() 调用 "small" 列表之一。
有没有办法实现这种内存效率？处理时间很重要，但只是一点点。如果列表大小加倍（这很可能），这可能会导致严重的问题。
unique(do.call("c", ts)) 调用在我的机器上使用了 < 4GB (3869.9 - 606 ~ 3GB) 的内存。 ts 对象是 568MB。
R> ts <- lapply(c(1:500), function(x) seq(as.POSIXct("2000/1/1"), as.POSIXct("2017/1/1"), "hours"))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221687 11.9 460000 24.6 392929 21
Vcells 74925836 571.7 112760349 860.3 79427802 606
R> t <- unique(do.call("c", ts))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221729 11.9 460000 24.6 392929 21.0
Vcells 75074953 572.8 413082177 3151.6 507227169 3869.9
R> print(object.size(ts), units="MB")
568.8 Mb
R> sessionInfo()
R version 3.3.2 (2016-10-31)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 14.04.5 LTS
locale:
[1] LC_CTYPE=en_US.UTF-8 LC_NUMERIC=C LC_TIME=en_US.UTF-8 LC_COLLATE=en_US.UTF-8
[5] LC_MONETARY=en_US.UTF-8 LC_MESSAGES=en_US.UTF-8 LC_PAPER=en_US.UTF-8 LC_NAME=C
[9] LC_ADDRESS=C LC_TELEPHONE=C LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C
attached base packages:
[1] stats graphics grDevices utils datasets methods base
设置 recursive = FALSE 和 use.names = FALSE 使其更快并将内存消耗降低到 ~2GB。
R> ts <- lapply(1:500, function(x) seq(as.POSIXct("2000-01-01"), as.POSIXct("2017-01-01"), "hours"))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221686 11.9 460000 24.6 371201 19.9
Vcells 74925836 571.7 111681359 852.1 80924280 617.5
R> u <- do.call("c", c(ts, recursive = FALSE, use.names = FALSE))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221725 11.9 460000 24.6 371201 19.9
Vcells 149446409 1140.2 413082872 3151.6 373009943 2845.9
使用具有相同参数的 unlist 在内存消耗上稍微轻一些：
R> ts <- lapply(1:500, function(x) seq(as.POSIXct("2000-01-01"), as.POSIXct("2017-01-01"), "hours"))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221686 11.9 460000 24.6 371201 19.9
Vcells 74925836 571.7 111681359 852.1 80924280 617.5
R> u <- .POSIXct(unlist(ts, recursive = FALSE, use.names = FALSE))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221695 11.9 460000 24.6 371201 19.9
Vcells 149446337 1140.2 358453576 2734.8 298487368 2277.3
加上，可以看到内存消耗只有可怜的230MB：
R> ts <- lapply(c(1:500), function(x) seq(as.POSIXct("2000/1/1"), as.POSIXct("2017/1/1"), "hours"))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 218429 11.7 460000 24.6 389555 20.9
Vcells 74922694 571.7 111432506 850.2 81226910 619.8
R> u <- Reduce(function(x, y) unique(c(x, y)), ts)
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 218893 11.7 460000 24.6 389555 20.9
Vcells 75072416 572.8 111432506 850.2 111399894 850.0
而不是用 do.call(c, .)/unlist(.) 和单个大哈希 table 创建一个大向量，如 Joshua 的回答所示，它具有高内存使用率，我们可以遵循较少的迭代处理 "ts" 的时间高效但内存效率更高的方式：
ff1 = function(x) ## a simple version of `Reduce(unique(c()), )`
{
ans = NULL
for(elt in x) ans = unique(c(ans, elt))
return(.POSIXct(ans))
}
system.time({ ans1 = ff1(ts) })
# user system elapsed
# 11.41 1.25 12.74
"ts" 具有相同的元素。虽然这种理想情况通常并非如此，但如果可能的话，我们可以尽量避免一些连接：
ff2 = function(x)
{
ans = NULL
for(elt in x) {
new = !(elt %in% ans)
if(any(new)) ans = c(ans, elt[new])
}
return(.POSIXct(ans))
}
system.time({ ans2 = ff2(ts) })
# user system elapsed
# 6.65 1.12 7.93
同样，fastmatch 包有一个非常有趣但不幸的是，它没有导出，我们可以在这里尝试使用的高级哈希 table 功能。它还应该减少内存消耗。
首先定义一些方便的包装器：
HASH = function(x, size) fastmatch:::mk.hash(x = x, size = size)
APPEND = function(x, what) fastmatch:::append.hash(hash = x, x = what, index = FALSE)
HTABLE = function(x) fastmatch:::levels.fasthash(x)
并在其上构建相同的概念：
ff3 = function(x, size)
{
h = HASH(double(), size)
for(elt in x) h = APPEND(h, elt)
return(.POSIXct(HTABLE(h)))
}
system.time({ ans3 = ff3(ts, sum(lengths(ts)) / 1e2) }) #an estimate of unique values
# user system elapsed
# 4.81 0.00 4.87
system.time({ ans3b = ff3(ts, length(ts[[1]])) }) #we know the number of uniques
# user system elapsed
# 2.03 0.03 2.10
并进行比较：
all.equal(ans1, ans2)
#[1] TRUE
all.equal(ans2, ans3)
#[1] TRUE
用一个更小的例子来说明：
set.seed(1821)
tmp = split(sample(1e2, 26, TRUE) + 0, rep(1:4, c(6, 3, 11, 6)))
identical(unique(unlist(tmp)), as.double(ff1(tmp)))
#[1] TRUE
identical(unique(unlist(tmp)), as.double(ff2(tmp)))
#[1] TRUE
identical(unique(unlist(tmp)), as.double(ff3(tmp, 1e2)))
#[1] TRUE
我有大约 500-2000 个 POSIXct 日期列表，列表如下所示：
ts <- lapply(c(1:500), function(x) seq(as.POSIXct("2000/1/1"), as.POSIXct("2017/1/1"), "hours"))
我需要一个唯一日期列表。我尝试了几件事：
t <- unique(do.call("c", ts))
这保留了 POSIXct class，但需要很长时间并使用 7-8GB 内存；尽管他的整个列表列表大约有 500MB。
t <- as.POSIXct(unique(unlist(ts, use.names = FALSE)), origin = "1970-01-01")
虽然消耗的内存大致相同，但速度要快得多。所以我试着把它和这个分开：
t <- lapply(split(ts, ceiling(seq_along(ts)/30)), function(x) {
return(unique(unlist(x, use.names = FALSE)))
})
t <- unique(unlist(x, use.names = FALSE))
相同的消耗，在我看来，内存来自 unlist() 或 unique() 调用 "small" 列表之一。
有没有办法实现这种内存效率？处理时间很重要，但只是一点点。如果列表大小加倍（这很可能），这可能会导致严重的问题。
unique(do.call("c", ts)) 调用在我的机器上使用了 < 4GB (3869.9 - 606 ~ 3GB) 的内存。 ts 对象是 568MB。
R> ts <- lapply(c(1:500), function(x) seq(as.POSIXct("2000/1/1"), as.POSIXct("2017/1/1"), "hours"))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221687 11.9 460000 24.6 392929 21
Vcells 74925836 571.7 112760349 860.3 79427802 606
R> t <- unique(do.call("c", ts))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221729 11.9 460000 24.6 392929 21.0
Vcells 75074953 572.8 413082177 3151.6 507227169 3869.9
R> print(object.size(ts), units="MB")
568.8 Mb
R> sessionInfo()
R version 3.3.2 (2016-10-31)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 14.04.5 LTS
locale:
[1] LC_CTYPE=en_US.UTF-8 LC_NUMERIC=C LC_TIME=en_US.UTF-8 LC_COLLATE=en_US.UTF-8
[5] LC_MONETARY=en_US.UTF-8 LC_MESSAGES=en_US.UTF-8 LC_PAPER=en_US.UTF-8 LC_NAME=C
[9] LC_ADDRESS=C LC_TELEPHONE=C LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C
attached base packages:
[1] stats graphics grDevices utils datasets methods base
设置 recursive = FALSE 和 use.names = FALSE 使其更快并将内存消耗降低到 ~2GB。
R> ts <- lapply(1:500, function(x) seq(as.POSIXct("2000-01-01"), as.POSIXct("2017-01-01"), "hours"))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221686 11.9 460000 24.6 371201 19.9
Vcells 74925836 571.7 111681359 852.1 80924280 617.5
R> u <- do.call("c", c(ts, recursive = FALSE, use.names = FALSE))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221725 11.9 460000 24.6 371201 19.9
Vcells 149446409 1140.2 413082872 3151.6 373009943 2845.9
使用具有相同参数的 unlist 在内存消耗上稍微轻一些：
R> ts <- lapply(1:500, function(x) seq(as.POSIXct("2000-01-01"), as.POSIXct("2017-01-01"), "hours"))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221686 11.9 460000 24.6 371201 19.9
Vcells 74925836 571.7 111681359 852.1 80924280 617.5
R> u <- .POSIXct(unlist(ts, recursive = FALSE, use.names = FALSE))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 221695 11.9 460000 24.6 371201 19.9
Vcells 149446337 1140.2 358453576 2734.8 298487368 2277.3
加上
R> ts <- lapply(c(1:500), function(x) seq(as.POSIXct("2000/1/1"), as.POSIXct("2017/1/1"), "hours"))
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 218429 11.7 460000 24.6 389555 20.9
Vcells 74922694 571.7 111432506 850.2 81226910 619.8
R> u <- Reduce(function(x, y) unique(c(x, y)), ts)
R> gc()
used (Mb) gc trigger (Mb) max used (Mb)
Ncells 218893 11.7 460000 24.6 389555 20.9
Vcells 75072416 572.8 111432506 850.2 111399894 850.0
而不是用 do.call(c, .)/unlist(.) 和单个大哈希 table 创建一个大向量，如 Joshua 的回答所示，它具有高内存使用率，我们可以遵循较少的迭代处理 "ts" 的时间高效但内存效率更高的方式：
ff1 = function(x) ## a simple version of `Reduce(unique(c()), )`
{
ans = NULL
for(elt in x) ans = unique(c(ans, elt))
return(.POSIXct(ans))
}
system.time({ ans1 = ff1(ts) })
# user system elapsed
# 11.41 1.25 12.74
"ts" 具有相同的元素。虽然这种理想情况通常并非如此，但如果可能的话，我们可以尽量避免一些连接：
ff2 = function(x)
{
ans = NULL
for(elt in x) {
new = !(elt %in% ans)
if(any(new)) ans = c(ans, elt[new])
}
return(.POSIXct(ans))
}
system.time({ ans2 = ff2(ts) })
# user system elapsed
# 6.65 1.12 7.93
同样，fastmatch 包有一个非常有趣但不幸的是，它没有导出，我们可以在这里尝试使用的高级哈希 table 功能。它还应该减少内存消耗。
首先定义一些方便的包装器：
HASH = function(x, size) fastmatch:::mk.hash(x = x, size = size)
APPEND = function(x, what) fastmatch:::append.hash(hash = x, x = what, index = FALSE)
HTABLE = function(x) fastmatch:::levels.fasthash(x)
并在其上构建相同的概念：
ff3 = function(x, size)
{
h = HASH(double(), size)
for(elt in x) h = APPEND(h, elt)
return(.POSIXct(HTABLE(h)))
}
system.time({ ans3 = ff3(ts, sum(lengths(ts)) / 1e2) }) #an estimate of unique values
# user system elapsed
# 4.81 0.00 4.87
system.time({ ans3b = ff3(ts, length(ts[[1]])) }) #we know the number of uniques
# user system elapsed
# 2.03 0.03 2.10
并进行比较：
all.equal(ans1, ans2)
#[1] TRUE
all.equal(ans2, ans3)
#[1] TRUE
用一个更小的例子来说明：
set.seed(1821)
tmp = split(sample(1e2, 26, TRUE) + 0, rep(1:4, c(6, 3, 11, 6)))
identical(unique(unlist(tmp)), as.double(ff1(tmp)))
#[1] TRUE
identical(unique(unlist(tmp)), as.double(ff2(tmp)))
#[1] TRUE
identical(unique(unlist(tmp)), as.double(ff3(tmp, 1e2)))
#[1] TRUE