Транспонировать матрицу, разбив на блоки

#c #матрицы #преобразование

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

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

void transposematrixblocked(int **src, int **dst, int size) {
  for (int i = 0; i < size; i + BLOCKSIZE) {
    for (int j = 0; j < size; j + BLOCKSIZE) {
      for (int ini = 0; ini < BLOCKSIZE; ini ++) {
        for (int inj = 0; inj < BLOCKSIZE; inj ++) {
            dst[i+ini][j+inj] = src[j+inj][i+ini];
        }
      }
    }
  }
}


где я оплошала и как сделать правильно?
    

Ответы

Ответ 1

В цикле for 3-й параметр должен быть вида i += BLOCKSIZE

void transposematrixblocked(int **src, int **dst, int size) {
  for (int i = 0; i < size; i += BLOCKSIZE) {
    for (int j = 0; j < size; j += BLOCKSIZE) {
      for (int ini = 0; ini < BLOCKSIZE; ini ++) {
        for (int inj = 0; inj < BLOCKSIZE; inj ++) {
            dst[i+ini][j+inj] = src[j+inj][i+ini];
        }
      }
    }
  }
}


Ответ 2

Основная ошибка действительно была в синтаксисе - i + BLOCKSIZE, вместо i += BLOCKSIZE.

Итоговый работающий код ниже:

/* Transpose the blocked square matrix src and put the result in dst */
void transposematrixblocked(int **src, int **dst, int size) {

  for (int i = 0; i < size; i += BLOCKSIZE) {
    for (int j = 0; j < size; j += BLOCKSIZE) {
      for (int ini = i; ini < i + BLOCKSIZE; ini ++) {
        for (int inj = j; inj < j + BLOCKSIZE; inj ++) {
            dst[ini][inj] = src[inj][ini];
        }
      }
    }
  }

Транспонирование прямоугольной матрицы

#cpp #матрицы

Предположим, что у нас есть матрица размеров m * n, которая хранится в одномерном
массиве. Как ее транспонировать?
    

Ответы

Ответ 1

Транспонировать прямоугольную матрицу, сохранённую в одномерном массиве, без создания
дополнительных массивов можно с помощью следующего алгоритма.

Для примера рассмотрим прямоугольную матрицу размера 3 x 5:

     1  2  3  4  5
     6  7  8  9 10
    11 12 13 14 15


В транспонированном виде она имеет вид:

    1 6 11
    2 7 12
    3 8 13
    4 9 14
    5 10 15


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

Таким образом, для транспонирования матрицы можно действовать по следующему алгоритму: 


Если количество столбцов матрицы равно 1, стоп;
Перемещаем элементы последнего столбца текущей матрицы так, чтобы они следовали непосредственно
за элементами всех остальных столбцов текущей матрицы. При этом порядок следования
элементов последнего столбца по отношению друг к другу должен быть сохранён. Также,
порядок следования элементов в текущей матрице "без последнего столбца" по отношению
друг к другу должен быть сохранён.
Считаем, что количество столбцов в матрице уменьшилось на 1.
Переходим к п. 1.


Пример кода:

template 
void MatrixTranspose(T &matr, typename T::size_type r, typename T::size_type c)
{
    //r - кол-во строк; c - кол-во столбцов;
    if ( r <= 1 || c <= 1 )
        return;

    typedef typename T::size_type  size_type;
    typedef typename T::value_type value_type;

    size_type  ind, ind_last;
    value_type buff;

    //Позиция в массиве в которую будет перемещён текущий элемент
    //текущего последнего столбца матрицы текущего размера.
    ind_last = r * c - 2;

    while ( c > 1 )
    {

        //Перебираем элементы последнего столбца в матрице 
        //текущего размера.
        for ( size_type i = r - 2; i != size_type(-1); --i )
        {
            //Рассчитываем индекс элемента из последнего столбца, 
            //который собираемся переместить.
            ind = i * c + (c - 1);

            //Запоминаем элемент последнего столбца в буфере.
            buff = matr.at(ind);

            //Все элементы матрицы, начиная с позиции элемента,
            //следующего за сохранённым в буфере и вплоть до
            //элемента находящегося в той позиции, в которую собираемся 
            //поместить элемент, сохранённый в буфере, смещаем на 
            //одну позицию влево.
            while ( ind < ind_last )
            {
                matr.at(ind) = matr.at(ind + 1);
                ++ind;
            }

            //Сохраняем элемент из буфера в его "правильную" позицию.
            matr.at(ind_last) = buff;

            --ind_last;
        }
        --ind_last;

        //Уменьшаем кол-во столбцов в матрице, т.е. на следующем шаге 
        //будем перемещать новый "последний" столбец.
        --c;
    }
}


Ответ 2

А в чем проблема?

Элемент a[i][j] - это a[i*n+j], так что можно в цикле создавать новую транспонированную
матрицу b:

for(int i = 0; i < m; ++i)
    for(int j = 0; j < n; ++j)
         b[j*m+i] = a[i*n+j];


"По-моему, так" (с) Пух


Ответ 3

фрагмент класса Matrix: ! - перегружен как транспонировать  прямоугольную матрицу
= перегружен 

Matrix& Matrix::operator = ( const Matrix&  a)
{

    for (int count = 0; count < row; count++)
        delete[] * (arr + count);
    delete[]arr;
    row = a.row;
    col = a.col;
    arr = new double*[row];
    for (int count = 0; count < row; count++)
    *(arr + count) = new double[col];

   for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            arr[i][j] = a.arr[i][j];
    return *this;
}
Matrix& Matrix::operator ! ()
{   
    Matrix tmp(col, row);
    for (int i = 0; i < tmp.row; i++)
        for (int j = 0; j < tmp.col; j++)
        {
            tmp.arr[i][j] = arr[j][i];
    }
    *this = tmp;
    return *this;
}

Как окружить единицы их порядковыми номерами в матрице?

#cpp #массивы #алгоритм #матрицы #олимпиада

  Дан двухмерный массив целых чисел. Массив заполнен нулями и единицами.
  "Окружить" каждую единицу, заменив только 0 на порядковый номер
  единицы в массиве, считая от левого верхнего угла и далее по строкам.
  
  Пример входного потока:5 5
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
     
  
  Пример выходного потока: 
1 1 2 0 0
1 1 2 0 0
3 3 4 5 5
0 0 5 1 5
0 0 5 5 5     


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

#include 
#include 
using namespace std;
int main()
{
  int x,y,q=0;
  cin >> x >> y;
  int a[x][y];
  for (int i=0;i> a[i][j];
    }
  }
  for (int i=0;i3) lim1=3; else lim1=x;
        if (y>3) lim2=3; else lim2=y;
        for (int m=0;m

Ответы
Ответ 1

Как-то так, если я правильно понял условие.

#include 
#include 
using namespace std;
int main() {
    int x, y, q = 0;
    cin >> x >> y;
    vector> m(x, vector(y, 0));
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            cin >> m[i][j];
        }
    }
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (m[i][j] == 1) {
                q++;
                // обход подматрицы 3x3, центр которой 1
                for (int a = i - 1; a <= i + 1; a++) {
                    for (int b = j - 1; b <= j + 1; b++) {
                        // проверка границ и что элемент можно изменить
                        if (a >= 0 && a < x && b >= 0 && b < y && m[a][b] == 0) {
                            m[a][b] = q;
                        }
                    }
                }
            }
        }
    }

    for (auto& v : m) {
        for (auto& i : v) {
            cout << i << ' ';
        }
        cout << '\n';
    }
}


Ответ 2

#include 


