ReSQL.ru
     
powered by simpleCommunicator - 2.0.58     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Работа с матрицей
169 сообщений из 169, показаны все 7 страниц
  все  
Работа с матрицей
    #39961379
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
Всем доброго времени суток! Сразу оговорюсь, что мой первый вопрос довольно прост, но что-то все никак не могу разобраться, как бы прискорбно это не звучало. Итак, задача состоит вот в чем:
1) всего лишь нужно найти сумму элементов заштрихованной области матрицы nxn, где n - число нечетное, которая вводится вручную с клавиатуры (данное условие обязательное) (рисунок прилагаю).
(если найдется человек, который захочет и сможет помочь, очень прошу вписать код полностью с начала и до конца, а не его часть)
2) а вот вторая часть интересней (лично для меня, так как любопытно, это придумал такой бред мой мозг, либо это действительно можно сделать)
вопрос следующий: нужно эти же элементы матрицы отсортировать по возрастанию. Можно ли это как-то выполнить в одном коде вместе с 1 пунктом, но после того, как сумма была найдена, либо же это обязательно нужно делать отдельным кодом?
Заранее спасибо!
...
Рейтинг: 0 / 0
24.05.2020, 18:09
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961388
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
1) А в чём проблема-то? if (заштриховано) сумма += матрица[i][j];
2) Можно и одновременно. Третий том Кнута в помощь, сортировка вставками.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
24.05.2020, 18:52
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961408
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
Dimitry Sibiryakov, упорно не доходит как делается 1 пункт, в отличии от второго, за что Вам спасибо)
А вот с первым совсем беда. Понимаю, что нужно задать условие отбора элементов, но в этом сама проблема, не соображу что нужно в if записать
...
Рейтинг: 0 / 0
24.05.2020, 19:33
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961413
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
JustSomething
Dimitry Sibiryakov, упорно не доходит как делается 1 пункт, в отличии от второго, за что Вам спасибо)
А вот с первым совсем беда. Понимаю, что нужно задать условие отбора элементов, но в этом сама проблема, не соображу что нужно в if записать

Ну давайте подумаем. Если размер матрицы нечётный то как найти координату по ширине верхнего (по X) угла?
...
Рейтинг: 0 / 0
24.05.2020, 19:51
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961422
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Пособие для студентов и школьников
...
Рейтинг: 0 / 0
24.05.2020, 20:33
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961431
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
Dima T, да, спасибо, но прочла это еще до того как зарегистрироваться здесь)
С первым вопросом пытаюсь разобраться уже второй день, при этом пособие моего же преподавателя не помогло, а на второй вопрос получила грамотную подсказку, хотя впрочем как и на первый) Так что абсолютно не пыталась просто получить решение, не прилагая усилий со своей стороны)
...
Рейтинг: 0 / 0
24.05.2020, 21:35
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961433
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
JustSomething, подумайте как устроить циклы перебора элементов матрицы. Предположительно нарисован ромб .
Тогда перебираем все элементы справа от левой-верхней стороны ромба.
Левая вершина с координатами в матрице: y0=(n-1)/2, x>=1
Строчкой выше, y1=y0-1, x>=2
Строчкой выше y=y1-1, x>=3
........
Наконец, верхняя строка матрицы y=1, x>=(n-1)/2

Ограничения справа в каждой строке - сообразите сами.
Аналогично в нижней половине ромба.
...
Рейтинг: 0 / 0
24.05.2020, 21:50
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961435
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
JustSomething
Dima T, да, спасибо, но прочла это еще до того как зарегистрироваться здесь)
С первым вопросом пытаюсь разобраться уже второй день, при этом пособие моего же преподавателя не помогло, а на второй вопрос получила грамотную подсказку, хотя впрочем как и на первый) Так что абсолютно не пыталась просто получить решение, не прилагая усилий со своей стороны)

Тут в основном высококвалифицированные программисты, мы плохо помним школьную арифметику, а задача не тривиальная. У меня за пять минут не получилось.
...
Рейтинг: 0 / 0
24.05.2020, 21:58
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961476
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
JustSomething,

код писать точно не буду, но что можно сделать подскажу :)

1) рассматриваем тривильный случай M = {a11=25}, в данном случае матрица состоит из одного элемента
n = 1, sum = a11 = 25

2) рассматриваем следующий случай n = 3
Код: plaintext
1.
2.
3.
1  2  3
4  5  6
7  8  9

n=3, sum = a12 + a21 + a22 + a23 + a32 = 2 + 4 +5 + 6 + 8 = 25

3) дальше рассмотрите случай n=5,
ну и т.д, просто все нужно выписать на бумаге, и тогда все станет понятно

4) в коде нужно просто пройтись по выделенным элементам матрицы
...
Рейтинг: 0 / 0
25.05.2020, 00:39
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961547
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
exp98, да что там ромб. Давай общий случай решим. Произвольный выпуклый многоугольник вписан в прямоугольник (матрица).
...
Рейтинг: 0 / 0
25.05.2020, 09:54
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961559
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
JustSomething, ну что, Данила-мастер, не выходит Аленький цветок? Ещё подсказки нужны?
...
Рейтинг: 0 / 0
25.05.2020, 10:15
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961657
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
rdb_dev, честно говоря, аж стыдно признаваться, что после стольких подсказок я все еще сижу над первым пунктом.
Даже решение нашла по моему условию, пусть и на C#.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
       public static int CalcRhomb(int[,] a)
        {
            var n = a.GetUpperBound(0)+1;
            var k = n/2;
            var s = 0;
            for (var i=0; i < n; i++) 
            {
                var d = i <= k ? i : n - i - 1;
                for (var j = k - d; j <= k + d; j++)
                {
                    s += a[i, j];
                }
            }
            return s;
        }


Все никак не доходит, а это ведь только 1/2 заданий. (код смещается, там он не так ужасно выглядит, а времени разбираться можно ли здесь вставлять код нормально, увы, нет)

Модератор: Оформляй исходники тегом SRC
...
Рейтинг: 0 / 0
25.05.2020, 13:07
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961672
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
JustSomething,

Работает?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
int const Size = 5;
int const Half = Size / 2;

int arr[Size][Size] =
{
     1,  2,  3,  4,  5,
     6,  7,  8,  9, 11,
    12, 14, 15, 16, 17,
    18, 19, 20, 21, 22,
    23, 24, 25, 26, 27
};

int calcSumm()
{
    int res = 0;

    for (int i=0; i<Half; ++i)
    {
        for (int j=Half-i; j<=Half+i; j++)
        {
            res += arr[i][j];
            res += arr[Size-i-1][j];
        }
    }
    for (int i=0; i<Size; ++i)
    {
        res += arr[Half][i];
    }

    return res;
}
...
Рейтинг: 0 / 0
25.05.2020, 13:32
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961684
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
Решение двух пунктов сразу.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
#include <vector>
#include <numeric>
#include <algorithm>

int const Size = 5;
int const Half = Size / 2;

int arr[Size][Size] =
{
     1,  2,  3,  4,  5,
     6,  7,  8,  9, 11,
    12, 14, 15, 16, 17,
    18, 19, 20, 21, 22,
    23, 24, 25, 26, 27
};

int calcSumm()
{
    std::vector<int> vec;

    for (int i=0; i<Half; ++i)
    {
        for (int j=Half-i; j<=Half+i; j++)
        {
            vec.push_back(arr[i][j]);
            vec.push_back(arr[Size-i-1][j]);
        }
    }

    for (int i=0; i<Size; ++i)
    {
        vec.push_back(arr[Half][i]);
    }

    std::sort(vec.begin(), vec.end());

    return std::accumulate(vec.cbegin(), vec.cend(), 0);
}
...
Рейтинг: 0 / 0
25.05.2020, 13:51
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961691
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
JustSomething, задачка не стоит и выеденного яйца!
Смотрите, "серединку" (k) вы уже нашли. k определяет индекс элемент первой и последней строки двумерного массива, а также индекс строки, все элементы которой необходимо включить в сумму. Для первой строки индекс первого элемента для суммирования равен k, а кол-во элементов = 1. Для второй строки индекс первого элемента равен k-1, а кол-во элементов равно 2 и т.д. На лицо декремент на единицу индекса первого суммируемого элемента в строке и инкремент кол-ва суммируемых элементов в строке до тех пор, пока индекс строки < k или пока индекс первого суммируемого элемента > 0, после чего наоборот - инкремент индекса первого элемента и декремент кол-ва суммируемых элементов в строке, до тех пор, пока индекс первого элемента не равен k или пока индекс строки не равен n-1.

Для упрощения алгоритма я рекомендую сделать два последовательных цикла. Первый цикл для индексов строк от 0 до k-1 и индексов первых суммируемых элементов строк от k до 1, а второй цикл для индексов строк от k до n-1 и индексов первых суммируемых элементов от 0 до k. Так алгоритм будет даже быстрее, так как нет никакого дополнительного условия внутри цикла.

Соответственно:
1. Инициализация индекса первого суммируемого элемента (k) и кол-ва элементов (1);
2. Цикл по строкам от 0 до k-1 с декрементом индекса первого суммируемого элемента и инкрементом кол-ва элементов + вложенный цикл по соответствующим элементам (проще через while);
3. Реинициализация индекса первого суммируемого элемента (0) и кол-ва элементов (n);
4. Цикл по строкам от k до n-1 с инкрементом индекса первого суммируемого элемента и декрементом кол-ва элементов + вложенный цикл по соответствующим элементам;
...
Рейтинг: 0 / 0
25.05.2020, 14:04
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961692
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav, и чему твой исходный код может научить? Здесь не принято давать готовые решения.
...
Рейтинг: 0 / 0
25.05.2020, 14:05
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961693
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У автора-ж надо посчитать сумму элементов расположенных по "diamond". Как в бубновой масти.
...
Рейтинг: 0 / 0
25.05.2020, 14:12
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961695
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
И у меня есть некое недоверие к тестовым данным которые расположены слишком уж ... закономерно.
Можем получить некую авто-компенсацию суммм.

Давайте возьмем случайные числа.
...
Рейтинг: 0 / 0
25.05.2020, 14:14
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961696
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
У автора-ж надо посчитать сумму элементов расположенных по "diamond". Как в бубновой масти.

А разве я не это посчитал?
...
Рейтинг: 0 / 0
25.05.2020, 14:14
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961698
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
И у меня есть некое недоверие к тестовым данным которые расположены слишком уж ... закономерно.
Можем получить некую авто-компенсацию суммм.

Давайте возьмем случайные числа.

Возьмите. Нужно написать unit test-ы. Это мы вам поручим. :)
...
Рейтинг: 0 / 0
25.05.2020, 14:16
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961701
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav, а сколько у тебя получилось?
...
Рейтинг: 0 / 0
25.05.2020, 14:19
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961703
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
petrav, а сколько у тебя получилось?

186.
...
Рейтинг: 0 / 0
25.05.2020, 14:22
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961706
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
mayton
petrav, а сколько у тебя получилось?

186.

Я прошу прощения. Да. Ты был прав. Я не заметил коррекцию цикла здесь.

Код: plaintext
1.
for (int j=Half-i; j<=Half+i; j++)



Так что твой код - корректен.

Кстати я хотел усугубить этот топик но несколько в другом направлении.

Ты читал Степанова (он по STL книжки писал) ?
...
Рейтинг: 0 / 0
25.05.2020, 14:28
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961710
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton

Кстати я хотел усугубить этот топик но несколько в другом направлении.

Ты читал Степанова (он по STL книжки писал) ?

Нет, Степанова не читал. Я что-то некорректно написал с точки зрения STL?
...
Рейтинг: 0 / 0
25.05.2020, 14:35
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961714
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Нет у тебя все корркетно. Я просто по инерции продолжаю топик https://www.sql.ru/forum/1280222/tyapnichnaya-hvostovaya-rekursiya

Мысль такая. У нас есть козырная бубновая функция которая чего-то считает в сях императивно.
Она - эффективна. В этом никто не сомневается исходя из нашего понимания компиллятора.

Далее. Я хочу ее транформировать в хвостовую функцию . И посмотреть как ее понял компиллятор
(хотя-бы 2 варианта GCC, Clang). И во что он свернул рекурсию.
...
Рейтинг: 0 / 0
25.05.2020, 14:46
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961717
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
Можно написать свой собственный итератор, который позволил бы сортировать элементы матрицы прямо на месте, т.е. прямо в матрице. И находить сумму. Но я боюсь, что такой код не поняли бы ни автор топика, ни её преподаватель.
...
Рейтинг: 0 / 0
25.05.2020, 14:47
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961718
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton
...

Ты читал Степанова (он по STL книжки писал) ?


он в 1995 году книжку по stl выпустил, единственную...
у него есть других полезных книжек почитать.

2petrav
а где pop_back?
значения отсортированные в ромб Степанов возвращать будет?

Ты вообще почему такой малограмотный?
складывать и сортировать можно за один проход.
Это называется сортировка подсчётом.
Потом раскладываешь назад сортированно-подсчитанное.
Тут программа на две строки, а не на три.
...
Рейтинг: 0 / 0
25.05.2020, 14:48
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961721
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
booby

складывать и сортировать можно за один проход.
Это называется сортировка подсчётом.
Потом раскладываешь назад сортированно-подсчитанное.
Тут программа на две строки, а не на три.

Стоп-стоп. При чем здесь это?

Сортировка подсчетом - это эффектвная темя для низко-кардинальных данных.

Кроме того сортировка в этом топике это вообще - minor. И никому особо не интересна.
...
Рейтинг: 0 / 0
25.05.2020, 14:52
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961727
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
booby

Ты вообще почему такой малограмотный?

Не знаю. А не знаю, видимо, потому что малограмотный.

booby
складывать и сортировать можно за один проход.
Это называется сортировка подсчётом.
Потом раскладываешь назад сортированно-подсчитанное.
Тут программа на две строки, а не на три.

Давай код.
...
Рейтинг: 0 / 0
25.05.2020, 14:57
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961731
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
booby

он в 1995 году книжку по stl выпустил, единственную...

Обобщенное программирование - это вобщем - тоже про STL.
...
Рейтинг: 0 / 0
25.05.2020, 15:07
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961737
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton

Стоп-стоп. При чем здесь это?
...

задание целиком описано в первом посте.

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


2petrav
здесь ты программист на c/c++, а не я.
хочешь кода на vba или pl/sql?
хотя требовать кода вообще для такой задачи - убожество.
...
Рейтинг: 0 / 0
25.05.2020, 15:22
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961738
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
booby

складывать и сортировать можно за один проход.
Это называется сортировка подсчётом.
Потом раскладываешь назад сортированно-подсчитанное.
Тут программа на две строки, а не на три.

Стоп-стоп. При чем здесь это?

Сортировка подсчетом - это эффектвная темя для низко-кардинальных данных.

Кроме того сортировка в этом топике это вообще - minor. И никому особо не интересна.

Может быть booby просто сумасшедший?
...
Рейтинг: 0 / 0
25.05.2020, 15:22
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961743
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
mayton
пропущено...

Стоп-стоп. При чем здесь это?

Сортировка подсчетом - это эффектвная темя для низко-кардинальных данных.

Кроме того сортировка в этом топике это вообще - minor. И никому особо не интересна.

Может быть booby просто сумасшедший?

Он - истинный мастер кун-фу. Но его стиль искусств для тебя будет слишком странным!
Слишком!
...
Рейтинг: 0 / 0
25.05.2020, 15:37
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961753
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
mayton
пропущено...
Стоп-стоп. При чем здесь это?
Сортировка подсчетом - это эффектвная темя для низко-кардинальных данных.
Кроме того сортировка в этом топике это вообще - minor. И никому особо не интересна.

Может быть booby просто сумасшедший?
Ну почему же он сумасшедший? Можно и в один проход, и без сортировки, и промежуточных результатов, и без STL...
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv)
{
  constexpr size_t dim = 5;
  constexpr size_t m = dim / 2;
  
  int arr[dim][dim] =
  {
       1,  2,  3,  4,  5,
       6,  7,  8,  9, 11,
      12, 14, 15, 16, 17,
      18, 19, 20, 21, 22,
      23, 24, 25, 26, 27
  };

  long long int sum = 0;
  int
      *head = ((int*)arr) + m,
      *tail = ((int*)arr) + dim*dim - m - 1;
  size_t
      n = 1,
      c = n,
      d;

  while (head != tail)
  {
    if (c--)
    {
      sum += *head++;
      sum += *tail--;
    }
    else
    {
      d = dim - 1 - n;
      head += d;
      tail -= d;
      n += 2;
      c = n;
    }
  }
  sum += *head;
  printf("SUM: %lli", sum);

  return (EXIT_SUCCESS);
}
...
Рейтинг: 0 / 0
25.05.2020, 16:03
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961757
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
rdb_dev,

давайте из этого сделаем pure-function. Чтоб точкой входа у нас был не какой-то уродский main.
А чтоб была видимость какого-то красивого входа наподобие.

Код: plaintext
1.
int summ_diamond(arr *matrix, int size);
...
Рейтинг: 0 / 0
25.05.2020, 16:14
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961760
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton, а смысл?
...
Рейтинг: 0 / 0
25.05.2020, 16:16
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961761
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я продолжаю форк своей темы. Хвостовой рекурсии.

Автор я думаю уже получил своё и пошел курить.
...
Рейтинг: 0 / 0
25.05.2020, 16:18
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961765
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton, мне лень вкрячивать проверку на нечётность (!(dim && 1)) и выброс исключения
...
Рейтинг: 0 / 0
25.05.2020, 16:21
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961767
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Пускай нечетность будет по заданию всегда. Не будем обращать внимания.
...
Рейтинг: 0 / 0
25.05.2020, 16:28
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961771
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
petrav
пропущено...

Может быть booby просто сумасшедший?
Ну почему же он сумасшедший? Можно и в один проход, и без сортировки, и промежуточных результатов, и без STL...

Можно и без сортировки, но в ТЗ написано отсортировать. Что по поводу кода, то, имхо, ваш вариант крайне плохо-читабельный. Я очень не люблю такие вот варианты: *ptr++. Мой же код (первый) отображает логику происходящего и тоже в один проход, и тоже без промежуточных результатов.

Но интересно было бы увидеть бенчмарки всех трёх вариантов.
...
Рейтинг: 0 / 0
25.05.2020, 16:37
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961776
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
rdb_dev
пропущено...
Ну почему же он сумасшедший? Можно и в один проход, и без сортировки, и промежуточных результатов, и без STL...

Можно и без сортировки, но в ТЗ написано отсортировать. Что по поводу кода, то, имхо, ваш вариант крайне плохо-читабельный. Я очень не люблю такие вот варианты: *ptr++. Мой же код (первый) отображает логику происходящего и тоже в один проход, и тоже без промежуточных результатов.

Но интересно было бы увидеть бенчмарки всех трёх вариантов.

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

Поэтому давайте отложим сортировки тем более что они - коробочные в STL и ничего новаторского мы тут не
превнесем.

По поводу реализации rdb_dev - она - хорошая. Мне нравится, но для трансформаци по Степанову - не подходит.
Поэтому я возьму некий более краткий вариант. Без конечного автомата с состояниями внутри. Грубо говоря
мне нужна функция без состояний.
...
Рейтинг: 0 / 0
25.05.2020, 16:55
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961779
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton

По поводу реализации rdb_dev - она - хорошая. Мне нравится...

Вы давеча резко критиковали код в стиле *++ptr. И учили новичков так не делать. Вариант rdb_dev интересен, но, имхо, он квинтэссенция запутанности кода, когда с первого взгляда совершенно не очевидно, что этот код делает. Мне думается мой код проще и максимально "математичен".
...
Рейтинг: 0 / 0
25.05.2020, 17:02
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961786
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да я и щас критикую все эти инкременты внутри операций. Но его код напоминает
мне мой, 20 летней давности. Когда я в SVGA режиме рисовал цветные полигоны. Там тоже была идея
таким вот скользящим указателем заполнить все что нужно. Я брал сложный
полигон. Даже вогнутый Резал его на трапеции и дальше - дело техники. Основной критерий - скорость
и он достигался.
...
Рейтинг: 0 / 0
25.05.2020, 17:13
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961789
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
mayton

Автор я думаю уже получил своё и пошел курить.


Только недавно заметила что получила ответ на свой вопрос. Восхищаюсь всеми вами, насколько для вас это уже все просто. Мне же к этому ещё шагать и шагать. Но это такое дело, прорвемся. Бесконечно благодарна всем вам, при этом не только за полностью решенную задачу, но и за понимание, к какому уровню стремиться!
Вся моя благодарность - вам!
...
Рейтинг: 0 / 0
25.05.2020, 17:15
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961792
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
JustSomething
mayton

Автор я думаю уже получил своё и пошел курить.


Только недавно заметила что получила ответ на свой вопрос. Восхищаюсь всеми вами, насколько для вас это уже все просто. Мне же к этому ещё шагать и шагать. Но это такое дело, прорвемся. Бесконечно благодарна всем вам, при этом не только за полностью решенную задачу, но и за понимание, к какому уровню стремиться!
Вся моя благодарность - вам!

Заметили? Задачу решил я, а благодарность всем. Вот и помогай людям после такого.
...
Рейтинг: 0 / 0
25.05.2020, 17:24
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961796
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
petrav

Заметили? Задачу решил я, а благодарность всем. Вот и помогай людям после такого.


Вам выражаю особую благодарность)

(не могла же я обойти людей, которые пытались поставить меня на правильный путь в решении задачи, потратив на это такой дорогой ресурс как время. Жаль только мой мозг решил выйти погулять, либо же я пытаюсь найти себе оправдание того, что моих знаний и навыков не хватило для решения такого задания)
...
Рейтинг: 0 / 0
25.05.2020, 17:34
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961800
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton
По поводу реализации rdb_dev - она - хорошая. Мне нравится, но для трансформаци по Степанову - не подходит.
Она хорошая только в условиях однопоточности. Если же применять OpenMP в расчёте на большие массивы, то лучше решать в лоб на двух вручную распараллеленных for - отдельно на подсчёты сверху и снизу с последующей синхронизацией по результату, так чтобы OpenMP мог ещё и эти два цикла распараллелить по разным отрезкам индекса.
...
Рейтинг: 0 / 0
25.05.2020, 17:40
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961802
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
Заметили? Задачу решил я, а благодарность всем. Вот и помогай людям после такого.
Не жмись! Поделись славой!!!
...
Рейтинг: 0 / 0
25.05.2020, 17:42
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961806
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
Да я и щас критикую все эти инкременты внутри операций. Но его код напоминает
мне мой, 20 летней давности. Когда я в SVGA режиме рисовал цветные полигоны. Там тоже была идея
таким вот скользящим указателем заполнить все что нужно. Я брал сложный
полигон. Даже вогнутый Резал его на трапеции и дальше - дело техники. Основной критерий - скорость
и он достигался.

Я не вижу, что бы тут у rdb_dev достигалась скорость. Я написал бенчмарк. В Релизе мой код быстрее в 1.3 раза. ИМХО, мой код проще и для человека, и для компилятора. Последнему проще оптимизировать мой код. Вы можете попробовать мой бенчмарк. И сообщить результаты.

Код: plaintext
1.
2.
3.
Elapsed time: 0.985154s
Elapsed time: 1.30105s
Relation: 1.32066

 

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
#include <chrono>

int const Size = 5;
int const Half = Size / 2;

int const arr[Size][Size] =
{
     1,  2,  3,  4,  5,
     6,  7,  8,  9, 11,
    12, 14, 15, 16, 17,
    18, 19, 20, 21, 22,
    23, 24, 25, 26, 27
};

int summ_diamond_1()
{
    int res = 0;

    for (int i=0; i<Half; ++i)
    {
        for (int j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
            res += arr[Size-i-1][j];
        }
    }

    for (int i=0; i<Size; ++i)
    {
        res += arr[Half][i];
    }

    return res;
}

int summ_diamond_2()
{
  constexpr size_t dim = Size;
  constexpr size_t m = dim / 2;

  int sum = 0;
  int
      *head = ((int*)arr) + m,
      *tail = ((int*)arr) + dim*dim - m - 1;
  size_t
      n = 1,
      c = n,
      d;

  while (head != tail)
  {
    if (c--)
    {
      sum += *head++;
      sum += *tail--;
    }
    else
    {
      d = dim - 1 - n;
      head += d;
      tail -= d;
      n += 2;
      c = n;
    }
  }
  sum += *head;

  return sum;
}

