🔒 Locked

Sorting parallel arrays

Started by Shannon Barber Oct 31, 2002 at 10:59 AM 27 replies 1k views

Original Post

Oct 31, 2002 at 10:59 AM

So the STL has made me incredulously lazy, and I have absolutely no motivation to write my own sorting algorithm that operates on a set of parallel arrays. I was curious what others have done to sort parallel arrays. I''m thinking about writing an iterator adaptor that you feed in a key iterator, and then iterators for each parallel array. I did a brief search and came-up empty with any such implementation. This seems like serious wheel-construction, and I figured something of the same nature already exist.

SabreMan

Oct 31, 2002 at 11:19 AM

The orthodox approach would be to design around the problem rather than create an implementation difficulty by not abstracting. For example, if you had 2 arrays of first name and last name, you might create a struct like this:


struct name
{
  string first_name;
  string last_name;
};

Then you would whack names into a single container and create a predicate for sorting on, say, last name only. An alternative might be to create a struct of pointers into the arrays and create a predicate which does a similar thing, thus building an index over the two arrays.

If you can''t / won''t do that, then I suspect you''ve got your work cut out.

OrangyTang

Oct 31, 2002 at 11:25 AM

Hows about having a separate array of indices, and sorting that? Might not be suitable though..

Zipster

Oct 31, 2002 at 11:28 AM

Right, I'd go with an aggregate type from the start.

However, what you might be able to do is sort one array, and whenever you go to swap, move, etc. an element in the algorithm, you simply perform the same operation on the other array. But that's a lot more difficult than a structure or other object than contains all your data nicely packed.

Hey, if you are only trying to sort two parallel arrays, you might be able to get away with using an std:air instead of your own structure

Thinking of which, if you have, let's say, 6 parallel arrays, then by all means, do this


std::vectorair<type1,std:air<type2,std:air<type3,std:air<type4,std:air<type5,type6> > > > > >

I've never tested it (nor would I), but it could work

By the way, the red guy on my right shoulder told me to say that...

[edited by - Zipster on October 31, 2002 12:37:07 PM]

SabreMan

Oct 31, 2002 at 11:38 AM

quote:
Original post by Zipster
Hey, if you are only trying to sort two parallel arrays, you might be able to get away with using an std:air instead of your own structure

boost::tuple will cope with entities of higher cardinality.

Shannon Barber

Oct 31, 2002 at 11:44 AM

The two arrays are part of different objects, so rearranging them into one struct is not entirely feasible.

quote:
Zipster
However, what you might be able to do is sort one array, and whenever you go to swap, move, etc. an element in the algorithm, you simply perform the same operation on the other array.

That''s the idea, but like Sabreman said, I have my work cut-out for me to implement this.

The problem with std:

air is that it looks at both items to determine equality and considers both elements during compares.

I may just sort the indices, then apply the rearrangement to both arrays, thanks for the idea OT.

Shannon Barber

Oct 31, 2002 at 4:34 PM

The compare isn''t the problem, it''s the swap.
This is turning out to be really hard, no wonder I didn''t find anything.

Shannon Barber

Oct 31, 2002 at 11:40 PM

That was my thinking, except it only works if swapping code uses the dereferening operator (so you can return a proxy with non-standard assignment semantics).

However STL swaps are not implemented using pointes, they''re implemented using references. So while smart-pointer classes are a dime-a-dozen, it''s not feasible to create a smart-reference class (as the proxy) with different assignment semantics.

This is the std:swap function:

template
void swap(T& left, T& right)
{
T tmp = left;
left = right;
right = tmp;
}

I need T and T& to behave differently. It''s *hard*.

daerid

Oct 31, 2002 at 11:44 PM

just a thought, but couldn''t you use boost::ref ?

sjelkjd

Nov 1, 2002 at 4:05 AM

Why can't you do this?

  
struct info
{
   mytype1* a; //points into first array

   mytype2* b; //points into second array

   bool operator<(info rhs)
   {
      //compares as you want it to

   }
};
//specialize swap for info

template<info>
void swap(info& a,info& b)
{
   swap(a->a,b->a);
   swap(a->b,b->b);
}
vector<info> v;
//fill out v appropriately

sort(v.begin(),v.end());

Of course this only works if std::sort calls std::swap...

(edit) code->source tags

[edited by - sjelkjd on November 1, 2002 5:07:24 AM]

SabreMan

Nov 1, 2002 at 4:50 AM

quote:
Original post by Anonymous Poster
You could cut'n'paste some STL sort implementation and make your own low-level sort_parallel()-algo just by swapping two iterators there instead of one.

Right, but where do you get the two iterators from. The problem is that there is no algorithm which allows you to pass a functor over multiple sequences simultaneously. Don't you just love C++?

quote:

Yea that's a dirty solution but it'd be fast. And not hard to make if you can just find all the necessary stuff the sort-algo requires, and copy it

Not hard? Since you've obviously put a lot of thought into this, I'd really be interested to hear more about it. It's not that it's hard to invent *a* solution, but it's tricky to come up with something that doesn't violate the idioms of the C++ Standard Library.

quote:
Original post by another Anonymous Poster
sort both arrays, using the same compare criteria.

Err... that's not a parallel sort, that's two different sorts.

To be a bit more constructive, I still think you should look at designing around the problem. You may well find it cheaper to do that than to write a good implementation of an algorithm to operate on multiple sequences.

[edited by - SabreMan on November 1, 2002 6:20:22 AM]

SabreMan

Nov 1, 2002 at 4:59 AM

quote:
Original post by sjelkjd
Why can''t you do this?

You possibly can, as long as you make sure that swap is a specialisation of std::swap; the implementation is not allowed to call another swap. Haven''t thought too hard about the implications of such an approach, though...

SabreMan

Nov 1, 2002 at 10:20 AM

quote:
Original post by Anonymous Poster
Why would I want to do that, if only one of the containers is used to do the comparing?

I think you may have misunderstood what I was saying. You can''t alter both containers via the algorithm if the algorithm does not know about both of them. As I said, there are no STL algorithms (AFAIK) which will pass a functor over two ranges simultaneously.

quote:

I just make my own version, something like this

template
_RandomAccessIter __unguarded_partition(_RandomAccessIter1 __first,
_RandomAccessIter1 __last, _RandomAccessIter2 __first2, _RandomAccessIter2 __last2,
_Tp __pivot, _Compare __comp)

Yes, that looks like its going to pass a Functor over 2 ranges.

quote:

Apparently it''s pretty easy to diss a solution too.

Sigh... I haven''t dissed your solution. I''ve expressed skepticism that it is easy to come up with a satisfactory solution which doesn''t go against the idioms of the Standard Library, or that you''ve put a great deal of thought into it, but *nowhere* have I dissed the solution.

Shannon Barber

Nov 1, 2002 at 11:00 AM

The problem with specializing swap (or any other algorithm) is that the sort isn''t guarunteed to call it - the Dinkumware sort boils down to std::rotate (an insertion sort).

I was looking for a more general solution, wherein you could take two iterators to parallel arrays and make one iterator out of it that would work with all existing algorithms.

As soon as you have a
parallel_sort(key_begin, key_end, para_begin, para_end);
then you''ll want:
parallel_sort2(key_begin, key_end, para1_begin, para1_end, para2_begin, para2_end);
etc...

But it''s about the only thing that acutally works :/

Shannon Barber

Nov 1, 2002 at 1:11 PM

Well here''s a hacked up version of the Dinkumware library that ships with MSVC7. I wasn''t motivated enough to make an optimal sort (a combination quick-sort/heap-sort/insertion-sort), so it''s just an insertion sort.

