Bitsort

[bitsorter]

Hallo

ich versuche ein lineares sortierverfahren auf basis von radixsort zu implementieren
dabei werden die zahlen (int) ihren bits nach sortiert. dabei identifiziert ein
ungesetzes bit eine kleine zahl (muss an den anfang) und ein gesetzes bit eine
"große" zahl.

daraus folgt, dass eine zahl deren (aktuell betrachtetes) bit gesetzt ist, nicht
vor einer zahl mit nicht gesetzem bit stehen darf. findet der algo diese
konstellation, werden die zahlen vertauscht. (das austauschverfahren basiert auf
quicksort).

die zahlen kommen je nach bit also nach vorne oder hinten (wichtig).

wenn ich das nächste bit betrachte, darf ich nicht einfach das ganze feld sortieren,
sondern immer nur bereichsweise (vorderer bereich oder hinterer bereich).

um den bereich "abzustecken", gucke ich mir also das höherwertige bit an,
was im letzen durchlauf verwendet wurde. HIER VERMUTE ICH DEN FEHLER!

der code:

/*
pbegin: anfangsiterator
pend: enditerator (zeigt eins hinter das feld)
*/
void sort(int *pbegin, int *pend)
{
	const unsigned bitcount = std::numeric_limits<int>::digits + 1;
	// anzahl bits

	for (unsigned i = 0; i < bitcount; ++i) // für jedes bit
	{
		const unsigned mask = 1 << (bitcount - 1 - i); // maskiert das akuelle bit(31tes, 30tes, 29tes....)

		int *begin = pbegin; // hilfszeiger für den aktuellen sortierbereich
		int *end = pend - 1;

		while (begin < pend) // solange der bereich nicht ganz durch ist
		{
			if (i) // immer, außer im ersten durchlauf, da es kein höheres bit gibt
			{
				// nächsten bereich finden:
				// begin rückt jeden durchlauf hinter end
				// danach das neue ende bestimmen
				// dazu solange laufen bin das HÖHERWERTIGE bit nicht mehr mit dem des anfangs übereinstimmt

				end = begin + 1;
				const unsigned oldmask = mask << 1; // höherwertiges bit
				const unsigned ref = *begin & oldmask;
				while (end < pend && (*end & oldmask) == ref)
					++end;

				--end; // end zeigt immer auf das element IN dem bereich, nicht dahinter
			}

			int *a = begin; // die eigentlichen tauschzeiger
			int *b = end;

			while (a < b) // laufen über den eben ermittelten bereich
			{
				// kleine elemente kommen an den anfang
				// deshalb suchen wir nach "großen" elementen (bit gesetzt), die vorne sind (falsche position)

				while (a != b && (*a & mask) == mask)
					++a;
				while (a != b && (*b & mask) == 0) // dito, nur von hinten
					--b;

				// und tauschen
				std::swap(*a, *b);
			}

			begin = end + 1; // bereich wandert weiter
		}
	}
}

das verfahren habe ich rekursiv schin erfolgreich zum laufen bekommen.
(für den unteren und oberen bereich ein neuer aufruf).

iterativ wollte ich das ganze dadurch lösen, das ich mehrere bereiche bilde,
die ich dann in der schleife durchgehe. der erste durchlauf funktioniert,
sprich die zahlen werden nach ihrem höchsten bit sortiert. die weiteren bits
funktioniern nicht, das ergebniss ist unsortiert.

meine vermutung bisher ist, dass das bestimmen des neuen bereiches so nicht
funktioniert. vielleicht muss ich nicht nur ein verhergehendes bit betrachten,
sondern mehrere (aber nur vermutung).

jede idee ist willkommen!

auch zu dieser späten stunde noch ein dankeschön an die fleißigen helfer

gute nacht,
bitsorter

[volkard]

ich glaube nicht, daß du bitsort iterativ hinkriegst. war es nicht so, daß man beide zweige, 0 und 1 rekursiv verfolgen muß? einen davon kannst du gerne iteratisieren, aber beide?? außerdem würde ich das vorhaben eh lassen, weil du selbst bei 64-bittigen ints nur maximal 64 iterationstiefe hast. das riecht mir danach, als würde die konsequent vereinfachte rekursive lösung am ende so einfach und klar und offensichtlich schnell sein, daß die iterative version dagegen abstinkt. ist nur so ein gefühl von mir.

