Linked list to Permutation vector 
Author Message
 Linked list to Permutation vector

I thought I'd follow up on the linked list to permutation
vector problem a bit:

The original problem arose from a client requirement. An
operating system data structure is a linked list of buffers, arranged
in LRU fashion. Hence, the N most recently used buffers are the
first N entries on the chain. Buffers are associated with files
though another mechanism, that gives a list of buffer indices for
each file. What I wanted to do was to provide a list of the N
most popular files being accessed at the moment. The idea was to
permute the linked list into a list sorted into LRU order,
then do some selection within other class information.

Nobody came up with a Gee-Whiz Swell algorithm using scan or
other linear(ish) time function.

So, I decided to brute force it on my PC to see how it would run
if compiled. Here's the APL 2000 version:


r{<-}({rho}links){rho}{neg}1
:for i :in {iota}{rho}links
r[hd]{<-}i
hd{<-}links[hd]
:endfor

On a 100k element vector, this takes 12.23 seconds on my
Belchfire 3000  486DX4-100 under the interpreter.

When compiled with APEX, it takes 0.14 seconds, or a factor of
about 87 times faster. And, you can read the code!

Bob



Tue, 10 Nov 1998 03:00:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. list permutations and weired list.remove funtion

2. Puzzler: function of permutation vector

3. Deallocating linked lists of linked lists

4. Pymacs - tuples/lists .vs. proper-lists/vectors

5. no vector = vector*vector in BLAS?

6. all-permutations is faster than permutation

7. A permutation on permutations

8. Wanted: a Logo program for listing permutations

9. Wanted: a Logo program for listing permutations

10. permutations of a list in scheme

11. All permutations of a list

12. Distinct permutations of a list

 

 
Powered by phpBB® Forum Software