Java Map vs Array(Temp)排序的最后一个索引

Question

我看过类似的问题，详细介绍了 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 的菜鸟，所以请不要建议任何算法避免重复...)。

我的 friend 说对 List 中 int[n] 的索引进行临时排序(使用临时变量)，其中 int[n] 是 last index和 value of the shortest path (ALGORITHM_1) 可能比 TreeMap (ALGORITHM_2) 更快，其中 key map 的value of the shortest path .

我们正在讨论在尝试查找 ALL lengths 时哪种实现会更快。的最短路径。我们可以将它存储为每个路径的最后一个索引(有一个 int[]，其中最后一个元素是最短路径的值(总和)(数组中的所有元素)(ALGORITHM_1)，或者我们可以将该总和存储为 map 的 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 中。那种结构。

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

问候，
克里斯

Answer 1

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

假设数据存储在 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 是 Red-Black Tree ，这是平衡二叉树的一种形式。与标准二叉树不同，平衡二叉树将旋转其分支以确保其近似平衡，从而确保 log(n) 查找和插入。红黑树保证最长分支不超过最短分支长度的两倍；一个 AVL Tree是具有更严格限制的平衡二叉树。长话短说，TreeMap 将在 n*log(n) 时间内对其数据进行排序(每次插入的 log(n)，乘以 n 个数据点)。假设您使用的是 Mergesort 或 Quicksort 或 Heapsort 等(与 Bubblesort 或其他 n^2 排序算法相反)，您的一次性数组排序还将在 n*log(n) 时间内对其数据进行排序。 You cannot do better than n*log(n) with a comparison sort ;顺便说一下，您可以使用像 Radix Sort 这样的转换排序。具有 O(n) 的大哦，但转换排序通常是内存占用并且表现出较差的缓存行为，因此您通常最好使用 n*log(n) 比较排序之一。

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