Java: имея коллекцию элементов, где каждый элемент имеет поле «previousItem», каков наиболее эффективный способ заказа коллекции? - PullRequest
Новая
       8

Java: имея коллекцию элементов, где каждый элемент имеет поле «previousItem», каков наиболее эффективный способ заказа коллекции?

0 голосов
/ 12 марта 2012

У меня есть коллекция иерархических элементов в несортированной коллекции.Каждый из этих элементов имеет поле previousItem: 

public class Item{
   public Item previousItem;
}

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

Моей первой идеей было бы реализовать интерфейс Comparable в классе Item: 

public int compareTo(Item that) {
    final int BEFORE = -1;
    final int EQUAL = 0;
    final int AFTER = 1;

    if(this.previousItem==null){
        return BEFORE;
    }

    if(that.previousItem==null){
        return AFTER;
    }

    if(this.previousItem.equals(that){
        return AFTER;
    }else if(that.previousItem.equals(this){
        return BEFORE;
    }

    return EQUAL;
}

, а затем выполнить цикл по элементам и добавитьих к TreeSet: 

SortedSet<Item> itemSortedSet = new TreeSet<Item>();
for (Item item : itemCollection) {
    itemSortedSet.add(item);
}

Есть ли более эффективный способ (меньше времени на обработку / необходимое количество итераций), чтобы упорядочить коллекцию так, чтобы они были в логическом, иерархическом порядке?

Ответы [ 4 ]

6 голосов
/ 12 марта 2012

Ваш компаратор не будет работать: он не обеспечивает транзитивность, то есть он будет работать неправильно, если вы сравните элементы A и C в случае A-> B-> C.

Если ни один элемент не может иметь такой же предыдущий элемент, ваши Item объекты по существу образуют базовый связанный список. Если вам известно, что это последний элемент, вы можете начать с одного цикла и распутать всю структуру: 

Item last = ...;

while (last != null) {
    result.add(last)
    last = last.previousItem
}

Если у вас нет способа узнать, какой элемент является последним, вы можете использовать IdentityHashMap, чтобы сопоставить каждое значение previousItem с объектом Item, который его использует : 

IdentityHashMap<Item,Item> m = new IdentityHashMap<Item,Item>(itemset.size());

for (Item i : itemset)
    m.put(i.previousItem, i);

Item i = m.get(null);

while (i != null) {
    result.add(i);

    i = m.get(i);
}

Это распутает вашу несортированную коллекцию, начиная с элемента, у которого нет предыдущего узла.

Оба метода имеют приблизительно линейную сложность w.r.t. количество предметов, но они делают два предположения, которые могут быть недействительными в вашем случае:

  • То, что каждый элемент может быть только предыдущим элементом не более одного другого узла, т. Е. Что ваши элементы представляют собой список вместо дерева.

  • То, что существует одна «нить» предметов.

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

0 голосов
/ 12 марта 2012

Вы можете использовать HashSet<Item>, в который вы изначально положили все предметы.Затем вы перебираете элементы в цикле и удаляете все previousItem из своего набора.В конце вы должны остаться с единственным элементом в наборе, последним, который не был previousItem для любого другого предмета.И тогда вы можете просто добавлять элементы, начиная с этого и переходя по ссылкам.

0 голосов
/ 12 марта 2012

Если я вас правильно понял, у вас есть дескриптор объекта Item без предыдущего объекта.Вы можете просто пройти по элементам (например, с помощью цикла while) и добавить их в ArrayList или LinkedList, потому что метод add () этих реализаций List просто добавляет новый элемент в конец списка.Таким образом, вы пройдете через O (n) -time.

0 голосов
/ 12 марта 2012

Из того, что я вижу, ваш Предмет уже реализует связанный список (если не по имени), поэтому естественный (для меня) способ поместить его в коллекцию - рекурсивно преобразовать его в реальный список.После преобразования элементов вам может потребоваться перевернуть список в соответствии с вашей спецификацией. 

public class Item {
   Item previousItem;

   public void putToCollection(ArrayList<Item> list) {
     list.add(this);
     if (previousItem == null) {
       Collections.reverse(list);
     } else {
       previousItem.putToCollection(list);
     }
   }
}
...