Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It may not be necessary to sort your data in order to find the shortest path. Instead, you could iterate through the data and keep track of the shortest path that you've encountered.</p> <p>Assuming the data is stored in an array of Data objects, with data.pathLength giving the path length,</p> <pre><code>Data[] data; // array of data Data shortest = data[0]; // initialize shortest variable for(int i = 1; i &lt; data.length; i++) { if(data[i].pathLength &lt; shortest.pathLength) shortest = data[i]; } </code></pre> <p>That said, TreeMap is a <a href="http://en.wikipedia.org/wiki/Red%E2%80%93black_tree" rel="nofollow">Red-Black Tree</a>, which is a form of balanced binary tree. Unlike a standard binary tree, a balanced binary tree will rotate its branches in order to ensure that it is approximately balanced, which ensures log(n) lookups and insertions. A red-black tree ensures that the longest branch is no more than twice the length of the shortest branch; an <a href="http://en.wikipedia.org/wiki/AVL_tree" rel="nofollow">AVL Tree</a> is a balanced binary tree with even tighter restrictions. Long story short, a TreeMap will sort its data in n*log(n) time (log(n) for each insertion, times n data points). Your one-time array sort will also sort its data in n*log(n) time, assuming you're using Mergesort or Quicksort or Heapsort etc (as opposed to Bubblesort or another n^2 sort algorithm). <a href="http://en.wikipedia.org/wiki/Comparison_sort" rel="nofollow">You cannot do better than n*log(n) with a comparison sort</a>; incidentally, you can use a transformation sort like <a href="https://en.wikipedia.org/wiki/Radix_sort" rel="nofollow">Radix Sort</a> that has a big-oh of O(n), but transformation sorts are usually memory hogs and exhibit poor cache behavior, so you're usually better off with one of the n*log(n) comparison sorts.</p> <p>Since TreeMap and your custom sort are both n*log(n), this means that there's not much theoretical advantage to either one, so just use the one that's easier to implement. TreeMap's complex data structure does not come free, however, so your custom sorting algorithm will probably exhibit slightly better performance, e.g. maybe a factor of 2; this probably isn't worth the complexity of implementing a custom sort as opposed to using a TreeMap, especially for a one-shot sort, but that's your call. If you want to play around with boosting your program's performance, then implement a sorting algorithm that's amenable to parallelization (like Mergesort) and see how much of an improvement that'll get you when you split the sorting task up among multiple threads.</p>
    singulars
    1. This table or related slice is empty.
    1. POJava Map vs Array (Temp) Sort of Last Index
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USZim-Zam O'Pootertoot
    1. USZim-Zam O'Pootertoot
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POJava Map vs Array (Temp) Sort of Last Index
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COI learned about Red-Black Tress in CIS 263 last semester. I didn't fully understand how they functioned (by adjusting themselves based on what values are on the next 'level' to maintain balance)... I understand that this implementation occurs in TreeMaps, as it makes sense entirely. I also understand that my 'custom sort' based on the last value of an int[] are both O(NlogN). Running through some custom data, I recognize these Big O patterns. Your idea seems the same as my friends, where you simply keep track of the shortest path by looking at the previous shortest path. This seems efficient.
      singulars
      1. PO
      1. USChris Cirefice
    2. CONOBODY fully understands how red-black trees work, except for the ten people in the world who implement them for language libraries.
      singulars
      1. PO
      1. USZim-Zam O'Pootertoot
    3. COContinuation from my previous comment... from what you've said, it seems that the implementation of TreeMap (red-black tree) in Java is very similar to keeping track of the latest value in the shortest pat (which is the last index of the int[] in ALGORITHM_1). This is all arbitrary of course because it's just a simple homework assignment based on gathering ~10 nodes from an input file, but I just wanted to clarify the difference between TreeMap sorting and int[] sorting. I remember the AVL and red-black trees now, so both methods seem easily applicable to the context. Thank you very much :)
      singulars
      1. PO
      1. USChris Cirefice
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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