Какая разница в фрагментах кода? - PullRequest
Новая
       51

Какая разница в фрагментах кода?

0 голосов
/ 04 июня 2018

Я новичок в операционных системах, и я пытаюсь понять некоторые фрагменты кода.Не могли бы вы объяснить мне разницу между этими фрагментами кода?

int sum_array_rows(int a[M][N])
 {
    int i,j,sum=0;
    for(i=0;i<M;i++)
      for(j=0;j<N;j++)
        sum+=a[i][j];
    return sum;
  }

и 

int sum_array_col(int a[M][N])
 {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[i][j];
    return sum;
  }

Разные части являются двойными Для атрибутов Одна из них должна быть быстрее другой ??Если да, то не могли бы вы объяснить, почему, потому что я не понимаю.

Ответы [ 3 ]

0 голосов
/ 04 июня 2018

Оба кода работают аналогично, только если значения M и N равны equal, в противном случае оба кодовых блока различны.

Случай 1: - Посмотрите на приведенное нижекодовый блок 

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<M;i++)
      for(j=0;j<N;j++)
        sum+=a[i][j];
    return sum;
}

здесь a - это массив из M строк и N столбцов. Вы суммируете каждый элемент строки-столбца с помощью sum+=a[i][j].Это хороший код, потому что внешний цикл вращается равным количеству строк, а внутренний цикл вращается равным количеству столбцов.

Case-2 : - Теперь посмотрите на второй блок кода, он вызываетпереполнение. 

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[i][j];
    return sum;
}

Здесь также a - это массив M строк и N столбцов.ваш первый внешний цикл for поворачивается с 0 на N, но у вас есть только M рядов.И когда вы делаете sum+=a[i][..], это создает большую проблему, если M & N не совпадают. Например, M равно 2 и N равно 5, то есть похоже на int a[2][5] и внешнеецикл повторяется от 0 до 5, и вы продолжаете делать

  • sum+=a[0][j] затем

  • sum+=a[1][j] до тех пор, пока это не будет в порядке(bcz M = 2), но когда он будет делать

  • sum+=a[2][j] и sum+=a[3][j] и т. д., тогда возникает проблема, так как a[2][j] или a[3][j] не происходит, поэтомувы пытаетесь получить доступ за границей, что вызывает неопределенное поведение .

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

Прежде всего, второй блок кода неправильный, но вы можете исправить его, выполнив sum+=a[j][i] вместо sum+=a[i][j] как 

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[j][i];
    return sum;
}

Как сказано другими из-за структуры памяти2D-массивы и способ работы системы кэширования, первая версия может работать лучше, чем вторая.С другой стороны, компилятор может оптимизировать две версии для одинаковой работы.

0 голосов
/ 04 июня 2018

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

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

Термины для поиска здесь: 'локальность кэша и шаг массива

0 голосов
/ 04 июня 2018

В первом примере:

i получит значения 0, 1, 2, ..., M-1

j получит значения 0, 1, 2, ..., N-1

Итак, sum рассчитывается как 

sum = a[0][0] + a[0][1] + a[0][2] + ... + a[0][N-1] +
      a[1][0] + a[1][1] + a[1][2] + ... + a[1][N-1] +
      a[2][0] + a[2][1] + a[2][2] + ... + a[2][N-1] +
      ...
      ...
      a[M-1][0] + a[M-1][1] + a[M-1][2] + ... + a[M-1][N-1]

Во втором примере это было переключено так, что

i получит значения 0, 1, 2, ..., N-1

j получит значения 0, 1, 2, ..., M-1

так что теперь 

sum = a[0][0] + a[0][1] + a[0][2] + ... + a[0][M-1] +
      a[1][0] + a[1][1] + a[1][2] + ... + a[1][M-1] +
      a[2][0] + a[2][1] + a[2][2] + ... + a[2][M-1] +
      ...
      ...
      a[N-1][0] + a[N-1][1] + a[N-1][2] + ... + a[N-1][M-1]

Обратите внимание, что вторая версия неверна , поскольку аргумент int a[M][N], то есть первый допустимый индекс 0..M-1, а второй допустимый индекс 0..N-1 В другихслова, если N и M отличаются во второй версии, обращаются к массиву без границ.

Чтобы сделать второй пример корректным.Эта строка sum+=a[i][j]; должна быть sum+=a[j][i];, так что sum теперь: 

sum = a[0][0] + a[1][0] + a[2][0] + ... + a[M-1][0] +
      a[0][1] + a[1][1] + a[2][1] + ... + a[M-1][1] +
      a[0][2] + a[1][2] + a[2][2] + ... + a[M-1][2] +
      ...
      ...
      a[0][N-1] + a[1][N-1] + a[2][N-1] + ... + a[M-1][N-1]

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

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

...