List array question

[olivier.scalbert]

Hello,

I have a list of N integers.
I want to be able to remove an integer at a given position p1 (0 <= p1
< N) in this list and reinsert it at an other position p2 (<0 <= p2
<N-1).
Lists are good for remove/insert but not for fast direct access.
Arrays are good for direct access but not for fast remove/insert.
What is the best way to manage this ?

Thanks,

Olivier

 

[Alf P. Steinbach]

* (e-mail address removed), on 24.05.2010 12:02:

Hello,

I have a list of N integers.
I want to be able to remove an integer at a given position p1 (0<= p1
< N) in this list and reinsert it at an other position p2 (<0<= p2
<N-1).
Lists are good for remove/insert but not for fast direct access.
Arrays are good for direct access but not for fast remove/insert.
What is the best way to manage this ?

Define "best".



Cheers & hth.,

- Alf

 

[olivier.scalbert]

Define "best".

Here "Best" = the most time efficient.

 

[Alf P. Steinbach]

* (e-mail address removed), on 24.05.2010 13:36:

Here "Best" = the most time efficient.

Depends on data sizes, operation mix and the system. Measure.


Cheers & hth.,

- Alf

 

[Kai-Uwe Bux]

Hello,

I have a list of N integers.
I want to be able to remove an integer at a given position p1 (0 <= p1
< N) in this list and reinsert it at an other position p2 (<0 <= p2
<N-1).
Lists are good for remove/insert but not for fast direct access.
Arrays are good for direct access but not for fast remove/insert.
What is the best way to manage this ?

Elsethread, you mentioned that you are looking for a time efficient
solution.

Have a look at:

Knuth: The Art of Computer Programming, Vol 3, Sect. 6.2.3,
page 471: "Linear list representation"

That shows the implementation of an abstract array data type, i.e., a
container indexed by integers [0,size), such that all operations (insert,
delete, access) take O(log size) time.

Using an indexable skip list, you could implement performance of _expected_
O(log size) for all operations. And the rope container that shipped with the
old SGI implementation of STL has similar performance characteristics.

Whether those perform better than std::list or std::vector depends (among
other things) on the relative importance of element access and the rotation
operation you described.


Best

Kai-Uwe Bux

 

[Paul N]

Hello,

I have a list of N integers.
I want to be able to remove an integer at a given position p1 (0 <= p1
< N) in this list and reinsert it at an other position p2 (<0 <= p2
<N-1).
Lists are good for remove/insert but not for fast direct access.
Arrays are good for direct access but not for fast remove/insert.
What is the best way to manage this ?

How about storing the list as a tree, with each node holding one value
plus a count of how many nodes are subsiduary to it? By my reckoning,
finding a value just involves going down the correct branch of the
tree, and deleting or inserting a value simply involves adjusting the
totals in one branch. Hence, if the tree is balanced, each of these
should take O(log N) time. And you can force the tree to be balanced
eg by using a red-black tree.

You might want to consider asking in comp.programming, as your
solution doesn't seem to depend on the details of C++.

Hope that helps.
Paul.

 

[Marcel Müller]

Hi,

Change the links of p1's neighbors so they point to each other, then
change the links of p2's neighbors so they point to the object that p1's
neighbors used to point to... or you could do it the other way around.

yes, but the essential hint is to use iterators rather than integers to
address the list elements to avoid the O(n) lookup.
The disadvantage might be that list iterators are not easily
serializable. If this is is a question then a tree solution like
purposed by others should be considered.


Marcel

 

[olivier.scalbert]

Have a look at:

  Knuth: The Art of Computer Programming, Vol 3, Sect. 6.2.3,
         page 471: "Linear list representation"

That shows the implementation of an abstract array data type, i.e., a
container indexed by integers [0,size), such that all operations (insert,
delete, access) take O(log size) time.

Using an indexable skip list, you could implement performance of _expected_
O(log size) for all operations. And the rope container that shipped with the
old SGI implementation of STL has similar performance characteristics.

Whether those perform better than std::list or std::vector depends (among
other things) on the relative importance of element access and the rotation
operation you described.

Best

Kai-Uwe Bux

