Проблема интервью c++: найти остров в 2D сетки


Я задал этот вопрос из интервью он-лайн кодирвоание и мне предоставили мое решение, которое проходит все тесты. Я хотел увидеть, если кто-то может посмотреть мой код.

Вы можете найти мое решение ниже, используя поиск в ширину. Вот также ссылка на вопрос, который был задан в Pramp.

Остров Графа

Учитывая 2Д binaryMatrix массив из 0 и 1, выполнять getNumberOfIslands функцию, которая возвращает количество островов 1С в binaryMatrix.

Остров определяется как группа смежных значений, 1С. Ячейки в binaryMatrix является прилегает к другой ячейке, если они находятся рядом друг с ЛЮБОМ на одной и той же строке или столбце. Обратите внимание, что два значения 1 не являются частью того же острова, если они делятся только взаимной “углу” (т. е. по диагонали соседей).

Объяснить и код самое эффективное решение возможно и проанализируйте свое время и пространство сложности.

input:  binaryMatrix = [ [0,    1,    0,    1,    0],
                         [0,    0,    1,    1,    1],
                         [1,    0,    0,    1,    0],
                         [0,    1,    1,    0,    0],
                         [1,    0,    1,    0,    1] ]

output: 6 # since this is the number of islands in binaryMatrix.
          # See all 6 islands color-coded below.
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

#define AND &&
using namespace std;

int getNumberOfIslands( const vector<vector<int>>& binaryMatrix ) 
{
  int ans=0;
  int n = binaryMatrix.size();
  if (!n) return 0;
  int m = binaryMatrix[0].size();
  unordered_set<int> *used = new unordered_set<int>[n];
  for (int i=0; i<n; i++) used[i].clear();
 //Implementation through Breadth First Search
 // starting origin for my x and y coordinates 
  int dx[] = {-1, 1, 0, 0};
  int dy[] = {0, 0, -1, 1};
  queue< pair<int, int> > q;



  for (int i=0; i<n; i++)
    for (int j=0; j<m; j++){

      if (!used[i].count(j) AND binaryMatrix[i][j]==1){

        ans++;

        q.push(make_pair(i, j));
        used[i].insert(j);
        while (!q.empty()){
          pair<int, int> pos = q.front();
          q.pop();

          for (int k=0; k<4; k++){
            int nx = pos.first+dx[k];
            int ny = pos.second+dy[k];
            if (nx<0 || nx>=n) continue;
            if (ny<0 || ny>=m) continue;
            if (used[nx].count(ny)) continue;
            if (binaryMatrix[nx][ny]!=1) continue;

            used[nx].insert(ny);
            q.push(make_pair(nx, ny));


          }



        }

      }

    }

  return ans;

}  



int main() {
  return 0;
}

Мой код проходит все тесты:

Test Case #1
Input: [[0]],Expected: 0,Actual: 0
Test Case #2
Input: [[1]],Expected: 1,Actual: 1
Test Case #3
Input: [[1,0,1,0]],Expected: 2,Actual: 2
Test Case #4
Input: [[1,0,1,0],[0,1,1,1],[0,0,1,0]],Expected: 2,Actual: 2
Test Case #5
Input: [[1,0,1,0],[0,1,1,1],[0,0,1,0],[1,1,0,0],[0,1,0,1]],Expected: 4,Actual: 4
Test Case #6
Input: [[0,1,0,1,0],[0,0,1,1,1],[1,0,0,1,0],[0,1,1,0,0],[1,0,1,0,1]],Expected: 6,Actual: 6
Test Case #7
Input: [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]],Expected: 1,Actual: 1


508
2
задан 11 апреля 2018 в 01:04 Источник Поделиться
Комментарии
3 ответа

Не использовать using namespace std

Это считается плохой практикой.

Не определить AND

Есть уже and в качестве альтернативы &&.

Использовать std::vector вместо new[]

У вас есть утечка памяти в данный момент, так как вы забыли delete[] выделенной памяти. std::vector предотвращает эту ошибку.

Использовать подходящие структуры данных

Мы используем массив unordered_set<int>С где std::unordered_set< std::pair<int,int> > будет достаточным. Кроме того, clear() не надо. Если ваше std::unordered_set реализация разрывается, std::unordered_set начинается пустой.

Рассмотрим const для переменных, которые не должны меняться

dx, dy, n и m никогда не должен меняться. const гарантирует, что вы не измените их случайно.

Всегда используйте фигурные скобки вокруг блока

Без брекетов после структуры управления привели к несколько ошибок, которые было трудно поймать. Всегда используйте их. Таким образом, вы не случайно забыли разместить их в случае необходимости.

11
ответ дан 11 апреля 2018 в 08:04 Источник Поделиться

Рекомендуется использовать с std::массив, где можно, что везде, где у вас есть массив, размер которого заранее знаешь. По сути, это современный c++ обертка вокруг старой массивы c стиль, так что вы получите все скорости int[] и четкость и сохранность вещей, как вектор.

Это хорошо, что есть комментарии, и комментарии, которые описывают в общей алгоритм и как различные части способствуют этому золото. Тем не менее, я лично нашел комментарий о широте поиска запутанным. Он мог бы сделать с несколько слов о том, как искать вписывается в проблему. Что-то вроде "широта первого поиска, чтобы найти границы острова".

Более выразительные имена переменных будут сделать вещи гораздо яснее. Одиночные переменные письме может почти всегда быть услужливо заменили то, что говорит, что это предназначается, чтобы сделать. Есть исключения, например, если вы реализуете стандартная математики и используя те же переменные, как в вашей ссылке текст, но это не этот случай. Даже просто используя ширину и высоту вместо N и M поможет.

Мне нравится использовать с std::пара в очереди. Он правильно представляет, что это не два разных номера, но в одной координате. Я бы, наверное, определить класс или структуру и называют его точкой, чтобы сделать чуть более самодокументированный код, но это незначительное повышение.
Я предложил бы использовать ту же модель в другом месте: например, а не отдельной DX и DY массивов вы можете иметь один массив, который содержит эти пары int (или очков).

Я не знаю об использовании массива наборов, которые вы называете "использовать". Это, несомненно, будет лучше, либо просто использовать набор (в этом случае пусть это будет набор пар точек, как указано выше) или просто использовать что-то вроде массивов (векторов или в соответствующих случаях).
Есть один маленький прием, если вы идете для вектора параметра векторы. Начните с переименования "используется" для "остальных". Инициализировать его как копию входного binaryMatrix, и всякий раз, когда вы проверить точки На острове, установить его к нулю. Затем вы можете одновременно проверить баллы за море и за то, что уже посетил.

Я ценю вашу маркировку вашего binaryMatrix пост. Стоит быть в курсе подробностей как константный взаимодействует с контейнерами: если вы хотите, чтобы убедиться, что функция не может изменить что-нибудь об этой переменной ты действительно хочешь const vector<const vector<const int>>. Это не просто повторение для усиления: оно говорит, что тебе нельзя связываться с binaryMatrix или любой из векторов вы выходите из binaryMatrix, или любое из чисел, что вы выберетесь из любой из этих векторов.

Проверка в отношении входного массива пустые-это очень хорошая вещь, чтобы помнить. Это ловкий трюк, что если массив пуст, то n будет равно нулю, который является ложным, который не соответствует действительности. Однако, было бы яснее написать if(n == 0) или даже if(binaryMatrix.empty()). Компилятор, вероятно, разобраться в оптимизации его вниз в то же самое, поэтому у людей есть свобода, чтобы код таким образом, чтобы люди читали.

4
ответ дан 14 апреля 2018 в 10:04 Источник Поделиться

Редактировать: это, наверное, то, что я должен был сказать прежде всего, чтобы сделать вещи более ясно:

После вашего интервью вопрос касается производительности:


Объяснить и код наиболее эффективное решение возможно и проанализируйте свое время и пространство сложности.

Единственное простое в 2Д char матрица гораздо быстрее, чем то, что вы написали (в 20 раз быстрее на самом деле).

Таким образом, это все о производительности. И вопросы алгоритма. ИМО, это уместно говорить об альтернативах, потому что твой не в пределах, что можно/требуется в производительности.

Он не отвечает "самая эффективная" критерий. В реальной ситуации интервью, это, вероятно, быть помечены интервьюером.