double test(int (&summ_func)())
{
    auto start = std::chrono::high_resolution_clock::now();
    for (size_t i=0; i<100000000; ++i)
    {
        summ_func();
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    double const res = elapsed_seconds.count();
    std::cout << "Elapsed time: " << res << "s\n";
    return res;
}

void calc_times()
{
    double const d1 = test(summ_diamond_1);
    double const d2 = test(summ_diamond_2);
    std::cout << "Relation: " << (d2 / d1) << "\n";
}


...
Рейтинг: 0 / 0
25.05.2020, 17:44
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961809
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ты серьезно?

Кто же тестит на такой мелкой матрице.
...
Рейтинг: 0 / 0
25.05.2020, 17:47
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961815
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav, а теперь в calc_times поменяй вызовы diamond1 с diamond2 и проверь ещё разок.
...
Рейтинг: 0 / 0
25.05.2020, 17:53
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961817
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
Ты серьезно?

Кто же тестит на такой мелкой матрице.

Виноват, не додумал. Увеличил матрицу до 129*129, заполнил std::rand(). Теперь мой код обгоняет в три раза.
Код: plaintext
1.
2.
3.
Elapsed time: 2.40027s
Elapsed time: 7.26546s
Relation: 3.02694
...
Рейтинг: 0 / 0
25.05.2020, 17:57
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961822
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
petrav, а теперь в calc_times поменяй вызовы diamond1 с diamond2 и проверь ещё разок.

Код: plaintext
1.
2.
3.
Elapsed time: 7.32503s
Elapsed time: 2.36428s
Relation: 0.322767
...
Рейтинг: 0 / 0
25.05.2020, 17:59
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961824
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav, вполне возможно и именно в 3 раза при использовании 32 разрядного приложения и в 7 раз при использовании 64 разрядного. Проблема производительности в доступе по декрементному указателю.
...
Рейтинг: 0 / 0
25.05.2020, 18:03
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961826
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
JustSomething
petrav

Заметили? Задачу решил я, а благодарность всем. Вот и помогай людям после такого.


Вам выражаю особую благодарность)

Спасибо. :) Я пошутил, обращайтесь. :)
...
Рейтинг: 0 / 0
25.05.2020, 18:07
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961831
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Можно переделать декремент. Он немножко портит картину доступа к памяти.
Пускай суммирование идет слева направо и все. До упора.
Справа налево - не надо.

Код: plaintext
1.
2.
3.
4.
    if (c--)
    {
      sum += *head++;
      sum += *tail--;
...
Рейтинг: 0 / 0
25.05.2020, 18:21
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961833
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
mayton
По поводу реализации rdb_dev - она - хорошая. Мне нравится, но для трансформаци по Степанову - не подходит.

Она хорошая только в условиях однопоточности.

На данный момент средствами объективного контроля я наблюдаю, что твоя реализация плохая во всех смыслах. Без обид. Она не читаемая, сложная, запутанная и плохо оптимизируемая. Попробуй обгони мой код. Думаю это возможно.
...
Рейтинг: 0 / 0
25.05.2020, 18:23
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961836
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да и возьмите матрицу хотя-бы в миллион.

И еще petrav. Чтобы тест был честным ты должен запускать в шахматном порядке
обе функции несколько раз и брать среднее время в финале. Это важно потому-то
первая-функция -первопроходец может наблюдать картину кешей L1/L2/L3 отличную
от второго запуска.
...
Рейтинг: 0 / 0
25.05.2020, 18:30
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961839
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
И выровняйте ширину матрицы по кеш-линии.
...
Рейтинг: 0 / 0
25.05.2020, 18:32
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961843
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
Да и возьмите матрицу хотя-бы в миллион.

И еще petrav. Чтобы тест был честным ты должен запускать в шахматном порядке
обе функции несколько раз и брать среднее время в финале. Это важно потому-то
первая-функция -первопроходец может наблюдать картину кешей L1/L2/L3 отличную
от второго запуска.

Взял 1024+1*1024+1. Миллион же? Ситуация ещё более усугубилась. Теперь не три, а 3.5 раза отставание.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
Elapsed time: 12.7407s
Elapsed time: 45.222s
Relation: 3.54941
Elapsed time: 45.2662s
Elapsed time: 12.7202s
Relation: 0.281008
Elapsed time: 12.7821s
Elapsed time: 45.2582s
Relation: 3.54074



Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
void calc_times()
{
    for (size_t i=0; i<Size; ++i)
    {
        for (size_t j=0; j<Size; ++j)
        {
            arr[i][j] = std::rand();
        }
    }

    double const d1_1 = test(summ_diamond_1);
    double const d2_1 = test(summ_diamond_2);
    std::cout << "Relation: " << (d2_1 / d1_1) << "\n";

    double const d1_2 = test(summ_diamond_2);
    double const d2_2 = test(summ_diamond_1);
    std::cout << "Relation: " << (d2_2 / d1_2) << "\n";

    double const d1_3 = test(summ_diamond_1);
    double const d2_3 = test(summ_diamond_2);
    std::cout << "Relation: " << (d2_3 / d1_3) << "\n";
}
...
Рейтинг: 0 / 0
25.05.2020, 18:45
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961848
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Показывай сорцы.

И вообще. Ты пользуешся GitHut или BitBucket?
...
Рейтинг: 0 / 0
25.05.2020, 18:52
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961850
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
Показывай сорцы.

И вообще. Ты пользуешся GitHut или BitBucket?

Нет. Показываю.

 

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
#include <chrono>

int const Size = 1024+1/*5*/;
int const Half = Size / 2;

int arr[Size][Size] =
{
     1,  2,  3,  4,  5,
     6,  7,  8,  9, 11,
    12, 14, 15, 16, 17,
    18, 19, 20, 21, 22,
    23, 24, 25, 26, 27
};

int summ_diamond_1()
{
    int res = 0;

    for (int i=0; i<Half; ++i)
    {
        for (int j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
            res += arr[Size-i-1][j];
        }
    }

    for (int i=0; i<Size; ++i)
    {
        res += arr[Half][i];
    }

    return res;
}

int summ_diamond_2()
{
  constexpr size_t dim = Size;
  constexpr size_t m = dim / 2;

  int sum = 0;
  int
      *head = ((int*)arr) + m,
      *tail = ((int*)arr) + dim*dim - m - 1;
  size_t
      n = 1,
      c = n,
      d;

  while (head != tail)
  {
    if (c--)
    {
      sum += *head++;
      sum += *tail--;
    }
    else
    {
      d = dim - 1 - n;
      head += d;
      tail -= d;
      n += 2;
      c = n;
    }
  }
  sum += *head;

  return sum;
}

double test(int (&summ_func)())
{
    auto start = std::chrono::high_resolution_clock::now();
    for (size_t i=0; i<100000; ++i)
    {
        int const res = summ_func();
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    double const res = elapsed_seconds.count();
    std::cout << "Elapsed time: " << res << "s\n";
    return res;
}

void calc_times()
{
    for (size_t i=0; i<Size; ++i)
    {
        for (size_t j=0; j<Size; ++j)
        {
            arr[i][j] = std::rand();
        }
    }

    double const d1_1 = test(summ_diamond_1);
    double const d2_1 = test(summ_diamond_2);
    std::cout << "Relation: " << (d2_1 / d1_1) << "\n";

    double const d1_2 = test(summ_diamond_2);
    double const d2_2 = test(summ_diamond_1);
    std::cout << "Relation: " << (d2_2 / d1_2) << "\n";

    double const d1_3 = test(summ_diamond_1);
    double const d2_3 = test(summ_diamond_2);
    std::cout << "Relation: " << (d2_3 / d1_3) << "\n";
}


...
Рейтинг: 0 / 0
25.05.2020, 18:55
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961855
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
И выровняйте ширину матрицы по кеш-линии.

В смысле? Выравнивание по умолчанию. 32-ва бита.
...
Рейтинг: 0 / 0
25.05.2020, 18:59
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961856
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
mayton
И выровняйте ширину матрицы по кеш-линии.

В смысле? Выравнивание по умолчанию. 32-ва бита.

Ну х*евое выравнивание. Кеш-линия - 64 байта. Вот посчитай.
...
Рейтинг: 0 / 0
25.05.2020, 19:02
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961857
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну и надо чтоб господин rdb_dev пофиксил свой реверсный итератор.

А я - сорян ребята. Я очень хочу тут с вами покомпилировать. Но у меня щас prod-дефект.
Так что я удаляюсь пока.
...
Рейтинг: 0 / 0
25.05.2020, 19:04
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961861
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
petrav
пропущено...

В смысле? Выравнивание по умолчанию. 32-ва бита.

Ну х*евое выравнивание. Кеш-линия - 64 байта. Вот посчитай.

Ну я переключился на Релиз 64. Ситуация улучшилась. Теперь отставание в 2.2:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
Elapsed time: 13.1537s
Elapsed time: 28.4684s
Relation: 2.16428
Elapsed time: 28.3625s
Elapsed time: 13.0515s
Relation: 0.460167
Elapsed time: 12.9651s
Elapsed time: 28.6319s
Relation: 2.20839
...
Рейтинг: 0 / 0
25.05.2020, 19:10
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961879
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
Итак, и снова у меня появились вопросы. Перейдя от теоретической части к практической, и скомпилировав данный код от уважаемого petrav
petrav
Решение двух пунктов сразу.

получила следующее:

....
/usr/bin/x86_64-linux-gnu-ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 19 has invalid symbol index 21
/usr/bin/x86_64-linux-gnu-ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_line): relocation 0 has invalid symbol index 2
/usr/lib/gcc/x86_64-linux-gnu/6/../../../x86_64-linux-gnu/crt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status

Пошарившись в интернетах, нашла такое:

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

int main()
{
// TODO: implementation
}


Хотела уточнить, это дело в компиляторе или мне действительно нужно добавить ф-цию main?
...
Рейтинг: 0 / 0
25.05.2020, 20:26
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961880
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
JustSomething

Хотела уточнить, это дело в компиляторе или мне действительно нужно добавить ф-цию main?

Ну вообще да, main() желательна. Напишите хотя бы так:

Код: plaintext
1.
2.
void main()
{}


А оттуда уже всё вызывайте. Но лучше, конечно, прочитать Кернигана и Ритчи. Всего-то 300 страниц.
...
Рейтинг: 0 / 0
25.05.2020, 20:32
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961922
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
JustSomething,
переходите на Питон! будет проще! :-)
это же тройной вынос мозга получается -> матрицы + (что-то с ними сделать) + С/С++!
...
Рейтинг: 0 / 0
25.05.2020, 23:45
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961941
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
mini.weblab, Вы знаете, я бы может и перешла, кто знает, что больше понравится, но вот эти странные люди как научные руководители говорят писать курсовую на плюсах ну и вот что ты будешь с этим делать?)
...
Рейтинг: 0 / 0
26.05.2020, 00:52
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961944
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
JustSomethingвот что ты будешь с этим делать?

Прямо заявить им в наглые глаза, что "я вообще программировать не умею, не хочу и не буду,
отвалите".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
26.05.2020, 00:58
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961945
JustSomething
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JustSomething
Гость
Dimitry Sibiryakov, так а кто сказал что не хочу и не буду? Не припоминаю что-то чтоб говорила такое)
То, что не совсем хорошо получается, это да, не спорю, но это ведь не значит, что на этом конец)
Добра Вам и позитива!
...
Рейтинг: 0 / 0
26.05.2020, 01:04
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39961957
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
по мотивам,
а можно ли транспозицию матрицы сделать через указатели?
т.е. мы не трогаем матрицу, а переставляем указатели на элементы матрицы нужным нам образом?
примерно так
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
#include <stdio.h>

