Как получить случайный элемент из дерева с учетом родительского узла? - PullRequest
Новая
       0

Как получить случайный элемент из дерева с учетом родительского узла?

0 голосов
/ 06 апреля 2010

У меня есть сценарий, в котором я хотел бы рандомизировать отображение некоторых предметов.Для данного родительского элемента, как я могу случайно выбрать один из его дочерних элементов?

Конечно, я мог бы загрузить ВСЕХ дочерних элементов и применить некоторый случайный индекс или еще много чего ... но это было бы крайне неэффективно.

Мне интересно, если это также неэффективно:

Parent.Children [random (Parent.Children.Count)]?

В какой момент элементы загружаются при доступеParent.Children

Ответы [ 2 ]

3 голосов
/ 07 апреля 2010

Item.Children - это загружаемое свойство с отложенным доступом, и я бы определенно не рекомендовал использовать его точно так, как показано здесь.

Перед тем, как опубликовать это, я немного покопался в API, чтобы посмотреть, нет ли в действительности способа подсчитать количество дочерних элементов без загрузки этого свойства, но, увы, я не смог найти способ, который мог бы показаться " законным». Похоже, что связано только свойство .HasChildren, и оно работает, выполняя большинство (но не все) того, что свойство .Children уже делает.

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

ChildList itemChildren = myItem.Parent.Children;
// Continue doing random() etc here, but using the itemChildren field.
0 голосов
/ 07 апреля 2010

У вас есть вся древовидная структура под рукой? Тогда вы могли бы сделать какой-то случайный обход. Например, вы можете выбрать случайный элемент из двоичного дерева, например, так (псевдокод): 

sub randomNode(node):
   randomVal = random(0, 3); // random value between 0 and 3

   if(randomVal == 0):
     return randomNode(node.left) if node.left != null else return node;
   elseif(randomVal == 1):
     return randomNode(node.right) if node.right != null else return node;
   else
     return node;

Для n-арного дерева у вас может быть что-то вроде этого: 

sub randomNode(node):
   randomVal = random(0, 2)

   if(randomVal == 0):
     return randomNode(node.children[random(0, node.children.length)]) if node.children.length != 0 else return node;
   elseif(randomVal == 1):
     return node;

Выполнение parent.children[random(parent.children.count)] не кажется мне неэффективным; это то, что я использовал в алгоритме выше. Что касается вашего последнего вопроса, я думаю, это зависит от того, как вы реализовали свое дерево. Если вы построили древовидную структуру самостоятельно, у вас должна быть вся древовидная структура под рукой. Если вы используете фреймворк, то это зависит от реализации этого фреймворка.

...