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

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

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

Класс для работы с матрицами 2х2 C++
C++ динамический класс для работы матрицами
Класс для работы с матрицами C++
Класс для работы с матрицами C++
C++ Класс для работы с матрицами
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
10.08.2013, 01:33     Структуры данных для хранения и работы с матрицами #2
Цитата Сообщение от miramentis Посмотреть сообщение
Если нужно и так и так, то приходится для чего-то одного(например, удаление строк) выбирать удаление вектора
Ясно
Цитата Сообщение от miramentis Посмотреть сообщение
а для другого(удаление столбцов) - создавать новую матрицу.
Ни фига не понятно... зачем?
Может в каждой строке удалить нужный элемент и всё?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.08.2013, 08:02     Структуры данных для хранения и работы с матрицами #3
Цитата Сообщение от Croessmah Посмотреть сообщение
Ясно

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

Если столбцы идут друг за другом, то ничего это не меняет. erase может удалять промежутки. И это будет не чуть не медленнее чем удалить один столбец. Если столбцы идут не друг за другом, то тут уже посложнее, могу чуть позже предложить идею.
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
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
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
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     Структуры данных для хранения и работы с матрицами
Еще ссылки по теме:

C++ класс для работы с матрицами
C++ Библиотека для работы с матрицами
C++ Создать класс для работы с матрицами

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

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

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

Текущее время: 19:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru