[erlang-questions] To name a function
Attila Rajmund Nohl
Thu Dec 16 11:28:32 CET 2010
2010/12/16, Raimo Niskanen <raimo+erlang-questions@REDACTED>:
> On Thu, Dec 16, 2010 at 09:44:29AM +0100, Morten Krogh wrote:
>> As soon as you have seen both an element that satisfies the condition
>> and one that doesn't, you can return "some", making a full list
>> traversal overkill for many inputs.
> To support that idea (regardless of what this thread is about,
> I am just throwing in an observation), if you have to traverse
> a list once - you have linear speed complexity; O(N).
> If you instead do it twice this does not change, you just
> get a constant factor speed degradation.
> If you (sub- ?) optimize by traversing the list once but do
> more work by building intermediate results of which most
> are uninteresting - you stress the garbage collector
> which makes the speed complexity harder to determine.
> You probably get anything from a large constant factor speed
> degradation to even O(N*log(N)) .. O(N*N).
> Therefore it is often a good idea to first traverse the list
> without building garbage to decide if you can skip the term building
> traversal entirely, unless it is obvious this rarely happens.
That probably explains why was the "traverse the list 3 times" faster
for smaller lists than the "traverse the list only once"...
More information about the erlang-questions