Форум программистов, компьютерный форум CyberForum.ru

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

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

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

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

Доброго времени суток!
Есть матрица, у которой надо периодически удалять то столбец целиком, то строку.
Вариант "вектор векторов" дает возможность удалять либо строки, либо столбцы.
Если нужно и так и так, то приходится для чего-то одного(например, удаление строк) выбирать удаление вектора, а для другого(удаление столбцов) - создавать новую матрицу.
Собственно вопрос: существуют ли какие-то уже готовые структуры, с которыми можно осуществлять подобные операции над матрицами?
Собственно, принимаются любые варианты, лишь бы это было быстро и не тратило много памяти.
Поиск в гугле по ключевым словам, увы, ни к чему толковому не привел.
Заранее спасибо всем откликнувшимся!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт CЭксперт С++
12980 / 7292 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
10.08.2013, 01:33     Структуры данных для хранения и работы с матрицами #2
Цитата Сообщение от miramentis Посмотреть сообщение
Если нужно и так и так, то приходится для чего-то одного(например, удаление строк) выбирать удаление вектора
Ясно
Цитата Сообщение от miramentis Посмотреть сообщение
а для другого(удаление столбцов) - создавать новую матрицу.
Ни фига не понятно... зачем?
Может в каждой строке удалить нужный элемент и всё?
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
10.08.2013, 08:02     Структуры данных для хранения и работы с матрицами #3
Цитата Сообщение от Croessmah Посмотреть сообщение
Ясно

Ни фига не понятно... зачем?
Может в каждой строке удалить нужный элемент и всё?
К сожалению, тупо скопировать будет быстрее.
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);
 }
};
Быстро получилось
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
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 секунд
мало ли... как вы оцениваете сложность вашего алгоритма, любезный?
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 10:32     Структуры данных для хранения и работы с матрицами #6
Цитата Сообщение от salam Посмотреть сообщение
мало ли... как вы оцениваете сложность вашего алгоритма, любезный?
Приемлемая) Что не так?
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
10.08.2013, 11:14     Структуры данных для хранения и работы с матрицами #7
Цитата Сообщение от Praktolock Посмотреть сообщение
Приемлемая) Что не так?
Автор темы ищет наиболее быстрый способ. Первым сообщением ему предлагают некий метод М. Вторым говорят, что тупое копирование быстрее, нежели метод М. Третьим вы предлагаете метод М... Вам не кажется, что что-то не так? Вам не кажется, что прежде чем советовать, нужно узнать, что вы советуете?
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.08.2013, 12:15     Структуры данных для хранения и работы с матрицами #8
salam, что Вы подразумеваете под "копировать"? При erase будет тоже самое копирование, только не всей строки, если, конечно, это не первый элемент.
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 12:23     Структуры данных для хранения и работы с матрицами #9
Цитата Сообщение от salam Посмотреть сообщение
К сожалению, тупо скопировать будет быстрее.
Я сомневаюсь в быстрости такого варианта. Приведи хотя-бы эскиз реализации и вместе оценим что быстрее работает.
И кстати если уж на то пошло, то вектора - не самый быстрый подход.
Belfegor
Ghost
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 524
10.08.2013, 12:38     Структуры данных для хранения и работы с матрицами #10
http://www.boost.org/doc/libs/1_42_0...doc/matrix.htm
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 минуту
Еще такой момент: держать в векторах нужно именно строки. так как при последующем преобразовании матрицы можно переставлять только строки. столбцы - нельзя.
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.08.2013, 14:28     Структуры данных для хранения и работы с матрицами #12
В любом случае нужно будет перемещать size - col элементов в каждой строке ( где col это номер столбца ). За константу Вы этого никак не сделаете.

Если столбцы идут друг за другом, то ничего это не меняет. erase может удалять промежутки. И это будет не чуть не медленнее чем удалить один столбец. Если столбцы идут не друг за другом, то тут уже посложнее, могу чуть позже предложить идею.
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(), чтобы уменьшить количество лишних, ненужных вызовов функций - будет работать немного быстрее. Но цикл, который ты добавил, делает алгоритм только медленнее.
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
10.08.2013, 14:43     Структуры данных для хранения и работы с матрицами #14
Praktolock, вариант ТС медленнее. Этот цикл просто ни к чему.

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

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

Или воспользуйтесь поиском по форуму:
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 16:33     Структуры данных для хранения и работы с матрицами #20
Могу ошибаться, но лично мое мнение - если нужно максимальное быстродействие, то нужно все делать вручную, без использования стандартных контейнеров. И не получится сделать чтобы и работало шустро и память экономилась.
Вместо erase() у битсета можно использовать сдвиги в комбинации с операторами &. Не так уж сложно на самом деле реализовать это всё без векторов

Добавлено через 1 минуту
В принципе, есть же масса различных специализированных библиотек для работы с матрицами, еслми не охота ничего изобретать, просто погугли немого
Yandex
Объявления
10.08.2013, 16:33     Структуры данных для хранения и работы с матрицами
Ответ Создать тему
Опции темы

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