int main()
{
    int x = 5;
    int y = 5;

    int matrix[x][y] = { {1, 0, 0, 0, 0},
                         {0, 0, 0, 0, 0},
                         {0, 0, 0, 0, 0},
                         {0, 0, 0, 1, 0},
                         {0, 0, 0, 0, 0} };

    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
        {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }

    std::cout << std::endl;

    int count = 0;
    int points[8][2] = { {-1,  1},
                         { 0,  1},
                         { 1,  1},
                         { 1,  0},
                         { 1, -1},
                         { 0, -1},
                         {-1, -1},
                         {-1,  0}};

    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
        {
            if (matrix[i][j] == 1)
            {
                ++count;
                for (auto point : points)
                {
                    int xi = i + point[0];
                    int yj = j + point[1];

                    if (xi < 0 || xi >= x)
                    {
                        continue;
                    }

                    if (yj < 0 || yj >= y)
                    {
                        continue;
                    }

                    if (matrix[xi][yj] == 0)
                    {
                        matrix[xi][yj] = count;
                    }
                }
            }
        }
    }

    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
        {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Помогите понять код: алгоритм генерации матрицы со спиралью

#python #алгоритм #матрицы

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

Задача:

Выведите таблицу размером n×n, заполненную числами от 1 до n2 по спирали, выходящей
из левого верхнего угла и закрученной по часовой стрелке

Сам код:

def zm(n):
    dx, dy = 1, 0
    x, y = 0, 0
    arr = [[None] * n for _ in range(n)]
    for i in range(1, n**2+1):
        arr[x][y] = i
        nx, ny = x+dx, y+dy
        if 0 <= nx < n and 0 <= ny < n and not arr[nx][ny]:
            x, y = nx, ny
        else:
            dx, dy = -dy, dx
            x, y = x+dx, y+dy
    for x in list(zip(*arr)):
        print(*x)

zm(int(input()))

    

Ответы

Ответ 1

# Создаётся функция, которая и будет всё делать
def zm(n):
    # Переменной dx присваивается значение 1
    # Переменной dy присваивается значение 0
    # Обычно dx и dy - это некие приращения для переменных x и y
    dx, dy = 1, 0
    # Переменным x и y присваивается значение 0
    x, y = 0, 0
    # Создаётся список списков
    # Это матрица n*n
    # Пока все её элементы - пустые (None)
    arr = [[None] * n for _ in range(n)]
    # Выполняется перебор
    # Для переменной i последовательно перебираем значения от 1 до (n-квадрат + 1)
    for i in range(1, n**2+1):
        # Элементу матрицы с координатами x и y присваивается значение i
        # Эта строчка будет присваивать последовательные натуральные числа
        # тем ячейкам, которые перебирает код чуть ниже
        arr[x][y] = i
        # Создаются временные переменные nx и ny
        # в которых вычисляются новые значения для x и y
        # для этого к старым значенииям прибавляются приращения
        nx, ny = x+dx, y+dy
        # Если всё нормально, и индекс не выскочил за пределы матрицы
        # или не наткнулся на уже занятую ячейку
        if 0 <= nx < n and 0 <= ny < n and not arr[nx][ny]:
            # то эти значения и оставляются
            x, y = nx, ny
        else:
            # а если индекс выскочил за границу матрицы
            # или наткнулся на уже занятую ячейку
            # то разворачиваемся на 90 градусов
            # путем замены приращения по x и y друг на друга
            # а минус нужен, чтобы он не ходил только вправо или вниз, 
            # а чередовал с движениями вверх или влево. 
            # Так и получается спираль 
            dx, dy = -dy, dx
            # и используем уже это изменённое движение для новых значений x и y
            x, y = x+dx, y+dy
    # После того, как перебрали все элементы, 
    # печатаем то, что получилось
    for x in list(zip(*arr)):
        print(*x)

# А здесь вся вышеописанная функция
# вызывается с аргументом, который вводит пользователь с клавиатуры
zm(int(input()))

Поворот матрицы (двумерного массива) на 90 градусов в Python с помощью zip

#python #массивы #python_3x #матрицы #zip

Как сделать поворот матрицы в одну строчку без numpy и циклов?

Например если исходная матрица

[[1, 2],
 [3, 4]]


то результирующая должна быть:

[[3, 1],
 [4, 2]]

    

Ответы

Ответ 1

Вполне себе рабочий вариант, если скорость не критична.

Но если есть требования по скорости обработки, то лучше все-таки воспользоваться NumPy.

Сравнение производительности для массива 100x100:

In [72]: a = np.random.randint(0, 99, (100, 100))

In [73]: m = a.tolist()

In [74]: a.shape
Out[74]: (100, 100)

In [75]: %timeit tuple(zip(*m[::-1]))
10000 loops, best of 3: 71 µs per loop

In [76]: %timeit np.rot90(a, 3)
The slowest run took 9.64 times longer than the fastest. This could mean that an
intermediate result is being cached.
100000 loops, best of 3: 2.63 µs per loop


Сравнение производительности для массива 1000x1000:

In [77]: a = np.random.randint(0, 99, (1000, 1000))

In [78]: m = a.tolist()

In [79]: a.shape
Out[79]: (1000, 1000)

In [80]: %timeit tuple(zip(*m[::-1]))
10 loops, best of 3: 32.6 ms per loop

In [81]: %timeit np.rot90(a, 3)
The slowest run took 7.54 times longer than the fastest. This could mean that an
intermediate result is being cached.
100000 loops, best of 3: 2.59 µs per loop


Сравнение производительности для массива 10000x10000:

In [82]: a = np.random.randint(0, 99, (10000, 10000))

In [83]: m = a.tolist()

In [84]: a.shape
Out[84]: (10000, 10000)

In [85]: %timeit tuple(zip(*m[::-1]))
1 loop, best of 3: 4.43 s per loop

In [86]: %timeit np.rot90(a, 3)
The slowest run took 11.29 times longer than the fastest. This could mean that an
intermediate result is being cached.
100000 loops, best of 3: 2.59 µs per loop


Ответ 2

​Нашел довольно элегантный способ сделать поворот матрицы в одну строчку без numpy
и циклов. В рунете ничего толкового не смог найти, может кому то поможет.
Оригинал здесь:
Линк на оригинал

rotated = zip(*original[::-1]) # Python 2
rotated = tuple(zip(*original[::-1])) # Python 3


Как это работает. 

original = [[1, 2],
            [3, 4]]


Сначала работает реверс   

 >>> original[::-1] 
    [[3, 4], [1, 2]]


И далее этот уже обернутый список передаётся функции zip()

zip([3, 4],
    [1, 2])
#    ^  ^----column 2
#    |-------column 1


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

как изогнуть изображение на bitmap

#android #bitmap #transform #матрицы

Можно ли деформировать изображение на bitmap , чтобы результат выглядел примерно так:



Методы матрицы (например setPolyToPoly() ) позволяют только растягивать и скашивать
изображение , но не изгибать
    

Ответы

Ответ 1

Оказывается у Canvas есть методы drawBitmapMesh() и drawVertices() , которые делают
именно то что нужно:

Как проще всего считать матрицу(f64) из файла на Rust?

#файлы #матрицы #rust

Содержимое файла, матрица квадратная, в первой строке после # указан размер.

#3
1.1 -0.2 0.1
0.1 -1.2 -0.2
0.2 -0.1 1.1


Примерно так я бы считал ее на Си.

double **A;
int i,j,size=0;
FILE *f=NULL;

f=fopen("input.txt","w");
fscanf(f,"#%d\n",&size);
A=(double**)malloc(size*sizeof(double*));
for(i=0;i

Ответы
Ответ 1

Перевод моего кода с Си на Rust

use std::fs::File;
use std::io::{BufRead, BufReader};

fn main() {
    // open the file
    let mut f = BufReader::new(File::open("input.txt").unwrap());

    // read the first line and extract the number from it
    let mut num_line = String::new();
    f.read_line(&mut num_line).unwrap();
    let n: usize = num_line[1..].trim().parse().unwrap();

    // preallocate the array and read the data into it
    let mut arr = vec![vec![0f64; n]; n];
    for (i, line) in f.lines().enumerate() {
        for (j, number) in line.unwrap().split(char::is_whitespace).enumerate() {
            arr[i][j] = number.trim().parse().unwrap();
        }
    }

    println!("{:?}", arr);
}


Более характерный код для Rust

use std::fs::File;
use std::io::{BufRead, BufReader};

fn main() {
    let mut f = BufReader::new(File::open("input.txt").unwrap());

    let mut num_line = String::new();
    f.read_line(&mut num_line).unwrap();
    let n: usize = num_line[1..].trim().parse().unwrap();

    let arr: Vec> = f.lines()
        .take(n)
        .map(|l| l.unwrap().split(char::is_whitespace)
             .take(n)
             .map(|number| number.parse().unwrap())
             .collect())
        .collect();

    println!("{:?}", arr);
}


Без учета размерности, указанной в первой строке

use std::fs::File;
use std::io::{BufRead, BufReader};

fn main() {
    let mut f = BufReader::new(File::open("input.txt").unwrap());

    let mut s = String::new();
    f.read_line(&mut s).unwrap();

    let arr: Vec> = f.lines()
        .map(|l| l.unwrap().split(char::is_whitespace)
             .map(|number| number.parse().unwrap())
             .collect())
        .collect();

    println!("{:?}", arr);
}

Как красиво прочитать двумерную матрицу?

#python #input #матрицы

Собственно, могу прочитать вот так: https://ideone.com/SCoCuG

def read_lines():
  try:
    line = input()
    while line:
      yield line
      line = input()
  except EOFError:
    pass

def read_matrix():
  return [[int(x) for x in line.split()] for line in read_lines()]

a = read_matrix()
print(a)

b = read_matrix()
print(b)


Но мне кажется, что это как-то не по-питоньи, и должен быть способ красивее?

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

1 2 3
4 5 6

7 8
9 0
1 2

    

Ответы

Ответ 1

мой вариант https://ideone.com/xwsY1A

import sys
from itertools import takewhile


def read_matrix():
    return [[int(x) for x in l.split()] for l in takewhile(str.strip, sys.stdin)]


a = read_matrix()
print(a)

b = read_matrix()
print(b)

Действия с элементами матрицы и ее диагональю

#python #массивы #циклы #матрицы #numpy

Добрый день! 

Вопрос: есть некий лист с элементами, например 

      X = [0.1, 0.7 , 1, 1.35]


Нужно  создать  массив, где в каждой строке элемент по порядку добавляется ко всем
остальным, причем чтобы сам этот элемент не учитывался ( первый добавляем ко второму,третьему...;
второй к первому,третьему,... и т.д. . Если просто запустить цикл (использую numpy):

   import numpy as np

   X = map(np.array,[X])
   X = [0.1, 0.5 , 1, 1.5]
   X = ( X[:,None] + X[:] )

 #Результат
 [[ 0.2   0.8   1.1   1.45]
  [ 0.8   1.4   1.7   2.05]
  [ 1.1   1.7   2.    2.35]
  [ 1.45  2.05  2.35  2.7 ]]


но диагональные элементы нужно исключить, то есть результат должен быть:

   [[  0.8   1.1   1.45]
    [ 0.8    1.7   2.05]
    [ 1.1    1.7    2.35]
    [ 1.45   2.05   2.35 ]]


Подскажите, как реализовать такое? И еще как потом найти сумму каждой строки?

А если нужно прибавить другой лист, такого же размера (например 

Y = [0.3, 0.5, 0.7, 0.9]

     (X[:,None] + X[:]) + (Y[:,None] + Y[:]) 


или 

      X[:,None] + Y[:]


как изменить код в таком случае? 
    

Ответы

Ответ 1

Я не уверен что до конца вас понял. Вот мое решение:

def f(array):
    new = [x+y for x in array for y in array if y!=x]
    return new

print(f([1, 2, 3]))


Результат:

[3, 4, 
3, 5,  
4, 5]


Делал без numpy. Но переделать будет не сложно.

UPDATE:

def for_stack(array):
    list_for_num_array = []
    for i in array:
        list_for_num_array.append([x+y for x in i for y in i if y!= x])
    return np.array(list_for_num_array)
X = np.array([[0.1, 0.7 , 1, 1.35]])
print(for_stack(X[:None]))


Результат:

[[ 0.8, 1.1, 1.45,
   0.8, 1.7, 2.05, 
   1.1, 1.7, 2.35, 
   1.45, 2.05, 2.35]]


Можно еще так:

foo = lambda array: ([j+n for i in array for x, j in enumerate(i) for y, n in enumerate(i)
if x != y])


Вариант с индексами:

def for_stack(array):
    list_for_num_array = []
    for i in array:
        list_for_num_array.append([j+n for x, j in enumerate(i) for y, n in enumerate(i)
if x != y])
    return np.array(list_for_num_array)
X = np.array([[1, 2, 2], [1, 2, 2]])
print(for_stack(X[:None]))


Результат:

[[3 3 3 4 3 4],
 [3 3 3 4 3 4]]


Еще один UPDATE:

def for_stack(array):
    list_for_num_array = []
    try:
        for i, j in enumerate(array):
                list_for_num_array.append([x+n for x, n in zip(array[i], array[i+1])])
    except IndexError:
            pass
    return np.array(list_for_num_array)
X = np.array([[0.1, 0.7 , 1, 1.35], [2, 3, 4, 5]])
print(for_stack(X[:None]))


Результат:

[[ 2.1   3.7   5.    6.35]]


Складываем каждый X[n] + Y[n].

UPD #3

Автор задавал вопрос как удалить диагональ матрицы:

arr = np.array([[1, 2, 3],
               [4, 5, 6],
               [7, 8, 9]])
foo = lambda array: np.delete(array, np.diagonal(array-1))


Результат:

[[2 3 4 6 7 8]]


Ответ 2

Можно сделать так:

In [221]: X = np.array([0.1, 0.7 , 1, 1.35])

In [222]: l = len(X)

In [223]: A = np.delete(X[:,None] + X[:], np.arange(0, l**2, l+1)).reshape(l,l-1)

In [224]: A
Out[224]:
array([[ 0.8 ,  1.1 ,  1.45],
       [ 0.8 ,  1.7 ,  2.05],
       [ 1.1 ,  1.7 ,  2.35],
       [ 1.45,  2.05,  2.35]])


найти сумму каждой строки:

In [225]: A.sum(axis=1)
Out[225]: array([ 3.35,  4.55,  5.15,  5.85])


Некоторые пояснения:

np.delete() удаляет элементы матрицы по указанным индексам. Причем по умолчанию np.delete()
сначала преобразует матрицу в одномерный (flattened) массив и соответственно ожидает
индексы для такого 1D массива:

Например удаление второго элемента диагонали по индексу (1,1) (со значением 1.4)
- для "flattened" матрицы этот элемент имеет индекс 5:

In [228]: np.delete(X[:,None] + X[:], 5)
Out[228]: array([ 0.2 ,  0.8 ,  1.1 ,  1.45,  0.8 ,  1.7 ,  2.05,  1.1 ,  1.7 , 
2.  ,  2.35,  1.45,  2.05,  2.35,  2.7 ])


np.arange(0, l**2, l+1) - вернет нам индексы диагональных элементов в одномерном
"flattened" массиве (для квадратной матрицы): 

In [229]: np.arange(0, l**2, l+1)
Out[229]: array([ 0,  5, 10, 15])


получится:

In [230]: np.delete(X[:,None] + X[:], np.arange(0, l**2, l+1))
Out[230]: array([ 0.8 ,  1.1 ,  1.45,  0.8 ,  1.7 ,  2.05,  1.1 ,  1.7 ,  2.35, 
1.45,  2.05,  2.35])


дальше преобразуем к нужной 2D матрице:

In [231]: np.delete(X[:,None] + X[:], np.arange(0, l**2, l+1)).reshape(l,l-1)
Out[231]:
array([[ 0.8 ,  1.1 ,  1.45],
       [ 0.8 ,  1.7 ,  2.05],
       [ 1.1 ,  1.7 ,  2.35],
       [ 1.45,  2.05,  2.35]])

Нахождение max() и min() в столбце CSV файла

#python #python_3x #список #матрицы #csv

Дан файловый объект .txt, в котором данные приведены как числа:


  Rosneft,07/19/06,00:00,220.32,220.32,203.03,203.95,51774,0


Таких данных около 2 тыс. и все они записаны в файле с новой строки.
Нужно найти максимальную и минимальную цену и ее дату в файле.  

file = open('file.txt') # Открыть файл
for line in file: # Пройти циклом 
    new_line1 = line.split(',') #разделить строки по запятым в new_line1
    new_file1 = new_line1[4:6] # срезать нужные строки  


И на этом логика выполнения задачи зашла в тупик. Хотелось бы понять эту логику в
примерах как с ф-цией min() и max(), так и без неё.
    

Ответы

Ответ 1

Решение без использования доп. модулей:

Файл с данными (C:\Temp\data.csv):

Rosneft,07/19/06,00:00,220.32,220.32,203.03,203.95,51774,0
Rosneft,07/20/06,00:00,230.33,230.34,230.35,230.36,56544,0
Rosneft,07/21/06,00:00,210.33,210.34,210.35,210.36,50344,0


Решение:

filename = r'C:\Temp\data.csv'

data = []
with open(filename) as f:
    for line in f:
        tmp = line.split(',')
        tmp[3:] = list(map(float, tmp[3:]))
        data.append(tmp)

def transpose(matrix):
    return list(zip(*matrix))

def get_min_idx(data, col_idx=0):
    return min(range(len(data)), key=transpose(data)[col_idx].__getitem__)

def get_max_idx(data, col_idx=0):
    return max(range(len(data)), key=transpose(data)[col_idx].__getitem__)

print('Min:\t', data[get_min_idx(data, col_idx=3)])
print('Max:\t', data[get_max_idx(data, col_idx=3)])


Результат:

Min:     ['Rosneft', '07/21/06', '00:00', 210.33, 210.34, 210.35, 210.36, 50344.0, 0.0]
Max:     ['Rosneft', '07/20/06', '00:00', 230.33, 230.34, 230.35, 230.36, 56544.0, 0.0]


Ответ 2

Для обработки табличных (2D) данных идеально подходит модуль Pandas.

Пример:

создадим тестовый файл похожей структуры, в качестве данных возьмем котирови Apple
начиная с 2001-го года (4490 строк)

import pandas as pd                             # pip install pandas
from pandas_datareader.data import DataReader   # pip install pandas-datareader

df = DataReader('AAPL', 'yahoo', '2001-01-01', '2018-11-06').reset_index()

df.to_csv('c:/temp/data.csv', index=False)


Несколько строк из файла:

Date,High,Low,Open,Close,Volume,Adj Close
2001-01-02,1.0892857313156128,1.0401785373687744,1.0625,1.0625,113078000.0,0.713999330997467
2001-01-03,1.1919642686843872,1.03125,1.0357142686843872,1.1696428060531616,204268400.0,0.7859991192817688
2001-01-04,1.3214285373687744,1.2008928060531616,1.2957571744918823,1.21875,184849000.0,0.818999171257019
2001-01-05,1.2410714626312256,1.1473214626312256,1.2098214626312256,1.1696428060531616,103089000.0,0.7859991192817688
2001-01-08,1.2131643295288086,1.1383928060531616,1.2098214626312256,1.1830357313156128,93424800.0,0.7949992418289185


Решение:

import pandas as pd

df = pd.read_csv(r'c:/temp/data.csv')


поиск строк с наименьшим и наибольшим значением в поле Adj Close:

In [27]: print(df.nsmallest(1, ['Adj Close']))
          Date      High       Low      Open     Close       Volume  Adj Close
573 2003-04-17  0.946429  0.908571  0.942857  0.937143  154064400.0   0.629759

In [28]: print(df.nlargest(1, ['Adj Close']))
           Date        High         Low        Open       Close      Volume   Adj Close
4466 2018-10-03  233.470001  229.779999  230.050003  232.070007  28654800.0  232.070007


TOP 5 значений:

In [29]: print(df.nlargest(5, ['Adj Close']))
           Date        High         Low        Open       Close      Volume   Adj Close
4466 2018-10-03  233.470001  229.779999  230.050003  232.070007  28654800.0  232.070007
4465 2018-10-02  230.000000  226.630005  227.250000  229.279999  24788200.0  229.279999
4445 2018-09-04  229.179993  226.630005  228.410004  228.360001  27390100.0  228.360001
4467 2018-10-04  232.350006  226.729996  230.779999  227.990005  32042000.0  227.990005
4444 2018-08-31  228.869995  226.000000  226.509995  227.630005  43340100.0  227.630005


Ответ 3

Логика такова:

line="Rosneft,07/19/06,00:00,220.32,220.32,203.03,203.95,51774,0"
elems=line.split(',')
date=elems[1]
prices = list(map(float,elems[3:7]))
print("На {} максимум: {}, минимум: {}".format(date, max(prices), min(prices)))


На выходе:

На 07/19/06 максимум: 220.32, минимум: 203.03

Как рассчитать матрицу SVG-преобразования по значениям rotate / translate / scale?

#svg #матрицы

У меня есть следующая последовательность трансформаций SVG:




Необходимо написать формулу matrix в соответствии с необходимыми трансформациями




Может ли кто-нибудь помочь мне сделать это?
    

Ответы

Ответ 1

В качестве примера использования matrix в SVG трансформациях привожу работы мастеров
"old school"
Эти файлы на моем ПК находятся давно. Поэтому буду благодарен тому, кто укажет ссылку
на первоисточник.   








Ещё примеры:

Example #1  

Example #2


Ответ 2

Translate(tx, ty) "перемещение" можно записать в виде матрицы: 

  1  0  tx
  0  1  ty
  0  0  1   


Scale(sx, sy) "увеличение" в виде матрицы: 

  sx  0  0
  0  sy  0
  0   0  1


Rotate(a)  "вращение" 

cos(a)  -sin(a)  0
sin(a)   cos(a)  0
0        0       1


Вращение rotate(a, cx, cy) в комбинации с перемещением  translation(-cx, cy), с последующим
перемещением назад в (cx, cy), достигается записью матрицы: 

cos(a)  -sin(a)  -cx × cos(a) + cy × sin(a) + cx
sin(a)   cos(a)  -cx × sin(a) - cy × cos(a) + cy
0        0       1


Если вы просто умножите это на матрицу translation, вы получите:

cos(a)  -sin(a)  -cx × cos(a) + cy × sin(a) + cx + tx
sin(a)   cos(a)  -cx × sin(a) - cy × cos(a) + cy + ty
0        0       1


Что соответствует матрице SVG-преобразования записью в одну строку: 

(cos(a), sin(a), -sin(a), cos(a), -cx × cos(a) + cy × sin(a) + cx + tx, -cx × sin(a)
- cy × cos(a) + cy + ty)   

В вашем случае это: матрица (0,866, -0,5 0,5 0,866 8,84 58,35).   

Если вы включите преобразование масштаба (sx, sy), матрица будет:

(sx × cos(a), sy × sin(a), -sx × sin(a), sy × cos(a), (-cx × cos(a) + cy × sin(a)
+ cx) × sx + tx, (-cx × sin(a) - cy × cos(a) + cy) × sy + ty)


Обратите внимание, что это предполагает, что вы делаете преобразования в том порядке,
в котором вы их написали.

Примечание переводчика:

Связанный ответ от @Grundy 

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

Полезные ссылки для более углубленного изучения вопроса:  

Затерянная документация или transform: matrix3d   

Матрица преобразований 

Transformation matrix

Как правильно умножить матрицу на другую матрицу в нескольких потоках?

#java #алгоритм #математика #матрицы

Моя задача такая. Мне нужно параллельно на 8 потоках умножить матрицу 200x248 на
матрицу 248x333. В интернете я нашел простой пример умножения двух матриц 4x4 на 4
потоках, но я не совсем понимаю логику разделения этой задачи между потоками. Почему
у каждого потока разные границы циклов и как они вообще образовываются? Почему в каждом
потоке аж 3 цикла, а не 2? Можете мне объяснить алгоритм, чтобы я мог по его аналогии
сделать умножение огромных матриц на 8 потоках?

Вот часть этого кода (там еще есть ввод данных с файла и вывод результата в другой
файл, графический интерфейс и другое, но это не столь важно в этом вопросе).

Инициализация статических полей:

public static int[][] a;
public static int[][] b;
public static int[][] c;


Где-то в main создаются и запускаются потоки:

            c = new int[a.length][b[0].length];

            Thread1 thread1 = new Thread1();
            Thread2 thread2 = new Thread2();
            Thread3 thread3 = new Thread3();
            Thread4 thread4 = new Thread4();

            thread1.start();
            thread2.start();
            thread3.start();
            thread4.start();

            try {
                thread1.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            try {
                thread2.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            try {
                thread3.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            try {
                thread4.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }


Код четырех потоков:

public static class Thread1 extends Thread {

    @Override
    public void run() {
        int m = a.length;
        int n = b[0].length;
        int k = (a.length) / 4;

        for (int i = 0; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l < b.length; l++) {
                    c[i][j] = c[i][j] + a[i][l] * b[l][j];
                }
            }
        }
    }
}

public static class Thread2 extends Thread {

    @Override
    public void run() {
        int m = a.length;
        int n = b[0].length;
        int k = (a.length) / 2 + 1;
        int s = ((a.length) / 4) + 1;

        for (int i = s; i < k; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l < b.length; l++) {
                    c[i][j] = c[i][j] + a[i][l] * b[l][j];
                }
            }
        }
    }
}

public static class Thread3 extends Thread {

    @Override
    public void run() {
        int m = a.length;
        int n = b[0].length;
        int k = ((3 * (a.length)) / 4) + 1;
        int s = (a.length) / 2 + 1;

        for (int i = s; i < k; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l < b.length; l++) {
                    c[i][j] = c[i][j] + a[i][l] * b[l][j];
                }
            }
        }
    }
}

public static class Thread4 extends Thread {

    @Override
    public void run() {
        int m = a.length;
        int n = b[0].length;
        int k = ((3 * (a.length)) / 4) + 1;


        for (int i = k; i < m; i++) {
            for (int j = 0; j < n; j++) {
          for (int l = 0; l < b.length; l++) {
                        c[i][j] = c[i][j] + a[i][l] * b[l][j];
                    }
                }
            }
        }
    }

    

Ответы

Ответ 1

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

import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;

/** Поток-вычислитель группы ячеек матрицы. */
class MultiplierThread extends Thread
{
    /** Первая (левая) матрица. */
    private final int[][] firstMatrix;
    /** Вторая (правая) матрица. */
    private final int[][] secondMatrix;
    /** Результирующая матрица. */
    private final int[][] resultMatrix;
    /** Начальный индекс. */
    private final int firstIndex;
    /** Конечный индекс. */
    private final int lastIndex;
    /** Число членов суммы при вычислении значения ячейки. */
    private final int sumLength;

    /**
     * @param firstMatrix  Первая (левая) матрица.
     * @param secondMatrix Вторая (правая) матрица.
     * @param resultMatrix Результирующая матрица.
     * @param firstIndex   Начальный индекс (ячейка с этим индексом вычисляется).
     * @param lastIndex    Конечный индекс (ячейка с этим индексом не вычисляется).
     */
    public MultiplierThread(final int[][] firstMatrix,
                            final int[][] secondMatrix,
                            final int[][] resultMatrix,
                            final int firstIndex,
                            final int lastIndex)
    {
        this.firstMatrix  = firstMatrix;
        this.secondMatrix = secondMatrix;
        this.resultMatrix = resultMatrix;
        this.firstIndex   = firstIndex;
        this.lastIndex    = lastIndex;

        sumLength = secondMatrix.length;
    }

    /**Вычисление значения в одной ячейке.
     *
     * @param row Номер строки ячейки.
     * @param col Номер столбца ячейки.
     */
    private void calcValue(final int row, final int col)
    {
        int sum = 0;
        for (int i = 0; i < sumLength; ++i)
            sum += firstMatrix[row][i] * secondMatrix[i][col];
        resultMatrix[row][col] = sum;
    }

    /** Рабочая функция потока. */
    @Override
    public void run()
    {
        System.out.println("Thread " + getName() + " started. Calculating cells from
" + firstIndex + " to " + lastIndex + "...");

        final int colCount = secondMatrix[0].length;  // Число столбцов результирующей
матрицы.
        for (int index = firstIndex; index < lastIndex; ++index)
            calcValue(index / colCount, index % colCount);

        System.out.println("Thread " + getName() + " finished.");
    }
}

class Main
{
    /** Заполнение матрицы случайными числами.
     *
     * @param matrix Заполняемая матрица.
     */
    private static void randomMatrix(final int[][] matrix)
    {
        final Random random = new Random();  // Генератор случайных чисел.

        for (int row = 0; row < matrix.length; ++row)           // Цикл по строкам
матрицы.
            for (int col = 0; col < matrix[row].length; ++col)  // Цикл по столбцам
матрицы.
                matrix[row][col] = random.nextInt(100);         // Случайное число
от 0 до 100.
    }

    //

    /** Вывод матрицы в файл.
     * Производится выравнивание значений для лучшего восприятия.
     *
     * @param fileWriter Объект, представляющий собой файл для записи.
     * @param matrix Выводимая матрица.
     * @throws IOException
     */
    private static void printMatrix(final FileWriter fileWriter,
                                    final int[][] matrix) throws IOException
    {
        boolean hasNegative = false;  // Признак наличия в матрице отрицательных чисел.
        int     maxValue    = 0;      // Максимальное по модулю число в матрице.

        // Вычисляем максимальное по модулю число в матрице и проверяем на наличие
отрицательных чисел.
        for (final int[] row : matrix) {  // Цикл по строкам матрицы.
            for (final int element : row) {  // Цикл по столбцам матрицы.
                int temp = element;
                if (element < 0) {
                    hasNegative = true;
                    temp = -temp;
                }
                if (temp > maxValue)
                    maxValue = temp;
            }
        }

        // Вычисление длины позиции под число.
        int len = Integer.toString(maxValue).length() + 1;  // Одно знакоместо под
разделитель (пробел).
        if (hasNegative)
            ++len;  // Если есть отрицательные, добавляем знакоместо под минус.

        // Построение строки формата.
        final String formatString = "%" + len + "d";

        // Вывод элементов матрицы в файл.
        for (final int[] row : matrix) {  // Цикл по строкам матрицы.
            for (final int element : row)  // Цикл по столбцам матрицы.
                fileWriter.write(String.format(formatString, element));

            fileWriter.write("\n");  // Разделяем строки матрицы переводом строки.
        }
    }

    /**
     * Вывод трёх матриц в файл. Файл будет перезаписан.
     *
     * @param fileName     Имя файла для вывода.
     * @param firstMatrix  Первая матрица.
     * @param secondMatrix Вторая матрица.
     * @param resultMatrix Результирующая матрица.
     */
    private static void printAllMatrix(final String fileName,
                                       final int[][] firstMatrix,
                                       final int[][] secondMatrix,
                                       final int[][] resultMatrix)
    {
        try (final FileWriter fileWriter = new FileWriter(fileName, false)) {
            fileWriter.write("First matrix:\n");
            printMatrix(fileWriter, firstMatrix);

            fileWriter.write("\nSecond matrix:\n");
            printMatrix(fileWriter, secondMatrix);

            fileWriter.write("\nResult matrix:\n");
            printMatrix(fileWriter, resultMatrix);
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }

    /** Однопоточное умножение матриц.
     *
     * @param firstMatrix  Первая матрица.
     * @param secondMatrix Вторая матрица.
     * @return Результирующая матрица.
     */
    private static int[][] multiplyMatrix(final int[][] firstMatrix,
                                          final int[][] secondMatrix)
    {
        final int rowCount = firstMatrix.length;             // Число строк результирующей
матрицы.
        final int colCount = secondMatrix[0].length;         // Число столбцов результирующей
матрицы.
        final int sumLength = secondMatrix.length;           // Число членов суммы
при вычислении значения ячейки.
        final int[][] result = new int[rowCount][colCount];  // Результирующая матрица.

        for (int row = 0; row < rowCount; ++row) {  // Цикл по строкам матрицы.
            for (int col = 0; col < colCount; ++col) {  // Цикл по столбцам матрицы.
                int sum = 0;
                for (int i = 0; i < sumLength; ++i)
                    sum += firstMatrix[row][i] * secondMatrix[i][col];
                result[row][col] = sum;
            }
        }

        return result;
    }

    /** Многопоточное умножение матриц.
     *
     * @param firstMatrix  Первая (левая) матрица.
     * @param secondMatrix Вторая (правая) матрица.
     * @param threadCount Число потоков.
     * @return Результирующая матрица.
     */
    private static int[][] multiplyMatrixMT(final int[][] firstMatrix,
                                            final int[][] secondMatrix,
                                            int threadCount)
    {
        assert threadCount > 0;

        final int rowCount = firstMatrix.length;             // Число строк результирующей
матрицы.
        final int colCount = secondMatrix[0].length;         // Число столбцов результирующей
матрицы.
        final int[][] result = new int[rowCount][colCount];  // Результирующая матрица.

        final int cellsForThread = (rowCount * colCount) / threadCount;  // Число
вычисляемых ячеек на поток.
        int firstIndex = 0;  // Индекс первой вычисляемой ячейки.
        final MultiplierThread[] multiplierThreads = new MultiplierThread[threadCount];
 // Массив потоков.

        // Создание и запуск потоков.
        for (int threadIndex = threadCount - 1; threadIndex >= 0; --threadIndex) {
            int lastIndex = firstIndex + cellsForThread;  // Индекс последней вычисляемой
ячейки.
            if (threadIndex == 0) {
                /* Один из потоков должен будет вычислить не только свой блок ячеек,
                   но и остаток, если число ячеек не делится нацело на число потоков. */
                lastIndex = rowCount * colCount;
            }
            multiplierThreads[threadIndex] = new MultiplierThread(firstMatrix, secondMatrix,
result, firstIndex, lastIndex);
            multiplierThreads[threadIndex].start();
            firstIndex = lastIndex;
        }

        // Ожидание завершения потоков.
        try {
            for (final MultiplierThread multiplierThread : multiplierThreads)
                multiplierThread.join();
        }
        catch (InterruptedException e) {
            e.printStackTrace();
        }

        return result;
    }

    /** Число строк первой матрицы. */
    final static int FIRST_MATRIX_ROWS  = 1000;
    /** Число столбцов первой матрицы. */
    final static int FIRST_MATRIX_COLS  = 1000;
    /** Число строк второй матрицы (должно совпадать с числом столбцов первой матрицы). */
    final static int SECOND_MATRIX_ROWS = FIRST_MATRIX_COLS;
    /** Число столбцов второй матрицы. */
    final static int SECOND_MATRIX_COLS = 1000;

    public static void main(String[] args)
    {
        final int[][] firstMatrix  = new int[FIRST_MATRIX_ROWS][FIRST_MATRIX_COLS];
   // Первая (левая) матрица.
        final int[][] secondMatrix = new int[SECOND_MATRIX_ROWS][SECOND_MATRIX_COLS];
 // Вторая (правая) матрица.

        randomMatrix(firstMatrix);
        randomMatrix(secondMatrix);

        final int[][] resultMatrixMT = multiplyMatrixMT(firstMatrix, secondMatrix,
Runtime.getRuntime().availableProcessors());

        // Проверка многопоточных вычислений с помощью однопоточных.
        final int[][] resultMatrix = multiplyMatrix(firstMatrix, secondMatrix);

        for (int row = 0; row < FIRST_MATRIX_ROWS; ++row) {
            for (int col = 0; col < SECOND_MATRIX_COLS; ++col) {
                if (resultMatrixMT[row][col] != resultMatrix[row][col]) {
                    System.out.println("Error in multithreaded calculation!");
                    return;
                }
            }
        }

        printAllMatrix("Matrix.txt", firstMatrix, secondMatrix, resultMatrixMT);
    }
}


P.S. Среди особенностей - форматированный вывод матриц в файл и автоматическое определение
размера матриц в функциях-вычислителях. В качестве бонуса - однопоточное вычисление
и контроль многопоточного результата с помощью однопоточного.


Ответ 2

Вот накидал рабочий код:

    public static class CalcThread extends Thread {
        private int startRow, endRow;
        private int[][] a, b, result;
        private int n;

        public CalcThread(int[][] a, int[][] b, int[][] result, int startRow, int
endRow) {
            this.a = a;
            this.b = b;
            this.result = result;
            this.startRow = startRow;
            this.endRow = endRow;
            this.n = b.length;
        }

        @Override
        public void run() {
            System.out.println("Считаю со строки " + startRow + " до строки " + endRow
+ " включительно");
            for (int row = startRow; row <= endRow ; row++) {
                for (int col = 0; col < result[row].length; col++) {
                    result[row][col] = calcSingleValue(row, col);
                }
            }
        }

        private int calcSingleValue(int row, int col) {
            int c = 0;
            for (int i = 0; i < n; i++) {
                c += a[row][i] * b[i][col];
            }
            return c;
        }

    }

    public static int[][] multiply(int[][] a, int[][] b, int threadsCount) {
        //проверки
        if (a == null || a.length == 0 || a[0] == null || a[0].length == 0) {
            throw new IllegalArgumentException("a");
        }
        if (b == null || b.length == 0 || b[0] == null || b[0].length == 0) {
            throw new IllegalArgumentException("b");
        }
        if (a[0].length != b.length) {
            throw new IllegalArgumentException("матрицы не согласованы");
        }
        //определяем размеры результирующей матрицы
        int m = a.length;
        int q = b[0].length;
        int[][] result = new int[m][q];
        //если количество потоков больше чем количество строк - уменьшим кол-во потоков
        if (threadsCount > m) {
            threadsCount = m;
        }
        //посчитаем сколько строк результирующей матрицы будет считать каждый поток
        int count = m / threadsCount;
        int additional = m % threadsCount; //если не делится на threadsCount, то
добавим к первому потоку
        //создаем и запускаем потоки
        Thread[] threads = new Thread[threadsCount];
        int start = 0;
        for (int i = 0; i < threadsCount; i++) {
            int cnt = ((i == 0) ? count + additional : count);
            threads[i] = new CalcThread(a, b, result, start, start + cnt - 1);
            start += cnt;
            threads[i].start();
        }
        //ждем завершения
        try {
            for (Thread thread : threads) {
                thread.join();
            }
        } catch (InterruptedException e) {
            System.out.println("Interrupted");
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] a = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
        int[][] b = {{2, 1, 2, 1, 2, 1, 2}, {1, 2, 1, 2, 1, 2, 1}, {2, 1, 2, 1, 2,
1, 2}, {1, 2, 1, 2, 1, 2, 1}};
        int[][] c = multiply(a, b, 8);

        for (int[] ints : c) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
}

Найти матрицу-множитель в произведении матриц при известном результате

#python #математика #numpy #матрицы #деление

Имеется произведение матриц a*b=c. Причем произведение матриц - это результат numpy.dot,
а не поэлементное произведение. Известны матрицы a и c. Требуется найти матрицу b.
Каким образом это можно сделать в python, не прибегая к решению системы уравнений с
множеством неизвестных? Если просто делить numpy.matrix, то получается совсем не тот
результат.

Вот пример:

import numpy as np
a = np.matrix([[ 1.,  2.],[ 3.,  4.]])
c = np.matrix([[ 2.],[ 1.]])
c/a
Out[201]: 
matrix([[ 2.        ,  1.        ],
        [ 0.33333333,  0.25      ]])


Решил письменно обратную задачу, получил ответ:

([[-3. ],
  [ 2.5]])


Проверяем:

b= np.matrix([[-3. ],[ 2.5]])
a*b
Out[207]: 
matrix([[ 2.],
        [ 1.]])


Если переводить в ndarray, то то же самое получается:

c.getA()/a.getA()
Out[213]: 
array([[ 2.        ,  1.        ],
       [ 0.33333333,  0.25      ]])

    

Ответы

Ответ 1

Воспользуйтесь обратной (inverse) матрицей:

In [224]: b = np.linalg.inv(a) * c

In [225]: b
Out[225]:
matrix([[-3. ],
        [ 2.5]])


Это будет работать для объектов типа numpy.matrix.
Если a и c - объекты типа numpy.ndarray, то нужно использовать dot product (как в
ответе @MarianD):

In [8]: np.linalg.inv(a).dot(c)
Out[8]:
matrix([[-3. ],
        [ 2.5]])


PS использование dot product (операции умножения матриц как это понимается в линейной
алгебре) - является более универсальным решением, т.к. оно правильно работает как для
объектов типа numpy.matrix так и для numpy.ndarray:

In [10]: np.linalg.inv(a.getA()).dot(c.getA())
Out[10]:
array([[-3. ],
       [ 2.5]])




Пояснение:

A * B = C  | умножим обе части на A-1

умножение матриц операция некомутативная, т.е.  A * B != B * A, поэтому чтобы получилась
единичная матрица будем делать так:

A-1 * A * B = A-1 * C

=>

B = A-1 * C

UPDATE: во многих случаях гораздо выгоднее решить систему уравнений, по сравнению
с нахождением обратной матрицы (спасибо @jfs за подсказку):

In [328]: b = np.linalg.solve(a, c)

In [329]: b
Out[329]:
matrix([[-3. ],
        [ 2.5]])


Вот некоторые из преимуществ подхода решения системы линейных уравнений по сравнению
с нахождением обратной матрицы:


решение СЛУ (системы линейных уравнений) дает более точные численные результаты по
сравнению с методами, использующими перемножение матриц. Пример скалярного произведения
возвращающего неточный результат
при использовании разреженных матриц (sparse matrices) есть методы, позволяющие найти
решение и возвращающие также разреженные матрицы (если это возможно), что существенно
экономит использование памяти. Обратная же матрица в общем случае не будет разреженной
и может занимать на несколько порядков больше памяти. Например разреженная матрица
размерности 1.000.000 x 1.000.000 у которой всего 1.000.000 ненулевых элементов (например
единичная матрица или такая, у которой в каждой строке/столбце по одному ненулевому
элементу) легко поместится в памяти и займет приблизительно: объем памяти необходимый
для данного типа (np.int8, np.int16, np.int32, np.int64, np.float64, etc.) плюс небольшие
накладные расходы (информация о позиции ненулевых элементов в разреженной матрице).
Если преобразовать такую матрицу в обычную или найти обратную ей то в результате надо
будет хранить в памяти уже 1.000.000 x 1.000.000 = 1.000.000.000.000 (один триллион
элементов, или около 3.6 TiB для 32-битных элементов)


Ответ 2

Произведением матриц очевидно во вашем случае не разумеется код

a * b


что в numpy значит просто произведение элементов на согласных позициях, 

но математическое произведение (скалярное произведение строк матрицы a со столбцами
матрицы b, что в numpy записывают как 

np.dot(a, b)


или - более просто -

a.dot(b)


(что нужно использовать для проверки результата).

Подобно этому, простое деление

c / a


делением элемент по элементу (с автоматическим расширением матрицы c на 2 x 2) на
согласных позициях - и это опять нет тем, что вам требуется).



Из-за того решение вашего задания маленько сложнее:

Tак как a * b = c влечет за собой (после произведения обух страниц уравнения слева
на а-1) b = а-1 * c. Это в numpy записывают как

np.dot(np.linalg.inv(a), c)


или - более просто -

np.linalg.inv(a).dot(c)


что результат вашего задания.

Медленное умножение матриц 1024х1024

#кэширование #матрицы #любой_язык

Почему матрицы размеров 1025x1025, 1023x1023 перемножаются быстрее матриц 1024x1024
стандартным алгоритмом?
    

Ответы

Ответ 1

В комментарий не влезет, но это не ответ. Это именно комментарий.

Написал для проверки (см. ниже). Обалдел, ибо у меня, скомпилированное VC++ 2017,
таки дало:

1023: 2106433
1024: 7664347
1025: 2106884


При отключенной оптимизации эффект выражен меньше:

1023: 9592402
1024: 11608342
1025: 9480406


Это для 64-разрядного приложения. 32-разрядное, впрочем, почти такое же.

1023: 2910957
1024: 7729545
1025: 2192236


"А я что? сама в шоке!" (с) Анекдот про пограничную собаку...

Вот код.

#include 
#include 
#include 
#include 
#include 

using namespace std;

class muTimer
{
    using Clock = std::chrono::high_resolution_clock;
    bool active = false;
    Clock::duration   duration_;
    Clock::time_point start_ = Clock::now(), stop_ = Clock::now();

    muTimer(const muTimer&)             = delete;
    muTimer& operator=(const muTimer&)  = delete;
public:
    using ns       = std::chrono::nanoseconds;
    using mks      = std::chrono::microseconds;
    using ms       = std::chrono::milliseconds;
    muTimer() { reset(); start(); }
    ~muTimer() = default;
    muTimer& reset()
    {
        duration_ = std::chrono::nanoseconds(0);
        active    = false;
        return *this;
    }
    muTimer& start()
    {
        if (!active)
        {
            start_ = Clock::now();
            active = true;
        }
        return *this;
    }
    muTimer& stop()
    {
        if (active)
        {
            stop_      = Clock::now();
            duration_ += stop_ - start_;
            active     = false;
        }
        return *this;
    }
    template
        unsigned long long duration()
    {
        return static_cast
            (std::chrono::duration_cast(stop_-start_).count());
    }
};


double m1024_1[1024][1024], m1024_2[1024][1024], m1024_3[1024][1024];
double m1025_1[1025][1025], m1025_2[1025][1025], m1025_3[1025][1025];
double m1023_1[1023][1023], m1023_2[1023][1023], m1023_3[1023][1023];

int main(int argc, const char * argv[])
{
    for(int i = 0; i < 1024; ++i)
        for(int j = 0; j < 1024; ++j)
        {
            m1024_1[i][j] = rand();
            m1024_2[i][j] = rand();
        }
    for(int i = 0; i < 1025; ++i)
        for(int j = 0; j < 1025; ++j)
        {
            m1025_1[i][j] = rand();
            m1025_2[i][j] = rand();
        }
    for(int i = 0; i < 1023; ++i)
        for(int j = 0; j < 1023; ++j)
        {
            m1023_1[i][j] = rand();
            m1023_2[i][j] = rand();
        }

    {
        muTimer mt;
        for(int i = 0; i < 1023; ++i)
            for(int j = 0; j < 1023; ++j)
            {
                double s = 0.0;
                for(int k = 0; k < 1023; ++k)
                {
                    s += m1023_1[i][k]*m1023_2[k][j];
                }
                m1023_3[i][j] = s;
            }
        mt.stop();
        cout << "1023: " << mt.duration() << endl;
    }
    {
        muTimer mt;
        for(int i = 0; i < 1024; ++i)
            for(int j = 0; j < 1024; ++j)
            {
                double s = 0.0;
                for(int k = 0; k < 1024; ++k)
                {
                    s += m1024_1[i][k]*m1024_2[k][j];
                }
                m1024_3[i][j] = s;
            }
        mt.stop();
        cout << "1024: " << mt.duration() << endl;
    }
    {
        muTimer mt;
        for(int i = 0; i < 1025; ++i)
            for(int j = 0; j < 1025; ++j)
            {
                double s = 0.0;
                for(int k = 0; k < 1025; ++k)
                {
                    s += m1025_1[i][k]*m1025_2[k][j];
                }
                m1025_3[i][j] = s;
            }
        mt.stop();
        cout << "1025: " << mt.duration() << endl;
    }

}


При 1024 ассемблерный код отличается:

Вот основной код для 1024:

; 104  :                 for(int k = 0; k < 1024; ++k)
; 105  :                 {
; 106  :                     s += m1024_1[i][k]*m1024_2[k][j];

    movsd   xmm1, QWORD PTR [rcx-8192]
    mulsd   xmm1, QWORD PTR [rax-8]
    movsd   xmm0, QWORD PTR [rax]
    mulsd   xmm0, QWORD PTR [rcx]
    addsd   xmm1, xmm2
    movaps  xmm2, xmm1
    movsd   xmm1, QWORD PTR [rcx+8192]
    mulsd   xmm1, QWORD PTR [rax+8]
    addsd   xmm2, xmm0
    movsd   xmm0, QWORD PTR [rcx+16384]
    mulsd   xmm0, QWORD PTR [rax+16]
    addsd   xmm2, xmm1
    movsd   xmm1, QWORD PTR [rcx+24576]
    mulsd   xmm1, QWORD PTR [rax+24]
    addsd   xmm2, xmm0
    movsd   xmm0, QWORD PTR [rcx+32768]
    mulsd   xmm0, QWORD PTR [rax+32]
    addsd   xmm2, xmm1
    movsd   xmm1, QWORD PTR [rcx+40960]
    mulsd   xmm1, QWORD PTR [rax+40]
    addsd   xmm2, xmm0
    movsd   xmm0, QWORD PTR [rcx+49152]
    mulsd   xmm0, QWORD PTR [rax+48]
    add rcx, 65536              ; 00010000H
    add rax, 64                 ; 00000040H
    addsd   xmm2, xmm1
    addsd   xmm2, xmm0
    sub r8, 1
    jne $LL37@main


А вот - для 1023:

; 89   :                 for(int k = 0; k < 1023; ++k)
; 90   :                 {
; 91   :                     s += m1023_1[i][k]*m1023_2[k][j];

    movsd   xmm1, QWORD PTR [rcx-8184]
    mulsd   xmm1, QWORD PTR [rax-8]
    movsd   xmm0, QWORD PTR [rcx]
    mulsd   xmm0, QWORD PTR [rax]
    addsd   xmm1, xmm2
    movaps  xmm2, xmm1
    movsd   xmm1, QWORD PTR [rcx+8184]
    mulsd   xmm1, QWORD PTR [rax+8]
    addsd   xmm2, xmm0
    add rax, 24
    add rcx, 24552              ; 00005fe8H
    addsd   xmm2, xmm1
    sub rdx, 1
    jne SHORT $LL28@main


Объяснений не даю, сам хочу услышать :)

P.S. Вносим единственное изменение:

double m1024_1[1025][1025], m1024_2[1025][1025], m1024_3[1025][1025];
double m1025_1[1025][1025], m1025_2[1025][1025], m1025_3[1025][1025];
double m1023_1[1025][1025], m1023_2[1025][1025], m1023_3[1025][1025];


Имеем:

1023: 1973593
1024: 1983533
1025: 1981114


Ответ 2

Решил и свою лепту внести на java.


  3615298956
   4363341525
   4608966672


Новые ответы считает
Считало где-то по 10 минут

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package time;

/**
 *
 * @author milan
 */
public class Time {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        System.out.println(i1023());
        System.out.println(i1024());
        System.out.println(i1025());



    }

    public static long i1023() {
        int mas1023_1[][] = new int[1023][1023];
        int mas1023_2[][] = new int[1023][1023];

        long ans[] = new long[10];
        long time1023 = 0;
        for (int k = 0; k < 10; k++) {
            long start;
            long finish;
            int[][] res = new int[1023][1023];

            start = System.nanoTime();
            for (int i = 0; i < 1023; i++) {
                for (int j = 0; j < 1023; j++) {
                    for (int l = 0; l < 1023; l++) {
                        res[i][j] += mas1023_1[i][l] * mas1023_2[l][j];
                    }
                }
            }
            finish = System.nanoTime();
            time1023 = finish - start;
            //System.out.println(time1023);
            ans[k] = time1023;
        }
        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += ans[i];
        }
        sum = sum / 10;
        return sum;
    }

    public static long i1024() {
        int mas1024_1[][] = new int[1024][1024];
        int mas1024_2[][] = new int[1024][1024];
        long ans[] = new long[10];
        long time1024 = 0;
        for (int k = 0; k < 10; k++) {
            long start;
            long finish;
            int[][] res = new int[1024][1024];

            start = System.nanoTime();
            for (int i = 0; i < 1024; i++) {
                for (int j = 0; j < 1024; j++) {
                    for (int l = 0; l < 1024; l++) {
                        res[i][j] += mas1024_1[i][l] * mas1024_2[l][j];
                    }
                }
            }
            finish = System.nanoTime();
            time1024 = finish - start;
            //System.out.println(time1024);
            ans[k] = time1024;
        }
        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += ans[i];
        }
        sum = sum / 10;
        return sum;
    }

    public static long i1025() {
        int mas1025_1[][] = new int[1025][1025];
        int mas1025_2[][] = new int[1025][1025];
        long ans[] = new long[10];
        long time1025 = 0;
        for (int k = 0; k < 10; k++) {
            long start;
            long finish;
            int[][] res = new int[1025][1025];
            start = System.nanoTime();
            for (int i = 0; i < 1025; i++) {
                for (int j = 0; j < 1025; j++) {
                    for (int l = 0; l < 1025; l++) {
                        res[i][j] += mas1025_1[i][l] * mas1025_2[l][j];
                    }
                }
            }
            finish = System.nanoTime();
            time1025 = finish - start;
            //System.out.println(time1025);
            ans[k] = time1025;
        }
        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += ans[i];
        }
        sum = sum / 10;
        return sum;
    }
}