Thanks for the reference !
In fact, I want to use this ADT to play a little with the TSP
(Traveling salesman problem).
The list represents the towns.
I want to be able to efficiently remove a town at a given position
from the list and reinsert it elswhere.
I have posted this in this newsgroup because I thought it can be
implemented with a mixed of STL containers.

Olivier

 

[Kai-Uwe Bux]

Have a look at:

Knuth: The Art of Computer Programming, Vol 3, Sect. 6.2.3,
page 471: "Linear list representation"

That shows the implementation of an abstract array data type, i.e., a
container indexed by integers [0,size), such that all operations (insert,
delete, access) take O(log size) time.

Using an indexable skip list, you could implement performance of
_expected_ O(log size) for all operations. And the rope container that
shipped with the old SGI implementation of STL has similar performance
characteristics.

Whether those perform better than std::list or std::vector depends (among
other things) on the relative importance of element access and the
rotation operation you described.

Best

Kai-Uwe Bux

Thanks for the reference !
In fact, I want to use this ADT to play a little with the TSP
(Traveling salesman problem).
The list represents the towns.
I want to be able to efficiently remove a town at a given position
from the list and reinsert it elswhere.
I have posted this in this newsgroup because I thought it can be
implemented with a mixed of STL containers.

I see. Essentially, you have the set T of all possible tours (represented by
a sequence of the cities) and a map l : T --> R assigning to each tour its
length. Now, you have an operation that only slightly alters a tour, namely
putting one city in a different position. This way, you turn T into a graph:
two tours are neighbors if they differ by one modification.

Well, what about using a different modification of tours: swap two cities.
That turns T into a different graph, but one that looks roughly similar.
E.g., vertices have similar degree and the graph has similar diameter. Also,
the length of the new tour can be efficiently computed from the length of
the old tour and four additional city-distances. Finally, swapping two
cities is fast in a std::vector.


Best

Kai-Uwe Bux

 

[olivier.scalbert]

I see. Essentially, you have the set T of all possible tours (represented by
a sequence of the cities) and a map l : T --> R assigning to each tour its
length. Now, you have an operation that only slightly alters a tour, namely
putting one city in a different position. This way, you turn T into a graph:
two tours are neighbors if they differ by one modification.

Well, what about using a different modification of tours: swap two cities..
That turns T into a different graph, but one that looks roughly similar.
E.g., vertices have similar degree and the graph has similar diameter. Also,
the length of the new tour can be efficiently computed from the length of
the old tour and four additional city-distances. Finally, swapping two
cities is fast in a std::vector.

Best

Kai-Uwe Bux

Hi,

I have start by using the two cities swap approach.
It is very easy to implement. It gives 'good' results but sometimes a
lot of swaps is needed.

Suppose the current tour is;
1, 2, 3, 4, 5, 6, 7,8, 9, 10

Suppose the solution tour is:
1. 10, 2, 3, 4, 5, 6, 7, 8, 9

Not easy to go from the "current tour" to the "solution tour" by
swapping !
By "remove" from list and reinsert in list, it is done in one "move".

I found this TSP so fascinating !

Olivier

 

[Kai-Uwe Bux]

Hi,

I have start by using the two cities swap approach.
It is very easy to implement. It gives 'good' results but sometimes a
lot of swaps is needed.

Suppose the current tour is;
1, 2, 3, 4, 5, 6, 7,8, 9, 10

Suppose the solution tour is:
1. 10, 2, 3, 4, 5, 6, 7, 8, 9

Not easy to go from the "current tour" to the "solution tour" by
swapping !
By "remove" from list and reinsert in list, it is done in one "move".

Since you tried the swap-two approach, let's go back to the problem of
realizing the rotation. First observe, that a std::list is capable of doing
the remove-reinsert operation in constant time. What is the tricky part is
two choose the two positions (std::list::iterator) for the rotation. What
about using a std::vector just for that purpose. So:

std::list< city > route;
std::vector< route::iterator > selector;

You have to initialize the route to go through all the cities and then you
initialize the selector with iterators into the route. Now, removing an item
will invalidate that iterator but it will leave all others valid. Thus, you
need to update that point in the selector after obtaining a new iterator
after re-inserting the selected city.


Best

