Skip to content

Instantly share code, notes, and snippets.

@gonzopancho
Created September 14, 2013 03:48
Show Gist options
  • Save gonzopancho/6558674 to your computer and use it in GitHub Desktop.
Save gonzopancho/6558674 to your computer and use it in GitHub Desktop.
#include "targetver.h"
#include <windows.h>
#include <iostream>
#include <tchar.h>
#include <assert.h>
using namespace std;
class VivaMeteringTimeStruct {
public:
VivaMeteringTimeStruct();
void StartMeteringTime();
void StopMeteringTime();
double GetUserSeconds() const;
private:
__int64 GetCurrentUserTime() const;
__int64 m_userTime;
bool m_isStoped;
};
VivaMeteringTimeStruct::VivaMeteringTimeStruct() {
m_userTime = 0;
m_isStoped = true;
}
__int64 VivaMeteringTimeStruct::GetCurrentUserTime() const {
FILETIME creationTime;
FILETIME exitTime;
FILETIME kernelTime;
FILETIME userTime;
bool result = GetThreadTimes(GetCurrentThread(), &creationTime, &exitTime,
&kernelTime, &userTime) != 0;
assert(result);
UNREFERENCED_PARAMETER(result);
__int64 curTime;
curTime = userTime.dwHighDateTime;
curTime <<= 32;
curTime += userTime.dwLowDateTime;
return curTime;
}
void VivaMeteringTimeStruct::StartMeteringTime() {
assert(m_isStoped);
m_isStoped = false;
m_userTime = GetCurrentUserTime();
}
void VivaMeteringTimeStruct::StopMeteringTime() {
assert(!m_isStoped);
m_isStoped = true;
__int64 curUserTime = GetCurrentUserTime();
assert(m_userTime <= curUserTime);
m_userTime = curUserTime - m_userTime;
}
double VivaMeteringTimeStruct::GetUserSeconds() const {
assert(m_isStoped);
return static_cast<double>(m_userTime) / 10000000.0;
}
const unsigned ArrayWidth_32 = 11;
const unsigned ArrayHeight_32 = 14;
const size_t ArrayWidth_64 = ArrayWidth_32;
const size_t ArrayHeight_64 = ArrayHeight_32;
const unsigned StartX_32 = 3;
const unsigned StartY_32 = 3;
const unsigned FinishX_32 = ArrayWidth_32 - StartX_32;
const unsigned FinishY_32 = ArrayHeight_32 - StartY_32;
const size_t StartX_64 = StartX_32;
const size_t StartY_64 = StartY_32;
const size_t FinishX_64 = FinishX_32;
const size_t FinishY_64 = FinishY_32;
typedef char FieldCell;
#define FREE_CELL 1
#define BARRIER_CELL 2
#define TRAVERSED_PATH_CELL 3
unsigned FindMinPathFromPoint32(FieldCell (*field)[ArrayHeight_32], unsigned x,
unsigned y, unsigned bestPathLen,
unsigned currentPathLen) {
++currentPathLen;
if (currentPathLen >= bestPathLen)
return UINT_MAX;
if (x == FinishX_32 && y == FinishY_32)
return currentPathLen;
FieldCell oldState = field[x][y];
field[x][y] = TRAVERSED_PATH_CELL;
unsigned len = UINT_MAX;
if (x > 0 && field[x - 1][y] == FREE_CELL) {
unsigned reslen = FindMinPathFromPoint32(field, x - 1, y, bestPathLen, currentPathLen);
len = min(reslen, len);
}
if (x < ArrayWidth_32 - 1 && field[x + 1][y] == FREE_CELL) {
unsigned reslen = FindMinPathFromPoint32(field, x + 1, y, bestPathLen, currentPathLen);
len = min(reslen, len);
}
if (y > 0 && field[x][y - 1] == FREE_CELL) {
unsigned reslen = FindMinPathFromPoint32(field, x, y - 1, bestPathLen, currentPathLen);
len = min(reslen, len);
}
if (y < ArrayHeight_32 - 1 && field[x][y + 1] == FREE_CELL) {
unsigned reslen = FindMinPathFromPoint32(field, x, y + 1, bestPathLen, currentPathLen);
len = min(reslen, len);
}
field[x][y] = oldState;
if (len >= bestPathLen)
return UINT_MAX;
return len;
}
size_t FindMinPath32(FieldCell (*field)[ArrayHeight_32]) {
unsigned BestPathLen = UINT_MAX;
field[StartX_32][StartY_32] = TRAVERSED_PATH_CELL;
unsigned ret = FindMinPathFromPoint32(field, StartX_32, StartY_32, BestPathLen, 0);
if (ret == UINT_MAX)
return SIZE_MAX;
return ret;
}
size_t FindMinPathFromPoint64(FieldCell (*field)[ArrayHeight_64], size_t x,
size_t y, size_t bestPathLen,
size_t currentPathLen) {
++currentPathLen;
if (currentPathLen >= bestPathLen)
return SIZE_MAX;
if (x == FinishX_64 && y == FinishY_64)
return currentPathLen;
FieldCell oldState = field[x][y];
field[x][y] = TRAVERSED_PATH_CELL;
size_t len = SIZE_MAX;
if (x > 0 && field[x - 1][y] == FREE_CELL) {
size_t reslen = FindMinPathFromPoint64(field, x - 1, y, bestPathLen, currentPathLen);
len = min(reslen, len);
}
if (x < ArrayWidth_64 - 1 && field[x + 1][y] == FREE_CELL) {
size_t reslen = FindMinPathFromPoint64(field, x + 1, y, bestPathLen, currentPathLen);
len = min(reslen, len);
}
if (y > 0 && field[x][y - 1] == FREE_CELL) {
size_t reslen = FindMinPathFromPoint64(field, x, y - 1, bestPathLen, currentPathLen);
len = min(reslen, len);
}
if (y < ArrayHeight_64 - 1 && field[x][y + 1] == FREE_CELL) {
size_t reslen = FindMinPathFromPoint64(field, x, y + 1, bestPathLen, currentPathLen);
len = min(reslen, len);
}
field[x][y] = oldState;
if (len >= bestPathLen)
return SIZE_MAX;
return len;
}
size_t FindMinPath64(FieldCell (*field)[ArrayHeight_64]) {
unsigned BestPathLen = UINT_MAX;
field[StartX_64][StartY_64] = TRAVERSED_PATH_CELL;
return FindMinPathFromPoint64(field, StartX_64, StartY_64, BestPathLen, 0);
}
int _tmain(int argc, _TCHAR* argv[])
{
int nRetCode = 0;
try {
FieldCell (*field)[ArrayHeight_64] = new FieldCell[ArrayWidth_64][ArrayHeight_64];
DWORD startTime = GetTickCount();
for (size_t x = 0; x != ArrayWidth_64; ++x)
for (size_t y = 0; y != ArrayHeight_64; ++y)
field[x][y] = rand() % 3 == 1 ? BARRIER_CELL : FREE_CELL;
field[StartX_64][StartY_64] = FREE_CELL;
field[FinishX_64][FinishY_64] = FREE_CELL;
for (size_t x = 0; x != ArrayWidth_64; ++x) {
for (size_t y = 0; y != ArrayHeight_64; ++y) {
char symbol;
switch (field[x][y]) {
case FREE_CELL: symbol = '.'; break;
case BARRIER_CELL: symbol = 'O'; break;
case TRAVERSED_PATH_CELL: symbol = '*'; break;
default: symbol = 'E'; assert(false); break;
}
cout << symbol;
}
cout << endl;
}
VivaMeteringTimeStruct metric;
size_t minLen;
metric.StartMeteringTime();
minLen = FindMinPath32(field);
metric.StopMeteringTime();
cout << endl << "32 bit type:" << endl;
if (minLen == SIZE_MAX)
cout << "No path found" << endl;
else
cout << "Minimal path len = " << minLen << endl;
cout << "Total time : " << metric.GetUserSeconds() << endl;
cout << endl;
cout << endl << "64 bit type:" << endl;
metric.StartMeteringTime();
minLen = FindMinPath64(field);
metric.StopMeteringTime();
if (minLen == SIZE_MAX)
cout << "No path found" << endl;
else
cout << "Minimal path len = " << minLen << endl;
cout << "Total time : " << metric.GetUserSeconds() << endl;
delete [] field;
}
catch (...) {
cout << "Fatal Error: some exception..." << endl;
nRetCode = 1;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment