Subject: RE: [hackers-il] Do Faster Computers Imply Slower Code?

From: Chen Shapira <[email-masked]>
Date: Sun, 2 Jun 2002 14:27:47 +0200

> The STL specification recommends (I think the word it uses is 
> 'should') an O(1) implementation, MS do have a good reason for 
> their choice, but as long as different implementations use 
> different algorithms, STL code is not portable, at least 
> performance-wise.

1. Checking the specification here:
http://www.sgi.com/tech/stl/index.html
The only complexity specification on Deque there, is the same one on a
container. That is - linear in the number of elements.
So it actually is standard, but less efficient than other implementation.
You were counting on a non-standard feature.

2. I have no pointer here, but AFAIK, they actually compute the size of
deque by pointer arithmethics.
They keep the deque in several fixed size arrays, and they go over those
arrays. Its still O(n), but not as silly as going over all the elements.

---

From: Shlomi Fish <[email-masked]>
Date: Sun, 2 Jun 2002 14:44:10 +0300 (IDT)

> arrays. Its still O(n), but not as silly as going over all the elements.

One can explicitly calculate the size of the deque according to the number
of elements that were inserted and extracted. It makes for slightly slower
modifications, but a much faster length lookup.

As a side note, I should add that it is possible to initialize an array in
O(1) time, but this time with a slower lookups (but still such that are
O(1)):

http://www.cis.ohio-state.edu/europa/projects/0015/#references

Regards,

	Shlomi Fish

>
>
> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"