StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POJava Map vs Array (Temp) Sort of Last Index
text
Body
copied!<p>I have looked at similar questions that detail the sorting of Maps and sorting of arrays of primitive data types, but no question directly details the difference between a one-time sort of a Java Map vs primitive data type array ([]).</p> <p><code>Primary note*</code> I know that 'TreeMap' is the sorted version (by key) of Map in Java, but I don't know 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)?</p> <p><code>Primary note 2*</code> Dijkstra's algorithm <code>in this case</code> is not an EXACT implementation. We are just finding the shortest path of weighted edges in a graph G of size M nodes. This means that adjacency matrix (format seen below) is of size M x M. This is <code>not</code> a SMART implementation. Pretty much just as base-line as you can get... sorry for the confusion!</p> <hr> <p>We are given an adjacency matrix, where elements are related to each other ('connected') in the following example:</p> <pre><code>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 </code></pre> <hr> <p>But never mind the input, just assume that we have a matrix of values to manipulate.</p> <p>We are looking at storing all the possible paths in a "shortest path" algorithm (I'm sure 75% or more of people on SO know Dijkstra's algorithm). This IS for homework, but an implementation question, not a "solve this for me" question.</p> <p><code>ASSUME</code> that the size of the matrix is <code>very large</code> (size M x M), maybe more than <code>50x50</code> in size. This would result in <code>[50-1]!/2 = 1.52 × 10^64</code> results in the result list assuming that our algorithm was smart enough to pick out duplicates and not find the length of a duplicate path (which it is not, because we are noobs at Graph Theory and Java, so please don't suggest any algorithm to avoid duplicates...).</p> <hr> <p>My friend says that a temp sort (using a temporary variable) on an index of int[n] in a List, where int[n] is the <code>last index</code> and <code>value of the shortest path</code> (ALGORITHM_1) may be faster than TreeMap (ALGORITHM_2) where the <code>key</code> of the Map is the <code>value of the shortest path</code>.</p> <p>We were debating as to what implementation would be faster in trying to find ALL <code>lengths</code> of the shortest path. We can store it as the last index of each path (have an int[] where the last element is the value (sum) of the shortest path (all elements int the array) (ALGORITHM_1), OR we can store that sum as the KEY of the Map (ALGORITHM_2).</p> <p>Because this is a <code>shortest path algorithm</code> (albeit not a great one...), we NEED to sort the results of each path by length, which is the sum of each edge in the graph, in order to find the shortest path.</p> <hr> <p>So the real question is: what would be faster in sorting the results <code>ONLY ONE TIME</code>? Through a Map.sort() algorithm (built into the Java standard library) or through creating a temporary variable to hold the value of the most recent 'length' in each int[]? For example:</p> <pre><code>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 </code></pre> <p>OR</p> <pre><code>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 } } </code></pre> <hr> <p><code>Note</code> that I haven't actually tested the implementations yet, nor have I checked my own Java syntax, so I don't know if these statements are declared correctly. This is just a theoretical question. Which would run faster? This is my 3rd year of Java and I don't know the underlying data structures used in HashMap, nor the Big O notation of either implementation.</p> <p>Perhaps someone who knows the Java standard could describe what kind of data structures or implementations are used in HashMap vs (Primitive data type)[], and what the differences in run times might be in a <code>ONE-TIME-ONLY</code> sort of the structures.</p> <p>I hope that this inquiry makes sense, and I thank anyone who takes the time to answer my question; I always appreciate the time and effort generous people such as yourselves put into helping to educate the newbies!</p> <p>Regards, Chris</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload