Алгоритм многопоточного построения неизменяемых деревьев в Java - PullRequest
8 голосов
/ 12 февраля 2011

Я хотел бы построить неизменную древовидную структуру данных, представляющую произвольное подмножество структуры каталогов filsystem.Как правило, существует фильтр, который знает о include / exclude, и я бы хотел иметь некоторую поддержку многопоточности в конструкции.

Звучит как занудное занятие, когда я сам пишу код, но мне интересно, естькакие-нибудь хорошие примеры, тексты или аналогичные по этой теме?Исходный код хорош;)

Ответы [ 5 ]

1 голос
/ 12 февраля 2011

В этой книге есть все ответы: http://www.amazon.co.uk/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504

0 голосов
/ 15 февраля 2011

Кросенволду:

Я думаю, что вы не поняли моего намерения.Может быть, я должен быть более ясным.

Предположения состоят в том, что Tree и TreeBuilder находятся в одном пакете.

Как вы можете видеть, конструктор Tree и метод freeze () имеют package уровень доступа.Таким образом, вы не можете создать его вне пакета и также не можете заморозить его вне пакета.

Единственный способ сделать это - через метод build ().Только TreeBuilder может создавать Tree, используя синхронизированный метод сборки.

Теперь я даже понял, что вы можете даже упростить удаление флага readonly и изменение метода Tree.addChild () для создания видимости.Следовательно, вы получите дерево, которое не имеет общедоступных мутаторов, а только методы доступа.

Как я уже сказал, Дерево не синхронизируется.TreeBuilder - это место, где происходит ваша синхронизация.Присмотритесь к аксессорам и мутаторам.Посмотрите, где находятся модификаторы public и package, и вы увидите, что единственный способ изменить дерево - это когда вы находитесь в одном пакете, так что это может сделать только построитель дерева.

public class Tree<T extends Filterable>{
   private final T data;
   private Tree<T> parent;
   private List<Tree<T>> children;
   private List<FilterChain<T>> filterChain;
   private boolean readonly = false;  
   /*package*/ Tree(T data) {...} 
   /*package*/ Tree(Tree<T> parent, T data) {...}

   /*package*/ void addChild(Tree<T> child){
       children.add(child);
   }
   public List<?> getResults(){
       return data.returnResults(filterChain);
   }

}

public class TreeBuilder<T>{
  public synchronized TreeNode createRoot(T data);
  public synchronized void addSubElement(TreeNode parentNode ,T data);
  public synchronized void addFilter(TreeNode node, Filter<T> filter);
  public Tree<T> synchronized build(){
     Tree<T> tree= ... 
     //build your tree
     //build filter chain for specific tree node
     return tree;
  }

}

0 голосов
/ 14 февраля 2011

Я бы предложил сохранить очередь «рабочих элементов». Каждый рабочий элемент инкапсулирует каталог для исследования и существующий родительский узел (если есть), к которому присоединяется результирующий узел дерева. Каждый поток выполняется в цикле, вытягивая элементы из передней части очереди, выполняя их и помещая любые подкаталоги в конец очереди как новые рабочие элементы.

Вы запускаете процесс, нажимая корневой каталог (без родительского узла дерева) в качестве первого рабочего элемента. Процесс заканчивается, когда очередь пуста, и все потоки находятся в режиме ожидания / ожидания.

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

0 голосов
/ 12 февраля 2011

Привет, я не знаю, что именно вы хотели бы достичь, особенно с точки зрения безопасности потоков, но, возможно, ниже псевдокод может быть использован как черновик.

public interface Filterable {
     List<?> returnResults(FilterChain chain);
} 

public class Tree<T extends Filterable>{
   private final T data;
   private Tree<T> parent;
   private List<Tree<T>> children;
   private List<FilterChain<T>> filterChain;
   private boolean readonly = false;  
   /*package*/ Tree(T data) {...} 
   /*package*/ Tree(Tree<T> parent, T data) {...}

   //freeze mtd makes object read-only
   /*package*/ void freeze(){         
          readonly = true;
      for(Tree<T> child: children){
          child.freeze();
      }
   }
   public void addChild(Tree<T> child){
       if(readonly){
           throws new NonModifiableException(...);
       }
       children.add(child);
   }
   public List<?> getResults(){
       return data.returnResults(filterChain);
   }

}

Вместо того, чтобы выполнять синхронизацию на дереве, возможно, вы могли бы сосредоточиться на создании синхронизации на построителе дерева

public class TreeBuilder<T>{
    public synchronized TreeNode createRoot(T data);
    public synchronized void addSubElement(TreeNode parentNode ,T data);
    public synchronized void addFilter(TreeNode node, Filter<T> filter);
    public Tree<T> synchronized build(){
       Tree<T> tree= ... 
       //build your tree
       //build filter chain for specific tree node
       tree.freeze(); //make your tree readonly
       return tree;
    }
}
0 голосов
/ 12 февраля 2011

Я не знаю, полезно ли это. Java SortedMap использует красное черное дерево, и вы можете посмотреть исходный код здесь.

 https://www.docjar.com/html/api/org/eclipse/ant/internal/ui/dtd/util/SortedMap.java.html

Для неизменяемой SortedMap. Вы можете увидеть исходный код для Collections.unmodifiableSortepMap здесь

http://www.docjar.com/html/api/java/util/Collections.java.html
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...