cost accessing of last(?List, ?Last)

[Dan]

Hello, 

I am curious,  for very large lists, what is the cost of access the last element in a list?

Does it require moving through the whole list, or is there an internal optimization here to get to the last one immediately?

thank you,

Dan

[Kuniaki Mukai]

I had the same question more than ten years ago,  when I used

last/2,  and is_list/1,  but I got no positive information.  As for them, I think 

no innovation was made since.

-K.M.

thank you,

Dan

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

[Peter Ludemann]

The cost of accessing the end of a list is O(N) where N is the length of the list.

Similarly, the cost of append(L1, L2, L) is also O(N) where N is the length of L1.

    you can define: last(List, Last) :- append(_, [Last], List).

Difference lists reduce the cost of append to O(1). [This is only if the occurs check is turned off, of course.]

Maybe there's a way of using difference lists for accessing the end of a list?

reverse/2 is O(N) if the non-naive implementation is used, so that's an option if you need to access the end of the list a lot.

There's no intrinsic reason why Prolog implementations couldn't do something more clever to make random list element access faster, but I don't know of any implementation that has done that (nor for Lisp, AFAIK, although Haskell has a special "++" operator, possibly because append can't be tail-recursive in functional languages). Similarly, association-lists could be O(1) [using hash tables] but O(log N) seems to be "good enough" most of the time.

[FWIW, Python implementers have put a lot of effort into making both list/array and hash table access fast, but maybe there's less need for this in Prolog programs, especially as Python also uses hash tables for run-time resolving of non-local names.]

[Paulo Moura]

Hi,

> On 22 Jan 2019, at 20:19, Peter Ludemann <peter.l...@gmail.com> wrote:
>
> The cost of accessing the end of a list is O(N) where N is the length of the list.
> Similarly, the cost of append(L1, L2, L) is also O(N) where N is the length of L1.
> you can define: last(List, Last) :- append(_, [Last], List).
> Difference lists reduce the cost of append to O(1). [This is only if the occurs check is turned off, of course.]
> Maybe there's a way of using difference lists for accessing the end of a list?

We can always derive a representation from difference lists that makes the last element explicit. For example:

last(List-Back+Last, Last) :- List \== Back.

append(List1-Back1+_, Back1-Back2+Last, List1-Back2+Last).

?- append(E-E+_, [1,2,3|T]-T+3, DL).
E = [1, 2, 3|T],
DL = [1, 2, 3|T]-T+3.

?- append(E-E+_, [1,2,3|T]-T+3, DL), append(DL, [4,5|T2]-T2+5, DL2), last(DL2, Last).
E = [1, 2, 3, 4, 5|T2],
T = [4, 5|T2],
DL = [1, 2, 3, 4, 5|T2]-[4, 5|T2]+3,
DL2 = [1, 2, 3, 4, 5|T2]-T2+5,
Last = 5.

The complexity that matters then becomes the complexity of constructing the List-Back+Last lists in the first place and likely how much conversion between these lists and normal lists would be required.

But I think you had something different in mind?

> reverse/2 is O(N) if the non-naive implementation is used, so that's an option if you need to access the end of the list a lot.
>
> There's no intrinsic reason why Prolog implementations couldn't do something more clever to make random list element access faster, but I don't know of any implementation that has done that (nor for Lisp, AFAIK, although Haskell has a special "++" operator, possibly because append can't be tail-recursive in functional languages). Similarly, association-lists could be O(1) [using hash tables] but O(log N) seems to be "good enough" most of the time.
>
> [FWIW, Python implementers have put a lot of effort into making both list/array and hash table access fast, but maybe there's less need for this in Prolog programs, especially as Python also uses hash tables for run-time resolving of non-local names.]

Cheers,
Paulo

> On Monday, January 21, 2019 at 11:24:24 PM UTC-8, Dan wrote:
> Hello,
>
> I am curious, for very large lists, what is the cost of access the last element in a list?
>
> Does it require moving through the whole list, or is there an internal optimization here to get to the last one immediately?
>
> thank you,
>
> Dan

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

[Dan]

I have this assoc, that i pass around where i store "global" dynamic data, such as other assocs. 

I was thinking that if needed i will just have to add another key for storing the last element explicitly, as you mentioned. 

but, having it all in one list is preferrable. 

Do the pairs in the difference list create some storage overhead ...

thanks,

Dan

[Paulo Moura]

Hi,

> On 23 Jan 2019, at 12:37, Dan <gros...@gmail.com> wrote:
>
> I have this assoc, that i pass around where i store "global" dynamic data, such as other assocs.
>
> I was thinking that if needed i will just have to add another key for storing the last element explicitly, as you mentioned.

That would give you O(log(N)) access to the last element instead of O(N) in the worst case. In the prototype code in my previous message, the cost to access the last element is O(1). But, as I mentioned, that must be weighted with the practicality of the representation.

> but, having it all in one list is preferrable.
>
> Do the pairs in the difference list create some storage overhead ...

The storage cost is minimal and independent of the number of elements in the list.

Cheers,
Paulo