The Fast Marking Algorithm



  • Ehrlich gesagt raff ich es nicht. Egal, was ich auch mache, um zu wissen, in welchem der Räume ein Schatz liegt, muss ich sozusagen in jeden Raum gehen und schauen, ob dort einer ist. Wie ich mir das Ganze dann merke, ist doch ziemlich egal. Dadurch, dass ich mir jeden Raum anschaue, habe ich O(n).

    Habe ich da einen totalen Denkfehler drin?



  • Es geht ja nur um das Initialisieren, nicht um das anschließende Räumebesuchen.
    Bei der Java-Variante werden alle 20.000 Elemente des Arrays anfangs auf false gesetzt, also läuft das in O(n).
    Beim Fast-Marking-Algorithmus entfällt das Initialisieren. Der Name ist aber irreführend, das Markieren an sich dauert nämlich länger als beim "naiven" Ansatz.



  • Da ist mal premature optimization the root of all evil. Zuerst wird mal doppelt so viel Speicher verbraucht und ein total simpler Algorithmus unnötig komplex gemacht. Und beim Test ob ein Element schon markiert ist, muss dreimal soviel geprüft werden wie beim simplen Algorithmus und das markieren ist auch aufwendiger. Bis alle Elemente markiert sind hat der "schnelle" Marker dann wahrscheinlich 10 mal so lang gebraucht. 🙄



  • extremTop schrieb:

    Bis alle Elemente markiert sind hat der "schnelle" Marker dann wahrscheinlich 10 mal so lang gebraucht. 🙄

    Richtig. Aber man will garnicht alle Felder markieren, sondern nur relativ wenige. Und dann ist es wirklich schneller.

    Das Problem ist, dass malloc nicht in O(1)\mathcal{O}(1) operiert.

    Ein anderes Problem ist, dass wenn n so groß ist, dass sich das Anwenden des Algorithmus lohnt, auch ohne Ende Speicher gebraucht wird. Dann ist zwar der Zugriff auf den Speicher immer noch O(1)\mathcal{O}(1), aber sobald ich den Cache des Prozessors verlasse, wird die konstante Zugriffszeit größer und sobald ich auf die Festplatte auslagern muss, habe ich ganz verloren.

    Eine wesentlich bessere Lösung ist eine Hash-Tabelle. Die hat, wenn es richtig gemacht wird, eine durchschnittliche Zugriffszeit von O(1)\mathcal{O}(1).



  • Der Zwerg schrieb:

    When we want to mark an item, instead of setting the corresponding element of array to true, we let it point to the next position in marks and we increment the number of marks. Now, we have this element in marks point back to the element in array. This way, an element in array can, by chance, point to an element in marks, but this won’t matter since the element in marks won’t point back, and so we can determine it’s fake.

    Warum ist es nicht möglich, dass das Element in marks zufälligerweise auch zurückzeigt?



  • Nexus schrieb:

    Der Zwerg schrieb:

    When we want to mark an item, instead of setting the corresponding element of array to true, we let it point to the next position in marks and we increment the number of marks. Now, we have this element in marks point back to the element in array. This way, an element in array can, by chance, point to an element in marks, but this won’t matter since the element in marks won’t point back, and so we can determine it’s fake.

    Warum ist es nicht möglich, dass das Element in marks zufälligerweise auch zurückzeigt?

    Weil zusätzlich noch die Anzahl der gültigen Marks abgespeichert wird.



  • Man kann doch einfach ein Array nehmen (nicht initialisiert) und darin die Raumnummer der besuchten Räume von vorne nach hinten abspeichern. Dazu merkt man sich noch wie viele Räume abgespeichert sind.
    Und schon hat man auch O(1) bei der Initialisierung.



  • Storm.Xapek.de schrieb:

    Man kann doch einfach ein Array nehmen (nicht initialisiert) und darin die Raumnummer der besuchten Räume von vorne nach hinten abspeichern. Dazu merkt man sich noch wie viele Räume abgespeichert sind.
    Und schon hat man auch O(1) bei der Initialisierung.

    Aber dann hat man nicht mehr O(1)\mathcal{O}(1) bei der Überprüfung, ob der Raum belegt ist.



  • ipsec schrieb:

    Weil zusätzlich noch die Anzahl der gültigen Marks abgespeichert wird.

    Also kann ein mark prinzipiell schon "aus Versehen" zurückzeigen, nur ist es dann nicht im gültigen Bereich. Danke für die Erklärung.



  • Habs mal nachgemessen.

    class Marker
    {
    public:
    	Marker(size_t size)
    	:marks(size, false)
    	{
        }
    
        void mark(size_t index) {
            marks[index] = true;
        }
    
        bool isMarked(size_t index) {
            return marks[index];
        }
    private:
    	std::vector<char> marks;
    };
    
    class FastMarker
    {
    public:
    	FastMarker(size_t size)
    	{
    		marks = new size_t[size];
    		ary = new size_t[size];
    		m_marksize = 0;
    		m_size = size;
        }
    
    	~FastMarker()
    	{
    		delete marks;
    		delete ary;
    	}
    
        void mark(size_t index) {
            marks[index] = m_marksize;
    		ary[m_marksize] = index;
    		m_marksize++;
        }
    
        bool isMarked(size_t index) {
            return marks[index]<m_size && marks[index]<m_marksize && ary[marks[index]]==index;
        }
    private:
    	size_t m_size;
    	size_t m_marksize;
    	size_t* marks;
    	size_t* ary;
    };
    
    class Set
    {
    public:
    	Set()
    	:marks()
    	{
        }
    
        void mark(size_t index) {
            marks.insert(index);
        }
    
        bool isMarked(size_t index) {
            return marks.find(index)!=marks.end();
        }
    private:
    	std::set<size_t> marks;
    };
    
    std::vector<size_t> getMarks(size_t size)
    {
    	std::vector<size_t> vec(size);
    	for(size_t i = 0; i<size; i++)
    	{
    		vec[i]=i;
    	}
    	std::random_shuffle(vec.begin(), vec.end());
    	return vec;
    }
    
    #define SET
    
    void test(size_t marksSize, size_t size)
    {
    	std::vector<size_t> marks = getMarks(marksSize);
    	clock_t start = clock();
    	for(size_t i = 0;i<1000; i++)
    	{
    #ifdef MARKER
    		Marker marker(size);
    #endif
    #ifdef SET
    		Set marker;
    #endif
    #ifdef FMARKER
    		FastMarker marker(size);
    #endif
    		for(size_t m = 0;m<marksSize; m++)
    		{
    			if(!marker.isMarked(m))
    			{
    				marker.mark(m);
    			}
    			//else
    			//{
    			//	std::cout<<"error";
    			//}
    			//if(!marker.isMarked(m))
    			//{
    			//	std::cout<<"error2";
    			//}
    		}
    
    	}
    	clock_t end = clock();
    	std::cout<<"Size: "<<size<<" Marks: "<<marksSize<<" Time: "<<end-start<<std::endl;
    }
    
    int main(){
    	test(100,200000);
    	test(1000,200000);
    	test(10000,200000);
    	test(20000,200000);
    	test(100000,200000);
    	test(10000,20000000);
    	test(2000000,20000000);
    	test(10000000,20000000);
    }
    
    FastMarker:
    Size: 200000 Marks: 100 Time: 0
    Size: 200000 Marks: 1000 Time: 16
    Size: 200000 Marks: 10000 Time: 78
    Size: 200000 Marks: 20000 Time: 156
    Size: 200000 Marks: 100000 Time: 719
    Size: 20000000 Marks: 10000 Time: 93
    Size: 20000000 Marks: 2000000 Time: 14719
    Size: 20000000 Marks: 10000000 Time: 74125
    
    Marker:
    Size: 200000 Marks: 100 Time: 156
    Size: 200000 Marks: 1000 Time: 156
    Size: 200000 Marks: 10000 Time: 172
    Size: 200000 Marks: 20000 Time: 172
    Size: 200000 Marks: 100000 Time: 234
    Size: 20000000 Marks: 10000 Time: 25360
    Size: 20000000 Marks: 2000000 Time: 27047
    Size: 20000000 Marks: 10000000 Time: 33766
    
    Set:
    Size: 200000 Marks: 100 Time: 31
    Size: 200000 Marks: 1000 Time: 265
    Size: 200000 Marks: 10000 Time: 2782
    Size: 200000 Marks: 20000 Time: 5812
    Size: 200000 Marks: 100000 Time: 35125
    Size: 20000000 Marks: 10000 Time: 2782
    Size: 20000000 Marks: 2000000 Time: abgebrochen
    Size: 20000000 Marks: 10000000 Time: abgebrochen
    

    Bis zu ca. 1/10 der Markierungen setzen ist der FastMarker schneller. Bei der Hälfte setzen wird er schon deutlich langsamer. std::set ist so gut wie immer viel langsamer. Wenn einer Lust hat, kann er ja noch ne HashMap testen.

    Wenn man noch davon ausgehen würde, dass das setzen einer Markierung auch mehrmals aufgerufen wird, müsste man beim FastMarker noch ein isMarked vor dem m_marksize++; einbauen und dann wäre er noch etwas langsamer.



  • Die Initialisierung beim Marker könnte man natürlich noch parallelisieren und so die Zeit bei großen Arrays halbieren, vierteln...



  • Messer schrieb:

    Die Initialisierung beim Marker könnte man natürlich noch parallelisieren und so die Zeit bei großen Arrays halbieren, vierteln...

    Der Flaschenhals dürfte meistens die Geschwindigkeit des Speichers sein. Also mal angenommen, dass du keinen Cluster, sondern eine SMP-Maschine hast.


Anmelden zum Antworten