Разрешены ли двусвязные структуры?
Я пишу пакет с классом S4, который выглядит как простая древовидная структура: класс, скажем S4node, имеет слот nodes, который представляет собой список дочерних элементов S4node (через общего виртуального предка, скажем S4base). В классе также есть слот parent типа S4base, который ссылается обратно на родительский узел дочерних узлов. Это выглядит примерно так (для ясности с использованием простого кода):
# Create the root node, slot parent is set to NA, slot id is set to 567
> root <- new_node(567)
# Create some child nodes, slot parent is set to root, slot nodes has new node added
> root <- add_node(root, 5671)
> root <- add_node(root, 5672)
Это работает нормально, и все слоты установлены правильно. Обход иерархии вниз работает так же, как и обход иерархии вверх. Но вот проблема: когда я хочу пройти вверх по иерархии, слот nodes устанавливается на NULL, что становится очевидным при путешествии вниз по другой ветке. Так:
> node5671 <- find_node(root, 5671)
# Now traverse 5671 -> 567 -> 5672
> node5672 <- node_travel(node5671, "../5672")
Error: path not found
На консоли это становится понятнее:
> length(root@nodes)
[1] 2
> node5671@parent@id
[1] 567
> nodes5671@parent@nodes
NULL
# Best one yet: take the root node, get a child, get the parent (= root), get the nodes = NULL!!!
> root@nodes[[1]]@parent@nodes
NULL
Мне кажется, что список с узлами очищается автоматически, но только при неявном доступе: я могу создать список в первую очередь, только при ссылке на список через поиск @parent список очищается. Это чтобы избежать бесконечной рекурсии? Это причуда gc()? Есть ли обходной путь для этого?
Похоже также, что это может быть проблема копирования/ссылки. В этом случае, я думаю, вам нужна ссылочная семантика, а узел — это ссылка на структуру данных. Вы можете использовать среды RefClass или R6 вместо S4.
@nicola Но все, что у меня здесь есть, это ссылки. Я не изменяю какую-либо часть древовидной структуры, поэтому не должно быть копирования, а только создание еще одной привязки к существующей древовидной структуре. Я рассмотрю ваши предложения по окружению. RC и R6 потребуют полного рефакторинга моего кода, поэтому я надеюсь, что смогу этого избежать.
Что значит, что у вас есть ссылки? Не видя реализации вашего класса, сложно что-либо сказать
@nicola Когда я говорю «ссылки», я имею в виду, что привязываю имя к объекту. Я ничего не изменяю, поэтому копирования объекта быть не должно.
Непонятно, что вы имеете в виду. Есть ли причина, по которой вы не хотите делиться реализацией? Как уже говорилось, ответить на этот вопрос невозможно. Вы должны предоставить воспроизводимый пример.
@nicola Отсутствие совместного использования не является проблемой, вся база кода находится на GitHub (github.com/pvanlaake/ncdfCF), за исключением этого фрагмента, потому что он не работает... MRE с классами S4 неработоспособен, как вы' мне придется загрузить, собрать и установить несколько файлов, чтобы получить работоспособный пример. Вот почему я предоставляю макет, чтобы продемонстрировать проблему.
Знаете ли вы о пакете ncdf4? Вот ссылка: cran.r-project.org/web/packages/ncdf4/index.html. Однако дело в реализации, поэтому вы можете показать, как вы определили этот класс S4node и какую функцию использовали. Иначе как можно помочь?
Думаю, я бы попробовал использовать cran.r-project.org/web/packages/pointr для реализации идеи связанного списка; или отойдите от языка и сделайте что-нибудь типа rcpp.
@Patrick У вас здесь нет никаких ссылок, поскольку R использует семантику значений и копирование, а не семантику ссылок (за исключением сред).
@NirGraham Господи, что это?! Это… извините за выбор слова, но, действительно: мерзость… совершенно не обязательно для реализации ссылочной семантики в R.
@NirGraham Этот пакет меня настолько взволновал, что я написал свой собственный, чтобы показать, как это правильно реализовать: cran.r-project.org/package=aka — учтите, использование «aka» здесь все равно неуместно ( или даже для большинства целей, на которые неумело претендует «pointr»).
Ответы 1
Я могу только предположить, что add_node изменяет слот nodes копии своего аргумента и возвращает измененную копию. Копия получает новый узел, а оригинал сохраняется. Придумать пример с использованием tracemem было несложно...
> setClass("S4base")
> setClass("S4root",
+ contains = "S4base",
+ slots = c(id = "integer", parent = "NULL", nodes = "list"),
+ prototype = list(id = 0L, parent = NULL, nodes = list()))
> setClass("S4node",
+ contains = "S4base",
+ slots = c(id = "integer", parent = "S4base", nodes = "list"),
+ prototype = list(id = 1L, parent = new("S4root"), nodes = list()))
>
> root <- new("S4root", id = 0L); tracemem(root)
[1] "<0x1370506d8>"
> node <- new("S4node", id = 1L, parent = root)
> root@nodes <- list(node)
tracemem[0x1370506d8 -> 0x1370f5aa8]:
> identical(root, root@nodes[[1L]]@parent)
[1] FALSE
>
> str(root)
Formal class 'S4root' [package ".GlobalEnv"] with 3 slots
..@ id : int 0
..@ parent: NULL
..@ nodes :List of 1
.. ..$ :Formal class 'S4node' [package ".GlobalEnv"] with 3 slots
.. .. .. ..@ id : int 1
.. .. .. ..@ parent:Formal class 'S4root' [package ".GlobalEnv"] with 3 slots
.. .. .. .. .. ..@ id : int 0
.. .. .. .. .. ..@ parent: NULL
.. .. .. .. .. ..@ nodes : list()
.. .. .. ..@ nodes : list()
>
Чтобы обойти копирование при изменении в R, вам, вероятно, следует использовать среды (возможно, расширяющие классы S4 environment):
> root <- new.env(parent = emptyenv()); try(tracemem(root))
Error in tracemem(root) :
'tracemem' is not useful for promise and environment objects
> node <- new.env(parent = emptyenv())
>
> root$id <- 0L
> root$nodes <- list(node)
>
> node$id <- 1L
> node$nodes <- list()
> node$parent <- root
>
> identical(root, root$nodes[[1L]]$parent)
[1] TRUE
>
Ого, это действительно удивительно! Изменение слота в экземпляре класса дает вам совершенно новый экземпляр! Я полагаю, что это имеет смысл, новое значение слота все-таки меняет экземпляр, но все же удивительно, поскольку оно делает S4 действительно неэффективным в таких типах иерархий классов. Ответ принят и +1 за отличное объяснение и демонстрацию.
Использование среды для решения этой проблемы означает, что я модифицирую свои классы с помощью R6. Может быть, все-таки пришло время перебазировать мой код...
root копируется только потому, что на него ссылается node, когда вы пытаетесь его изменить. Копия не возникла бы, если бы на root не было ссылки. Я подозреваю, что вы сможете реализовать это в S4, если убедитесь, что S4base расширяет базовый класс environment. Есть пример в help("setClass").
Что делает функция
node_travel?