StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Well, I have been thinking and thinking and I think it is possible.</p> <p>The solution is however not ideal, because it may be O(1) in the beginning, but O(n) dependency is still there, however for some type of data and usage, it should be near the constant time. So it depends if it is useful to you (the number of changes is dramatically less compared to length of arrays and/or number of operations).</p> <p>For every delete, you should add into the "list of changes" that change. For example, you delete the line no. 10, so you add into your list : "above no. 10, subtract 1".</p> <p>When counting the right line, you have to subtract/add through the "list of changes".</p> <p>Also you need one more array, which contains the last subtracted/added number used and the number of "list of changes", so you don't have to count the changes already counted for that line.</p> <p>In worst case it is still "a*n", where a is some constant.</p> <hr> <p>Example :</p> <pre><code>rows, cols = 1000; delete(row,573); //=> list_of_changes[0] = {573, 'deleted'} access_row(581) //=> help_array[581] = {-1, 1} //=> help_array.structure = {"how much add/subtract on this line", "number of changes used"} access_row(581) //=> look at the help_array[581] seeing having used 1 change, // the size of list_of_change is 1, so you don't have to count // anything, using the -1 value. - constant time </code></pre> <hr> <p>Of course, if I delete row[0] and then I access all the 0..998 values, it will be the O(n) cause it has to count n times the help_array.</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