comment on

I'll concede that splice, as currently implemented, is O(N) (much as I hate to say that).

That said, splice, shift, and unshift could all become O(1) if the following were to happen:

Whenever a shift happens, that space is kept at the front of the array and the internal starting point gets moved. (This already happens, I believe).
Whenever a mutation is made that would force a reshuffle, instead a pointer is made to another area (kind of like an arrayref). This would mean that bookkeeping would have to be instituted so that the memory location can be found in the case of a random access. I haven't written this bookkeeping code, but my gut says that it's not too squirrelly. This would work for both unshift and splice.
In the case of a normal interaction with the array, no shuffling would occur, so this would just entail a single extra check into the bookkeeping data structure to determine that there is no special bookkeeping.

I suppose I could write up a Tie::Array that would do this. In thinking about it, this may sound like a proper solution for DBM::Deep's arrays. What do you think?

My criteria for good software:

Does it work?
Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

In reply to Re^7: Array VS Linked List (reality) by dragonchild
in thread Array VS Linked List by asset

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		`&`
	<		`<`
	>		`>`
	[		`[`
	]		`]`

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.