Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
#1

Структуры данных для хранения и работы с матрицами - C++

10.08.2013, 01:31. Просмотров 1801. Ответов 37
Метки нет (Все метки)

Доброго времени суток!
Есть матрица, у которой надо периодически удалять то столбец целиком, то строку.
Вариант "вектор векторов" дает возможность удалять либо строки, либо столбцы.
Если нужно и так и так, то приходится для чего-то одного(например, удаление строк) выбирать удаление вектора, а для другого(удаление столбцов) - создавать новую матрицу.
Собственно вопрос: существуют ли какие-то уже готовые структуры, с которыми можно осуществлять подобные операции над матрицами?
Собственно, принимаются любые варианты, лишь бы это было быстро и не тратило много памяти.
Поиск в гугле по ключевым словам, увы, ни к чему толковому не привел.
Заранее спасибо всем откликнувшимся!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2013, 01:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Структуры данных для хранения и работы с матрицами (C++):

Выбор контейнера для хранения структуры - C++
Доброе время суток! Ребят нужна помочишь при выборе контейнера для хранения структуры, точнее трех структур! Первая, (если кому...

Библиотека для работы с матрицами - C++
Пожалуйста, подскажите библиотеку, где можно находить определитель матрицы. И какой функцией если можно))

Конструкторы для работы с матрицами - C++
Доброго времени суток, многоуважаемые форумчане. Ситуация такая: преподаватель дал задание - создать класс матриц, НО предварительно...

Класс для работы с матрицами - C++
Разработать класс обеспечивающий представление матрицы произвольного размера с возможностью изменения числа строки столбцов,вывода на экран...

Класс для работы с матрицами - C++
Разработать класс обеспечивающий представление матрицы произвольного размера с возможностью изменения числа строки столбцов,вывода на экран...

Класс для работы с матрицами - C++
Неплохая библиотека :) . Люди, у кого есть нервы скачать весь сайт и в архиве прислать ко мне на мыло :) (Библиотека хорошая, а на качалку...

37
Croessmah
Ушел
Эксперт CЭксперт С++
13554 / 7705 / 872
Регистрация: 27.09.2012
Сообщений: 19,006
Записей в блоге: 3
Завершенные тесты: 1
10.08.2013, 01:33 #2
Цитата Сообщение от miramentis Посмотреть сообщение
Если нужно и так и так, то приходится для чего-то одного(например, удаление строк) выбирать удаление вектора
Ясно
Цитата Сообщение от miramentis Посмотреть сообщение
а для другого(удаление столбцов) - создавать новую матрицу.
Ни фига не понятно... зачем?
Может в каждой строке удалить нужный элемент и всё?
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.08.2013, 08:02 #3
Цитата Сообщение от Croessmah Посмотреть сообщение
Ясно

Ни фига не понятно... зачем?
Может в каждой строке удалить нужный элемент и всё?
К сожалению, тупо скопировать будет быстрее.
0
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 09:12 #4
C++
1
2
3
4
5
6
7
void udalit_stolbec(vector<vector<double>>*matrix, int stolb)
{
 for(int i=0;i<matrix->size();i++)
 {
  matrix[i].erase(matrix[i].begin()+stolb);
 }
};
Быстро получилось
1
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.08.2013, 10:28 #5
Цитата Сообщение от Praktolock Посмотреть сообщение
C++
1
2
3
4
5
6
7
void udalit_stolbec(vector<vector<double>>*matrix, int stolb)
{
 for(int i=0;i<matrix->size();i++)
 {
  matrix[i].erase(matrix[i].begin()+stolb);
 }
};
Быстро получилось
профессиональный совет проктолога... палиц вверхъ

Добавлено через 56 секунд
мало ли... как вы оцениваете сложность вашего алгоритма, любезный?
0
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 10:32 #6
Цитата Сообщение от salam Посмотреть сообщение
мало ли... как вы оцениваете сложность вашего алгоритма, любезный?
Приемлемая) Что не так?
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.08.2013, 11:14 #7
Цитата Сообщение от Praktolock Посмотреть сообщение
Приемлемая) Что не так?
Автор темы ищет наиболее быстрый способ. Первым сообщением ему предлагают некий метод М. Вторым говорят, что тупое копирование быстрее, нежели метод М. Третьим вы предлагаете метод М... Вам не кажется, что что-то не так? Вам не кажется, что прежде чем советовать, нужно узнать, что вы советуете?
0
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
10.08.2013, 12:15 #8
salam, что Вы подразумеваете под "копировать"? При erase будет тоже самое копирование, только не всей строки, если, конечно, это не первый элемент.
0
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 12:23 #9
Цитата Сообщение от salam Посмотреть сообщение
К сожалению, тупо скопировать будет быстрее.
Я сомневаюсь в быстрости такого варианта. Приведи хотя-бы эскиз реализации и вместе оценим что быстрее работает.
И кстати если уж на то пошло, то вектора - не самый быстрый подход.
0
Belfegor
Ghost
173 / 173 / 6
Регистрация: 16.09.2012
Сообщений: 526
10.08.2013, 12:38 #10
http://www.boost.org/doc/libs/1_42_0/libs/numeric/ublas/doc/matrix.htm
0
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 14:12  [ТС] #11
Цитата Сообщение от Praktolock Посмотреть сообщение
C++
1
2
3
4
5
6
7
void udalit_stolbec(vector<vector<double>>*matrix, int stolb)
{
 for(int i=0;i<matrix->size();i++)
 {
  matrix[i].erase(matrix[i].begin()+stolb);
 }
};
Быстро получилось
При квадратной матрице(для простоты примера):
в худшем случае такое удаление будет иметь сложность O(n^2)

