Predicate nth( and big list

Discussions related to Visual Prolog
Posts: 15
Joined: 3 Sep 2001 23:01

Predicate nth( and big list

Unread post by PERRAUD » 2 Jun 2009 16:39


Exist there a very fast function of access to an element of a list, other that the predicate 'nth' (of a unit 'list') who uses the recursivity, therefore which is slow if the list is big. (direct access with the pointers?)

I work with VP7.1. (I want make a dicotomic access with a large list)
Thank you for your help.
and sorry for my bad English.
Daniel Perraud

Gildas Menier
VIP Member
Posts: 78
Joined: 8 Jun 2004 23:01

Unread post by Gildas Menier » 2 Jun 2009 20:40

Hi Daniel,

I don't think this function exists in VP7.1 (but wait for the answer from Thomas to be sure). It is possible to perform such an access using underlying pointers in C (see the wiki for list structures) but I do not think it is the best way to perform (updating is a problem then).

I would rather suggest the use of redblacktree predicates (it depends of course of the size of the set you want to manage).
(Don't be shy of your english - still better than mine ;) )

Best regards

User avatar
Thomas Linder Puls
VIP Member
Posts: 2438
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 2 Jun 2009 21:04

Indexing in lists is inefficient (i.e. O(N) where N is the length of the list), that is the nature of lists (and working directly with pointers will not make any difference).

Using list::nth should always trigger you: It is most likely a bad idea.

Sometimes the alternative is to change the algorithm; sometimes it is better to change to another data structure; sometimes you should do both.
Regards Thomas Linder Puls

User avatar
Tonton Luc
VIP Member
Posts: 814
Joined: 16 Oct 2001 23:01

Unread post by Tonton Luc » 3 Jun 2009 6:50

:idea: Maybe you can add your big list in an invisible listControl and use listControl::getAt to recover the nth element...

Post Reply