Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><code>ArrayList</code> is backed by an array. Typically, addressing something by index is assumed to be <code>O(1)</code>, i.e., in constant time. In assembly, you can index into a memory location in constant time, as there are certain <code>LOAD</code> instructions that take an optional index in addition to a base address. Arrays are usually allocated in memory in a contiguous block. For example, assume you have a base address of <code>0x1000</code> (where the array starts) and you provide an index of <code>0x08</code>. This means that for your array starting at <code>0x1000</code> you want to access the element at location <code>0x1008</code>. The processor only needs to add the base address and the index, and look up that location in memory<sup>*</sup>. This can happen in constant time. So assume you have the following in Java:</p> <pre><code>int a = myArray[9]; </code></pre> <p>Internally, the JVM will know the address of <code>myArray</code>. Like our example, let us assume that it is at location <code>0x1000</code>. Then it knows that it needs to find the <code>9</code>th subscript. So basically the location it needs to find is simply:</p> <pre><code>0x1000 + 0x09 </code></pre> <p>Which gives us:</p> <pre><code>0x1009 </code></pre> <p>So the machine can simply load it from there.</p> <p>In C, this is actually a lot more evident. If you have an array, you can access the <code>i</code>th location as <code>myArray[i]</code> like in Java. But you can access it via pointer arithmetic too (a pointer contains an address of the actual value the pointer points to)! So if you had a pointer <code>*ptrMyArray</code>, you can access the <code>i</code>th subscript by doing <code>*(ptrMyArray + i)</code>, which is exactly as I described: base address plus subscript!</p> <p>In contrast, the worst case for accessing a location in a <code>LinkedList</code> is <code>O(n)</code>. If you recall your data structures, a linked list usually has a <code>head</code> and a <code>tail</code> pointer, and each node has a <code>next</code> pointer to the next node. So to find a node, you have to start with <code>head</code> and then inspect each node in turn until you get to the right one. You cannot simply index into a location either since there is no guarantee that the nodes of the linked list are next to each other in memory; they could be anywhere.</p> <p><sup>*</sup>Indexing must also take into account the size of the element, since you have to take into account how much space each element is taking. The basic example I provided assumes that each element only takes up a byte. But if you have larger elements, the formula is basically <code>BASE_ADDRESS + (ELEMENT_SIZE_IN_BYTES * INDEX)</code>. In our case, where we assume a size of <code>1</code> byte, the formula reduces to <code>BASE_ADDRESS + INDEX</code>.</p>
    singulars
    1. This table or related slice is empty.
    1. POJava: What is index based access of arrays and why are they fast?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USVivin Paliath
    1. USVivin Paliath
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POJava: What is index based access of arrays and why are they fast?
      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. CO+1, this is exactly what I wanted to understand. Thank you! Question: When you said 0x08, it roughly translates to something like Object o = arr[8]; in the code right?
      singulars
      1. PO
      1. USPhantomReference
 

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