дело в том, что matrix[i].begin() - очевидно, итератор и если stolb = n,то итератору придется пробежаться по всем столбцам.

Логично было бы сперва пробежаться по столбцам и удалять уже:
C++
1
2
std::vector<int>::iterator it = matrix.begin();
for (int i=0; i<stolb; i++) it++;
а дальше чуть подправленный ваш код:
C++
1
2
3
for(int i=0;i<matrix.size();i++){
  matrix[i].erase(it);
}
Тогда сложность удаления будет всего O(2n)
Но, все, же это гораздо раз больше, чем O(1)

Добавлено через 4 минуты
Цитата Сообщение от Croessmah Посмотреть сообщение
Ясно

Ни фига не понятно... зачем?
Может в каждой строке удалить нужный элемент и всё?
Прошу прощения, забыл написать с самого начала, а потом форум не дает уже править:

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

Добавлено через 1 минуту
Еще такой момент: держать в векторах нужно именно строки. так как при последующем преобразовании матрицы можно переставлять только строки. столбцы - нельзя.
0
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
10.08.2013, 14:28 #12
В любом случае нужно будет перемещать size - col элементов в каждой строке ( где col это номер столбца ). За константу Вы этого никак не сделаете.

Если столбцы идут друг за другом, то ничего это не меняет. erase может удалять промежутки. И это будет не чуть не медленнее чем удалить один столбец. Если столбцы идут не друг за другом, то тут уже посложнее, могу чуть позже предложить идею.
0
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 14:36 #13
Я не понимаю, чем такая конструкция:
C++
1
2
std::vector<int>::iterator it = matrix.begin();
for (int i=0; i<stolb; i++) it++;
Лучше такой конструкции:
C++
1
matrix[i].begin()+stolb
Те же яйца только в профиль. Сложность не уменьшится ни разу. Если не терпится оптимизировать, можно заранее куда-нибудь запомнить size(); и begin(), чтобы уменьшить количество лишних, ненужных вызовов функций - будет работать немного быстрее. Но цикл, который ты добавил, делает алгоритм только медленнее.
0
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
10.08.2013, 14:43 #14
Praktolock, вариант ТС медленнее. Этот цикл просто ни к чему.

Цитата Сообщение от Praktolock Посмотреть сообщение
можно заранее куда-нибудь запомнить size(); и begin()
С "релизными" параметрами компиляции, эти функции, я почти уверен, встроятся.
0
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 14:43  [ТС] #15
Цитата Сообщение от Praktolock Посмотреть сообщение
Я не понимаю, чем такая конструкция:
C++
1
2
std::vector<int>::iterator it = matrix.begin();
for (int i=0; i<stolb; i++) it++;
Лучше такой конструкции:
C++
1
matrix[i].begin()+stolb
Те же яйца только в профиль. Сложность не уменьшится ни разу. Если не терпится оптимизировать, можно заранее куда-нибудь запомнить size(); и begin(), чтобы уменьшить количество лишних, ненужных вызовов функций - будет работать немного быстрее. Но цикл, который ты добавил, делает алгоритм только медленнее.
да. согласен, вы правы. я перепутал с другой конструкцией
0
10.08.2013, 14:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2013, 14:43
Привет! Вот еще темы с ответами:

Класс для работы с матрицами 2х2 - C++
Нужна помощь. Задание звучит так : разработать класс для работы с матрицами 2х2 . Прога уже почти написана , код работает , но вот...

Создать класс для работы с матрицами - C++
Нужно создать класс для работы с матрицами и предусмотреть функции: -добавления(+); -умножения двух матриц(*); -транспонирования...

Перегрузка операторов для работы с матрицами - C++
нужно перегрузить оператор + для сложения двух матриц. Всё сделал, и всё работет. class overload { private: int** arr; ...

Создать динамический класс для работы с матрицами - C++
Доброго времени суток. Нужно создать динамический класс для работы с массивами. Вопрос как его создать? В книгах Дейтела и Лафоре...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru