Могу ли я использовать список как hash в R? Если да, то почему это так медленно?

Перед использованием R я использовал довольно много Perl. В Perl я часто использовал хеши, и поиск hashей обычно рассматривается как быстрый в Perl.

Например, следующий код заполняет хеш до 10000 пар ключ / значение, где ключи являются случайными буквами, а значения – случайными целыми числами. Затем он выполняет 10000 случайных поисков в этом хеше.

#!/usr/bin/perl -w use strict; my @letters = ('a'..'z'); print @letters . "\n"; my %testHash; for(my $i = 0; $i < 10000; $i++) { my $r1 = int(rand(26)); my $r2 = int(rand(26)); my $r3 = int(rand(26)); my $key = $letters[$r1] . $letters[$r2] . $letters[$r3]; my $value = int(rand(1000)); $testHash{$key} = $value; } my @keyArray = keys(%testHash); my $keyLen = scalar @keyArray; for(my $j = 0; $j < 10000; $j++) { my $key = $keyArray[int(rand($keyLen))]; my $lookupValue = $testHash{$key}; print "key " . $key . " Lookup $lookupValue \n"; } 

Теперь, когда все чаще, я хочу иметь hash-подобную структуру данных в R. Ниже приведен эквивалентный R-код:

 testHash <- list() for(i in 1:10000) { key.tmp = paste(letters[floor(26*runif(3))], sep="") key <- capture.output(cat(key.tmp, sep="")) value <- floor(1000*runif(1)) testHash[[key]] <- value } keyArray <- attributes(testHash)$names keyLen = length(keyArray); for(j in 1:10000) { key <- keyArray[floor(keyLen*runif(1))] lookupValue = testHash[[key]] print(paste("key", key, "Lookup", lookupValue)) } 

Кажется, что код выполняет эквивалентные вещи. Однако Perl один намного быстрее:

 >time ./perlHashTest.pl real 0m4.346s user **0m0.110s** sys 0m0.100s 

По сравнению с R:

 time R CMD BATCH RHashTest.R real 0m8.210s user **0m7.630s** sys 0m0.200s 

Что объясняет несоответствие? Являются ли поиски в списках R просто не хорошими?

Увеличение до 100 000 строк списка и 100 000 поисковых запросов только преувеличивает несоответствие? Есть ли лучшая альтернатива для hash-структуры данных в R, чем собственный список ()?

Основная причина в том, что списки R с именованными элементами не хешируются. Поиск hashа – это O (1), потому что во время вставки ключ преобразуется в целое число с использованием хеш-функции, а затем значение помещается в пробел hash(key) % num_spots массива num_spots long (это большое упрощение и позволяет избежать сложность борьбы с столкновениями). Поиск ключа просто требует hashирования ключа, чтобы найти позицию значения (это O (1), по сравнению с поиском массива O (n)). В списках R используются запросы имен, которые являются O (n).