Обратите внимание, что, если бы Вы были [много] ближе, говорить в пределах 10%, это не будет проблемой [и я бы не опубликовали.

Я не уверен, что вы можете встретиться с задачей без полного рефакторинга кода.

Ваше решение накладывает дополнительную нагрузку на кэш процессора, и, кажется, больше сложности, чем нужно было бы. Он также, кажется, использует больше памяти, чем также требуется. И, ряд стл примитивов, которые вы используете, по своей природе, появляются получить доступ к куче много (т. е.) они медленные.

Я бы сказал, что просто освобождаться из клетки, как вы пройти будет лучше, чем добавление сложность у вас [или см. ниже].

Также, для вашего алгоритма, вы имеете ориентиры и анализа, сколько производительности занимает каждый из компонентов стл, которую вы используете. Это, вероятно, потребуется при обсуждении времени/пространства компромиссы. Как это, они немного "черного ящика".

Есть ли лучшая альтернатива vector<vector<int>> для вашей матрицы? Я думаю, что это добавляет дополнительный [внутренней] указатель разыменовать [что оптимизатор может игнорировать] для каждой ячейки доступ.

И, например, я вижу лучше альтернативы с помощью отдельного unordered_set для отслеживания посещенных узлов. Когда узел был посещен [используется], или просто с 2. Устранить ваши used в целом. Затем, вы можете заменить:

if (!used[i].count(j) AND binaryMatrix[i][j]==1)

С:

if (binaryMatrix[i][j]==1)

И изменить все места, где вы делаете (например):

used[i].insert(j);

В:

binaryMatrix[i][j] |= 2;

Если вам нужна функция, чтобы быть без разрушения исходной матрицы, в ваши функции заканчиваются, чтобы отменить это, вы могли бы петлю на:

binaryMatrix[i][j] &= 1;

Это дополнительная работа, но [возможно] еще быстрее в целом.


Редактировать: это было мое первоначальное открытие раздела, в котором был отказ. Я оставляю его в, Для справки, но, перечитав, хотя это мог быть затянут немного, это говорит о проблемах производительности

Нюанс: это не критика вашего кода стиль [как зеты уже сделал это], а альтернативный алгоритм, который может быть в 20 раз быстрее.

Один простой 2D char матрицу можно значительно быстрее, чем при использовании std::* примитивов.

Как вы делали c++ интервью вопрос, демонстрируя std::* классность может быть первостепенное значение, и это может быть вопрос спорный.

Но, когда разница в производительности на порядок быстрее, что может сделать разницу. У меня было несколько связанных с интервью и скорость иногда важнее. Оценивая такой компромисс, возможно, на самом деле, часть требуемого/желаемого решения.

Чтобы исключить проверку границ, я создал негабаритных матрицу, которая имеет границы нулей со всех сторон. Фактические данные матрицы инкрустацией из [1,1]. Это метод, используемый в видео/обработка изображения.

Используя указатели вместо переменных индекс, это также устраняет ряд размножается внутри цикла.


Впрочем, вот полная программа, которая делает бенчмаркинг сравнение. Игнорировать большинство из них, и сравнить mtxcount и zapline функции против ваших getNumberOfIslands функция. Они во многом c/c++ агностик.

Основной целью здесь является создание резервной копии производительность 20х планку выше, а не просто констатирую, что без доказательств.

Это также позволит, если вы так выбрать, чтобы обеспечить базовым для любого перекодировать/твики вы можете сделать

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <time.h>

#ifndef OPT_XPT
#define OPT_XPT 0
#endif

#ifndef OPT_ZPRT
#define OPT_ZPRT 0
#endif

int opt_xpt;
int opt_v;
int opt_T;
int del_Y = -1;
int del_X = -1;

char xptfmt[20];

int xfidx;
FILE *xfstream[2];

#define sysfault(_fmt...) \
do { \
prtf(_fmt); \
xfdone(); \
exit(1); \
} while (0)

int
prtf(const char *fmt,...)
__attribute__((__format__(__printf__,1,2)));

#define zprtok(_lvl) \
opt_T

#if OPT_ZPRT
#define zprt(_lvl,_fmt...) \
do { \
if (zprtok(_lvl)) \
prtf(_fmt); \
} while (0)
#else
#define zprt(_lvl,_fmt...) /**/
#endif

double
tvgetf(void)
{
struct timespec ts;
double sec;

clock_gettime(CLOCK_REALTIME,&ts);

sec = ts.tv_nsec;
sec /= 1e9;
sec += ts.tv_sec;

return sec;
}

void
xfinit(void)
{

xfstream[0] = fopen("/tmp/orig.txt","w");
xfstream[1] = fopen("/tmp/fast.txt","w");
xfidx = 0;
}

void
xfset(int idx)
{

xfidx = idx;
}

void
xfdone(void)
{

fclose(xfstream[0]);
fclose(xfstream[1]);
}

int
prtf(const char *fmt,...)
{
FILE *xf;
va_list ap;
int len;

xf = xfstream[xfidx];

va_start(ap,fmt);
len = vfprintf(xf,fmt,ap);
va_end(ap);

return len;
}

void
banner(void)
{

prtf("\n");
for (int col = 1; col <= 80; ++col)
prtf("-");
prtf("\n");
}

void
rowmark(int ycur,int ymax,int xmax)
{
int xcur;
int ylen;
int xlen;
char buf[40];

ylen = sprintf(buf,"%d",ymax);
ylen = sprintf(buf,"%*d:",ylen,ycur);

//int xlen = sprintf(buf,"%d",xmax);

if ((ycur % 10) == 0) {
for (xcur = 0; xcur <= ylen; ++xcur)
prtf(" ");

xlen = 0;
for (xcur = 0; xcur < xmax; xcur += 10) {
xlen += prtf("%d",xcur);
for (; (xlen % 20) != 0; ++xlen)
prtf(" ");
}
prtf("\n");

for (xcur = 1; xcur <= ylen; ++xcur)
prtf(" ");

for (xcur = 0; xcur < xmax; ++xcur)
prtf(" %c",((xcur % 10) == 0) ? '|' : ' ');
prtf("\n");
}

prtf("%s",buf);
}
// since this is the number of islands in binaryMatrix.
// See all 6 islands color-coded below.

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#define AND &&
using namespace std;

#define bigvector vector< vector<int> >

#if 0
bigvector binaryMatrix = [
[0, 1, 0, 1, 0],
[0, 0, 1, 1, 1],
[1, 0, 0, 1, 0],
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 1]];
#endif

