3

我的问题总结：我需要一个可以快速迭代和排序的列表（通过排序方法或添加/删除对象）。

我正在编写一个游戏，其中有很多“碰撞区域”，每帧都会检查。为了优化，我有一个想法，根据它们的 X 位置对它们进行排序。问题不是所有的碰撞区域都是静态的，因为其中一些可以移动。

我已经设法处理了所有的更改，但是维护ArrayList（或ConcurrentLinkedQueue）排序使用Collections.sort()太慢了。

所以我有了一个新的想法：我可以使用树，每当一个区域的 X 发生变化时，我就可以从树中删除然后重新添加它，而不是再次对所有元素进行排序。但是，我认为在 TreeList 中添加和删除运算符也很昂贵。此外，遍历 Tree 不如ConcurrentLinkedQueue,LinkedList或有效ArrayList。

请告诉我是否有任何满足我需要的内置数据结构。如果没有这样的数据结构，我打算扩展ArrayList类，重写add方法以确保顺序（通过使用重载add(index, item)。如果您认为这是最好的方法，请给我找到索引的最佳方法。我已经使用 BinarySearch但我认为有一个错误：

@Override
public boolean add(T e) {
    // Find the position
    int left = 0;
    int right = this.size() - 1;
    int pos = right / 2;
    if (e.compareTo(this.get(0)) <= 0) {
        pos = 0;
    } else if (e.compareTo(this.get(this.size() - 1)) >= 0) {
        pos = this.size();
    } else {
        // Need: e[pos - 1] <= e[pos] <= e[pos + 1] 
        boolean firstCondition = false;
        boolean secondCondition = false;

        do {
            firstCondition = this.get(pos - 1).compareTo(this.get(pos)) <= 0;
            secondCondition = this.get(pos).compareTo(this.get(pos + 1)) >= 0;

            if (!firstCondition) {
                right = pos - 1;
                pos = (left + right) / 2;
            } else if (!secondCondition) {
                left = pos + 1;
                pos = (left + right) / 2;
            }
        } while (!(firstCondition && secondCondition));
    }

    this.add(pos, e);

    return true;
}
4

3 回答 3

1

我会使用树集。如果您需要允许重复，您可以使用自定义比较器。虽然迭代树集比数组稍慢，但添加和删除要快得多。

看来您正在执行 O (n) 的插入排序。树集上的插入是 O (ln n)

TreeMap<MyKey, List<MyType>>恕我直言，使用这样的存储重复项的最佳方法

Map<MyKey, List<MyType>> map = new TreeMap<>();
// to add
MyType type = ...
MyKey key = ...
List<MyType> myTypes = map.get(key);
if (myTypes == null)
    map.put(key, myTypes = new ArrayList<>());
myTypes.add(type);

// to remove
MyType type = ...
MyKey key = ...
List<MyType> myTypes = map.get(key);
if (myTypes != null) {
    myTypes.remove(myType);
    if (myTypes.isEmpty())
        map.remove(key);
}

在这种情况下，添加和删除是 O(ln N)；

您可以通过将所有对象定义为不同的方式来允许“重复”是 TreeSet

Set<MyType> set = new TreeSet<>(new Comparator<MyType>() {
   public int compare(MyType o1, MyType o2) {
      int cmp = /* compare the normal way */
      if (cmp == 0) {
          // or use System.identityHashCode()
         cmp = Integer.compare(o1.hashCode(), o2.hashCode());
         return cmp == 0 ? 1 : cmp; // returning 0 is a bad idea.
      }
   }
}

如您所见，除非您有某种方法可以使每个对象都独一无二，否则这种方法很丑陋。

于 2012-12-22T10:55:37.527 回答
0

听起来你想要一个TreeSet。

于 2012-12-22T10:53:30.240 回答
0

如果您打算在已排序的数组或 ArrayList 上使用二进制搜索/插入，那么您将获得与二叉树相同的大 O 复杂度。

所以我建议您实际测试提供的树实现（即TreeSet），而不仅仅是猜测。由于它们不是普通的树实现，如果它们的迭代速度也很快，我不会感到惊讶。

于 2012-12-22T10:53:55.110 回答