Also, it seems like O(N²) on splice is a worst case, where best case (either all or no deletions) would be O(N), leading me to think it'd be closer to O(N log N) in practice.

I tried all N=16 inputs:

0 elements were shifted 1 times
16 elements were shifted 16 times
31 elements were shifted 120 times
45 elements were shifted 560 times
58 elements were shifted 1820 times
70 elements were shifted 4368 times
81 elements were shifted 8008 times
91 elements were shifted 11440 times
100 elements were shifted 12870 times
108 elements were shifted 11440 times
115 elements were shifted 8008 times
121 elements were shifted 4368 times
126 elements were shifted 1820 times
130 elements were shifted 560 times
133 elements were shifted 120 times
135 elements were shifted 16 times
136 elements were shifted 1 times
98 elements where shifted on average
[download]

The average result is 98, which is about twice O(N log N). So,
Average case
= O({loop body cost}*N + {element shift cost}*N log N)
= O(N + N log N)
= O(N log N)

The thing is, the worst case is also in the same order, so
Worse case
= O(N log N)

I accept your better average case, and I propose a better worst case than we both thought.

I read this to mean that while naive implementation would have yielded O(N2), perl is smart enough that the exponent drops (closer) to O(N). Is this incorrect?

A naïve implementation of push would take O(N) for every element pushed. Currently, it takes O(1) for most pushes, and O(N) on occasion.

@a = qw( a b c );

+---+---+---+---+
| a | b | c | / |      / = allocated, but unused.
+---+---+---+---+

push @a, 'd';

+---+---+---+---+
| a | b | c | d |
+---+---+---+---+

push @a, 'e';

+---+---+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | / | / | / | / | / | / | / |
+---+---+---+---+---+---+---+---+---+---+---+---+
[download]

It only preallocates so much. As soon as the preallocated memory is used up, a new memory block is alocated. the whole array must be copied. The shift-push solution is therefore O(N * N*{chance of reallocation needed}) which probably ressembles worse/average case O(N log N).

So I that makes the scalability as follows:

• The grep solution you provided uses O(N) time and O(N) memory.
• The splice solution you provided uses O(N log N) time and O(1) memory.
• The shift-push solution you provided uses O(N log N) time and O(N) memory.
• The shift-push solution I provided uses O(N) time and O(N) memory.

The crux of my question though was supposed to be about the constant in front of the memory term, particularly as all scale equivalently in memory.

I thought you were more interested in speed, sorry.

• splice is done in-place. (Assuming you get rid of the reverse!!)
• grep probably uses N SV* extra memory. It could possibly be done in place.
• My shift-push uses N SV* extra memory.
• Your shift-push uses between N and 5*N SV* (peak), and between N and 3*N SV* (final) extra memory.

Pushing slightly more than doubles the allocated memory when a reallocation is forced. If N' is the number of elements kept, 3*N is 2*(N+N') when N'=N, minus the initial memory. The peak occurs when copying the pointers from the old memory block to the new memory block.

---

---

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! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

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:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

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

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