[Sebastian Pizer]

Mach's rekursiv und benutze dabei std::partition.

Gruß,
SP

[bitsorter]

rekursiv klappt das ja auch schon. nur wollte ich diesen overhead reduzieren.
vllt mit einem software-stack. aber ein bissel speed sollte da doch noch drin sein.

vielen dank bis her
bitsorter

[Sebastian Pizer]

bitsorter schrieb:

nur wollte ich diesen overhead reduzieren.

Welchen Overhead?

(Du nimmst an, dass es einen gibt. Aber stimmt das? Denk mal drüber nach.)

Gruß,
SP

[bitsorter]

das komplette stackframe zu pushen ist doch etwas overhead. mit einem software-stack
kann ich selber bestimmen was ich pushe.
aber du hast recht, im vergleich zur normalen rekursion bringt es nicht viel,
zumindest nicht genug um den algo signifikant zu beschleunigen

MfG
bitsorter

[volkard]

bitsorter schrieb:

das komplette stackframe zu pushen ist doch etwas overhead. mit einem software-stack kann ich selber bestimmen was ich pushe.

Ja. Aber die Helden von Intel verbauen Millionen von Transistoren, damit Funktionsaufrufe extrem schnell gehen. Bei wenigen zu übewrgebenden Daten ist der Hardwarestack eigentlich gut. Außerdem steckt die Rechenzeit eh nur in der Schleife zum Partitionieren, Du kannst also kostenlos den Ansatz nehmen, der einfacher ist.

[hustbaer]

Also ich hab mich mal ein wenig gespielt...
Meine Version tauscht wohl öfter als nötig, aber dafür ist sie IMO halbwegs simpel, und vor allem: sie funktioniert

#include <boost/type_traits/is_integral.hpp>
#include <boost/type_traits/is_signed.hpp>
#include <boost/static_assert.hpp>
#include <cassert>
#include <limits>

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template <class T>
struct get_high_bit
{
	static T const value = T(1) << (sizeof(T) * CHAR_BIT - 1);
};

// makes bit_sort work with signed integers
// (if the machine uses two's complement)
template <class It>
typename It::value_type magick_deref(It it)
{
	typedef typename It::value_type value_type;
	static value_type const flip_mask = boost::is_signed<value_type>::value ? get_high_bit<value_type>::value : 0;

	return (*it) ^ flip_mask;
}

template <class FwdIt>
void bit_sort_impl(FwdIt begin, FwdIt end, bool ascending)
{
	typedef typename FwdIt::value_type value_type;
	BOOST_STATIC_ASSERT(boost::is_integral<value_type>::value);

	// scan for relevant bits
	value_type relevant_bits = 0;

	{
		value_type set_bits = 0;
		value_type clear_bits = 0;
		for (FwdIt it = begin; it != end; ++it)
		{
			value_type const v = magick_deref(it);
			set_bits |= v;
			clear_bits |= ~v;
		}

		relevant_bits = set_bits & clear_bits;
	}

	if (relevant_bits == 0)
		return;

	// sort
	static value_type const high_bit_mask = get_high_bit<value_type>::value;

	value_type completed_bits = 0;
	// NOTE: (bit_mask >> 1) & (~high_bit_mask) is necessary to clear the sign bit in signed types after shifting
	for (value_type bit_mask = high_bit_mask; bit_mask != 0; bit_mask = (bit_mask >> 1) & (~high_bit_mask))
	{
		if ((bit_mask & relevant_bits) == 0)
			continue; // skip irrelevant bits

		value_type current_sub_partition = magick_deref(begin) & completed_bits;
		value_type first_partition_value = ascending ? 0 : bit_mask;
		FwdIt swap_pos(begin);
		for (FwdIt it(begin); it != end; ++it)
		{
			value_type v = magick_deref(it);

			// check for sub-partition change
			if ((v & completed_bits) != current_sub_partition)
			{
				swap_pos = it;
				current_sub_partition = v & completed_bits;
			}

			// swap
			if ((v & bit_mask) == first_partition_value)
			{
				std::iter_swap(swap_pos, it);
				++swap_pos;
			}
		}

		completed_bits |= bit_mask;
	}

	assert(completed_bits == relevant_bits);
}

