[erlang-questions] To name a function

[Attila Rajmund Nohl]

2010/12/16, Raimo Niskanen <raimo+erlang-questions@REDACTED>:
> On Thu, Dec 16, 2010 at 09:44:29AM +0100, Morten Krogh wrote:
>> Hi
>>
>> 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"...