Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg <incal@dataswamp.org>]

Jean Louis wrote:

>> You certainly don't need to remove all nils from the list.
>> If your list is 100,000,000 elements long and the first
>> element is t, why would you want to copy the entire list
>> and then remove all the nils from it? Testing the first
>> element tells you the answer.
>
> [...] What I know is that by testing the first element does
> not tell the answer if list has any non nil element:
>
> (let ((my-list '(nil nil nil nil)))
>     (car my-list)) ⇒ nil
>
> (let ((my-list '(nil nil nil nil 1)))
>     (car my-list)) ⇒ nil
>
> So testing the first element did not give me the answer that
>  my-list has one non-nil element.

He means that case shows how poor that solution would be,
which means it's just not a good solution.

There are several ways to search a list for a specific element
but they rely on sorting the list first and if that isn't
desired is there really any other way than to examine the
items one by one?

In that case it's the Linear Search algorithm which is at
worst O(n), i.e. the whole list has to be searched until the
element is found at the last element or not found at all.

OTOH if sorting is done then one does Quick Sort first, which
is at worst O(n^2), then Binary Search on the result which is
at worst O(log n), so combined they are, at worst, worse than
O(n^2) or in other words, much worse than Linear Search at
O(n).

However if the data is *kept* sorted after the sorting and
insertions are made in a way that will uphold the order, that
means Binary Search can be used directly, that means we are at
a much better O(log n) again compared to Linear Search at
O(n) ...

-- 
underground experts united
https://dataswamp.org/~incal