int main() {
	int mtx[3][3] = { {1,2,3}, {4,5,6}, {7,8,9} };

	// Create a matrix of pointers: each pointer contains an address of the corresponding matrix element
	int *pt[3][3];

	// We apply transposition on the matrix of pointers, and the initial matrix is left unchanged
	for (int i=0; i<3; i++) {
		for (int j=0; j<3; j++){
			pt[i][j] = mtx[j] + i;
		}
	}

	// Print the matrix mtx
	for (int i=0; i<3; i++) {
		for (int j=0; j<3; j++) {
			printf("%d ", mtx[i][j]);
		}
		printf("\n");
	}

	// Print the transposed matrix mtx using transposed pointer matrix
	for (int i=0; i<3; i++) {
		for (int j=0; j<3; j++) {
			printf("%d ", *pt[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}
...
Рейтинг: 0 / 0
26.05.2020, 02:31
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962060
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Транспозиция это транспонирование?
...
Рейтинг: 0 / 0
26.05.2020, 10:57
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962072
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
На данный момент средствами объективного контроля я наблюдаю, что твоя реализация плохая во всех смыслах. Без обид. Она не читаемая, сложная, запутанная и плохо оптимизируемая. Попробуй обгони мой код. Думаю это возможно.
Дружище, во-первых, я не ставил перед собой задачу сделать быстрый и эффективный алгоритм, а во вторых, я давно вышел из того возраста, когда делают засечки на столешнице, меряясь "гордостью" (я тебе об этом намекнул 22139187 , но ты не догнал ;) ). Тем не менее, вызов принят.
 
Сравни с этим алгоритмом, мне самому лень
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
int64_t diamond(int *matrix, size_t dim)
{
  int64_t sum = 0;

  const size_t m = dim >> 1;
  auto const middl_row = matrix + dim * m;

  register size_t tmp;

  size_t
      cnt_frst,
      cnt_scnd;

  int
      *p_frst,
      *p_scnd;

  for (size_t row_idx = 0; row_idx < m; row_idx++)
  {
    tmp = (row_idx << 1);
    cnt_frst = tmp + 1;
    cnt_scnd = dim - tmp;

    tmp = dim * row_idx;
    p_frst = matrix + tmp + m - row_idx;
    p_scnd = middl_row + tmp + row_idx;

    //do sum += *p_frst++; while (--cnt_frst);
    for (auto *p = p_frst; p < p_frst + cnt_frst; p++)
      sum += *p;

    //do sum += *p_scnd++; while (--cnt_scnd);
    for (auto *p = p_scnd; p < p_scnd + cnt_scnd; p++)
      sum += *p;
  }
  sum += *(matrix + dim * (dim - 1) + m);
  return sum;
}

...
Рейтинг: 0 / 0
26.05.2020, 11:11
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962152
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
JustSomethingа кто сказал что не хочу и не буду?

Весь топик об этом. Собственных попыток - ноль.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
26.05.2020, 12:37
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962158
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mini.weblab
JustSomething,
переходите на Питон! будет проще! :-)
Питон для слабаков! :)

 

Модератор: Под спойлер
...
Рейтинг: 0 / 0
26.05.2020, 12:43
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962161
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Интересно что Python-разработчик как таковой - редок в вакансиях.

Его часто подмешивают к таким хеш-тегам как data-engineer, data-scientist, devops.

+Еще часто его можно видеть как необходимый в машинном обучении.

Тоесть он необходим как bash, но о нем не говорят как о независимом языке.
Скорее как о слое который управляет более низким слоем написанном уже на этих
ваших CUDA-х, OpenCV-ах.
...
Рейтинг: 0 / 0
26.05.2020, 12:47
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962177
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
я не призываю никого становиться Питон-разработчиком :)
просто для начинающего алгоримы было бы проще начать изучать на Питоне (а не на С или С++)
в данном случае я за divide and conquer :)
...
Рейтинг: 0 / 0
26.05.2020, 13:02
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962190
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mini.weblab, проще всего начинать с Intel x86 ассемблера под flat модель, если преподам показать правильный подход к его изучению. После чего учащийся сможет легко и непринуждённо самостоятельно осваивать любые языки.
...
Рейтинг: 0 / 0
26.05.2020, 13:16
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962197
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
rdb_devпроще всего начинать с Intel x86 ассемблера под flat модель

Замороченный всё же у интеля ассемблер. DEC PDP-11 попроще будет и на Си хорошо проецируется.
...
Рейтинг: 0 / 0
26.05.2020, 13:22
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962213
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
Dimitry Sibiryakov, можно даже VAX или MIPS, что интереснее, полезнее и денежнее. Главное - показать чем и как, в конечном итоге, оперирует АЛУ.
...
Рейтинг: 0 / 0
26.05.2020, 13:35
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962296
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblab
я не призываю никого становиться Питон-разработчиком :)
просто для начинающего алгоримы было бы проще начать изучать на Питоне (а не на С или С++)
в данном случае я за divide and conquer :)

Дидактические свойства Питона - под большим сомнением.

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

Сообщения-же компилляции которые выдает С++ - поражают воображение объемом
трафика особнно когда не сматчились паттерны процессора шаблонов, или
ошибки линкера (смотрим топик где бедный Петро пытается победить
Visual Studio и при том он - не новичек). Тоесть такой подход в обучении обречен
сразу на провал и на демотивацию если нет учителя который в состоянии прочитать
и прокомментировать эту техническую лабуду. И не дай бох это рантайм где
мы видим ошибку как дамп памяти + содержимое регистров процессора (ага) посчитайте
какой объем знаний уже тут нужен чтоб разобраться. Это к С++ надо еще и учебник
Юрова читать про Ассемблер.

Тоесть в учебном смысла С++ - непригоден если вы нуб и решили его учить самостоятельно.
Демотивация гарантирована особенно на фоне C# к примеру.

Щас еще крупно-корпорации открывают курсы для детей где обучают их Scratci но
я этот язык пока не видел и ничего не могу сказать.
...
Рейтинг: 0 / 0
26.05.2020, 16:00
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962305
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton, сделал как ты хотел!
 
Не желаешь потестить производительность на больших массивах? :)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
int64_t diamond(const int *matrix, const size_t dim)
{
  int64_t sum = 0;

  const size_t m = dim >> 1;
  auto const middl_row = matrix + dim * m;

#pragma omp parallel reduction(+: sum)
  {
  #pragma omp for
    for (size_t row_idx = 0; row_idx < m; row_idx++)
    {
      register size_t tmp = row_idx << 1;

      const size_t
          cnt_upper = tmp + 1,
          cnt_lower = dim - tmp;

      tmp = dim * row_idx;

      auto
          *p_upper = matrix + tmp + m - row_idx,
          *p_lower = middl_row + tmp + row_idx;

    #pragma omp parallel reduction (+: sum)
      {
      #pragma omp for
        for (auto *p = p_upper; p < p_upper + cnt_upper; p++)
          sum += *p;

      #pragma omp for
        for (auto *p = p_lower; p < p_lower + cnt_lower; p++)
          sum += *p;
      } // #pragma omp parallel reduction(+: sum)
    }
  } // #pragma omp parallel reduction(+: sum)
  sum += *(matrix + dim * (dim - 1) + m);
  return sum;
}

Собирать надо с опцией -fopenmp
...
Рейтинг: 0 / 0
26.05.2020, 16:13
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962309
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
rdb_dev,

дружище я протещу только вечером. Доберусь до своей линукс машинки где у меня и железо хорошее. И clang
установлен.
...
Рейтинг: 0 / 0
26.05.2020, 16:16
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962311
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
 
я тоже свою версию написала (С) :)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
long long diamondsum(int *mtx, size_t n) {
	long long sum = 0;
	size_t m = n >> 1 ;
	size_t i, j;

	for (i = 0; i < n; i++) {
		for (j = abs(m - i); j < n - abs(m - i)  ; j++){
			sum += *(mtx + i * n + j);
		}
	}
	return sum;
}

...
Рейтинг: 0 / 0
26.05.2020, 16:19
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962312
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
mayton, сделал как ты хотел!
Собирать надо с опцией -fopenmp

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

На маленьких матрицах ваш OpenMP тормознёт алгоритм разов в 10-ть.

Ну а вы вообще... писать страшные алгоритмы один за одним вам не лень, подставить их в бенчмарк вам лень. Типа я должен сделать.
...
Рейтинг: 0 / 0
26.05.2020, 16:21
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962315
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
maytonМне кажется что единственный полезный язык для обучения новичков - это Pascal.

Лично я начинал на ДВК-1 с Бейсика и машинных кодов, так что считаю эту связку
оптимальной. Первый даёт языковые навыки для всех директивных языков и при этом достаточно
беден чтобы руководство (список операторов) уместилось на один листок, второй - понимание
как работает компьютер.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
26.05.2020, 16:22
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962316
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
я сейчас тоже попробую бенчмарки делать, но не знаю получится или нет :)
...
Рейтинг: 0 / 0
26.05.2020, 16:23
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962318
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton, забыл добавить, что нужно ещё заинклюдить <omp.h>
...
Рейтинг: 0 / 0
26.05.2020, 16:25
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962321
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
На маленьких матрицах ваш OpenMP тормознёт алгоритм разов в 10-ть.
У тебя есть возможность проверить сие утверждение. ;) Тормознуть, конечно, может, особенно на очень многоядерных/многопроцессорных компах, да ещё и с несколькими NUMA узлами, но сомневаюсь, что так сильно - в 10 раз.
...
Рейтинг: 0 / 0
26.05.2020, 16:30
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962327
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
Ну а вы вообще... писать страшные алгоритмы один за одним вам не лень, подставить их в бенчмарк вам лень. Типа я должен сделать.
У меня старый комп 2008 года на Q9550 с недетерминированным TSC.
...
Рейтинг: 0 / 0
26.05.2020, 16:36
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962328
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
petrav
На маленьких матрицах ваш OpenMP тормознёт алгоритм разов в 10-ть.
У тебя есть возможность проверить сие утверждение. ;) Тормознуть, конечно, может, особенно на очень многоядерных/многопроцессорных компах, да ещё и с несколькими NUMA узлами, но сомневаюсь, что так сильно - в 10 раз.

Я уже проверял много лет назад с перемножением маленьких матриц с использованием OpenMP. Результаты были плачевные, ожидаемо, один только барьер памяти тебе снесёт все надежды на производительность.

А у тебя нет возможности проверить? Как написать так возможность есть, как проверить так нет возможности. Зачем тогда писать. Короче ждём бенчмарк на маленьких матрицах.

Например, 9. Размерность мира в котором мы двигаемся — 3, а не миллион.
...
Рейтинг: 0 / 0
26.05.2020, 16:38
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962340
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dimitry Sibiryakov

maytonМне кажется что единственный полезный язык для обучения новичков - это Pascal.

Лично я начинал на ДВК-1 с Бейсика и машинных кодов, так что считаю эту связку
оптимальной. Первый даёт языковые навыки для всех директивных языков и при этом достаточно
беден чтобы руководство (список операторов) уместилось на один листок, второй - понимание
как работает компьютер.

Мой первый язык это был Бейсик для Электроника БК 10. И первый софт я не написал
а содрал с книжки 1 в 1. Вот такое было обучение.
...
Рейтинг: 0 / 0
26.05.2020, 16:52
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962347
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
Dimitry Sibiryakov

пропущено...

Лично я начинал на ДВК-1 с Бейсика и машинных кодов, так что считаю эту связку
оптимальной. Первый даёт языковые навыки для всех директивных языков и при этом достаточно
беден чтобы руководство (список операторов) уместилось на один листок, второй - понимание
как работает компьютер.

Мой первый язык это был Бейсик для Электроника БК 10. И первый софт я не написал
а содрал с книжки 1 в 1. Вот такое было обучение.

Это не круто. Программируемый калькулятор МК-52 круче, ассемблер и машинный код. Я на нём программировал даже в поезде на втором "этаже". А ещё мама приносила из института перфокарты и я умел их расшифровывать. Но первый софт я написал на советском лунаходе .
...
Рейтинг: 0 / 0
26.05.2020, 17:01
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962352
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
rdb_dev
mayton, сделал как ты хотел!
Собирать надо с опцией -fopenmp

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

На маленьких матрицах ваш OpenMP тормознёт алгоритм разов в 10-ть.

Давай порассуждаем. У этой задачи есть 2 аспекта. Первый - это оценка асимптоматики. Она - квадратичная по size - матрицы.
Что-бы мы не придумывали. Какие - бы хитровыеб.... умные способы мы не избирали - все одно сведем к перебору всех
чисел "бубнового туза".

Второй аспект - чисто машиный. Это

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

- Игры с кешами L1/L2/L3. И padding с целю попадания в кеш-линию.
Есть творческая задачка где умножаются 2 большие матрицы. Кстати вторая - транспонируется предварительно
(угадай зачем). И в зависимости от кластеризации данных (близко они лежат или далеко в памяти) мы
можем получать в разы отличающееся характеристики. А поскольку эта задача идеально
ложиться в map-reduce - то мы можем этот ромбик как торт резать на трапеции так как
будет выгодно Threads процессора или разложить данные в 2 канала памяти. Или предварительно
прогрев кеши нужными данными очень быстро дернуть сложение и таким образом "нае6аtь"
потенциального заказчика показав ему сферическое сложение в вакууме. Ведь время
загрузки матрицы с диска мы не учли. А хардкодные цифры никому не интересны.