// expected 6
bigvector binaryMatrix = {
{0, 1, 0, 1, 0},
{0, 0, 1, 1, 1},
{1, 0, 0, 1, 0},
{0, 1, 1, 0, 0},
{1, 0, 1, 0, 1}};

// expected 0
bigvector test_1 = {
{ 0 }
};

// expected 1
bigvector test_2 = {
{ 1 }
};

// expected 2
bigvector test_3 = {
{ 1, 0, 1, 0 }
};

// expected 2
bigvector test_4 = {
{ 1, 0, 1, 0 },
{ 0, 1, 1, 1 },
{ 0, 0, 1, 0 }
};

// expected 4
bigvector test_5 = {
{1,0,1,0},
{0,1,1,1},
{0,0,1,0},
{1,1,0,0},
{0,1,0,1}
};

// expected 6
bigvector test_6 = {
{0,1,0,1,0},
{0,0,1,1,1},
{1,0,0,1,0},
{0,1,1,0,0},
{1,0,1,0,1}
};

// expected 6
bigvector test_7 = {
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,1}
};

int
getNumberOfIslands(const vector<vector<int> >&binaryMatrix)
{
int ans = 0;
int n = binaryMatrix.size();

if (!n)
return 0;
int m = binaryMatrix[0].size();
unordered_set<int> *used = new unordered_set<int>[n];

for (int i = 0; i < n; i++)
used[i].clear();

// Implementation through Breadth First Search
// starting origin for my x and y coordinates
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
queue< pair<int,int> > q;

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {

if (!used[i].count(j) AND binaryMatrix[i][j] == 1) {
if (OPT_XPT && opt_xpt) {
prtf("XPT:");
prtf(xptfmt,i,j);
prtf("\n");
}

ans++;

q.push(make_pair(i, j));
used[i].insert(j);
while (!q.empty()) {
pair<int,int> pos = q.front();

q.pop();

for (int k = 0; k < 4; k++) {
int nx = pos.first + dx[k];
int ny = pos.second + dy[k];

if (nx < 0 || nx >= n)
continue;
if (ny < 0 || ny >= m)
continue;
if (used[nx].count(ny))
continue;
if (binaryMatrix[nx][ny] != 1)
continue;

used[nx].insert(ny);
q.push(make_pair(nx, ny));
}
}
}
}
}

return ans;
}
#define XYDEF(_cur) \
int ycur = _cur - mtxbase; \
int xcur = (ycur % stride) - 1; \
ycur /= stride; \
ycur -= 1

struct mtxctl {
char *mtxbase;
char *mtxzero;
int ymax;
int xmax;
int stride;
char *vmargin;
int delstop;

mtxctl()
{
mtxbase = NULL;
}

char *
mtxloc(int ycur,int xcur)
{

ycur += 1;
xcur += 1;

return &mtxbase[(ycur * stride) + xcur];
}

void
zapone(char *mtxcur)
{

#ifdef ZAPCHK
if (del_X >= 0) {
XYDEF(mtxcur);
prtf("DEL: %s\n",mtxtag(mtxcur));
if ((ycur == del_Y) && (xcur == del_X) && delstop)
sysfault("zapone: fault\n");
delstop = 1;
}
#endif

*mtxcur = 0;
}

void
mtxalloc(int ydim,int xdim);

void
mtxfree(void);

int
mtxget(int ycur,int xcur);

void
mtxset(int ycur,int xcur,int val);

void
zapline(char *mtxcur);

void
mtxshow(void);

int
mtxcount(void);

char *
mtxtag(char *mtxcur);
};

