1

我看过类似的问题，详细介绍了 Map 的排序和原始数据类型数组的排序，但没有问题直接详细说明 Java Map 的一次性排序与原始数据类型数组 ([]) 之间的区别。

Primary note*我知道“TreeMap”是 Java 中 Map 的排序版本（按键），但我不知道 TreeMap 如何对键进行排序的“幕后”有多少（在添加数据时，或在添加数据完成后）？

Primary note 2*Dijkstra 的算法in this case不是一个精确的实现。我们只是在大小为 M 个节点的图 G 中找到加权边的最短路径。这意味着邻接矩阵（格式见下文）的大小为 M x M。这是not一个 SMART 实现。几乎就像你能得到的基线一样……抱歉造成混乱！

我们得到了一个邻接矩阵，在以下示例中，元素彼此相关（“连接”）：

0,1,5   // 0 is connected to 1, and the weight of the edge is 5
0,2,7   // 0 is connected to 2, and the weight of the edge is 7
0,3,8   // 0 is connected to 3, and the weight of the edge is 8
1,2,10  // 1 is connected to 2, and the weight of the edge is 10
1,3,7   // 1 is connected to 3, and the weight of the edge is 7
2,3,3   // 2 is connected to 3, and the weight of the edge is 3

但不要介意输入，只要假设我们有一个值矩阵来操作。

我们正在考虑将所有可能的路径存储在“最短路径”算法中（我相信 SO 上 75% 或更多的人都知道 Dijkstra 的算法）。这是家庭作业，而是一个实施问题，而不是“为我解决这个问题”。

ASSUME矩阵的大小为very large（大小 M x M），可能大于50x50大小。这将导致[50-1]!/2 = 1.52 × 10^64结果列表中的结果假设我们的算法足够聪明，可以挑选出重复项并且找不到重复路径的长度（事实并非如此，因为我们是图论和 Java 的菜鸟，所以请不要建议任何算法以避免重复...）。

我的朋友说，对 List 中 int[n] 的索引进行临时排序（使用临时变量），其中 int[n] 是last index并且value of the shortest path（ALGORITHM_1）可能比keyMap 是的TreeMap（ALGORITHM_2）更快value of the shortest path. _

我们正在讨论在尝试找到所有lengths最短路径时哪种实现会更快。我们可以将它存储为每个路径的最后一个索引（有一个 int[]，其中最后一个元素是最短路径的值（总和）（数组中的所有元素）（ALGORITHM_1），或者我们可以将该总和存储为地图的 KEY (ALGORITHM_2)。

因为这是一个shortest path algorithm（虽然不是很好......），我们需要按长度（即图中每条边的总和）对每条路径的结果进行排序，以便找到最短路径。

所以真正的问题是：对结果进行排序会更快ONLY ONE TIME吗？通过 Map.sort() 算法（内置在 Java 标准库中）或通过创建一个临时变量来保存每个 int[] 中最新“长度”的值？例如：

myMap.sort(); // Unless TreeMap in Java does 'behind=the-scenes' sorting on keys...
myMap.get(0); // This would return the first element of the map, which is the shortest path

或者

int temp = myList.get(0)[m]; // Store a temp variable that is the 'shortest path'
for( int[] i in myList<int[]>) {
    if (temp > myList.get(i)[m]) { // Check if the current path is shorter than the previous
        temp = myList.get(i)[m]; // Replace temp if current path is shorter
    }
}

Note我还没有真正测试过实现，也没有检查过我自己的 Java 语法，所以我不知道这些语句是否正确声明。这只是一个理论问题。哪个跑得更快？这是我学习 Java 的第三年，我不知道 HashMap 中使用的底层数据结构，也不知道这两种实现的大 O 表示法。

也许了解 Java 标准的人可以描述在 HashMap 与（原始数据类型）[] 中使用了哪种数据结构或实现，以及在ONE-TIME-ONLY某种结构中运行时间的差异可能是什么。

我希望这个调查是有意义的，我感谢任何花时间回答我问题的人；我一直很感激像你们这样慷慨的人为帮助教育新手所付出的时间和精力！

问候，克里斯

4

3 回答 3

2

可能没有必要对数据进行排序以找到最短路径。相反，您可以遍历数据并跟踪您遇到的最短路径。

假设数据存储在 Data 对象数组中， data.pathLength 给出路径长度，

Data[] data; // array of data
Data shortest = data[0]; // initialize shortest variable
for(int i = 1; i < data.length; i++) {
    if(data[i].pathLength < shortest.pathLength)
        shortest = data[i];
}

也就是说，TreeMap 是一棵红黑树，它是平衡二叉树的一种形式。与标准二叉树不同，平衡二叉树将旋转其分支以确保其近似平衡，从而确保 log(n) 查找和插入。红黑树确保最长分支不超过最短分支长度的两倍；AVL 树是具有更严格限制的平衡二叉树。长话短说，TreeMap 将在 n*log(n) 时间内对其数据进行排序（每次插入的 log(n)，乘以 n 个数据点）。假设您使用的是 Mergesort 或 Quicksort 或 Heapsort 等（与 Bubblesort 或其他 n^2 排序算法相反），您的一次性数组排序还将在 n*log(n) 时间内对其数据进行排序。 使用比较排序你不能比 n*log(n) 做得更好；顺便说一句，您可以使用像基数排序这样的转换排序，它的 O(n) 很大，但是转换排序通常会占用内存并且表现出较差的缓存行为，因此您通常最好使用 n*log 之一(n) 比较排序。

由于 TreeMap 和您的自定义排序都是 n*log(n)，这意味着任何一个都没有太大的理论优势，所以只需使用更容易实现的那个。然而，TreeMap 的复杂数据结构并不是免费的，因此您的自定义排序算法可能会表现出稍微更好的性能，例如可能是 2 倍；与使用 TreeMap 相比，这可能不值得实现自定义排序的复杂性，特别是对于一次性排序，但这是您的决定。如果您想尝试提高程序的性能，那么请实现一种适合并行化的排序算法（如 Mergesort），并看看当您将排序任务拆分到多个线程中时会得到多少改进。

于 2013-04-10T03:55:32.853 回答
0

如果您想要最短路径，则不需要排序。只需在完成每条路径时跟踪最短路径，并在遇到较短路径时更新最短路径。这最终会给你一个 O(n)，其中 n 是路径的数量。无论如何，您实际上无法存储 10^64 条路径，因此需要对结果集进行一些截断。

于 2013-04-10T04:01:54.730 回答
0 
 how much about the 'behind-the-scenes' of how TreeMap sorts the keys (either while data   
 is being added, or after the data is FINISHED being added)?

TreeMap使用 RedBlack 树算法（BST 的一种变体），其中操作、containsKey和操作需要 O(log(n)) 时间，这是非常好的。正如 TreeMap 定义（在链接中）解释的那样，每次添加元素后，键都会被排序。排序将花费 O(nlog(n))getputremove

我不确定您为什么要比较 Map 类型 - 它使用键、值对与 Array。您已经提到过使用最短路径的长度作为 TreeMap 中的键，但是您将什么作为值？如果您只想存储“路径长度”，我建议将它们放入数组中并使用Arrays.Sort()对它们进行排序，这也将使用不同的算法 Dual-Pivot Quicksort 在 O(nlog(n)) 中排序。

希望这可以帮助！

于 2013-04-10T04:11:12.397 回答