Как говорит Дирк, используйте hash-пакет. Огромное ограничение заключается в том, что он использует среды (которые hashируются) и переопределяет [ методы для имитации хеш-таблиц. Но среда не может содержать другую среду, поэтому вы не можете иметь вложенные hashи с hash-функцией.

Некоторое время назад я работал над реализацией чистой структуры данных hash-таблицы в C / R, которая могла быть вложенной, но она продолжала работу над моим проектом, когда я работал над другими вещами. Было бы неплохо иметь хотя 🙂

Вы можете попробовать среду и / или hash- пакет Кристофера Брауна (который, случается, использует среды под капотом).

Ваш код очень не похож на R-R, и это одна из причин, почему это так медленно. Я не оптимизировал код ниже для максимальной скорости, только R’ness.

 n <- 10000 keys <- matrix( sample(letters, 3*n, replace = TRUE), nrow = 3 ) keys <- apply(keys, 2, paste0, collapse = '') value <- floor(1000*runif(n)) testHash <- as.list(value) names(testHash) <- keys keys <- sample(names(testHash), n, replace = TRUE) lookupValue = testHash[keys] print(data.frame('key', keys, 'lookup', unlist(lookupValue))) 

На моей машине работает почти мгновенно, исключая печать. Ваш код работал примерно с той же скоростью, о которой вы сообщали. Он делает то, что вы хотите? Вы можете установить n до 10 и просто посмотреть на вывод и testHash и посмотреть, все ли это.

ПРИМЕЧАНИЕ к синтаксису: apply выше правило представляет собой просто цикл, и они медленны в R. Точка применения этих семейных команд является выразительностью. Многие из следующих команд могли быть помещены внутри цикла с apply и если бы это был цикл for это было бы искушением. В R берут как можно больше из вашей петли. Использование применяемых семейных команд делает это более естественным, потому что команда предназначена для представления приложения одной функции в список определенного типа, а не в общий цикл (да, я знаю, что apply может использоваться для нескольких команд).

Я немного взломан R, но я эмпирик, поэтому я поделюсь некоторыми вещами, которые я наблюдал, и пусть те, у кого больше теоретического понимания R, проливают свет на whys.

  • R кажется намного медленнее, используя стандартные streamи, чем Perl. Поскольку stdin и stout гораздо чаще используются в Perl, я предполагаю, что он имеет оптимизацию вокруг того, как он это делает. Таким образом, в RI намного быстрее читать / писать текст, используя встроенные функции (например, write.table ).

  • Как говорили другие, векторные операции в R быстрее, чем циклы … и скорость wrt, большинство apply () синтаксис семейства – просто симпатичная shell в цикле.

  • Индексированные вещи работают быстрее, чем неиндексированные. (Очевидно, я знаю.) Пакет data.table поддерживает индексирование объектов типа фрейма данных.

  • Я никогда не использовал hash-среды, такие как @Allen, проиллюстрированные (и я никогда не вдыхал hash … насколько вам известно)

  • Некоторые из синтаксиса, который вы использовали, работают, но могут быть затянуты. Я не думаю, что это действительно важно для скорости, но код немного читабельнее. Я не пишу очень жесткий код, но я отредактировал несколько вещей, таких как смена floor(1000*runif(1)) на sample(1:1000, n, replace=T) . Я не хочу быть педантичным, я просто написал это так, как я бы сделал это с нуля.

Поэтому с учетом этого я решил проверить hash-подход, который использовал @allen (потому что это для меня роман) против моего hashа «бедняга», который я создал с помощью индексированной таблицы данных в качестве справочной таблицы. Я не уверен на 100%, что то, что @allen и я делаю, – это именно то, что вы делали в Perl, потому что мой Perl довольно ржавый. Но я думаю, что два метода ниже делают то же самое. Мы оба выбираем второй набор ключей из ключей в «hash», поскольку это предотвращает пропуски hashа. Вы хотите проверить, как эти примеры обрабатывают хеш-обманы, как я не думал об этом.

 require(data.table) dtTest <- function(n) { makeDraw <- function(x) paste(sample(letters, 3, replace=T), collapse="") key <- sapply(1:n, makeDraw) value <- sample(1:1000, n, replace=T) myDataTable <- data.table(key, value, key='key') newKeys <- sample(as.character(myDataTable$key), n, replace = TRUE) lookupValues <- myDataTable[newKeys] strings <- paste("key", lookupValues$key, "Lookup", lookupValues$value ) write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F ) } 

#

 hashTest <- function(n) { testHash <- new.env(hash = TRUE, size = n) for(i in 1:n) { key <- paste(sample(letters, 3, replace = TRUE), collapse = "") assign(key, floor(1000*runif(1)), envir = testHash) } keyArray <- ls(envir = testHash) keyLen <- length(keyArray) keys <- sample(ls(envir = testHash), n, replace = TRUE) vals <- mget(keys, envir = testHash) strings <- paste("key", keys, "Lookup", vals ) write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F ) } 

если я запускаю каждый метод, используя 100 000 ничьих, я получаю что-то вроде этого:

 > system.time( dtTest(1e5)) user system elapsed 2.750 0.030 2.881 > system.time(hashTest(1e5)) user system elapsed 3.670 0.030 3.861 