- Игры с разрядностью. С компиллятором. С железом.

Все части машинного аспекта - выгодно тестировать на больших объемах оперативки. На малых - непонятно
что мы тестируем. Ведь ты должен динамически генерить новые матрицы для каждого вызова.
Ты-же думал об этом? Верно?

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

По моему ... я вообще первый энтузиаст кто на скруле поднял тему бенчмарков и даже организовал группу разработчиков
в некий соревновательный процесс лет 5 назад.
...
Рейтинг: 0 / 0
26.05.2020, 17:07
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962353
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
mayton
пропущено...

Мой первый язык это был Бейсик для Электроника БК 10. И первый софт я не написал
а содрал с книжки 1 в 1. Вот такое было обучение.

Это не круто. Программируемый калькулятор МК-52 круче, ассемблер и машинный код. Я на нём программировал даже в поезде на втором "этаже". А ещё мама приносила из института перфокарты и я умел их расшифровывать. Но первый софт я написал на советском лунаходе .

Я помню его. (Калькулятор). Я решал кубическое уравнение исопльзуя только стек. Из 4х ячеек.
...
Рейтинг: 0 / 0
26.05.2020, 17:09
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962368
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
Кстати вторая - транспонируется предварительно (угадай зачем).

Не вижу зачем заранее транспонировать матрицу если нам нужна транспонировання матрица. Ведь можно написать спец. функцию где индексы i и j будут просто поменяны местами.

mayton
Все части машинного аспекта - выгодно тестировать на больших объемах оперативки. На малых - непонятно
что мы тестируем.

Мы тестируем то что нам нужно по прикладной задаче. У нас размерность мира 3, а не 1000000.

mayton
Ведь ты должен динамически генерить новые матрицы для каждого вызова.
Ты-же думал об этом? Верно?

Ну я доработал бенчмарк до генерации массива для каждого вызова. Теперь в 64-бит отставание в 1.8 раз.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
Elapsed time: 0.170488s
Elapsed time: 0.299534s
Relation: 1.75692
Elapsed time: 0.293203s
Elapsed time: 0.168493s
Relation: 0.574663
Elapsed time: 0.167437s
Elapsed time: 0.299641s
Relation: 1.78957

 

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
#include <chrono>

#if 1
using Type = int;
#else
using Type = double;
#endif

int const Size = 1024+1/*5*/;
int const Half = Size / 2;

Type arr[Size][Size] =
{
     1,  2,  3,  4,  5,
     6,  7,  8,  9, 11,
    12, 14, 15, 16, 17,
    18, 19, 20, 21, 22,
    23, 24, 25, 26, 27
};

Type summ_diamond_1()
{
    Type res = 0;

    for (size_t i=0; i<Half; ++i)
    {
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
            res += arr[Size-i-1][j];
        }
    }

    for (size_t i=0; i<Size; ++i)
    {
        res += arr[Half][i];
    }

    return res;
}

Type summ_diamond_2()
{
  constexpr size_t dim = Size;
  constexpr size_t m = dim / 2;

  Type sum = 0;
  Type
      *head = ((Type*)arr) + m,
      *tail = ((Type*)arr) + dim*dim - m - 1;
  size_t
      n = 1,
      c = n,
      d;

  while (head != tail)
  {
    if (c--)
    {
      sum += *head++;
      sum += *tail--;
    }
    else
    {
      d = dim - 1 - n;
      head += d;
      tail -= d;
      n += 2;
      c = n;
    }
  }
  sum += *head;

  return sum;
}

double test(Type (&summ_func)())
{
    double res = 0.0;
    for (size_t i=0; i<1000; ++i)
    {
        for (size_t i=0; i<Size; ++i)
        {
            for (size_t j=0; j<Size; ++j)
            {
                arr[i][j] = std::rand();
            }
        }

        auto start = std::chrono::high_resolution_clock::now();
        summ_func();
        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> elapsed_seconds = end - start;
        res += elapsed_seconds.count();
    }
    std::cout << "Elapsed time: " << res << "s\n";
    return res;
}

void testComplex(Type (&summ_func_1)(), Type (&summ_func_2)())
{
    double const d1 = test(summ_func_1);
    double const d2 = test(summ_func_2);
    std::cout << "Relation: " << (d2 / d1) << "\n";
}

void calc_times()
{
    testComplex(summ_diamond_1, summ_diamond_2);
    testComplex(summ_diamond_2, summ_diamond_1);
    testComplex(summ_diamond_1, summ_diamond_2);
}


...
Рейтинг: 0 / 0
26.05.2020, 17:36
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962372
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
кстати, для тестов хорошо подходят единичные матрицы ( а также матрицы со всеми одинаковыми элементами )
думаю что для бенчмарков тоже подойдут
...
Рейтинг: 0 / 0
26.05.2020, 17:40
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962377
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
mayton
Кстати вторая - транспонируется предварительно (угадай зачем).

Не вижу зачем заранее транспонировать матрицу если нам нужна транспонировання матрица. Ведь можно написать спец. функцию где индексы i и j будут просто поменяны местами.

Разумеется можно менять местами индекcы. А что почувствует канал памяти когда первая матрица сканируется
for(i...) for (j... ) а вторая матрица - наоборот for(j...) for (i...) ?
...
Рейтинг: 0 / 0
26.05.2020, 17:43
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962382
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
Блин, я же забыл матрицу сделать размера 9. Теперь результаты одинаковые:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
Elapsed time: 0.0448235s
Elapsed time: 0.0464368s
Relation: 1.03599
Elapsed time: 0.0466745s
Elapsed time: 0.0470738s
Relation: 1.00855
Elapsed time: 0.045949s
Elapsed time: 0.0463073s
Relation: 1.0078



Я, правда, не уверен, что <chrono> честно считает время. А прикручивать QPC мне лень.
...
Рейтинг: 0 / 0
26.05.2020, 17:46
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962383
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblab
кстати, для тестов хорошо подходят единичные матрицы ( а также матрицы со всеми одинаковыми элементами )
думаю что для бенчмарков тоже подойдут

Нет. Не подойдет. Единичную матрицу можно свести к функции которая продуцирует единички или нули
а это сводит на нет все предыдущие достижения по памяти например. Тоесть вы поиграетесь с полиморзимом
но его результаты можно будет натянуть только на единичные матрицы но никак не на общие (real-world matrix).
...
Рейтинг: 0 / 0
26.05.2020, 17:48
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962397
Алексей Роза
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Роза
Гость
mini.weblab
просто для начинающего алгоримы было бы проще начать изучать на Питоне (а не на С или С++)

для начинающего лучше сразу на C++, чтобы понять, как и что работает
кроме того, только на нём ты получаешь ровно тот результат, который ожидаешь
ты точно знаешь, где какой байт за что отвечает
без сюрпризов.
это важно.
нужен только правильный Учитель.
...
Рейтинг: 0 / 0
26.05.2020, 18:19
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962402
Алексей Роза
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Роза
Гость
mayton
Сообщения-же компилляции которые выдает С++ - поражают воображение объемом
трафика особнно когда не сматчились паттерны процессора шаблонов

есть такая штука: -Wfatal-errors
оставит 1 строчку
...
Рейтинг: 0 / 0
26.05.2020, 18:22
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962405
Алексей Роза
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Роза
Гость
petrav
mayton
пропущено...

Мой первый язык это был Бейсик для Электроника БК 10. И первый софт я не написал
а содрал с книжки 1 в 1. Вот такое было обучение.

Это не круто. Программируемый калькулятор МК-52 круче, ассемблер и машинный код. Я на нём программировал даже в поезде на втором "этаже". А ещё мама приносила из института перфокарты и я умел их расшифровывать. Но первый софт я написал на советском лунаходе .

и у нас есть победитель!
...
Рейтинг: 0 / 0
26.05.2020, 18:27
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962409
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Алексей Роза
mayton
Сообщения-же компилляции которые выдает С++ - поражают воображение объемом
трафика особнно когда не сматчились паттерны процессора шаблонов

есть такая штука: -Wfatal-errors
оставит 1 строчку

Смысл же не в том чтобы оставить строчку. А в том чтобы месседж об ошибке нес смысл для newcomer-а который
только вчера взялся изучать С++.
...
Рейтинг: 0 / 0
26.05.2020, 18:30
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962412
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
Алексей Роза
petrav
пропущено...

Это не круто. Программируемый калькулятор МК-52 круче, ассемблер и машинный код. Я на нём программировал даже в поезде на втором "этаже". А ещё мама приносила из института перфокарты и я умел их расшифровывать. Но первый софт я написал на советском лунаходе .

и у нас есть победитель!

Не завидуй так громко.
...
Рейтинг: 0 / 0
26.05.2020, 18:34
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962413
Алексей Роза
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Роза
Гость
mayton
Алексей Роза
пропущено...

есть такая штука: -Wfatal-errors
оставит 1 строчку

Смысл же не в том чтобы оставить строчку. А в том чтобы месседж об ошибке нес смысл для newcomer-а который
только вчера взялся изучать С++.

ну так он и получит инфу о последней ошибке, а не простыню на 8 экранов
1 ошибку пофиксит, получит инфу по следующей...
...и заряд оптимизма
...
Рейтинг: 0 / 0
26.05.2020, 18:35
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962549
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Сорямба.

Я только щас добрался до компа. И то не до мощной рабочей станции а до Corei3 ноутбучика.

Из хорошего. Помимо OpenMP есть еще другая библиотечка. Называется OpenACC.
Поддерживается в GCC, и для Clang. И мы ее попробуем для "туза бубей".

Из вопросов. У кого из вас есть учётка в github?
...
Рейтинг: 0 / 0
26.05.2020, 22:50
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962582
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
По OpenMP, OpenAAC, OpenCL может отдельный топик создать?
Тут как-то цели никакой не поставлено.
...
Рейтинг: 0 / 0
26.05.2020, 23:40
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962716
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mayton

- Игры с разрядностью. С компиллятором. С железом.

И еще забыл. SIMD. Это конечно уже далеко от С++ но - тоже машинный аспект.

IMHO. Надо попробовать SIMD. Может подойдет а может и нет.
...
Рейтинг: 0 / 0
27.05.2020, 11:09
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962767
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblab
 
я тоже свою версию написала (С) :)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
long long diamondsum(int *mtx, size_t n) {
	long long sum = 0;
	size_t m = n >> 1 ;
	size_t i, j;

	for (i = 0; i < n; i++) {
		for (j = abs(m - i); j < n - abs(m - i)  ; j++){
			sum += *(mtx + i * n + j);
		}
	}
	return sum;
}


Давай - еще короче. Два цикла - обычно связанны зависимостью. Если предположить
что они - разряды системы счисления с основанием SIZE.

Заменим циклы на итерацию по всему диапазону двухзначного числа (SIZE,SIZE)
А внутри по сути идет проверка что координата ограничена четырьмя гипер-прямыми под 45 градусов.

Этот алгоритм будет не очень быстрый - зато самый короткий.

У нас в топике два совревнования. В одном два чела выжимают скорость из С++ с ОпенМП.
В другом мы будем сокращать функцию до брейнфака.
...
Рейтинг: 0 / 0
27.05.2020, 12:55
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962795
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
Я, правда, не уверен, что <chrono> честно считает время. А прикручивать QPC мне лень.
К сожалению, если операционная система не предоставляет специальных средств измерения уровня ядра, измерить что-либо точно в третьем кольце не представляется возможным и измерения можно делать только относительные, постаравшись снизить влияние разных факторов.

Добрался до i5 с детерминированным TSC и сделал свой платформозависимый бенчмарк для GNUC'а.

Результат использования OpenMP для маленьких массивов просто катастрофический даже с "прогревом" OpenMP - хуже в тысячу раз!!! Но на массиве размером в гигабайт твой же распараллеленный алгоритм обгоняет однопоточный примерно в 1.3 раза.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
DIAMOND_1
SUM: 18016597801181184
Elapsed time(nsec): 52176491.312428

OpenMP warmingup
SUM: 18016597801181184
Elapsed time(nsec): 39681171.870135

DIAMOND_2
SUM: 18016597801181184
Elapsed time(nsec): 34749407.371903
 
