Filter: 2013-08-25

Vor kurzem lief mir ein interessanter Bug über den Weg, dazu erst kurzer Beispielcode:

uint64_t nTimeout;
 
void Func1()
{
    uint64_t nTickCount = GetTickCount();
    myLock.lock();
    ...
    nTimeout = nTickCount;
    ...
    myLock.unlock();
}
 
void Func2()
{
    uint64_t nTickCount = GetTickCount();
    myLock.lock();
    ...
    if((nTickCount-nTimeout)/1000>30) // Beispiel 30s 
        // Timeout
    ...
    myLock.unlock();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Auswirkungen

Func1 und Func2 werden von unterschiedlichen Threads aufgerufen. Func1 setzt ab und zu, aber rechtzeitig innerhalb der 30s den Timeout zurück. Trotzdem wirft Func2 ab und zu einen Timeout.

Analyse

Der Code hat mindestens zwei Probleme:

Das erste Problem ist, dass der TickCounter jeweils vor der Sperre gelesen wird. So kann es passieren, das innerhalb der Sperre in Func2 nTickCount kleiner als nTimeout ist. Dies ist dann der Fall, wenn nach dem Lesen des TickCounters in Func2 der Thread angehalten wird…

Die binäre Suche hilft sehr schnell zu entscheiden, ob ein Element in einem sortierten Datenfeld vorhanden ist. Dabei werden maximal nur log2(n) Vergleiche benötigt, die Position zu finden, an der dieses Element sein sollte sofern vorhanden.

Beispiel (Quellcode): binarysearch.cpp
Download (Quellcode): binarysearch.zip

Beschreibung

Die binäre Suche schaut in der Mitte des Datenfeldes, ob der gesuchte Wert größer oder kleiner des Feldschlüsselwertes ist. Ist er kleiner, wird der untere Teil des Datenfeldes weiter benutzt, im anderen Fall der obere. Bei nächsten Durchlauf, wird mit dem entsprechenden Teilfeld weitergearbeitet. Die Suche ist beendet, wenn nur noch ein Element vorhanden ist und dieses dem gesuchten Wert entspricht.

Aufgrund dieser Vorgehensweise, ist es unbedingt notwendig, dass dieses Datenfeld sortiert ist. Nur in diesem Fall kann davon ausgegangen werden, dass nach dem Wertevergleich, das entsprechende Teilfeld den Suchwert nicht enthalten kann.

Beispieldarstellung

In diesem Bild wird di…

Mergesort gehört auf Grund der vorhersagbaren, stabilen Laufzeit, der möglichen stabilen Sortierung und der möglichen Parallelisierung zu den beliebten Sortierverfahren. Die Anzahl der nötigen Schiebeoperationen liegt bei n*log2(n), die Anzahl der maximal benötigten Vergleiche kann durch die Summe der log(n) Durchläufe von den Zweiterpotenzen des Durchlaufs minus Eins errechnet werden.

Beispiel (Quellcode): mergesort.cpp
Download (Quellcode): mergesort.zip

Aufteilung des Feldes

Bei der rekursiven Variante ist es möglich, das Eingangsfeld immer zu halbieren (linke und rechte Hälfte), bis nur zwei oder weniger Elemente zu Verfügung stehen. Die maximale Rekursionsebene liegt bei log2 der Elementgesamtanzahl. Bei Beispielhaften 65536 Elementen also nur 16 Ebenen.

Bei der nicht rekursiven/iterativen Variante, wird direkt mit der kleinstmöglichen Teilfeldgröße (zwei Elemente) begonnen und die Teilfeldgröße in jedem Durchgang erhöht/verdoppelt. Ebenso wie bei der rekursiven Variante beträgt die Anzahl der Durc…