Как найти все матрицы состоящие из заданного числа элементов, с ненулевым определителем?

#математика #комбинаторика #матрицы

Имеется матрица 7×7. Элементами матрицы может быть любой из 33 элементов. Если мы
перебором всевозможные матрицы, то количество комбинаций будет равно  33^49. Это очень
долго для компьютера. Но мне не нужны все матрицы, мне нужны лишь те, которые имеет
ненулевой определитель. Какие свойства матриц можно использовать, чтобы ускорить поиск
неворожденных матриц? Ведь количество таких матриц ограничено в сравнении с общим количеством
комбинаций. Какие будет предложения?
    

Ответы

Ответ 1

В постановке ОП задача нерешаема.

Если 33 ненулевых элемента не равны попарно, то существует 33^7 = 42618442977 вариантов
их размещения на главной диагонали, .
Если это не смущает, можно разместить те же элементы в любой из 7! = 5040 "ладейных"
расстановок (по одному на строку и по одному на столбец).
И такие коэффициенты можно добавлять многократно (например, использовать свойства
блочных матриц).

UPD. 


Если задать элементы ниже главной диагонали нулевыми, элементы главной диагонали
- ненулевыми, а элементы выше главной диагонали - произвольными, то определитель будет
ненулевым (и равным произведению элементов главной диагонали). 
Если нуль использовать нельзя, то можно заполнить матрицу ниже главной диагонали
одним и тем же элементом, главную диагональ - неравными ему элементами, а матрицу выше
главной диагонали - произвольно. В этом случае определитель будет произведением разностей
элементов главной диагонали и "нижнего" элемента.
Перестановка строк и столбцов матрицы может изменить только знак её определителя.
Таким образом, количество ненулевых определителей не меньше, чем
33 * 327 * 3321 * 7! = 5040 * 3322 * 327 ≈ 4 * 1047

