R Проверка на дубликаты мучительно медленная, даже с mclapply

У меня есть данные о повторных продажах нескольких автомобилей с уникальными идентификаторами. Автомобиль может быть продан более одного раза.

Однако некоторые из идентификаторов ошибочны, поэтому я проверяю для каждого идентификатора, записан ли размер одинаковым для нескольких продаж. Если это не так, то я знаю, что идентификатор ошибочен.

Я пытаюсь сделать это с помощью следующего кода:

library("doMC")

Data <- data.frame(ID=c(15432,67325,34623,15432,67325,34623),Size=c("Big","Med","Small","Big","Med","Big"))
compare <- function(v) all(sapply( as.list(v[-1]), FUN=function(z) {isTRUE(all.equal(z, v[1]))}))

IsGoodId = function(Id){
  Sub = Data[Data$ID==Id,]
  if (length(Sub[,1]) > 1){
    return(compare(Sub[,"Size"]))
  }else{
    return(TRUE)
  }
}

WhichAreGood = mclapply(unique(Data$ID),IsGoodId)

Но это мучительно, ужасно, ужасно медленно на моем четырехъядерном i5.

Кто-нибудь может увидеть, где узкое место? Я новичок в оптимизации R.

Спасибо, -Н


r optimization multicore mclapply domc
person N. McA.    schedule 28.03.2013    source источник
comment
Всем привет! Пожалуйста, сделайте свой пост воспроизводимым, взглянув на Как сделать отличный воспроизводимый пример для нас, чтобы помочь вам. Спасибо.   -  person Arun    schedule 28.03.2013
comment
Проверка на недопустимые записи может быть более эффективной, но я не думаю, что проверка на дубликаты должна быть более эффективной с параллельной обработкой.   -  person IRTFM    schedule 28.03.2013
comment
Я предлагаю вам найти R inferno Патрика Бернса. Это открытие.   -  person Roman Luštrik    schedule 29.03.2013

Ответы (1)


arrow_upward
4
arrow_downward

Похоже, ваш алгоритм делает N ^ 2 сравнений. Возможно, что-то вроде следующего будет лучше масштабироваться. Мы находим повторяющиеся продажи, думая, что это небольшая часть от общего числа.

dups = unique(Data$ID[duplicated(Data$ID)])
DupData = Data[Data$ID %in% dups,,drop=FALSE]

Оператор %in% очень хорошо масштабируется. Затем разделите столбец размера на основе идентификатора, проверяя идентификаторы с более чем одним размером.

tapply(DupData$Size, DupData$ID, function(x) length(unique(x)) != 1)

Это дает именованный логический вектор с TRUE, указывающим, что существует более одного размера для каждого идентификатора. Это масштабируется примерно линейно с количеством дублирующих продаж; есть умные способы сделать это быстро, поэтому, если ваши дублированные данные сами по себе большие...

Хм, подумав об этом немного, я думаю

u = unique(Data)
u$ID[duplicated(u$ID)]

делает свое дело.

person Martin Morgan    schedule 28.03.2013
comment
Ахах, ты герой. Я начал понимать, что у него квадратичная сложность, но не мог разобраться. Благодарю вас! - person N. McA.; 29.03.2013