Benchmark
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
#include <windows.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>
#include <windows.h>

# ifndef __INLINE
#   ifdef __GNUC__
#     define __INLINE inline __attribute__((always_inline, __target__("default")))
#   endif
# endif

template <typename T>
__INLINE
static
void volatilize(T &r) noexcept
{
  asm volatile ("" : "=m" (r) : "m" (r) :);
}

__INLINE
static
void cpu_pause()
{
  asm volatile ("pause" : : :);
}

__INLINE
static
uint64_t xchg(uint64_t &recv, uint64_t src)
{
  uint64_t register ret;
  asm volatile ("\
      xchg %[ret], %[recv];\n"
    : [ret] "=r" (ret), [recv] "=m" (recv)
    : "0" (src)
    :
  );
  return ret; // old value
}

__INLINE
static
uint64_t tsc_get_ticks() noexcept
{
  register size_t tsc_lo;
  register size_t tsc_hi;
  register size_t tsc_id;
  register uint64_t ret;
  asm volatile ("\
    mov $0, %[tsc_hi];\n\
    mov $0, %[tsc_lo];\n\
    mov $0, %[tsc_id];\n\
    rdtscp;\n"
    : [tsc_lo] "=a" (tsc_lo), [tsc_hi] "=d" (tsc_hi), [tsc_id] "=c" (tsc_id)
    :
    :
  );
  return (tsc_hi << 32) | tsc_lo;
}


struct TSC
{
  uint64_t  value;
  timespec  tmsp;
};

static
double tsc_get_ticks_per_nanosec
    (
      uint32_t pre_delay,
      uint32_t delay,
      TSC *tsc = NULL
    )
{
  alignas(16)
  timespec tmsp_before;
  alignas(8)
  timespec tmsp_after;

  register double ticks_per_nanosec = 0;
  register uint64_t
      ticks_before,
      ticks_after,
      nsec_delta;

  Sleep(pre_delay);
  // -- barrier of insructions
  tsc_get_ticks();
  clock_gettime(CLOCK_REALTIME, &tmsp_before);
  ticks_before = tsc_get_ticks();
  Sleep(delay);
  // -- barrier of instructions
  tsc_get_ticks();
  clock_gettime(CLOCK_REALTIME, &tmsp_after);
  ticks_after = tsc_get_ticks();
  if (NULL != tsc)
  {
    tsc->value = ticks_after;
    tsc->tmsp = tmsp_after;
  }
  if (ticks_after < ticks_before)
    ticks_after += ~(--ticks_before);
  else
    ticks_after -= ticks_before;

  tmsp_after.tv_sec -= tmsp_before.tv_sec;
  tmsp_after.tv_nsec -= tmsp_before.tv_nsec;
  if (0 > tmsp_after.tv_nsec)
  {
    tmsp_after.tv_sec--;
    tmsp_after.tv_nsec += 1000000000L;
  }
  nsec_delta = tmsp_after.tv_sec * 1000000000 + tmsp_after.tv_nsec;
  ticks_per_nanosec = (double)ticks_after / nsec_delta;

  return ticks_per_nanosec;
}

class TSC_ELAPSED
{
  double ticks_per_nsec;
  uint64_t before;
  uint64_t after;

public:
  __INLINE
  TSC_ELAPSED() : before(0), after(0)
  {
    this->ticks_per_nsec = tsc_get_ticks_per_nanosec(16, 7000);
  };

  __INLINE
  void start()
  {
    Sleep(16);
    this->before = tsc_get_ticks();
  }

  __INLINE
  void stop()
  {
    this->after = tsc_get_ticks();
  }

  __INLINE
  double get_ticks_per_nsec()
  {
    return this->ticks_per_nsec;
  }

  __INLINE
  double evaluate_nsec()
  {
    register double ret = 1;
    TSC_ELAPSED & _ = *this;
    if (_.after < _.before)
      ret += _.after + (~_.before);
    else
      ret = _.after - _.before;
    return ret /= _.ticks_per_nsec;
  }
};

constexpr size_t dim = 16384;
//constexpr size_t dim = 5;
typedef int TArr[dim][dim];
static TArr arr;

int64_t diamond1()
{
  const size_t Half = dim / 2;
  int64_t res = 0;

  for (size_t i=0; i < Half; ++i)
    for (size_t j = Half-i; j <= Half+i; ++j)
    {
      res += arr[i][j];
      res += arr[dim-i-1][j];
    }

  for (int i=0; i < dim; ++i)
    res += arr[Half][i];

  return res;
}

int64_t diamond2()
{
  const size_t Half = dim / 2;
  int64_t res = 0;

#pragma omp parallel for reduction (+: res)
  for (size_t i=0; i < Half; ++i)
    for (size_t j = Half-i; j <= Half+i; ++j)
    {
      res += arr[i][j];
      res += arr[dim-i-1][j];
    }

#pragma omp parallel for reduction (+: res)
  for (int i=0; i < dim; ++i)
    res += arr[Half][i];

  return res;
}

int main(int argc, char** argv)
{
  printf("\r\nTSC calibrating, please wait...\r\n");
  TSC_ELAPSED elapsed;
  volatilize(elapsed);
  printf("TSC ticks per nanosec: %lf\r\n", elapsed.get_ticks_per_nsec());

  if (NULL == arr)
    return 1;

  printf("\r\nSize of matrix: %lli\r\n", sizeof(arr));

  constexpr size_t dim_plain = dim * dim;
  int *e = (int*)arr;
  for (size_t i = 0; i < dim_plain; i++) e[i] = i + 1;

  int64_t val;

#pragma omp flush(arr)
  elapsed.start();
  val = diamond1();
  elapsed.stop();
  printf
      (
        "\r\nDIAMOND_1\r\nSUM: %lli\r\nElapsed time(nsec): %lf\r\n",
        val,
        elapsed.evaluate_nsec()
      );

#pragma omp flush(arr)
  elapsed.start();
  val = diamond2();
  elapsed.stop();
  printf
      (
        "\r\nOpenMP warmingup\r\nSUM: %lli\r\nElapsed time(nsec): %lf\r\n",
        val,
        elapsed.evaluate_nsec()
      );

#pragma omp flush(arr)
  elapsed.start();
  volatilize(val);
  val = diamond2();
  elapsed.stop();
  printf
      (
        "\r\nDIAMOND_2\r\nSUM: %lli\r\nElapsed time(nsec): %lf\r\n",
        val,
        elapsed.evaluate_nsec()
      );

  return (EXIT_SUCCESS);
}

...
Рейтинг: 0 / 0
27.05.2020, 13:38
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962805
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton

Давай - еще короче.


это будет нечитабельно и неэффективно.
я потренируюсь лучше бенчмарки делать :)
...
Рейтинг: 0 / 0
27.05.2020, 13:54
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962835
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblab
mayton

Давай - еще короче.


это будет нечитабельно и неэффективно.
я потренируюсь лучше бенчмарки делать :)

Хорошо. Потренируйся. Но этот синтетический тест - не особо показателен.
Его эффективность мало зависит от алгоритма а больше предварительного
состояния кешей и количества threads процессора которые в этом участвуют.

Вобщем я к тому что резултаты этого теста сложно будет на что-то другое натянуть.
...
Рейтинг: 0 / 0
27.05.2020, 14:44
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962843
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton,
главное, разобраться как это делается

 
покa что, функция умножения матриц
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
// mtx = mtxa * mtxb

double *matrix_multiplication(double *mtxa, double *mtxb, double *mtx,
		size_t anrow, size_t ancol, size_t bnrow, size_t bncol) {
	int i, j, k;
	double tmpa, tmpb;

	if (ancol != bnrow) {
		return NULL;
	}

	for (i = 0; i < anrow; i++) {
		for (j=0; j< bncol; j++) {
			*(mtx + i * bncol + j) = 0;
			for (k = 0; k < ancol; k++) {
				tmpa = *(mtxa + i * ancol + k);
				tmpb = *(mtxb + k * bncol + j);
				*(mtx + i * bncol + j) += tmpa * tmpb;
			}
		}
	}
	return mtx;
}



по матрицам в С:
мне бы хотелось работать с элементами матрицы, типа mtx[ i ][ j ], но не я понимаю как это сделать, и можно ли это вообще сделать.
...
Рейтинг: 0 / 0
27.05.2020, 15:00
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962846
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
petrav
Я, правда, не уверен, что <chrono> честно считает время. А прикручивать QPC мне лень.
К сожалению, если операционная система не предоставляет специальных средств измерения уровня ядра, измерить что-либо точно в третьем кольце не представляется возможным и измерения можно делать только относительные, постаравшись снизить влияние разных факторов.

Ваши слова натолкнули меня на мысль, что я вообще по-дибильному время считаю. Я генерирую маленькую матрицу, подсчитываю время одного вызова функции и так в цикле суммирую. Время, понятно, крайне маленькое. И библиотека <chrono> не справляется. По сути я суммирую некие минимально доступные кванты времени.

Я переделал на сначала генерацию большого количества маленьких матриц. И теперь замеряю суммирование сразу их всех N раз. Теперь на маленьких матрицах вариант № 1 обгоняет вариант № 2 в 1.2 раза. Это не потому что я пытаюсь письками мерятся, как вы предположили. Я вообще (точнее почти) не думал о производительности когда код писал. Да я и о бенчмарке особо не думал.

rdb_dev
Добрался до i5 с детерминированным TSC и сделал свой платформозависимый бенчмарк для GNUC'а.

Ну WinAPI QPC вроде как тоже возвращает значение некоего аппаратного счётчика. MS пишет про точность 10 -6 сек.

rdb_dev
Результат использования OpenMP для маленьких массивов просто катастрофический даже с "прогревом" OpenMP - хуже в тысячу раз!!!

Прикольно.
...
Рейтинг: 0 / 0
27.05.2020, 15:01
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962857
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Наверное OpenMP на старт-стоп потоков тратит накладные расходы. Их в коде не видно
но они-же где-то стоят.
...
Рейтинг: 0 / 0
27.05.2020, 15:16
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962865
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton, про "прогрев" я упомянул, но дело даже не в этом. Просто получается очень маленькая "зернистость" и скорость выполнения каждого зерна выше, чем скорость синхронизации результатов через барьеры и атомарные функции (по крайней мере на том компе, где я тестировал, так как реальная скорость зависит от скорости шины памяти или от скорости FSB на предыдущих поколениях процессоров). Соответственно, реальный выигрыш получается только на очень больших массивах - свыше 1 Гб, но такие массивы пихать целиком в адресное пространство процесса как-то некомильфо.
...
Рейтинг: 0 / 0
27.05.2020, 15:26
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962867
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton
Их в коде не видно
но они-же где-то стоят.
Очевидно, в "libgomp-1.dll", которая болтается в таблице импорта исполняемого файла.
...
Рейтинг: 0 / 0
27.05.2020, 15:29
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962868
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я-ж про это писал. Настоящую мощь этих оптимизаций можно почувствовать только на больших данных.

Какой смысл др04ить параллелизм когда 5х5 целых чисел сложатья быстрее чем мы подготовим
потоки и диспетчер их успеет форкнуть и менеджер ОС успеет их разложить по ядрам и
они в ядрах успеют получить в L1 нужный им срез матрицы.

Этож не зелёные мать их потоки как в Java. И не корутины. Это реальные потоки операционки.
...
Рейтинг: 0 / 0
27.05.2020, 15:30
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962874
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton, это понятно, но я не ожидал таких огромных накладных расходов, увеличивающих время выполнения более чем в тысячу раз.
...
Рейтинг: 0 / 0
27.05.2020, 15:33
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962889
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Кстати - в тему Java - самый убойный вопрос на собеседовании - как сделать kill для JavaThread.
...
Рейтинг: 0 / 0
27.05.2020, 15:50
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962896
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
А в чём, собственно, проблема?
Регулярно проверяем состояние прерывания и, при необходимости, выходим, делая нужную очистку.
Насколько я понимаю, оно везде так, не только в Java.
...
Рейтинг: 0 / 0
27.05.2020, 15:59
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962903
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да вы можете вежливо (gracefully) попросить поток завершиться. И он завершиться.
Если такая возможность была заложена.
...
Рейтинг: 0 / 0
27.05.2020, 16:06
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962906
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
Я переделал на сначала генерацию большого количества маленьких матриц. И теперь замеряю суммирование сразу их всех N раз. Теперь на маленьких матрицах вариант № 1 обгоняет вариант № 2 в 1.2 раза. Это не потому что я пытаюсь письками мерятся, как вы предположили. Я вообще (точнее почти) не думал о производительности когда код писал. Да я и о бенчмарке особо не думал.
В моём тесте оба варианта твои, только второй вариант распараллелен через OpenMP и тест надо собирать с "-fopenmp".
...
Рейтинг: 0 / 0
27.05.2020, 16:11
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962909
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ребят. Сейчас уже трудно собрать осколки сорцов в кучку. Вы можете еще раз их актуализировать.
Где чей последни релиз?
...
Рейтинг: 0 / 0
27.05.2020, 16:13
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962917
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton, мои можно не смотреть, они явно хуже, чем у petrav и я пока даже не знаю, что в его алгоритме ещё можно оптимизировать. Кажется, он случайно создал самое эффективное решение. :)
...
Рейтинг: 0 / 0
27.05.2020, 16:22
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962920
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
rdb_dev
Кажется, он случайно создал самое эффективное решение. :)

Чисто случайно - это самый лучший паттерн разработки!
...
Рейтинг: 0 / 0
27.05.2020, 16:24
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962935
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
mayton, мои можно не смотреть, они явно хуже, чем у petrav и я пока даже не знаю, что в его алгоритме ещё можно оптимизировать. Кажется, он случайно создал самое эффективное решение. :)

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

Если по делу и без шуток. Я видел матричную арифметику реализованную и в стиле arr[i][j], и в стиле сдвигания указателей *++ptr. Причём вторая (на сдвиге указателей) побеждала в бенчмарках. Хотя теоретически было совершенно непонятно почему? Логически казалось, что что должно быть наоборот.

Я думаю можно мой алгоритм улучшить.
...
Рейтинг: 0 / 0
27.05.2020, 16:46
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962937
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav, в английском флоте в личном деле офицеров указывают "индекс удачливости".

Вобщем... petrav, ты - фартовый. Тебя можно кидать на нерешаемые проблемы и
ты рандомно постучав по клавиатуре - все порешаешь.
...
Рейтинг: 0 / 0
27.05.2020, 16:53
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962956
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
petrav
...
Я видел матричную арифметику реализованную и в стиле arr[i][j], и в стиле сдвигания указателей *++ptr
...

если нет помех, то ++ptr инлайнится в регистровую операцию.
это невозможно обогнать,
mini.weblab давала же цитату из Кернигана, а ты игнорируешь...
...
Рейтинг: 0 / 0
27.05.2020, 17:17
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962975
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
boobymini.weblab давала же цитату из Кернигана

Вот только у современной интеловской системы команд нет косвенной автоинкрементной
адресации. Та цитата относилась к дековской продукции.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
27.05.2020, 18:04
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39962997
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если в OpenMP версии уменьшить размер матрицы до 1 или до нуля то мы наверное сможем
как-раз увидеть накладные расходы на ::createThread или pthread_create (для linux)
и для джоина их обратно в основной поток.
...
Рейтинг: 0 / 0
27.05.2020, 19:00
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963002
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Dimitry Sibiryakov,

во, страсть какая...
Регистры-то хоть есть какие-нибудь,
чтобы смещение на константу организовать?
...
Рейтинг: 0 / 0
27.05.2020, 19:03
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963006
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
petrav
Я видел матричную арифметику реализованную и в стиле arr[i][j], и в стиле сдвигания указателей *++ptr. Причём вторая (на сдвиге указателей) побеждала в бенчмарках. Хотя теоретически было совершенно непонятно почему? Логически казалось, что что должно быть наоборот.

у Голуба был пример:
# 88. Используйте указатели вместо индексов массива.
Вообще, инкрементирование указателя - лучший способ перемещения по массиву, чем индекс массива. Например, простой цикл, подобный следующему, страшно неэффективен:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
struct thing
{
    int field;
    int field2;
    int field3;
};

thing array[ nrows ][ ncols ];

int row, col;
for (row = 0;   row < nrows;   ++nrows)
{
    for (col = 0;   col < ncols;   ++cols)
        {array[row][col].field = 0;}
}



Выражение array[row][col] требует двух умножений и одного сложения во время выполнения. Вот что происходит на самом деле:
array + (row * size_of_one_row) + (col * size_of_a_thing)
Каждая структура имеет размер 12 байтов, и 12 не является степенью 2, поэтому вместо умножения нельзя использовать более эффективный сдвиг.

Код: plaintext
1.
2.
3.
4.
5.
// Вы можете сделать то же самое посредством указателей следующим образом:
thing *p = (thing*)array;
int n_cells = nrows * ncols;
while (--n_cells >= 0 )
    {(p++)->field = 0;}



При этом здесь вообще нет умножения во время выполнения. Оператор инкрементирования p++ просто прибавляет 12 к p.
С другой стороны, указатель лучше только тогда, когда вы можете его инкрементировать, то есть когда вы обращаетесь к последовательным элементам.
Если вам нужен по настоящему случайный доступ в массив, то запись с квадратными скобками намного проще читается и разницы в скорости выполнения нет.

Аналогично, если внутренняя часть цикла в принципе неэффективна - скажем, например, мы сделали следующее:
Код: plaintext
1.
2.
3.
4.
for (row = 0;   row < nrows;   ++nrows){
    for (col = 0;   col < ncols;   ++cols)
        {f(array[row][col]);}
}


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

Наконец, верно, что оптимизатор часто может преобразовать вариант цикла с индексами массива в вариант с указателями, но я думаю, что это плохой стиль - писать неэффективный код в надежде на то, что оптимизатор очистит его после вас. Указатели так же хорошо читаемы, как и индексы массивов, для того, кто знает язык программирования.
...
Рейтинг: 0 / 0
27.05.2020, 19:11
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963009
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
Офтопим мы последнее время сурово. Ну и я добавлю. Как я вижу через 20-ть минут планируется первый запуск SpaceX Crew Dragon с людьми на борту. Ждём прямой трансляции.
...
Рейтинг: 0 / 0
27.05.2020, 19:12
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963013
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,
подозревается мне, что в вопросах нахождения именно суммы (на непрерывном отрезке памяти)
векторизация интересней параллелизации будет.
если уж идти до низа, то ромб интереснее делить на зоны подходящей векторизации, а не параллелить.
Это функция размера ромба, и формирует самостоятельную задачу.
Параллелизацию, если строить, то уже вторым этажом над этим.
Вот такое мне сейчас подумалось.
...
Рейтинг: 0 / 0
27.05.2020, 19:16
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963032
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да ромб смешал все карты. Если-бы можно было свести это к пересечению квадратной матрицы
и единичной-ромбовидной одновременно со сложением через SIMD тогда нам было бы все равно
какая там форма внутри. Бубновая или Трефовая.
...
Рейтинг: 0 / 0
27.05.2020, 19:33
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963046
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Транспонируем матрицу на 45 градусов и ромб превращается в привычный квадрат.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
27.05.2020, 20:10
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963048
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dimitry Sibiryakov, у меня сильное дежа-вю в плане поворота матрицы на 45 градусов.

Был тут один.. любитель вращать матрицы.
...
Рейтинг: 0 / 0
27.05.2020, 20:16
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963075
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
mayton
petrav, в английском флоте в личном деле офицеров указывают "индекс удачливости".

Вобщем... petrav, ты - фартовый. Тебя можно кидать на нерешаемые проблемы и
ты рандомно постучав по клавиатуре - все порешаешь.

На моей первой работе я ведущему программисту показал сидиром, который я себе купил. Начало 2000-ных. И вот такой разговор:

- Дерьмовый сидиром ты купил. Плохо будет работать. Деньги по-дурацки потратил.
- Но почему? Нормально же выглядит. Я его подключал.
- Не знаю. Но наверное же моё мнение основано на личном опыте?

PS: Работал сидиром хреново. Но это было уже в будущем.
...
Рейтинг: 0 / 0
27.05.2020, 21:11
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963080
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
ну я когда работал сис.админом в молодости тоже компьютеры лечил взглядом
бывает, жалуется тётка, что комп тупит
подошёл к нему, зыркнул... и уже не тупит
...
Рейтинг: 0 / 0
27.05.2020, 21:32
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963087
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
полудух, это называется "Эффект присутствия". Звонит юзверь, жалуется, мол, что-то глючит ворд/эксель/пауэрпоинт. Приходишь, просишь воспроизвести проблему - не выходит, всё работает. :) Я вообще толковых пользователей (power users) встречал раз-два и обчёлся.
Помню как-то более 20 лет назад работал на фарм.предприятии. Звонят из лаборатории, говорят, дискету 5,25 из дисковода вытащить не могут. Прихожу, смотрю на системник - никакого дисковода нет, одни заглушки на морде. Спрашиваю - куда же вы дискету вставляли? Отвечают - а вот в щёлочку (между двумя заглушками). Вскрываю корпус а там дискета лежит себе на полочке для устройств.
...
Рейтинг: 0 / 0
27.05.2020, 22:27
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963091
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
полудух, а ещё забавный показательный случай, что не только в России пользователи дундуки. Приехала как-то делегация из пендостанской HQ, прямиком из Коста-Мезы, вопросы порешали, специалисты из делегации разбрелись по разным кабинетам своих российских коллег и вот один такой российский коллега звонит, просит подойти и помочь. Прихожу... Просят засунуть несколько документов на одну дискету 3.5'', а размер документов сильно больше 1.4 Мб. Жму архиватором, запихиваю на дискету, а меня пендосы спрашивают как им потом эти документы выудить. Ити иху мать! Пришлось объяснить на пальцах и записать на бумажке, как использовать консольную утилиту arj.exe.
...
Рейтинг: 0 / 0
27.05.2020, 22:34
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963098
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мы их на 1.7 мб форматировали.
...
Рейтинг: 0 / 0
27.05.2020, 22:50
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963174
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
rdb_dev
mayton, мои можно не смотреть, они явно хуже, чем у petrav и я пока даже не знаю, что в его алгоритме ещё можно оптимизировать. Кажется, он случайно создал самое эффективное решение. :)
Ну прямо случайно... лицом по клавиатуре катался и случайно создал. Удача не простое ремесло.
Ну, не так грубо , конечно... Я утрирую.
...
Рейтинг: 0 / 0
28.05.2020, 09:01
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963176
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton
Мы их на 1.7 мб форматировали.
Да, качество носителей некоторых производителей позволяли. До сих пор ещё с тех времён несколько коробок Verbatim'ов дома на полке пылятся.
...
Рейтинг: 0 / 0
28.05.2020, 09:02
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963291
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
rdb_dev
Да, качество носителей некоторых
Некоторых???
Это ничего, что неформатированная ёмкость 3,5-дюймовой дискеты - два мегабайта?

P.S.
Дистрибутив OS/2, если что, поставлялся на дискетах, отформатированных на 1,7МБ. И даже на компакт-диске были образы этих дискет, что позволяло установить OS/2 и на компьютеры без CD.
Достигалось это нестандартным сектором в 1КБ, который уменьшает межсекторные потери и позволяет разместить на дорожке близкий к максимуму объём данных.

P.P.S.
В OS/2 дискеты с нестандартным форматированием читал штатный драйвер. Для записи образов использовалась специальная утилита.
...
Рейтинг: 0 / 0
28.05.2020, 12:50
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963443
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
mayton, мне, таки, удалось написать алгоритм на указателях по массиву, размерность которого известна только в рантайме, сравнимый по производительности с алгоритмом petrav по массиву, размерность которого известна на стадии компиляции.
 
Конечно, не обошлось без шаманства с арифметикой указателей.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
template <class T>
class LOG2
{
  static
  constexpr size_t log2of(size_t size)
  {
    return (size > 1) ?(log2of(size >> 1) + 1) :0;
  }

public:
  static constexpr size_t value = LOG2::log2of(sizeof(T));

  static_assert
      (
        (((size_t)1 << LOG2::value) == sizeof(T)),
        "Incompatible size of type"
      );
};