Магический квадрат

#python #массивы #матрицы

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

Мой код:

import random
p=0
n=int(input('Введите четное число: '))
matrix=[[random.randrange(10) for i in range(n)] for j in range(n)]
for elem in matrix:
    print(elem)
for k in range(n):    #Проверяю равны ли суммы всех элементов строк между собой
    for l in range(k+1,n):
         if sum(matrix[k])==sum(matrix[l]):
            p+=1    #если предыдущая строка равна по сумме элементов следущей, то
переменную p увеличиваю на единицу, чтобы потом если p==n (если p равняется кол-ву
строк, то потом проверять на сумму элементов по столбцам матрицы)


Но как проверить равны ли суммы элементов столбцов матрицы? Подскажите пожалуйста.
    

Ответы

Ответ 1

Нет нужды сравнивать все строки со всеми, чтобы выяснить, что все суммы равны. Достаточно
найти первую сумму и сравнивать остальные с ней.

first = sum(matrix[0])
for k in range(1, n):
    if sum(matrix[0]) != first:
        return False


Для столбцов - просто посчитать их суммы и так же сравнить с эталоном

for k in range(0, n):
    if sum([row[k] for row in matrix]) != first:
        return False


Ответ 2

Я бы, наверное, сделал так:

import numpy as np

def ismagic(a):
    if np.array_equal(np.unique(a.sum(axis=1)),np.unique(a.sum(axis=0))):
        return True
    else:
        return False


Проверяем:

a = np.matrix([[1, 2], [4, 3]])
print(ismagic(a))
b = np.ones((5,5))
print(ismagic(b))
c = np.matrix([[2,7,6],[9,5,1],[4,3,8]])
print(ismagic(c))
d = np.matrix([[17,24,1,8,15],[23,5,7,14,16],[4,6,13,20,22],[10,12,19,21,3],[11,18,25,2,9]])
print(ismagic(d))


На выходе:

False
True
True
True


Ответ 3

Решение с использованием модуля Numpy для проверки на настоящий магический квадрат
(с проверкой сумм главной и побочной диагоналей):

import numpy as np

a = np.array([[2,7,6],[9,5,1],[4,3,8]])




In [90]: a
Out[90]:
array([[2, 7, 6],
       [9, 5, 1],
       [4, 3, 8]])

In [91]: a.sum(axis=0)
Out[91]: array([15, 15, 15])

In [92]: a.sum(axis=1)
Out[92]: array([15, 15, 15])

In [93]: np.diag(a).sum()
Out[93]: 15

In [94]: np.diag(np.flipr(a)).sum()
Out[94]: 15




решение:

In [98]: s = np.diag(a).sum()

In [99]: (s == np.diag(np.flipr(a)).sum()) and (a.sum(axis=0) == s).all() and (a.sum(axis=1)
== s).all()
Out[99]: True