void
mtxctl::mtxalloc(int ydim,int xdim)
{
char buf[20];

mtxfree();

mtxbase = (char *) calloc(1,(ydim + 2) * (xdim + 2));
ymax = ydim;
xmax = xdim;
stride = xmax + 2;
vmargin = mtxloc(ymax,-1);
mtxzero = mtxloc(0,0);

ydim = sprintf(buf,"%d",ydim);
xdim = sprintf(buf,"%d",xdim);
sprintf(xptfmt,"[%%%d.%dd,%%%d.%dd]",ydim,ydim,xdim,xdim);
}

void
mtxctl::mtxfree(void)
{

if (mtxbase != NULL)
free(mtxbase);
mtxbase = NULL;
}

void
mtxctl::mtxset(int ycur,int xcur,int val)
{
char *mtxcur;

mtxcur = mtxloc(ycur,xcur);
*mtxcur = val;
}

int
mtxctl::mtxget(int ycur,int xcur)
{
char *mtxcur;
int val;

mtxcur = mtxloc(ycur,xcur);
val = *mtxcur;

return val;
}

char *
mtxctl::mtxtag(char *mtxcur)
{
XYDEF(mtxcur);
static char buf[100];

sprintf(buf,xptfmt,ycur,xcur);

return buf;
}

void
mtxctl::mtxshow(void)
{
int ycur;
int xcur;

xfset(1);
banner();

for (ycur = 0; ycur < ymax; ++ycur) {
if (opt_v)
rowmark(ycur,ymax,xmax);
for (xcur = 0; xcur < xmax; ++xcur)
prtf(" %d",mtxget(ycur,xcur));
prtf("\n");
}
}

int
mtxctl::mtxcount(void)
{
char *mtxlhs;
char *mtxrhs;
char *mtxcur;
int hitflg;
int count;

count = 0;

mtxlhs = mtxzero;

for (; mtxlhs < vmargin; mtxlhs += stride) {
// point to start and end of row
mtxcur = mtxlhs;
mtxrhs = mtxlhs + xmax;

// scan current row
while (1) {
// find next non-zero in row (i.e. an island)
hitflg = 0;
for (; mtxcur < mtxrhs; ++mtxcur) {
if (*mtxcur) {
hitflg = 1;
break;
}
}
if (! hitflg)
break;

if (OPT_XPT && opt_xpt)
prtf("XPT:%s\n",mtxtag(mtxcur));

count += 1;

// remove all adjoining ones connected to current island
delstop = 0;
zapline(mtxcur);

// point to rightmost immediate neighbor
++mtxcur;
}
}

return count;
}

void
mtxctl::zapline(char *mtxmid)
{
char *mtxcur;
char *mtxnxt;

zprt(ZPXHOWPGM,"zapline: ENTER mtxmid=%s\n",mtxtag(mtxmid));

// zap from current position rightward
for (mtxcur = mtxmid; *mtxcur != 0; ++mtxcur) {
zapone(mtxcur);

// look at neighbor above us
mtxnxt = mtxcur - stride;
if (*mtxnxt != 0)
zapline(mtxnxt);

// look at neighbor below us
mtxnxt = mtxcur + stride;
if (*mtxnxt != 0)
zapline(mtxnxt);
}

// zap from previous position leftward
for (mtxcur = mtxmid - 1; *mtxcur != 0; --mtxcur) {
zapone(mtxcur);

// look at neighbor above us
mtxnxt = mtxcur - stride;
if (*mtxnxt != 0)
zapline(mtxnxt);

// look at neighbor below us
mtxnxt = mtxcur + stride;
if (*mtxnxt != 0)
zapline(mtxnxt);
}

zprt(ZPXHOWPGM,"zapline: EXIT mtxmid=%s\n",mtxtag(mtxmid));
}

void
showvec(const bigvector &mtx)
{
int n = mtx.size();

xfset(0);
banner();

if (!n)
return;
int m = mtx[0].size();

for (int i = 0; i < n; i++) {
if (opt_v)
rowmark(i,n,m);
for (int j = 0; j < m; j++) {
int val = mtx[i][j];
prtf(" %d",val);
}
prtf("\n");
}
}

