Thoughts for faster indexing

Hello,

I have a fairly large data.frame.  (About 150,000 rows of 100
variables.) There are case IDs, and multiple entries for each ID, with a
date stamp.  (i.e. records of peoples activity.)


I need to iterate over each person (record ID) in the data set, and then
process their data for each date.  The processing part is fast, the date
part is fast.  Locating the records is slow.  I've even tried using
data.table, with ID set as the index, and it is still slow.

The line with the slow process (According to Rprof) is:


j <- which( d$id == person )

(I then process all the records indexed by j, which seems fast enough.)

where d is my data.frame or data.table

I thought that using the data.table indexing would speed things up, but
not in this case.

Any ideas on how to speed this up?


Thanks!

-- 
Noah Silverman, M.S., C.Phil
UCLA Department of Statistics
8117 Math Sciences Building
Los Angeles, CA 90095

Hello,

I have a fairly large data.frame.  (About 150,000 rows of 100
variables.) There are case IDs, and multiple entries for each ID, with a
date stamp.  (i.e. records of peoples activity.)


I need to iterate over each person (record ID) in the data set, and then
process their data for each date.  The processing part is fast, the date
part is fast.  Locating the records is slow.  I've even tried using
data.table, with ID set as the index, and it is still slow.

The line with the slow process (According to Rprof) is:


j <- which( d$id == person )

(I then process all the records indexed by j, which seems fast enough.)

where d is my data.frame or data.table

I thought that using the data.table indexing would speed things up, but
not in this case.

Any ideas on how to speed this up?


Thanks!

-- 
Noah Silverman, M.S., C.Phil
UCLA Department of Statistics
8117 Math Sciences Building
Los Angeles, CA 90095

R-help@

 mailing list

you need to show the statement in context with the rest of the
script.  you need to tell us what you want to do, not how you want
to do it.

Sent from my iPad

On Nov 20, 2013, at 15:16, Noah Silverman
<noahsilverman at g.ucla.edu> wrote:

Hello,

I have a fairly large data.frame.  (About 150,000 rows of 100 
variables.) There are case IDs, and multiple entries for each ID,
with a date stamp.  (i.e. records of peoples activity.)


I need to iterate over each person (record ID) in the data set,
and then process their data for each date.  The processing part
is fast, the date part is fast.  Locating the records is slow.
I've even tried using data.table, with ID set as the index, and
it is still slow.

The line with the slow process (According to Rprof) is:


j <- which( d$id == person )

(I then process all the records indexed by j, which seems fast
enough.)

where d is my data.frame or data.table

I thought that using the data.table indexing would speed things
up, but not in this case.

Any ideas on how to speed this up?


Thanks!

-- Noah Silverman, M.S., C.Phil UCLA Department of Statistics 
8117 Math Sciences Building Los Angeles, CA 90095

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



On 11/21/13, 12:34 , Jim Holtman wrote:

you need to show the statement in context with the rest of the
script.  you need to tell us what you want to do, not how you want
to do it.

Agreed - a few details will result in guesses (see my guess below)

Sent from my iPad

On Nov 20, 2013, at 15:16, Noah Silverman
<noahsilverman at g.ucla.edu> wrote:

Hello,

I have a fairly large data.frame.  (About 150,000 rows of 100
variables.) There are case IDs, and multiple entries for each ID,
with a date stamp.  (i.e. records of peoples activity.)


I need to iterate over each person (record ID) in the data set,
and then process their data for each date.  The processing part
is fast, the date part is fast.  Locating the records is slow.
I've even tried using data.table, with ID set as the index, and
it is still slow.

The line with the slow process (According to Rprof) is:


j <- which( d$id == person )

Possibly use

d_by_id <- split(d, d$id)

which splits the data.frame d into a listt, where each list represents
the data.frame of one id.

But: Just a guess.

Cheers,

Rainer

(I then process all the records indexed by j, which seems fast
enough.)

where d is my data.frame or data.table

I thought that using the data.table indexing would speed things
up, but not in this case.

Any ideas on how to speed this up?


Thanks!

-- Noah Silverman, M.S., C.Phil UCLA Department of Statistics
8117 Math Sciences Building Los Angeles, CA 90095

- --
Rainer M. Krug, PhD (Conservation Ecology, SUN), MSc (Conservation
Biology, UCT), Dipl. Phys. (Germany)

Centre of Excellence for Invasion Biology
Stellenbosch University
South Africa

Tel :       +33 - (0)9 53 10 27 44
Cell:       +33 - (0)6 85 62 59 98
Fax :       +33 - (0)9 58 10 27 44

Fax (D):    +49 - (0)3 21 21 25 22 44

email:      Rainer at krugs.de

Skype:      RMkrug
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.22 (Darwin)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQEcBAEBAgAGBQJSjg/+AAoJENvXNx4PUvmC/kcH/3eaMvOTCAvA6ewwH/XJHH6X
B4BgstscvvJ3yArFeWqLIV0CEgk3da4c28+4Jk50vnltRVwUieFxKA1UK6Ef3gPl
pZUg9TaUNAeHPfkrxQSrYIa+hLWMZ1Ybe6GM1OlXnkc9ZBT9KS+rX3HFfr9rdyFI
Rv7SgrylUnpZIyiMeAzQS/FBzozV3G6mGu8FJ8YW5mHCqajI2alK3B3BBREzuLsL
ZMSuFDPTzxrE63O+uU6yFDibhz/4chKVz6CEF52WUgpgP+X4rW/DcLDrDfXxEvwM
ZDHcOZ8FJsuDl1lb1bdzSyS61KfzWls37i9VtOozqQwSFbaHbcdV16jHCPDzRPA=
=u5ol
-----END PGP SIGNATURE-----

I have some processes where I do the same thing, iterate over subsets of a
data frame.
My data frame has ~250,000 rows, 30 variables, and the subsets are such
that there are about 6000 of them.

Performing a which() statement like yours seems quite fast.

For example, wrapping unix.time() around the which() expression, I get

  user  system elapsed   0.008   0.000   0.008

It's hard for me to imagine the single task of getting the indexes is slow
enough to be a bottleneck.



On the other hand, if the variable being used to identify subsets is a
factor with many levels (~6000 in my case), it is noticeably slower.

  user  system elapsed
 0.024   0.002   0.026


I haven't tested it, and have no real expectation that it will make a
difference, but perhaps sorting by the index variable before iterating
will help (if you haven't already). Since these are not true indexes in
the sense used by relational database systems, maybe it will make a
difference.

-- 
Don MacQueen

Lawrence Livermore National Laboratory
7000 East Ave., L-627
Livermore, CA 94550
925-423-1062





On 11/20/13 12:16 PM, "Noah Silverman" <noahsilverman at g.ucla.edu> wrote:

Hello,

I have a fairly large data.frame.  (About 150,000 rows of 100
variables.) There are case IDs, and multiple entries for each ID, with a
date stamp.  (i.e. records of peoples activity.)


I need to iterate over each person (record ID) in the data set, and then
process their data for each date.  The processing part is fast, the date
part is fast.  Locating the records is slow.  I've even tried using
data.table, with ID set as the index, and it is still slow.

The line with the slow process (According to Rprof) is:


j <- which( d$id == person )

(I then process all the records indexed by j, which seems fast enough.)

where d is my data.frame or data.table

I thought that using the data.table indexing would speed things up, but
not in this case.

Any ideas on how to speed this up?


Thanks!

-- 
Noah Silverman, M.S., C.Phil
UCLA Department of Statistics
8117 Math Sciences Building
Los Angeles, CA 90095

The line with the slow process (According to Rprof) is:
j <- which( d$id == person )
(I then process all the records indexed by j, which seems fast enough.)

-----Original Message-----
From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] On Behalf
Of Noah Silverman
Sent: Wednesday, November 20, 2013 12:17 PM
To: 'R-help at r-project.org'
Subject: [R] Thoughts for faster indexing

Hello,

I have a fairly large data.frame.  (About 150,000 rows of 100
variables.) There are case IDs, and multiple entries for each ID, with a
date stamp.  (i.e. records of peoples activity.)


I need to iterate over each person (record ID) in the data set, and then
process their data for each date.  The processing part is fast, the date
part is fast.  Locating the records is slow.  I've even tried using
data.table, with ID set as the index, and it is still slow.

The line with the slow process (According to Rprof) is:


j <- which( d$id == person )

(I then process all the records indexed by j, which seems fast enough.)

where d is my data.frame or data.table

I thought that using the data.table indexing would speed things up, but
not in this case.

Any ideas on how to speed this up?


Thanks!

--
Noah Silverman, M.S., C.Phil
UCLA Department of Statistics
8117 Math Sciences Building
Los Angeles, CA 90095

Noah,

If N is # of rows, k is # of unique IDs

Using which() is O(N), using which() in a loop is going to  be O(Nk);

sorting the entire data is O(N ln N) and then you can process it in
contiguous blocks, no which required.

-Neal

All interesting suggestions.

I guess a better example of the code would have been a good idea.  So,
I'll put a relevant snippet here.

Rows are cases.  There are multiple cases for each ID, marked with a
date.  I'm trying to calculate a time recency weighted score for a
covariate, added as a new column in the data.frame.

So, for each row, I need to see which ID it belongs to, then get all the
scores prior to this row's date, then compute the recency weighted summary.

Right now, I do this in an obvious, but very very slow way.

Here is my slow code:
======================
for(i in 1:nrow(d)){
    for(j in which( d$id == d$id[i] & d$date[j] < d$date[i]) ){
        days_since = as.numeric( d$date[i] - d$date[j] )
        w <- exp( -days_since/decay )
        temp <- temp + w * as.numeric(d[j,'score'])
        wTemp <- wTemp + w
    }

    temp <- temp / wTemp
    d$newScore[i,] <- temp
}
======================

One immediate thought was to turn the "date" into an integer.  That
should save a few cycles of date math.

I need to do this process for a bunch of scores.  A grid search over
different time decay levels might be nice.  So any speedup to this
routine will save me a ton of time.

Ideas?