Ответ 4

In [12]: import numpy as np

In [13]: matrix = [
    ...: [1, 2, 3, 4, 5],
    ...: [8, 9, 5, 4, 5],
    ...: [0, 1, 2, 3, 5],
    ...: [7, 8, 9, 4, 2]
    ...: ]

In [14]: main_sum = sum(matrix[0]) * 2

In [15]: def foo(matrix):
    ...:     tran = np.array(matrix).T
    ...:     for i, j in zip(matrix, tran):
    ...:         if sum(i) + sum(j) != main_sum:
    ...:             return False
    ...:     return True
    ...:
    ...:

In [16]: foo(matrix)
Out[16]: False

In [17]: matrix = [[2, 7, 6], [9, 5, 1], [4, 3, 8]] # magic

In [18]: foo(matrix)
Out[18]: True



  Работает на матрицах где кол-во строк равно кол-ву столбцов.

Работа с изображениями в D

У меня есть двумерный массив булевых значений (bool[][]), и мне нужно записать этот массив в BMP. То есть, к примеру, есть такая матрица:
[0 0 0 0 1] [0 0 1 1 1] [0 0 0 0 1] [0 0 0 0 1] [0 0 0 0 1]
и мне нужно каким-то образом получить из нее .bmp файл с изображением цифры "1". То бишь, true — черный пиксель, false — белый. Как можно это сделать в D?