Perhaps a policy based sorter would be the more scalable/flexible/generic appraoch?

  
namespace MKH
	{
	namespace STL
		{
		namespace
			{
			template<class KeyIterator, class ParallelIterator>
			inline void _parallel_insertion_sort(KeyIterator key_begin, KeyIterator key_end,
											             ParallelIterator para_begin, ParallelIterator para_end)
				{	// parallel insertion sort [key_begin, key_end), using operator<

				if(key_begin != key_end)
					{
					KeyIterator key = key_begin;
					ParallelIterator para = para_begin;
					for(; ++para, ++key != key_end;)
						{
						if(*key < *key_begin)
							{	// found new earliest element, rotate to front

							KeyIterator key1 = key;
							std::rotate(key_begin, key, ++key1);
							ParallelIterator para1 = para;
							std::rotate(para_begin, para, ++para1);
							}
						else
							{	// look for insertion point after first

							KeyIterator key_dest = key;
							ParallelIterator para_dest = para;
							
							KeyIterator key_dest0 = key_dest;
							ParallelIterator para_dest0 = para_dest;
							for(; --para_dest0, *key < *--key_dest0; )
								{
								key_dest  = key_dest0;
								para_dest = para_dest0;
								}
							if (key_dest != key)
								{	// rotate into place

								KeyIterator key1 = key;
								std::rotate(key_dest, key, ++key1);
								ParallelIterator para1 = para;
								std::rotate(para_dest, para, ++para1);
								}
							}
						}
					}
				}
			}//anonymous namespace

		
		template<class KeyIterator>
		inline bool parallel_sort(KeyIterator key_begin, KeyIterator key_end)
			{
			std::sort(key_begin, key_end);
			return true;
			}
		
		template<class KeyIterator, class ParallelIterator>
		inline bool parallel_sort(KeyIterator key_begin, KeyIterator key_end,
		                          ParallelIterator para_begin, ParallelIterator para_end)
			{
#			ifndef NDEBUG
				if( (key_end-key_begin) != (para_end-para_begin) )
					return false;
#			endif
			_parallel_insertion_sort(key_begin,  key_end,
			                         para_begin, para_end);
			return true;
			}
		
		/*
		template<class KeyIterator, class ParallelIterator1, class ParallelIterator2>
		inline bool parallel_sort(KeyIterator key_begin, KeyIterator key_end,
		                          ParallelIterator1 para1_begin, ParallelIterator1 para1_end,
		                          ParallelIterator2 para2_begin, ParallelIterator2 para2_end)
			{
#			ifndef NDEBUG
				if( (key_end-key_begin) != (para1_end-para1_begin) || 
				    (key_end-key_begin) != (para2_end-para2_begin) )
					return false;
#			endif
			_parallel_insertion_sort(key_begin,   key_end,
			                         para1_begin, para1_end,
			                         para2_begin, para2_end);
			return true;
			}
		//*/

		}//ns STL

	}//ns MKH

Kylotan

Nov 1, 2002 at 10:13 PM

Hmm. You could have a structure containing an index and the element from the first array. Create an array of those from that first array, incrementing the index for each one accordingly, so that the elements go from {0, array1[0]} to {N, array1[N]}. Then, sort this new array based on that second element. You now have a sorted list of the first element, which you can copy back into the first array. You also have a sorted list of the indices, which can be used to reconstitute the 2nd array into a temporary one which you then copy back into the original. This costs you O(4N) on top of your original sort algorithm: once through the data to generate your new array to be sorted, once to copy the sorted first elements back to the first source array, once to copy the unsorted second elements to the temporary array, and once to copy those sorted second elements back again.

Anybody spot any flaws, apart from the performance?

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Premandrake

Nov 1, 2002 at 11:33 PM

A more generalized method might be to have an iterator of an iterator. So your parent iterator goes over the number of elements that need to be sorted and has a child iterator that goes over all the elements that need to be moved (perhaps with the first child being the key for sorting).

I can see this being quite ugly, but it is more than general (and safe I think) than passing in 4 iterators into a sort method.

I''m currently hacking on how to do this, we''ll see how things turn out.

Shannon Barber

Nov 2, 2002 at 3:40 PM

That was my original battle plan, but I couldn''t figure out a way to do it. It is actually much safer to use an algorithm built for parallel sorting, than toy with objects that violate value semantics and the STL.

...
That would work well enough Kylotan, but I was also trying to avoid the copy-copy-copy scenario. Actually, that just gave me another idea.

You can just make a new index array, and sort it using a predicate that indexes into the key array to determine <. Then the swaps are performed on just the integers. Ah damn... now to actually sort the original arrays, you still have to make a copy, because you destroy the contents of the array while replacing each item with the sorted index item.

Either way it''s copy-copy-copy.

Nypyren

Nov 2, 2002 at 5:55 PM

Use a map/multimap with a sort functor that you define.

If you need to sort using a different algorithm after that, just create a new map using the new functor and use the copy stuff.

Of course, this all assumes you only have two "arrays", since maps use key/value pairs. I suppose you could fold multiple non-key arrays into the value, though.

And yes, you *can* write a functor that takes pointers, in case you only want to store pointers to objects in your map (faster)

Maps: for much **enjoyment**!

[edited by - Nypyren on November 2, 2002 6:59:26 PM]

Shannon Barber

Nov 2, 2002 at 9:23 PM

That might reduce it to a double copy instead of a triple - I think a custom parallel sorting algorithm is the best method so far.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.