2

我订阅了一个数据提要，并使用 INSERT/DELETE 消息上的索引值创建和维护一个结构。我想问一下组装好的行家，他们是否知道任何可以有效处理零碎更新的算法——通常批量更新包含两到六个这样的消息。

数组的估计大小约为 1000 个元素。

批量更新作为按索引排序的消息列表到达，它规定在给定索引处插入或删除项目。我预计数组中的大部分流失都比结束更接近开始。

我突然想到，通过一些基本处理，我可以确定受批次影响的范围和整体大小增量，因此只移动一次数组的未受影响的尾部。

同样，我可以在第一个元素之前和最后一个元素之后保留一定数量的可用空间，以尽可能减少复制量。

其他优化包括识别更新，如下所示：

DELETE 10, INSERT 10 - effectively a replace which requires no copying  
INSERT 10, DELETE 11 - as above  
DELETE 10, DELETE 10, DELETE 10 - bulk deletion can be optimised into one copy operation  
INSERT 11, INSERT 12, INSERT 13 - bulk insertion can be optimised into one copy operation

等等。

但是，我对执行识别步骤的开销持谨慎态度——它带有前瞻和回溯的味道，这可能比简单地执行复制需要更多时间。

鉴于数组的预期大小，树结构似乎重量级：一些基本性能测试表明二叉树或自平衡树（在本例中为红黑树列表实现）仅在大约 15K - 20K 个元素后才开始显示性能优势：数组副本在较小的尺寸下明显更快。我可能应该补充一点，我正在使用 Java 进行此实现。

欢迎任何提示、提示或建议。

干杯

麦克风

4

8 回答 8

2

始终权衡代码清晰度与优化。如果现在没有性能问题，只需确保代码清晰即可。如果将来出现性能问题，那么您就会知道它的确切性质。现在为它做准备是一种猜测的练习。

如果您需要进行大量操作，则链表可能是值得的。

但是，对于简单清晰的代码，我会使用 apache commons collection utils 来处理原始数组或数组列表：

myArray = ArrayUtils.add(myArray, insertionIndex, newItem);

或者

ArrayList<> mylist = new ArrayList<>(Arrays.asList(myArray));
myList.add(insertionIndex, newItem);
于 2010-09-01T19:36:21.970 回答
2

一般来说，如果您有按索引顺序列出的更改，您可以构建一个只复制一次的简单循环。这是一些伪代码：

array items;
array changes; // contains a structure with index, type, an optional data members
array out; // empty, possibly with ensureCapacity(items.length)
int c = 0, delta = 0;
// c is the current change
//delta tracks how indexing has changed by previous operations
for (i = 0; i < items.length; i++) {
    if c < changes.length {
        curchange = changes[c]
        if (i + delta) == curchange.index {
            c++;
            if (curchange.type == INSERT) {
                out.add(curchange.data)
                delta--;
            } else {
                delta++;
                continue; // skip copying i
            }
        }
    }
    out.add(items[i])
}
for (; c < changes.length; c++) { // handle trailing inserts
    assert(c.index == out.length && c.type == INSERT)
    out.add(c.data);
}

这将遍历输入数组一次，并使用所做的所有更改构建输出数组。

请注意，这不会处理同一位置的多个插入。这样做会使代码更加复杂，但这并不难。

但是，它总是会一直运行通过阵列，每批一次。稍微强硬的更改是保留一个临时变量并使用两个索引变量就地进行更改；然后，如果您到达更改列表的末尾，您可以提前跳出循环而不触及列表的其余部分。

于 2010-09-01T19:55:50.873 回答
0

有一个非常简单的实现数据结构，名为“笛卡尔树”或“Treaps”，它允许对数组（以及更多东西）进行 O(log N) 拆分、连接、插入和删除。

2-3棵树也很容易实现（我实现的一个稍微复杂的设施在第一次编译后只有一个错误）并且符合您的目的。

于 2010-09-01T19:37:58.250 回答
0

If space is not a constraint and you are not going to have duplicates, go for Set datastructure, in particular Java's HashSet. The power of this data structure is the insertion and deletion are done in O(1) time which would best suit you if performance is 'the' criterion.

Moreover, whenever you speak of Arrays besides their fast retrieval, you have the serious limitation of numerous array copies that might happen which not only is going to take up space (for array growth) but also the efficiency will be poor as each of Insert/Delete might take O(n) time.

于 2010-09-01T19:41:48.303 回答
0

使用链表 ( java.util.LinkedList) 可能值得研究。在特定索引处获取元素当然是昂贵的，但它可能比执行数组复制更好。

于 2010-09-01T19:32:39.390 回答
0

最简单的方法是运行更新并在应用更新时将数组复制到新数组中。

1000并没有那么大，可能不值得进一步优化。

为了让您的生活更轻松，更好地使用ArrayList.

于 2010-09-01T19:23:43.793 回答
0

如果这确实是您的数据集的样子，您可能会考虑使用 Collection（如 HashMap）进行重复跟踪。Array 将是您按顺序列出的每个活动的有序列表，而您的 Collection 将是该数组的索引。

例如：

类事件队列
{
  向量事件队列；
  哈希映射事件映射；

  公共同步事件 getNextEvent()
  {
      事件事件 = eventQueue.remove(0);
      eventMap.remove(event.getId()); // 这将是 'INSERT 10' 中的 10
                                       // 在来自 OP 的样本中
  }

  公共同步添加事件（事件 e）
  {
     if(eventMap.containsKey(e.getId())
     {
        // 替换已经存在的事件
        int idx = eventMap.get(e.getId());
        eventQueue.removeElementAt(idx);
        eventQueue.add(idx, e);
     } 别的 {
        // 添加新事件
        eventQueue.add(e);
        eventMap.add(e.getId(), eventQueue.size()); // 可能相差一个...
     }
  }

  公共布尔 isReady()
  {
    返回 eventQueue.size() > 0;
  }
}

类 FeedListener 扩展线程 {
 事件队列队列；
 EventFeed 提要；
 ...
 公共无效运行（）
 {
    在跑步的时候） {
       睡眠（睡眠时间）；
       如果（饲料.isEventReady（））{
         queue.addEvent(feed.getEvent());
       }
    }
 }
}

抽象类 EventHandler 扩展线程 {
 事件队列队列；
 ...
 公共无效运行（）
 {
   在跑步的时候）
   {
     睡眠（睡眠时间）；
     如果（队列.isReady（））
     {
       事件事件 = queue.getNextEvent();
       处理事件（事件）；
     }
   }
 }

 公共抽象无效句柄事件（事件事件）；
}
于 2010-09-01T20:01:50.900 回答
0

除了对单个更新进行排序（如您已经提到的）以尝试合并事物之外，我不知道我会打扰太多。坦率地说，1000 个元素在大范围内算不上什么。我有一个包含 2500 万个元素的系统，使用简单的批量复制，它（就我们的目的而言）远远超过足够快的速度。

所以，我不会戴上“未成熟优化”的帽子，但我可能会先在书架上看一眼。

于 2010-09-01T19:26:44.490 回答