Ответ

Для записи BMP можете воспользоваться, например, библиотекой arsd, из которой потребуется модули bmp и color
import arsd.bmp, arsd.color;
void main() { ubyte[][] image = [ [ 0, 0, 0, 0, 0, 0, 0, 1], [ 0, 0, 0, 0, 0, 0, 1, 1], [ 0, 0, 0, 0, 0, 1, 1, 1], [ 0, 0, 0, 0, 1, 1, 1, 1], [ 0, 0, 0, 1, 1, 1, 1, 1], [ 0, 0, 1, 1, 1, 1, 1, 1], [ 0, 1, 1, 1, 1, 1, 1, 1], [ 1, 1, 1, 1, 1, 1, 1, 1], [ 0, 1, 0, 1, 0, 1, 0, 1], ];
auto col = [Color.black, Color.green];
auto w = image[0][].length; auto h = image[].length;
ubyte[] data;
for (int j=0; j auto img = new TrueColorImage(w, h, data); writeBmp(img, "result.bmp"); }

C++: как задать размерность двумерного вектора в конструкторе класса

Class Matrix { int dimension; vector> matrix; public: Matrix(int dimension); ... }
Matrix::Matrix(int dimension) { this->dimension = dimension; }
В методе Matrix::Matrix(int dimension) хочется задать размерность двумерного вектора
dimension x dimension
но тот способ, которым делал это я, не работает
matrix.reserve(dimension); for (int i = 0; i < dimension; ++i) { matrix[i].reserve(dimension); }

Ответ

vector::reserve только резервирует память под элементы, но не выделяет их.
Используйте vector::resize
Matrix::Matrix(int dimension) : dimension(dimension), matrix(dimension) { for (auto& row : matrix) { row.resize(dimension); } }

Математика. Определитель матрицы n-го порядка

Помогите с задачей, не могу до конца додумать, что куда и как. Спасибо большое заранее!
Для начала я попытался изменить вторую строчку с помощью первой, у меня вышло:
x x+h x+2h ... x+(n-1)h 0 2x+h x+2h ... x+(n-1)h 0 -x x ... 0 ............................. 0 0 0 ... x
Если здесь что-то ещё менять то, -x из 3ей строчки не уходит, а я хочу привести матрицу к виду:
x x x x 0 x x x 0 0 x x 0 0 0 x
Чтобы можно было разложить на миноры по 1 эл-ту.
Далее я попытался вторую оставить без изменения, а 3ью строчку изменить с помощью первой, но там тоже получилась белиберда и далекая к истине матрица. Я думал может можно при помощи какого-нибудь столбца изменить другой, но тем самым больше проблем создам.
В принципе тут ещё одна идея - изменять вторую с помощью первой, третью с помощью второй и т.д., а потом выносить из каждой строчки множитель (x+h), но остаются единицы и нужному виду не придти. :(

Ответ

Ну, если я не ошибся...

Update Доказывается методом матиндукции. Для каких-нибудь 1, 2, 3 - легко посчитать.
Затем берем nxn и идем по последнему столбцу. Имеем минор для (x+nh) - получается простая матрица с одной диагональю из (-x)n, а для x в нижнем правом углу - наша формула для n. Умножаем, суммируем - все получается как надо :)
Update2

Транспонировать матрицу, разбив на блоки

Требуется ускорить транспонирование большой матрицы, элементы размещены в памяти последовательно. Ускорить нужно за счет обработки матрицы блоками, чтобы из кэша необходимые куски памяти не успевали стираться.
Проблема возникла в написании кода самого транспонирования - выполнение затыкается и ничего не работает. Ниже сам кусок кода
void transposematrixblocked(int **src, int **dst, int size) { for (int i = 0; i < size; i + BLOCKSIZE) { for (int j = 0; j < size; j + BLOCKSIZE) { for (int ini = 0; ini < BLOCKSIZE; ini ++) { for (int inj = 0; inj < BLOCKSIZE; inj ++) { dst[i+ini][j+inj] = src[j+inj][i+ini]; } } } } }
где я оплошала и как сделать правильно?

Ответ

В цикле for 3-й параметр должен быть вида i += BLOCKSIZE
void transposematrixblocked(int **src, int **dst, int size) { for (int i = 0; i < size; i += BLOCKSIZE) { for (int j = 0; j < size; j += BLOCKSIZE) { for (int ini = 0; ini < BLOCKSIZE; ini ++) { for (int inj = 0; inj < BLOCKSIZE; inj ++) { dst[i+ini][j+inj] = src[j+inj][i+ini]; } } } } }