I have a best first search function. I did some profiling and found that
the majority of time is used in the sorting of the *open* list of states.
For example, one small case takes 2 seconds to generate all the descendants
to find the solution. But takes 12 seconds to do all the sorting.
Currently I am using the sort function and calling my own predicate. Since
the *open* list is already sorted, and I just am appending the newly created
descendants to the list and then sorting, I am thinking this sort (common
lisp) must be using a version of qsort and running in O(n*n) time for an
almost sorted list.
If I switch over to the merge function and first sort by descendants and
then merge them with the current *open* list, will this improve on the sort
time? Does the merge function handle sorted list in a fast manner?
Or should I just write my own insertion sort which would run in O(k*n) time
which is okay if k (the descendants) is much smaller then n.
Just curious if others have run into the same dilemma?
-- Scott
"Scott" <·········@prodigy.xyz> wrote in message news:<······················@comcast.com>...
> If I switch over to the merge function and first sort by descendants and
> then merge them with the current *open* list, will this improve on the sort
> time? Does the merge function handle sorted list in a fast manner?
It's impossible to say anything with certainty about performance
without having your machine, your program and your Lisp
implementation.
But I would be surprised if an implementation of the merge function
did not work in O(m + n) time where m and n are the lengths of the
input sequences. The most straightforward way of implementing merging
has this property.
Because you're working in Lisp, it's probably faster to just try it
than to get an answer. You don't have to radically change your program
to try a different algorithm.
> Or should I just write my own insertion sort which would run in O(k*n) time
> which is okay if k (the descendants) is much smaller then n.
By the way, have you considered some data structure that maintains
order, such as some balanced binary tree?
"Scott" <·········@prodigy.xyz> ha scritto nel messaggio ···························@comcast.com...
> If I switch over to the merge function and first sort by descendants and
> then merge them with the current *open* list, will this improve on the sort
> time? Does the merge function handle sorted list in a fast manner?
This would be better, but note that you don't need to maintain the
states sorted. A priority queue is enough.
A heap implemented by an adjustable vector with fill-pointer
is simple to implement and would probably the fastest choice
if the descendants are few.
> Or should I just write my own insertion sort which would run in O(k*n) time
> which is okay if k (the descendants) is much smaller then n.
Ouch.
P.
Looks like you are implementing an A* procedure.
You are using the wrong data structure. It is best to keep your *OPEN*
set as a PRIORITY-QUEUE. In this case you will not need to re-sort
after every (batch) insertion. With a PQ, each insertion will only cost
O(lg n) and each removal from the "top" will cost the same. With
explicit sorting of *OPEN* every insertion will cost you O(n lg n) (or,
as you may have observed O(n^2)) Note that most likely you will need to
use the MODIFY-KEY operation as well.
You can get a priority queue implementation (shameless plug) from the
CMU AI.Repository. (write me if it does not work).
(Of course you can become adventurous and implement a Binomial or a
Fibonacci Heap in CL :) )
Cheers
Marco Antoniotti
Scott wrote:
> I have a best first search function. I did some profiling and found that
> the majority of time is used in the sorting of the *open* list of states.
> For example, one small case takes 2 seconds to generate all the
> descendants
> to find the solution. But takes 12 seconds to do all the sorting.
>
> Currently I am using the sort function and calling my own predicate.
> Since
> the *open* list is already sorted, and I just am appending the newly
> created
> descendants to the list and then sorting, I am thinking this sort (common
> lisp) must be using a version of qsort and running in O(n*n) time for an
> almost sorted list.
>
> If I switch over to the merge function and first sort by descendants and
> then merge them with the current *open* list, will this improve on the
> sort
> time? Does the merge function handle sorted list in a fast manner?
>
> Or should I just write my own insertion sort which would run in O(k*n)
> time
> which is okay if k (the descendants) is much smaller then n.
>
> Just curious if others have run into the same dilemma?
> -- Scott
>
>
Thanks all.
I tested the merge function and tested my own insertion sort. Ideally I
probably should use a priority queue. I've written several versions in C,
so it would be good practice to write one one LISP.
I actually did get better performance using the insertion sort rather than
the sort or merge function since my data was already mostly sorted and I was
only adding a small number of new elements each time. Though the priority
queue would have been faster yet.
-- Scott
"Marco Antoniotti" <·······@cs.nyu.edu> wrote in message
····················@typhoon.nyu.edu...
>
> Looks like you are implementing an A* procedure.
>
> You are using the wrong data structure. It is best to keep your *OPEN*
> set as a PRIORITY-QUEUE. In this case you will not need to re-sort
> after every (batch) insertion. With a PQ, each insertion will only cost
> O(lg n) and each removal from the "top" will cost the same. With
> explicit sorting of *OPEN* every insertion will cost you O(n lg n) (or,
> as you may have observed O(n^2)) Note that most likely you will need to
> use the MODIFY-KEY operation as well.
>
> You can get a priority queue implementation (shameless plug) from the
> CMU AI.Repository. (write me if it does not work).
> (Of course you can become adventurous and implement a Binomial or a
> Fibonacci Heap in CL :) )
>
> Cheers
>
> Marco Antoniotti
>
> Scott wrote:
>
> > I have a best first search function. I did some profiling and found
that
> > the majority of time is used in the sorting of the *open* list of
states.
> > For example, one small case takes 2 seconds to generate all the
> > descendants
> > to find the solution. But takes 12 seconds to do all the sorting.
> >
> > Currently I am using the sort function and calling my own predicate.
> > Since
> > the *open* list is already sorted, and I just am appending the newly
> > created
> > descendants to the list and then sorting, I am thinking this sort
(common
> > lisp) must be using a version of qsort and running in O(n*n) time for an
> > almost sorted list.
> >
> > If I switch over to the merge function and first sort by descendants and
> > then merge them with the current *open* list, will this improve on the
> > sort
> > time? Does the merge function handle sorted list in a fast manner?
> >
> > Or should I just write my own insertion sort which would run in O(k*n)
> > time
> > which is okay if k (the descendants) is much smaller then n.
> >
> > Just curious if others have run into the same dilemma?
> > -- Scott
> >
> >
>