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

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

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

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

Организовать информационный массив для хранения данных в виде заданной структуры и заполнить его данными с клавиатуры
Информация о сотрудниках предприятия состоит из фамилии, имени, отчества,...

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

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

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

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

37
Croessmah
++Ͻ
14158 / 8083 / 1513
Регистрация: 27.09.2012
Сообщений: 19,919
Записей в блоге: 3
Завершенные тесты: 1
10.08.2013, 01:33 #2
Цитата Сообщение от miramentis Посмотреть сообщение
Если нужно и так и так, то приходится для чего-то одного(например, удаление строк) выбирать удаление вектора
Ясно
Цитата Сообщение от miramentis Посмотреть сообщение
а для другого(удаление столбцов) - создавать новую матрицу.
Ни фига не понятно... зачем?
Может в каждой строке удалить нужный элемент и всё?
0
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
10.08.2013, 08:02 #3
Цитата Сообщение от Croessmah Посмотреть сообщение
Ясно

Ни фига не понятно... зачем?
Может в каждой строке удалить нужный элемент и всё?
К сожалению, тупо скопировать будет быстрее.
0
Praktolock
71 / 71 / 18
Регистрация: 29.11.2011
Сообщений: 345
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
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
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
71 / 71 / 18
Регистрация: 29.11.2011
Сообщений: 345
10.08.2013, 10:32 #6
Цитата Сообщение от salam Посмотреть сообщение
мало ли... как вы оцениваете сложность вашего алгоритма, любезный?
Приемлемая) Что не так?
0
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
10.08.2013, 11:14 #7
Цитата Сообщение от Praktolock Посмотреть сообщение
Приемлемая) Что не так?
Автор темы ищет наиболее быстрый способ. Первым сообщением ему предлагают некий метод М. Вторым говорят, что тупое копирование быстрее, нежели метод М. Третьим вы предлагаете метод М... Вам не кажется, что что-то не так? Вам не кажется, что прежде чем советовать, нужно узнать, что вы советуете?
0
Toshkarik
1148 / 865 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
10.08.2013, 12:15 #8
salam, что Вы подразумеваете под "копировать"? При erase будет тоже самое копирование, только не всей строки, если, конечно, это не первый элемент.
0
Praktolock
71 / 71 / 18
Регистрация: 29.11.2011
Сообщений: 345
10.08.2013, 12:23 #9
Цитата Сообщение от salam Посмотреть сообщение
К сожалению, тупо скопировать будет быстрее.
Я сомневаюсь в быстрости такого варианта. Приведи хотя-бы эскиз реализации и вместе оценим что быстрее работает.
И кстати если уж на то пошло, то вектора - не самый быстрый подход.
0
Belfegor
Ghost
173 / 173 / 40
Регистрация: 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 / 1
Регистрация: 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
1148 / 865 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
10.08.2013, 14:28 #12
В любом случае нужно будет перемещать size - col элементов в каждой строке ( где col это номер столбца ). За константу Вы этого никак не сделаете.

Если столбцы идут друг за другом, то ничего это не меняет. erase может удалять промежутки. И это будет не чуть не медленнее чем удалить один столбец. Если столбцы идут не друг за другом, то тут уже посложнее, могу чуть позже предложить идею.
0
Praktolock
71 / 71 / 18
Регистрация: 29.11.2011
Сообщений: 345
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
1148 / 865 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
10.08.2013, 14:43 #14
Praktolock, вариант ТС медленнее. Этот цикл просто ни к чему.

Цитата Сообщение от Praktolock Посмотреть сообщение
можно заранее куда-нибудь запомнить size(); и begin()
С "релизными" параметрами компиляции, эти функции, я почти уверен, встроятся.
0
miramentis
3 / 0 / 1
Регистрация: 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
Praktolock
71 / 71 / 18
Регистрация: 29.11.2011
Сообщений: 345
10.08.2013, 14:44 #16
Цитата Сообщение от miramentis Посмотреть сообщение
matrix[i].begin()+stolb - будет вычисляться каждый раз.
it - будет вычисляться один раз
C++
1
matrix[i].begin()+stolb
Можно вычислить 1 раз и запомнить, зачем тебе использовать цикл для вычисления итератора?
0
miramentis
3 / 0 / 1
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 14:50  [ТС] #17
Цитата Сообщение от Praktolock Посмотреть сообщение
C++
1
matrix[i].begin()+stolb
Можно вычислить 1 раз и запомнить, зачем тебе использовать цикл для вычисления итератора?
вы правы.
но, все же, возможно ли удали столбец за О(1)?
0
Praktolock
71 / 71 / 18
Регистрация: 29.11.2011
Сообщений: 345
10.08.2013, 14:58 #18
Цитата Сообщение от miramentis Посмотреть сообщение
но, все же, возможно ли удали столбец за О(1)?
В любом случае время выполнения будет зависеть от габаритов матрицы.
0
miramentis
3 / 0 / 1
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 15:56  [ТС] #19
ясно...
а подскажите: в случае булевой матрицы логично использовать битсет, это чрезвычайно уменьшает размеры занимаемой памяти. но(на сколько мне известно) у битсетов нет метода erase() или аналога. есть ли какой-то еще способ реализовать удаление столбца в этом случае?
0
Praktolock
71 / 71 / 18
Регистрация: 29.11.2011
Сообщений: 345
10.08.2013, 16:33 #20
Могу ошибаться, но лично мое мнение - если нужно максимальное быстродействие, то нужно все делать вручную, без использования стандартных контейнеров. И не получится сделать чтобы и работало шустро и память экономилась.
Вместо erase() у битсета можно использовать сдвиги в комбинации с операторами &. Не так уж сложно на самом деле реализовать это всё без векторов

Добавлено через 1 минуту
В принципе, есть же масса различных специализированных библиотек для работы с матрицами, еслми не охота ничего изобретать, просто погугли немого
0
10.08.2013, 16:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2013, 16:33
Привет! Вот еще темы с решениями:

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

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

Перегрузка операторов для работы с матрицами
нужно перегрузить оператор + для сложения двух матриц. Всё сделал, и всё...

Создать класс для работы с матрицами
Нужно создать класс для работы с матрицами и предусмотреть функции:...


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

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

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