Algorithmen Geeks aufgepasst, Denksportaufgabe!

[rean]

Hier mal ne quick'n'dirty-Lösung "mit der Hand am Arm" wie mein Mathelehrer immer so schön gesagt hat

#include <algorithm>
#include <vector>
#include <iostream>
#include <conio.h>
#include <cassert>

int main()
{
	const int d = 8;

	int t1[d] = { 10, 15, 18, 20, 26, 35, 47, 54 };

	std::vector<int> feld1( t1, t1+d ), feld2( d, 0 );

	int val;

	std::cin >> val;

	// Da du eh mindestens d/2-1 Elemente von feld1 nach feld2
	// kopieren musst kannst du val auch "auf dem Weg suchen"
	// Du solltest dir aber überlegen was das Verfahren in dem Fall
	// machen soll das val bereits in feld1 vorhanden ist.

	//ich arbeite hier mit schritthaltenden iteratoren
	std::vector<int>::reverse_iterator it1 = feld1.rbegin(),
		it2( std::vector<int>::iterator( &feld2[ d/2 ], &feld2 ) ),
		tmp_it;

	bool val_inserted = false;

	while( it2 != feld2.rend() )
	{
		// wenn val größer ist als der nächste zu kopierende
		// Wert nimmt val seinen Platz ein
		if( val > *it1 && !val_inserted )
		{
			*it2 = val;
			++it2;
			val_inserted = true;
		}
		// val ist kleiner als der nächste zu kopierende Wert
		// der Wert wird kopiert
		else if( val < *it1 || val_inserted )
		{
			*it2 = *it1;
			++it1;
			++it2;
		}
		else // Wenn ich das korrekt durchgedacht hab müsste val an
			 // dieser Stelle weder kleiner noch größer als nächste
			 // zu kopierende Wert sein, also gleich
		{
			assert( 0 );
		}
	}

	// wenn val bereits eingefügt wurde wird
	// der nächste zu kopierende Wert das neue val
	// An dieser Stelle wären wir dann fertig da
	// die restlichen Werte in feld1 verbleiben
	if( val_inserted )
	{
		val = *it1;
	}
	else
		if( val > *it1 ); //val ist größer als der größte verbleibende Wert
						  //in feld1, also bleibt val val
	else // val wurde noch nicht eingefügt
	{
		int nval = *it1; // Das größte verbleibende Element wird auf alle
						 // Fälle das neue val

		// Diesmal gehen wir bis zum 'vorletzten' Element, also bis begin
		std::vector<int>::reverse_iterator begin = feld1.rend();
		--begin;

		while( it1 != begin )
		{
			// Ablauf ähnlich wie oben
			if( val < *it1 )
			{
				tmp_it = it1;
				*tmp_it = *(++it1);
			}
			else if( val > *it1 ) break;
			else
			{
				assert( 0 ); // val ist bereits in feld1 vorhanden
			}
		}

		*it1 = val;
		val = nval;
	}

	_getch();

	return 0;

Das Nullen von feld1 hab ich mal weggelassen weil das für deinen Anwendungsfall eigentlich unnötig ist.

Das ist vielleicht minimal schneller als die Lösung von Michael weil du dir die binäre Suche sparst.
Ich würde aber die Lösung von Michael bevorzugen.

[hustbaer]

Die Stelle an die das "i" gehört kann man auch hübsch suchen, während man Elemente kopiert. Natürlich muss dazu selbst etwas mehr Code schreiben, und kann nichtmehr so schön std::copy etc. verwenden.

@rean:
Sehr D auf jeden Fall, ja
Man kann das auch viel schöner z.B. mit einem Method-Object lösen.

[rean]

hustbaer schrieb:

Die Stelle an die das "i" gehört kann man auch hübsch suchen, während man Elemente kopiert. Natürlich muss dazu selbst etwas mehr Code schreiben, und kann nichtmehr so schön std::copy etc. verwenden.

@rean:
Sehr D auf jeden Fall, ja
Man kann das auch viel schöner z.B. mit einem Method-Object lösen.

Zu meiner Verteidigung: Es ist spät und ich sollte eigentlich lernen
Die Lösung mit dem Method-Object würde mich interessieren, willste da mal nen Schnipsel posten?

Für den hier gegebenen Anwendungsfall dürfte es aber sinnvoll sein im Voraus zu gucken ob der neue Wert nicht schon vorhanden ist weil man sich dann das komplette splitten sparen kann. Und dann wären beide Lösungen gleichwertig, außer dass die von Michael viel weniger Programmierarbeit ist.

[hustbaer]

Inetwa so z.B.:

#include <iostream>
#include <cassert>

template <class T>
T insert_split(T* page1, T* page2, size_t pageSize, T newElement)
{
	struct method_object
	{
		T* const page1;
		T* const page2;
		size_t const pageSize;

		T* next_output_ptr; // where the next element shall go
		T* output_segment_back_ptr; // the last position in the current output segment that we can write to (NOT one-past-last!)

		T run(T const& newElement)
		{
			// setup first output segment
			next_output_ptr = page1;
			output_segment_back_ptr = final_page1_back_ptr();

			assert(pageSize >= 2);

			T buffer = page1[0];
			bool newElementInserted = false;

			for (size_t i = 0; i < pageSize; i++)
			{
				T const current = buffer;

				// if there is another element after "current",
				// we have to buffer it, because writing the current element
				// could overwrite it, if the new element is inserted anywhere in page1
				if ((i + 1) < pageSize)
					buffer = page1[i + 1];

				// emit the new element before "current", if "current" is bigger
				if ((!newElementInserted) && current > newElement)
				{
					emit(newElement);
					newElementInserted = true;
				}

				// emit the "current" element
				emit(current);
			}

			// if the new element goes in last, it hasn't been emitted yet
			if (!newElementInserted)
				emit(newElement);

			// return the new middle element
			return *final_middle_element_ptr();
		}

		void emit(T const& element)
		{
			*next_output_ptr = element;

			// check if the current output segment is full, and switch to the next one if necessary
			if (next_output_ptr == output_segment_back_ptr)
			{
				if (output_segment_back_ptr == final_page1_back_ptr())
				{
					// switch from segment 1 (page1) to segment 2 (middle element)
					next_output_ptr = final_middle_element_ptr();
					output_segment_back_ptr = next_output_ptr; // only one element
				}
				else if (output_segment_back_ptr == final_middle_element_ptr())
				{
					// switch from segment 2 (middle element) to segment 3 (page2)
					next_output_ptr = page2;
					output_segment_back_ptr = page2 + final_page2_size();
					// NOTE: this is actually the "end" position (=one-past-last),
					//       but that's the easiest way to not trigger the assert below
					//       when the last element is being emitted
				}
				else
					assert(0 && "logic error :(");
			}
			else
				next_output_ptr++;
		}

		// the final size of page1
		size_t final_page1_size() const { return (pageSize + 1) / 2; }

		// the final size of page2
		size_t final_page2_size() const { return pageSize - final_page1_size(); }

		// the position of the last element in page1
		T* final_page1_back_ptr() const { return page1 + (final_page1_size() - 1); }

		// pointer to where the new middle element shall be stored after we're done
		// NOTE: we use the space after the last used element of page2.
		//       of course we could also use an extra variable of type T instead.
		T* final_middle_element_ptr() const { return page2 + final_page2_size(); }

	}
		mo = { page1, page2, pageSize };

	return mo.run(newElement);
}

/////////////////////////////////////////////////////////////////////////////
// test code
/////////////////////////////////////////////////////////////////////////////

template <class T>
void dump(T* page1, T* page2, size_t pageSize, T middleElement)
{
	for (size_t i = 0; i < pageSize; i++)
	{
		std::cout << page1[i];
		if ((i + 1) < pageSize)
			std::cout << ", ";
	}

	std::cout << "\n" << middleElement << "\n";

	for (size_t i = 0; i < pageSize; i++)
	{
		std::cout << page2[i];
		if ((i + 1) < pageSize)
			std::cout << ", ";
	}

	std::cout << "\n\n";
}

template <class T>
void test(T e1, T e2, T e3, T e4, T newElement)
{
	T page1[4] = { e1, e2, e3, e4 };
	T page2[4] = { T(), T(), T(), T() };

	dump(page1, page2, 4, newElement);

	T middle = insert_split(page1, page2, 4, newElement);

	dump(page1, page2, 4, middle);

	std::cout << "--------------------------\n";
}

int main()
{
	// in page 1
	test(10, 20, 30, 40, 12);

	// in page 2
	test(10, 20, 30, 40, 35);

	// first
	test(10, 20, 30, 40, 5);

	// last
	test(10, 20, 30, 40, 50);

	return 0;
}

Sieht jetzt mächtig riesig aus, aber wenn man den Test-Code und die Kommentare wegnimmt, dann ist es eigentlich recht schlank.

Die Funktion geht "page1" genau 1x durch (jedes Element wird 1x gelesen), und zwar in vorwärts Richtung. Verglichen wird während des Kopierens. Und kopiert (geschrieben) wird auch immer in vorwärts Richtung.

Wenn das Kopieren von Elementen relativ teuer ist, liesse sich die Funktion relativ einfach umbauen so dass ...
* Elemente nicht "auf sich selbst" kopiert werden
* Elemente ausschliesslich mit swap()/move() getauscht/bewegt werden

Hab ich mir der Einfachkeit halber mal gespart.

p.S.: mir ist durchaus klar, dass man ein paar Dinge einfacher schreiben könnte, wenn man davon ausgeht dass die Page-Grösse immer durch 2 teilbar ist. Und dass es für B-Bäume kaum Sinn macht, eine nicht durch 2 teilbare Grösse zu verwenden.

[hustbaer]

p.p.S.: ich denke auch dass "meine" Variante kaum jemals schneller sein wird als die einfache Suchen + Kopieren Variante. Ganz einfach weil die Kopierschleife in "meiner" Variante wesentlich komplizierter ist. Was vermutlich schwerer wiegt als der extra Such-Durchgang bzw. das Rückwärts-Kopieren in der Suchen + Kopieren Variante. Speziell wenn man binär such, und die Daten vor dem Funktionsaufruf schon im Cache stehen (was wohl oft der Fall sein wird).

Der (theoretische) Vorteil wäre, dass alle Daten sequentiell verarbeitet werden, also kein Random-Access und kein rückwärts Kopieren. Würde vielleicht was bringen wenn man grosse Datenmengen direkt von HDD zu HDD kopiert, aber mit ein paar wenigen tausend Integers im RAM wohl eher nicht.

Und der Vorteil den ich in der Verwendung eines Method-Objects sehe, ist, dass alles viel übersichtlicher wird. Auch wenn man im Endeffekt ein paar Zeilen mehr schreibt/liest. Man muss sich nur mal ansehen wie kurz und gut verständlich die Kopier-Schleife wird.

------

Achja, nochwas: wenn man in Kauf nimmt dass page1 und page2 nach dem Aufruf von insert_split vertauscht sind, kann man sich natürlich das "Puffern" des nächsten Elements sparen - man schreibt ja dann zuerst nach page2, und es besteht nie die Chance dass man das als nächstes zu bearbeitende Element in page1 überschreibt.

Dadurch würde die Kopierschleife deutlich einfacher.

Und wenn man davon ausgeht, dass der Compiler gut Inlining betreibt, könnte es noch was bringen, denn äusseren "else" Zweig in "emit()" zu eliminieren, und "next_output_ptr++" unconditional auszuführen. Spart dann einen Sprung, und sollte sich leicht machen lassen.

Allerdings schätze ich, dass selbst mit diesen Änderungen "meine" Variante noch nicht schneller sein wird, als die Suchen + Kopieren Variante.

Um das auszuprobieren ist es mir aber jetzt schon zu spät *schnurch*

[BitShift]

Hallo zusammen,

ich bin echt platt! Ihr habt Euch gestern Nacht noch mächtig ins Zeug gelegt! Ich schaue mir Eure Lösungsvorschläge in Ruhe an und melde mich dann wieder bei Euch.

Gruß,
B!

[knivil]

#include <iostream>

void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main()
{
    const int size = 4;
    int feld1[size] = {10, 20, 30, 40};
    int feld2[size] = {0};
    int i = 12;

    for(int k = 0; k < size; ++k) if (i < feld1[k]) swap(&i,&feld1[k]);
    for(int k = size/2+1, l = 0; k < size; ++k, ++l) feld2[l] = feld1[k];
    feld2[size/2-1] = i;
    i = feld1[size/2];
    // set to zeros
    for(int k = size/2; k< size; ++k) feld1[k] = 0;

    // testing

    // printing
    std::cout << "feld1: ";
    for(int l = 0; l < size; ++l)
    {
        std::cout << feld1[l] << " ";
    }
    std::cout << std::endl;

    std::cout << "feld2: ";
    for(int l = 0; l < size; ++l)
    {
        std::cout << feld2[l] << " ";
    }
    std::cout << std::endl << "i: " << i << std::endl;

    return 0;
}

5 Zeilen Code in C++. Das kan man gerne auch noch in Templates packen. Man braucht nur eine swap- und eine Vergleichsfunktion. Aufpassen muss man nur, falls die Laenge der Ausgangsarrays ungerade ist. Alle anderen vorgestellten Loesungen sind mir zu kompliziert.

[hustbaer]

Hihi, sehr elegant.
Damit schlägst du vermutlich auch die Suchen + Kopieren Variante

[Anti-Obfuscator]

knivil schrieb:

5 Zeilen Code in C++.

Bei vernüftiger Einrückung wären es mindestens 10.

[hustbaer]

Anti-Obfuscator schrieb:

knivil schrieb:

5 Zeilen Code in C++.

Bei vernüftiger Einrückung wären es mindestens 10.

Das sehe ich auch so.
Trotzdem finde ich den Code sehr elegant (abgesehen von der Formatierung).

[rean]

knivil schrieb:

#include <iostream>

void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main()
{
    const int size = 4;
    int feld1[size] = {10, 20, 30, 40};
    int feld2[size] = {0};
    int i = 12;

    for(int k = 0; k < size; ++k) if (i < feld1[k]) swap(&i,&feld1[k]);
    for(int k = size/2+1, l = 0; k < size; ++k, ++l) feld2[l] = feld1[k];
    feld2[size/2-1] = i;
    i = feld1[size/2];
    // set to zeros
    for(int k = size/2; k< size; ++k) feld1[k] = 0;

    // testing

    // printing
    std::cout << "feld1: ";
    for(int l = 0; l < size; ++l)
    {
        std::cout << feld1[l] << " ";
    }
    std::cout << std::endl;

    std::cout << "feld2: ";
    for(int l = 0; l < size; ++l)
    {
        std::cout << feld2[l] << " ";
    }
    std::cout << std::endl << "i: " << i << std::endl;

    return 0;
}

5 Zeilen Code in C++. Das kan man gerne auch noch in Templates packen. Man braucht nur eine swap- und eine Vergleichsfunktion. Aufpassen muss man nur, falls die Laenge der Ausgangsarrays ungerade ist. Alle anderen vorgestellten Loesungen sind mir zu kompliziert.

Über Eleganz kann man sich streiten, Fakt ist jedoch dass du wesentlich mehr herumkopierst. Bei einfachen ints ist das natürlich egal, bei anderen Typen kanns da schon wieder ganz anders aussehen.