template <class T>
double diamond(const T *matrix, const size_t dim)
{
  constexpr size_t
      element_log2 = LOG2<T>::value,
      element_size = sizeof(T);

  double sum = 0;

  const size_t
      m = dim >> 1,
      row_size = dim << element_log2;

  const char
      *p_upper = (const char*)matrix + (m << element_log2),
      *p_lower = (const char*)matrix + (m << element_log2);

  p_lower += (dim - 1) * row_size;

  for (size_t row_idx = 0; row_idx < m; row_idx++)
  {
    size_t element_shift = row_idx << element_log2;
    for (
          size_t i = 0;
          i < ((element_shift << 1) + element_size);
          i += element_size
        )
    {
      register
      size_t row_shift = row_idx * row_size;
      sum += *(const T*)(p_upper + row_shift - element_shift + i);
      sum += *(const T*)(p_lower - row_shift - element_shift + i);
    }
  }
  auto p = matrix;
  for (size_t i = 0; i < dim; i++) sum += p[i];
  return sum;
}

...
Рейтинг: 0 / 0
28.05.2020, 16:05
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963460
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
Надо только заменить три нижних строки на:
Код: plaintext
1.
2.
3.
4.
  const char *p_middle = (const char*)matrix + m * row_size;
  for (const char* p = p_middle; p < p_middle + row_size; p += element_size)
    sum += *(const T*)p;
  return sum;

:)
...
Рейтинг: 0 / 0
28.05.2020, 16:24
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963491
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
rdb_dev,

дело не только в регистрах.
Двигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х, время молодости Кнута
Тогда модели памяти не предусматривали понятия "пропуск кеша".
на современных процах и больших размерах блока памяти - это шторм по перезагрузке кеша
на каждой следующей операции.
...
Рейтинг: 0 / 0
28.05.2020, 17:15
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963494
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
booby
rdb_dev,

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

Кстати да! Мой алгоритм тоже этим грешит. Сейчас перепишу. Точнее ещё один даимонд_н создам.
...
Рейтинг: 0 / 0
28.05.2020, 17:25
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963510
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
boobyДвигаться с обоих концов навстречу друг другу - это алгоритмика начала 60-х

Зато ничто не мешает двигаться навстречу друг другу с разных сторон матрицы по вертикали.
На больших размерах каждая строка всё равно в линию не влезет.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
28.05.2020, 17:44
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963514
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ромбик - симметричен. И для мультипоточки к примеру гораздо оптимальнее заранее сделать некую
декомпозицию или некий план разбиения tasks на суб-таски (по аналогии с ForkJoinPool) и работать
сверху вниз везде. Да учитывая свойсвта ромбика можно предположить что у него серединка - мясная
и там цикл будет чуть дольше считать если делать не 2 а 4 потока к примеру.

Я исхожу из предпложения что каждый поток обрабатывает "трапецию".
...
Рейтинг: 0 / 0
28.05.2020, 17:54
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963520
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
вот еще немного потока сознания, навеянного алгоритмами инвертирования массива.

Пусть задача не сумму получить, а инвертировать "очень большой" массив.
Пропуск кеша неизбежен, но хочется его как-то компенсировать/минимизировать.
Тогда инвертируют блоками (включая векторизацию).
То есть, текущие края копируются в малые буферы, взаимно инвертируется содержание буферов,
а затем каждый из буферов копируется целиком блоком на свое место.
Когда в качестве буферов используются векторные регистры, векторизация получается сама-сама.

Эту идею можно приспособить для данной задачи, если уж именно с двух сторон складывать.
Можно и к одностороннему проходу пришить, с оговоркой на то, что нечетность задачи требует к себе уважения, и,
может быть, заведенияе отдельного указателя на левый или правый нечетный элемент,
с последующим самостоятельным сложением, а сам буфер сложения (четный) можно
и скользящим окном видеть для зоны сложения, с обработкой правого края начале/конце траектории движения.
Мне кажется какого-то такого рода ходы могли бы проверяться...
...
Рейтинг: 0 / 0
28.05.2020, 18:00
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963523
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
booby
rdb_dev,

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

Я доработал свой алгоритм учитывая ваши замечания. Ожидаемо на больших матрицах выигрыш в примерно 1.4 раза, на маленьких проигрыш в 1.3. Привожу оба. summ_diamond_1() и summ_diamond_1a(). Кажется второй не очень написан, но лень думать, в индексах запутался.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
Type summ_diamond_1(Type arr[Size][Size])
{
    Type res = 0;

    for (size_t i=0; i<Half; ++i)
    {
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
            res += arr[Size-i-1][j];
        }
    }

    for (size_t i=0; i<Size; ++i)
    {
        res += arr[Half][i];
    }

    return res;
}

Type summ_diamond_1a(Type arr[Size][Size])
{
    Type res = 0;

    for (size_t i=0; i<Half; ++i)
    {
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
        }
    }

    for (size_t i=0; i<=Half; ++i)
    {
        size_t const ii = Size-i-1;
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[ii][j];
        }
    }

    return res;
}
...
Рейтинг: 0 / 0
28.05.2020, 18:08
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963524
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
Кстати да! Мой алгоритм тоже этим грешит.
Нет, твой алгоритм обходит элементы строки вперёд. Это нормально! booby имел в виду мой первый алгоритм в один цикл, который я накидал только ради того, чтобы было в один цикл. :)

Дело в том, что современные процессоры Intel x86 "оформляют" доступ к данным в памяти чтением сразу 8 выровненных байт (QWORD), причём, это делает RISC'овое ядро, которое используется микрокодом CISC-обвязки. По всей видимости, ядро процессора просто не умеет пользоваться чем-либо, кроме 64 бит.
...
Рейтинг: 0 / 0
28.05.2020, 18:08
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963530
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
petrav
Кстати да! Мой алгоритм тоже этим грешит.
Нет, твой алгоритм обходит элементы строки вперёд. Это нормально! booby имел в виду мой первый алгоритм в один цикл, который я накидал только ради того, чтобы было в один цикл. :)

Строки вперёд, а столбцы на встречу. Первый алгоритм summ_diamond_1().

rdb_dev
Дело в том, что современные процессоры Intel x86 "оформляют" доступ к данным в памяти чтением сразу 8 выровненных байт (QWORD), причём, это делает RISC'овое ядро, которое используется микрокодом CISC-обвязки. По всей видимости, ядро процессора просто не умеет пользоваться чем-либо, кроме 64 бит.

А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад.
...
Рейтинг: 0 / 0
28.05.2020, 18:19
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963539
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petrav
А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад.

Я предлагаю краш-тест. Выдели 2Гига.

И просто прочитай их спереди-назад. А потом сзаду-наперед. Ясно что здесь кеш-линия уже особ роли играть не будет.
Но возможно мы не просекли еще какие-то эффекти оптимизаций?
...
Рейтинг: 0 / 0
28.05.2020, 18:40
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963590
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я наверное register с вашего позволения уберу.

Код: plaintext
1.
'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
...
Рейтинг: 0 / 0
28.05.2020, 19:48
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963593
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
А есть здесь что-то специфичное, чего не знает gcc-4.6.3 (из сборки Rtools version 2.15.0.1919 для х32)?
или специфичное для х64 (вместо х32) ?
rdb_dev

 
Benchmark
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
#include <windows.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>
#include <windows.h>

# ifndef __INLINE
#   ifdef __GNUC__
#     define __INLINE inline __attribute__((always_inline, __target__("default")))
#   endif
# endif
...
...
...
...

А то gcc ругается и сразу на шаблон void volatilize(T &r) noexcept ...
error: expected initializer before 'noexcept'
и далее очень много разных
error: attribute(target("default")) is unknown
error: attribute(target("default")) is unknown
.....
...
Рейтинг: 0 / 0
28.05.2020, 19:51
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963779
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
exp98, ещё более старый GNUC найти не получилось? Так-то уже версия 10+ :)
...
Рейтинг: 0 / 0
29.05.2020, 00:54
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963866
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад.
По всей видимости, при движении назад плохо работает предсказание чтения кэшлайнов, а 64 битный регистр приходится дважды прогружать значением, так как чтобы получить сначала старший DWORD, нужно сдвинуть всё содержимое влево на 32 бита, что приводит к потере содержимого младшего DWORD.
...
Рейтинг: 0 / 0
29.05.2020, 09:08
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963869
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
exp98
А то gcc ругается и сразу на шаблон void volatilize(T &r) noexcept ...
error: expected initializer before 'noexcept'
и далее очень много разных
error: attribute(target("default")) is unknown
error: attribute(target("default")) is unknown
.....
По-моему, встретившись в исходниках со спецификатором noexcept , становиться совершенно очевидно, что компилировать эти исходники надо с опцией компилятора -std=c++11 .

Выкиньте __target__("default")! В чём проблема?
...
Рейтинг: 0 / 0
29.05.2020, 09:17
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39963876
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
petrav
Я доработал свой алгоритм учитывая ваши замечания. Ожидаемо на больших матрицах выигрыш в примерно 1.4 раза, на маленьких проигрыш в 1.3. Привожу оба. summ_diamond_1() и summ_diamond_1a(). Кажется второй не очень написан, но лень думать, в индексах запутался.
 
На матрице 128x128 результат одного прогона очень нестабилен.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
TSC calibrating, please wait...
TSC ticks per nanosec: 2.993169

Size of matrix: 65536

diamond_ptr
===========
SUM: 68173888
Elapsed time(nsec): 9468.558974

summ_diamond_1
==============
SUM: 68173888
Elapsed time(nsec): 5334.479416

summ_diamond_1a
==============
SUM: 68165697
Elapsed time(nsec): 7664.451199

против

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
TSC calibrating, please wait...
TSC ticks per nanosec: 2.993187

Size of matrix: 65536

diamond_ptr
===========
SUM: 68173888
Elapsed time(nsec): 9606.482488

summ_diamond_1
==============
SUM: 68173888
Elapsed time(nsec): 7364.390814

summ_diamond_1a
==============
SUM: 68165697
Elapsed time(nsec): 8551.753921
...
Рейтинг: 0 / 0
29.05.2020, 09:53
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39964042
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
rdb_dev
petrav
А что будет при суммировании "назад"? Потому что summ_diamond_1a() суммирует нижнюю часть бриллианта по столбцам именно назад.
По всей видимости, при движении назад плохо работает предсказание чтения кэшлайнов, а 64 битный регистр приходится дважды прогружать значением, так как чтобы получить сначала старший DWORD, нужно сдвинуть всё содержимое влево на 32 бита, что приводит к потере содержимого младшего DWORD.

Да, вы правы. Я написал третью версию своего алгоритма summ_diamond_1b(). Только движение вперёд, никаких скачков вперёд-назад по столбцам. На больших матрицах она самая быстрая из моих алгоритмов.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
Type summ_diamond_1b(Type arr[Size][Size])
{
    Type res = 0;

    for (size_t i=0; i<Half; ++i)
    {
        for (size_t j=Half-i; j<=Half+i; ++j)
        {
            res += arr[i][j];
        }
    }

    for (size_t i=0; i<=Half; ++i)
    {
        for (size_t j=i; j<=Size-i-1; ++j)
        {
            res += arr[i+Half][j];
        }
    }

    return res;
}
...
Рейтинг: 0 / 0
29.05.2020, 13:18
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39964544
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
В общем убрал я всю ерундистику, что выше Сpp2003.
Правда и с замерами возиться не стал, использовал обычный Clock() и без потоков. Да тут и отладчика нету. Ну да, фоновыые процессы есть и отнимают ~4% времени неизвестно в какие моменты.

Компик 32x, 1 ядро, 1.6Ггц, винд-7, памяти 2 Г, но под задачку оставалось около 260 М.
Конкретно для матрицы 11К*11К-1 все три диамонда около 750мс. И матрица int32.
Для размерости 12К*12К-1 не дождался ответа. Возможно не хватило памяти.

Если интересны замеры для мелких матриц на медленном компе, приложу позднее.
...
Рейтинг: 0 / 0
30.05.2020, 23:44
| Ответить | Цитировать | Написать  
Работа с матрицей
    #39964985
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
exp98, мой бенчмарк годится только для более-менее современных процессоров с ядром Nehalem и выше, так как в более ранних ядрах TimeStampCounter тикал по частоте процессора, которая могла меняться по Intel SpeedStep.
...
Рейтинг: 0 / 0
01.06.2020, 12:48
| Ответить | Цитировать | Написать  
169 сообщений из 169, показаны все 7 страниц
  все  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Работа с матрицей
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=57&tid=2017415]:
 0ms
get settings:
 8ms
get forum list:
 12ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 30ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 153ms
get tp. blocked users:
 1ms
others: 277ms
total:  498ms
созд. / загр.: 498ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]