Kai-Uwe Bux

 

[olivier.scalbert]

Since you tried the swap-two approach, let's go back to the problem of
realizing the rotation. First observe, that a std::list is capable of doing
the remove-reinsert operation in constant time. What is the tricky part is
two choose the two positions (std::list::iterator) for the rotation. What
about using a std::vector just for that purpose. So:

  std::list< city >              route;
  std::vector< route::iterator > selector;

You have to initialize the route to go through all the cities and then you
initialize the selector with iterators into the route. Now, removing an item
will invalidate that iterator but it will leave all others valid. Thus, you
need to update that point in the selector after obtaining a new iterator
after re-inserting the selected city.

Best

Kai-Uwe Bux

Hi,

Mmmm ...

If, at the beginning route is: t0 -> t1 -> t2 -> t3.
Then selector[0] = it0, selector[1] = it1, selector[2] = it2, ...
If I remove t0 and put it elsewhere at the end for example, then
selector[0] is invalid but selector[1] will still contain it1,
selector[2]; it2 ...
So selector is not so trivial to manage no ?

As the discussion is less C++ than I imagine at the beginning, I will
perhaps move to comp.programming !

Thanks again,

Olivier

 

[Kai-Uwe Bux]

Since you tried the swap-two approach, let's go back to the problem of
realizing the rotation. First observe, that a std::list is capable of
doing the remove-reinsert operation in constant time. What is the tricky
part is two choose the two positions (std::list::iterator) for the
rotation. What about using a std::vector just for that purpose. So:

std::list< city > route;
std::vector< route::iterator > selector;

You have to initialize the route to go through all the cities and then
you initialize the selector with iterators into the route. Now, removing
an item will invalidate that iterator but it will leave all others valid.
Thus, you need to update that point in the selector after obtaining a new
iterator after re-inserting the selected city.

Best

Kai-Uwe Bux

Hi,

Mmmm ...

If, at the beginning route is: t0 -> t1 -> t2 -> t3.
Then selector[0] = it0, selector[1] = it1, selector[2] = it2, ...
If I remove t0 and put it elsewhere at the end for example, then
selector[0] is invalid but selector[1] will still contain it1,
selector[2]; it2 ...
So selector is not so trivial to manage no ?

I was thinking of something like this:


#include <list>
#include <vector>
#include <cassert>

#include <iostream>
#include <ostream>
#include <iterator>

class route {
public:

typedef unsigned int city;

private:

typedef std::list< city > tour;
typedef tour::iterator site;
typedef std::vector< site > site_seq;

tour the_tour;
site_seq the_site_seq;

public:

route ( unsigned int num_cities )
: the_tour ()
, the_site_seq ()
{
for ( city c = 0; c < num_cities; ++c ) {
site next = the_tour.insert( the_tour.end(), c );
the_site_seq.push_back( next );
assert( c == * the_site_seq[c] );
}
}

template < typename OutIter >
OutIter write_tour ( OutIter where ) const {
return( std::copy( the_tour.begin(), the_tour.end(), where ) );
}

route & move_city ( city moving, city target ) {
site moving_site = the_site_seq[ moving ];
assert( moving == *moving_site );
site target_site = the_site_seq[ target ];
assert( target == *target_site );
the_tour.erase( moving_site );
moving_site = the_tour.insert( target_site, moving );
the_site_seq[ moving ] = moving_site;
}

};


int main ( void ) {
route::city const new_york = 0;
route::city const chicago = 1;
route::city const syracuse = 2;
route::city const salt_lake = 3;
route::city const num_cities = 4;

route the_route ( num_cities );
the_route.write_tour
( std:stream_iterator< route::city >( std::cout, " " ) );
std::cout << "\n";

the_route.move_city( new_york, salt_lake );
the_route.write_tour
( std:stream_iterator< route::city >( std::cout, " " ) );
std::cout << "\n";

the_route.move_city( chicago, new_york );
the_route.write_tour
( std:stream_iterator< route::city >( std::cout, " " ) );
std::cout << "\n";
}


Note: you can place any city in front of any other city in constant time.
However, you reference the cities by a unique id not by their current
position in the tour.


Best

Kai-Uwe Bux