Fastest way of numbering instances of a value within a vector

user_9429625 0
Viewed 74

I am looking to number each instance of a value in a vector as it appears. For example the first instance of a value with get '1' the second instance will get '2' and so on - counting how many this value has appeared before it in the vector. I can do this with a for loop in R using the EuStockMarkets example data in datasets.

#load data
data <- as.data.frame(datasets::EuStockMarkets)
df <- data.frame(order = 1:nrow(data),value = data$DAX)
head(df)

#calculate number of instances 
start_time <- Sys.time()
for (i in 1:nrow(df)) {
 df[i,"instance"]<- sum(df[1:i,"value"] == df[i,"value"])
}
end_time <- Sys.time()
end_time - start_time
#Time difference of 0.1126978 secs

This is fine but I would rather not use a for loop if there was a faster option for much larger datasets and was wondering if their was a preexisting function that - perhaps with tidyverse package.

dplyr dataframe r
3 Answers

base R

This is a good use of ave:

table(df$instance) # yours
#    1    2    3    4 
# 1774   66   17    3 
df$instance3 <- ave(df$value, df$value, FUN = seq_along)
table(df$instance3)
#    1    2    3    4 
# 1774   66   17    3 
all(df$instance == df$instance3)
# [1] TRUE

dplyr

library(dplyr)
df %>%
  group_by(value) %>%
  mutate(instance4 = row_number()) %>%
  ungroup()

Benchmark

No surprise, Waldi's data.table breaks out:

DT <- as.data.table(df)
useful.function = function(x) { temp.idx = x[1]; sum(x[2] == df$value[1:temp.idx]); }
bench::mark(
  OP = {
    for (i in 1:nrow(df)) {
      df[i,"instance"]<- sum(df[1:i,"value"] == df[i,"value"])
    }
  },
  Waldi = {
    DT[,instance2:=seq_len(.N),by=value]
  },
  r2evans_base = {
    df$instance3 <- ave(df$value, df$value, FUN = seq_along)
  },
  r2evans_dplyr = {
    df %>%
      group_by(value) %>%
      mutate(instance4 = row_number()) %>%
      ungroup()
  },
  PlasticMan = {
    df$instance5 <- apply(df, MARGIN = 1, useful.function)
  },
  min_terations = 500, check = FALSE)
# # A tibble: 5 x 13
#   expression         min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result memory                 time    gc     
#   <bch:expr>    <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list> <list>                 <list>  <list> 
# 1 OP             54.42ms  59.45ms      16.6    39.9MB    11.1    300   200     18.07s <NULL> <Rprofmem [7,360 x 3]> <bench~ <tibbl~
# 2 Waldi          997.3us   1.11ms     828.     81.6KB     1.66   499     1   602.36ms <NULL> <Rprofmem [12 x 3]>    <bench~ <tibbl~
# 3 r2evans_base    3.11ms   3.52ms     273.    389.1KB     1.65   497     3      1.82s <NULL> <Rprofmem [35 x 3]>    <bench~ <tibbl~
# 4 r2evans_dplyr  13.04ms  15.85ms      59.5     347KB     6.03   454    46      7.63s <NULL> <Rprofmem [35 x 3]>    <bench~ <tibbl~
# 5 PlasticMan      12.7ms  14.12ms      65.3    26.9MB     4.47   468    32      7.16s <NULL> <Rprofmem [5,507 x 3]> <bench~ <tibbl~
user_33582720

With data.table:

library(data.table)
setDT(df)

df[,instance2:=seq_len(.N),by=value]

identical(df$instance,df$instance2)
[1] TRUE
user_135133280

The trick is to use the apply() function:

# Loading data.
data = as.data.frame(datasets::EuStockMarkets)
df = data.frame(order = 1:nrow(data), value = data$DAX)
head(df)

# Your solution.
for (i in 1:nrow(df)) 
{
  df[i, "instance"] = sum(df[1:i, "value"] == df[i, "value"])
}

# My solution.
useful.function = function(x)
{
  temp.idx = x[1]
  sum(x[2] == df$value[1:temp.idx])
}

df$instance2 = apply(df, MARGIN = 1, useful.function)

# Double check.
identical(df$instance, df$instance2)

# Benchmarking.
microbenchmark::microbenchmark(
  your.solution = 
  {
    for (i in 1:nrow(df)) 
    {
      sum(df[1:i, "value"] == df[i, "value"])
    }
  },
  my.solution =
  {
    apply(df, MARGIN = 1, useful.function)
  }
)

# Unit: milliseconds
# expr              min       lq     mean    median     uq     max neval
# your.solution() 37.7382 39.92370 44.29684 42.99385 44.67285 98.0862   100
# my.solution()   15.0171 16.52995 21.60575 20.41060 21.32430 75.8235   100

Basically, I have written a useful.function() that relies on the df$order to use only df$values up to the position of a certain value to compute what you ask. Then, this function is applied to each row of df with apply(). The results of microbenchmarking (which evaluates both solutions 100 times so to see which one is faster) shows that using apply() is about twice as faster than the for loop. This derives from the fact that the loop needs to make a lot of call (nrow(df) in your case) to other functions (possibly written in C), while apply() makes a single call.

user_176920830
Related