4

我需要创建一个基于链表、数组和常量内存使用的数据结构。

作为输入，我得到两个数字：N 和 M。

N代表密钥盘的最大容量，M代表计算机硬盘的最大容量，所以M>N。

所以我需要创建一个程序，将信息从硬盘驱动器“移动”到密钥磁盘，该程序需要实现以下方法：

  1. 插入（数据） - 将数据插入密钥磁盘，如果它已满，则删除最不重要的数据（*）：最坏情况运行时 O(1)。
  2. delete(data) - 从磁盘上删除给定的数据 - O(1)

(*) 用户可以更改文件的重要性。

最大内存使用量为 O(M)

到目前为止我做了什么：

我创建了一个数组 [1...M] 来“保存”计算机数据，我创建了一个双向链表来保存磁盘键数据。[想法是：每次将数据添加到disk-on-key时，它都会添加到链表中，我可以使用数组作为索引（/key）存储直接访问数据。]

我的电脑数据字段：

node firstNode;
node currentNode; 
node[] dataCollection; // Will hold computer hard-drive data

所以我想创建一个方法，用我想添加的数据替换最不重要的数据[这样我就可以在插入中使用]，我的替换代码：

public void replace(int leastImportantdata, int insertData){
    node leastImportant = dataCollection[leastImportantdata];
    if (leastImportant.prev!=null) leastImportant.prev.next=dataCollection[insertData-1];
    if (leastImportant.next!=null) leastImportant.next.prev=dataCollection[insertData-1];
    numOfReplacements++;

所以，我的主要问题是在给定这两个“组合”数据结构的情况下找到最不重要的数据，并且仍然保持 O(1) 的运行时间，尤其是当用户决定更改文件重要性时。

  • 假设我们从 {4,3,2,1} 开始（数字代表重要性），最不重要的数据是 1。突然，用户决定将最后一个文件的重要性更改为 5，我们得到 {4,3,2, 5}，最不重要的数据是 2。

任何想法？

4

2 回答 2

-1

为了能够找出最不重要的数据，您需要将订单添加到您的列表中。

那么首先想到链表的顺序是否重要？您似乎是根据索引而不是通过遍历列表来获取数据。（如果该顺序很重要，那么我的其余答案可能不是很有帮助：D）。

这意味着您可以潜在地将项目插入列表，以便按最低优先级对它们进行排序，这将允许您以恒定的性能获得要删除的项目，只要您有对列表头部的引用。

不幸的是，这会导致插入的复杂性上升。要解决此问题，您可以将优先级映射保留到具有该优先级的链接列表中的最后一个（也可能是第一个）文件。

使用此映射，您应该能够立即找出需要插入新文件的位置，从而获得稳定的性能。

所以如果你有 3 个文件 P(A) = 1 ， P(B) =3 ， P(C) = 3，你的地图看起来像 1->(A,A) 3->(B,C) 说如果你想插入另一个优先级为 1 的文件，它应该在 A 之后，如果你想插入一个优先级为 2 的文件，它应该在 B 之前。

显然，我在这里假设有限数量的可能优先级，并且使用的优先级之间没有差距。（这需要搜索）

希望这可以帮助

于 2013-04-06T18:09:45.900 回答
-1

我对解决您的问题的建议如下：

  • 定义节点类来实现 Comparable 接口。

  • 将数据收集实现为跳过列表 - 您可以通过使用ConcurrentSkipListMap来做到这一点。

使用 SkipList 实现可以确保条目按重要性排序。

根据 Java API doc - 此类 ( ConcurrentSkipListMap ) 实现了 SkipLists 的并发变体，为 containsKey、get、put 和 remove 操作及其变体提供预期的平均 log(n) 时间成本。

通常，该实现允许以与平衡二叉搜索树相当的效率进行项目查找（即，探测器的数量与 log n 而不是 n 成正比）。

最后在 [这里]了解更多关于 SkipList 的信息，以及如何编写自己的实现。

于 2013-04-06T18:18:21.957 回答