template <class FwdIt>
void bit_sort_asc(FwdIt begin, FwdIt end)
{
	bit_sort_impl(begin, end, true);
}

template <class FwdIt>
void bit_sort_desc(FwdIt begin, FwdIt end)
{
	bit_sort_impl(begin, end, false);
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// tests

#include <algorithm>
#include <vector>
#include <deque>
#include <list>
#include <iostream>

template <class CONTAINER>
CONTAINER make_random_sequence(size_t length)
{
	BOOST_STATIC_ASSERT(boost::is_integral<typename CONTAINER::value_type>::value);

	CONTAINER con;
	while (length--)
	{
		long long val =
			static_cast<long long>(rand())
			^ (static_cast<long long>(rand()) << 12)
			^ (static_cast<long long>(rand()) << 24)
			^ (static_cast<long long>(rand()) << 36)
			^ (static_cast<long long>(rand()) << 48)
			^ (static_cast<long long>(rand()) << 60);

		con.push_back(static_cast<typename CONTAINER::value_type>(val));
	}

	return con;
}

template <class CONTAINER>
size_t test_type_in_container(size_t sequence_size, size_t loops)
{
	typedef typename CONTAINER::value_type INT;
	BOOST_STATIC_ASSERT(boost::is_integral<INT>::value);

	std::cout << typeid(CONTAINER).name() << "...\n";

	size_t failures = 0;
	for (size_t i = 0; i < loops; i++)
	{
		// ascending

		CONTAINER s1 = make_random_sequence<CONTAINER>(sequence_size);
		CONTAINER s2 = s1;

		std::stable_sort(s1.begin(), s1.end()); // sort don't work with bidi iterators like list<T>::iterator
		bit_sort_asc(s2.begin(), s2.end());

		if (s1 != s2)
			failures++;

		// descending

		s1 = make_random_sequence<CONTAINER>(sequence_size);
		s2 = s1;

		std::stable_sort(s1.begin(), s1.end(), std::greater<INT>());
		bit_sort_desc(s2.begin(), s2.end());

		if (s1 != s2)
			failures++;
	}

	if (failures != 0)
		std::cout << "FAILED.\n";

	return failures;
}

template <class INT>
size_t test_type(size_t sequence_size, size_t loops)
{
	size_t failures = 0;
	failures += test_type_in_container<std::vector<INT> >(sequence_size, loops);
	failures += test_type_in_container<std::deque<INT> >(sequence_size, loops);
	failures += test_type_in_container<std::list<INT> >(sequence_size, loops);
	return failures;
}

size_t test_all()
{
	size_t const sequence_sizes[] = { 6, 20, 50, 1000 };
	size_t const loops = 10;

	size_t failures = 0;

	for (size_t i = 0; i < (sizeof(sequence_sizes)/sizeof(sequence_sizes[0])); ++i)
	{
		size_t const seqsz = sequence_sizes[i];

		failures += test_type<char>(seqsz, loops);
		failures += test_type<signed char>(seqsz, loops);
		failures += test_type<unsigned char>(seqsz, loops);
		failures += test_type<signed int>(seqsz, loops);
		failures += test_type<unsigned int>(seqsz, loops);
		failures += test_type<signed short>(seqsz, loops);
		failures += test_type<unsigned short>(seqsz, loops);
		failures += test_type<signed long>(seqsz, loops);
		failures += test_type<unsigned long>(seqsz, loops);
		failures += test_type<signed long long>(seqsz, loops);
		failures += test_type<unsigned long long>(seqsz, loops);
	}

	return failures;
}

int main(int argc, char** argv)
{
	if (test_all() == 0)
		std::cout << "\nall passed :)\n";

	return 0;
}

[hustbaer]

um den bereich "abzustecken", gucke ich mir also das höherwertige bit an,
was im letzen durchlauf verwendet wurde. HIER VERMUTE ICH DEN FEHLER!

jopp. du musst alle bereits abgearbeiteten bits angucken.