bigvector *
bldvec(void)
{
bigvector *mtx = new(bigvector);
int ymax;
int xmax;
int val;

while (1) {
ymax = rand() % 100;
if (ymax)
break;
}

while (1) {
xmax = rand() % 100;
if (xmax)
break;
}

for (int ycur = 0; ycur < ymax; ++ycur) {
vector<int> row;
for (int xcur = 0; xcur < xmax; ++xcur) {
val = rand() & 1;
row.push_back(val);
}
mtx->push_back(row);
}

return mtx;
}

void
vec2mtx(const bigvector &vec,mtxctl *mtx)
{
int ymax;
int xmax;
int val;

ymax = vec.size();
if (! ymax)
return;

xmax = vec[0].size();

mtx->mtxalloc(ymax,xmax);
for (int ycur = 0; ycur < ymax; ++ycur) {
for (int xcur = 0; xcur < xmax; ++xcur) {
val = vec[ycur][xcur];
mtx->mtxset(ycur,xcur,val);
}
}
}

void
vecall(bigvector *vec)
{
int who;
mtxctl mymtx;
int counts[2];
double tvbeg;
double elap[2];
double ratio;
const char *tag;

showvec(*vec);

vec2mtx(*vec,&mymtx);
mymtx.mtxshow();

for (int iter = 0; iter <= 1; ++iter) {
#if 0
who = iter;
#else
who = ! iter;
#endif

xfset(who);

if (opt_v)
prtf("\n");

tvbeg = tvgetf();
switch (who) {
case 0:
counts[who] = getNumberOfIslands(*vec);
break;

default:
counts[who] = mymtx.mtxcount();
break;
}

elap[who] = tvgetf() - tvbeg;

prtf("COUNT: %d\nELAPSED: %.9f\n",counts[who],elap[who]);
}

do {
xfset(1);

if (elap[0] > elap[1]) {
if (elap[1] == 0.0)
break;
ratio = elap[0] / elap[1];
tag = "faster";
}
else {
if (elap[0] == 0.0)
break;
ratio = elap[1] / elap[0];
tag = "slower";
}

prtf("RATIO: %.3fX %s\n",ratio,tag);
} while (0);

mymtx.mtxfree();
}

// main -- main program
int
main(int argc,char **argv)
{
char *cp;
bigvector *vec;
mtxctl mymtx;

--argc;
++argv;

xfinit();

for (; argc > 0; --argc, ++argv) {
cp = *argv;
if (*cp != '-')
break;

switch (cp[1]) {
case 't':
opt_xpt = 1;
break;

case 'v':
opt_v = 1;
break;

case 'D':
del_Y = strtol(cp + 2,&cp,10);
del_X = strtol(cp + 1,&cp,10);
break;

case 'T':
opt_T = 1;
break;

default:
break;
}
}

#if 1
vecall(&binaryMatrix);
vecall(&test_1);
vecall(&test_2);
vecall(&test_3);
vecall(&test_4);
vecall(&test_5);
vecall(&test_6);
vecall(&test_7);
#endif

vec = bldvec();
vecall(vec);

xfdone();

return 0;
}


Вот вывод разница между исходным кодом и шахты:

9c9,10
< ELAPSED: 0.000009060
---
> ELAPSED: 0.000000477
> RATIO: 19.000X faster
14c15
< ELAPSED: 0.000000238
---
> ELAPSED: 0.000000000
19c20
< ELAPSED: 0.000002861
---
> ELAPSED: 0.000000000
24c25,26
< ELAPSED: 0.000000715
---
> ELAPSED: 0.000000238
> RATIO: 3.000X faster
31c33,34
< ELAPSED: 0.000003099
---
> ELAPSED: 0.000000238
> RATIO: 13.000X faster
40c43,44
< ELAPSED: 0.000003815
---
> ELAPSED: 0.000000238
> RATIO: 16.000X faster
49c53,54
< ELAPSED: 0.000003815
---
> ELAPSED: 0.000000238
> RATIO: 16.000X faster
58c63,64
< ELAPSED: 0.000006199
---
> ELAPSED: 0.000000238
> RATIO: 26.000X faster
145c151,152
< ELAPSED: 0.001625061
---
> ELAPSED: 0.000070095
> RATIO: 23.184X faster

3
ответ дан 13 апреля 2018 в 12:04 Источник Поделиться