Имейте в виду, что это все еще значительно медленнее, чем код Perl, который на моем ПК, кажется, запускает 100K выборок в течение секунды.

Надеюсь, что приведенный выше пример поможет. И если у вас есть какие-либо вопросы относительно того, why возможно, @allen, @vince и @dirk смогут ответить;)

После того, как я напечатал выше, я понял, что не проверял, что сделал @john. Итак, что, черт возьми, давайте сделаем все 3. Я изменил код из @john, чтобы использовать write.table (), и вот его код:

 johnsCode <- function(n){ keys = sapply(character(n), function(x) paste(letters[ceiling(26*runif(3))], collapse='')) value <- floor(1000*runif(n)) testHash <- as.list(value) names(testHash) <- keys keys <- names(testHash)[ceiling(n*runif(n))] lookupValue = testHash[keys] strings <- paste("key", keys, "Lookup", lookupValue ) write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F ) } 

и время выполнения:

 > system.time(johnsCode(1e5)) user system elapsed 2.440 0.040 2.544 

И вот он у вас есть. @john пишет жесткий / быстрый R-код!

Но среда не может содержать другую среду (цитата из ответа Винса).

Может быть, так было некоторое время назад (я не знаю), но эта информация, похоже, уже не точна:

 > d <- new.env() > d$x <- new.env() > d$x$y = 20 > d$x$y [1] 20 

Таким образом, среда делает довольно способную карту / dict сейчас. Может быть, вы пропустите оператор «[», используйте hash-пакет в этом случае.

Эта заметка, взятая из документации хеш-пакета, также может представлять интерес:

R медленно двигается к собственной реализации hashей с использованием окружения (см. Extract. Доступ к средам с использованием $ и [[был доступен в течение некоторого времени, а в последнее время объекты могут наследовать из среды и т. Д. Но многие функции, которые делают хеши / словари Больших все еще не хватает, таких как операция среза, [.

Прежде всего, как сказал Винс и Дирк, вы не используете hashи в своем примере кода. Дословный перевод примера perl был бы

 #!/usr/bin/Rscript testHash <- new.env(hash = TRUE, size = 10000L) for(i in 1:10000) { key <- paste(sample(letters, 3, replace = TRUE), collapse = "") assign(key, floor(1000*runif(1)), envir = testHash) } keyArray <- ls(envir = testHash) keyLen <- length(keyArray) for(j in 1:10000) { key <- keyArray[sample(keyLen, 1)] lookupValue <- get(key, envir = testHash) cat(paste("key", key, "Lookup", lookupValue, "\n")) } 

который быстро запускается на моей машине, а основное время - настройка. (Попробуйте и опубликуйте тайминги.)

Но настоящая проблема, как сказал Джон, заключается в том, что вы должны думать о векторах в R (например, о карте в perl), и его решение, вероятно, является лучшим. Если вы хотите использовать хеши, подумайте

 keys <- sample(ls(envir = testHash), 10000, replace = TRUE) vals <- mget(keys, envir = testHash) 

после той же настройки, что и выше, которая почти мгновенно работает на моей машине. Чтобы распечатать их, попробуйте

 cat(paste(keys, vals), sep="\n") 

Надеюсь, это немного поможет.

Аллан

  • Генерировать случайные числа с фиксированным средним значением и sd
  • идентифицировать группы связанных эпизодов, которые соединяются вместе
  • Почему data.table определен: = а не перегрузка <-?
  • Линейная регрессия с известным фиксированным перехватом в R
  • Как сказать, что находится в одном векторе, а не в другом?
  • Объединить столбец для удаления NA
  • Сохранить импортированные данные csv в векторе - R
  • R - изображение матрицы пикселей?
  • Как я могу заставить rJava использовать новую версию java для osx?
  • Какова цель установки ключа в data.table?
  • Как мне обращаться с «пакетом ххх» не доступно (для R версии xyz)? Предупреждение?
  • Давайте будем гением компьютера.