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

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

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

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

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

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

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

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

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

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

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

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

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

Добавлено через 1 минуту
В принципе, есть же масса различных специализированных библиотек для работы с матрицами, еслми не охота ничего изобретать, просто погугли немого
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 734
10.08.2013, 17:23 #21
Цитата Сообщение от miramentis Посмотреть сообщение
Тогда сложность удаления будет всего O(2n)
во-первых, никогда не пишите константы в O-обозначениях. это безграмотно.
во-вторых, сложность будет квадратичной все равно. кто вам сказал, что удаление выполняется за 1?
Complexity of vector::erase(): Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).
Добавлено через 2 минуты
moving не позволит вам удалять константно. потому я и говорил о копировании.

Добавлено через 4 минуты
с векторами вы не выиграете в скорости. вопрос только в управлении памятью. если матрица будет активно расширяться-сужаться, то лучше используйте вектор. я бы его использовал, потому как полагаю, что хуже умею работать с памятью, чем авторы STL. если нет, то напишите что-нибудь свое. сэкономите немного памяти и, возможно, немного времени.
0
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 19:55  [ТС] #22
Цитата Сообщение от Praktolock Посмотреть сообщение
Могу ошибаться, но лично мое мнение - если нужно максимальное быстродействие, то нужно все делать вручную, без использования стандартных контейнеров. И не получится сделать чтобы и работало шустро и память экономилась.
Вместо erase() у битсета можно использовать сдвиги в комбинации с операторами &. Не так уж сложно на самом деле реализовать это всё без векторов

Добавлено через 1 минуту
В принципе, есть же масса различных специализированных библиотек для работы с матрицами, еслми не охота ничего изобретать, просто погугли немого
спасибо за информацию про свиги.
что вы скажете про такой способ удалить элемент (а, точнее переместить его в хвост битсета)?
C++
1
2
3
4
    boost::dynamic_bitset<> mask(col,0ul);
    for(int i=0;i<del;i++)
        mask[i]=1;
    row=(mask.flip()&(row>>1))|(row&mask);
Добавлено через 40 минут
Цитата Сообщение от salam Посмотреть сообщение
во-первых, никогда не пишите константы в O-обозначениях. это безграмотно.
во-вторых, сложность будет квадратичной все равно. кто вам сказал, что удаление выполняется за 1?

Добавлено через 2 минуты
moving не позволит вам удалять константно. потому я и говорил о копировании.
спасибо за информацию. буду знать теперь.

Добавлено через 1 час 33 минуты
думаю, что удалять таким методом - очень и очень долго...
такой вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
std::vector< boost::dynamic_bitset<> > Matrix(row,boost::dynamic_bitset<>(col,0));
... (заполняем матрицу)
int col_new=col;
for(int i=0;i<col_new;i++)
    if(Base[i][1]!=1){
        boost::dynamic_bitset<> mask(col,0ul);
        for(int j=0;j<i;j++) mask[j]=1;
        for(int r=0;r<row;r++)
            Matrix[r]=(Matrix[r]&mask.flip())|(mask.flip()&(Matrix[r]>>1));
        i--; col_new--;
    }
при
row = 87
col = 2589

работает где-то 2 секунды
0
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 20:27 #23
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
 int rows=2500;
 int cols=2500;
 int matrixsize=rows*cols;
 unsigned char*matrix=new unsigned char[matrixsize];
 //..заполняем
 //представим что хранятся строки непрерывно одна за одной
 //строку удалить слишком легко, я не хочу это делать
 int coltodelete=5;//такой вот столбец мы хотим удалить, например
 DWORD start=_GetTickCount();
 for(int i=0;i<rows;i++)
 {
  memcpy(matrix+cols*i+coltodelete, matrix+cols*i+coltodelete+1, cols-coltodelete);
 };
 DWORD end=_GetTickCount();
 printf("\n%d ms", end-start);
 delete[]matrix;
 _getch();
}
4000x4000 8 ms.
Правда после удаления столбца остаётся мусорный байт в конце каждой строки. Но это для тебя ведь не проблема?
1
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 21:09  [ТС] #24
Цитата Сообщение от Praktolock Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
 int rows=2500;
 int cols=2500;
 int matrixsize=rows*cols;
 unsigned char*matrix=new unsigned char[matrixsize];
 //..заполняем
 //представим что хранятся строки непрерывно одна за одной
 //строку удалить слишком легко, я не хочу это делать
 int coltodelete=5;//такой вот столбец мы хотим удалить, например
 DWORD start=_GetTickCount();
 for(int i=0;i<rows;i++)
 {
  memcpy(matrix+cols*i+coltodelete, matrix+cols*i+coltodelete+1, cols-coltodelete);
 };
 DWORD end=_GetTickCount();
 printf("\n%d ms", end-start);
 delete[]matrix;
 _getch();
}
4000x4000 8 ms.
Правда после удаления столбца остаётся мусорный байт в конце каждой строки. Но это для тебя ведь не проблема?

вот за это отдельное огромное спасибо!
а не подскажите, каким образом memcpy можно приспособить для bool - копировать не байты а биты?
0
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 21:13 #25
Цитата Сообщение от miramentis Посмотреть сообщение
а не подскажите, каким образом memcpy можно приспособить для bool - копировать не байты а биты?
Никак. Щас пишу тебе подобный пример работы с битами без векторов. Там сложнее немного (на самом деле намного), но зато интереснее
0
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 21:20  [ТС] #26
Цитата Сообщение от Praktolock Посмотреть сообщение
Никак. Щас пишу тебе подобный пример работы с битами без векторов. Там сложнее немного (на самом деле намного), но зато интереснее
эх.. жаль, что никак...
я пробовал использовать bitset. но, как только доходило дело до работы со строками - тут возникают сложности.
Вы меня очень заинтриговали! с нетерпением жду)
0
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 21:55 #27
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <windows.h>
#include <stdio.h>
#include <conio.h>
 
struct STMATRIX
{
 int rows;
 int cols;
 int bufferwidth;
 int bufferheight;
 unsigned char*data;
 STMATRIX();
~STMATRIX();
 void Create(int _rows, int _cols);
 int GetBufferSize();
 void DeleteRow(int _rowtodelete);//слишком легко
 void DeleteCol(int _coltodelete);
};
 
STMATRIX::STMATRIX()
{
 //ZeroMemory(this, sizeof(this));
};
 
STMATRIX::~STMATRIX()
{
 delete[]data;
};
 
int STMATRIX::GetBufferSize()
{
 return(bufferwidth*bufferheight);
};
 
void STMATRIX::Create(int _rows, int _cols)
{
 rows=_rows;
 cols=_cols;
 bufferheight=rows;
 bufferwidth=cols/8+1;
 data=new unsigned char[GetBufferSize()];
};
 
void STMATRIX::DeleteCol(int _coltodelete)
{
 unsigned char*pbyte=data+(_coltodelete/8);
 int bitnum=_coltodelete%8;
 
 BYTE mask1=255;  //бит bitnum и все биты старше ==1
 for(int i=0;i<bitnum;i++)
 {
  mask1^=1<<i;
 };
 BYTE mask2=mask1^(1<<bitnum);//вообще это лишнее, но мне так проще будет сориентироваться
                               //такаяже маска, только бит bitnum выключен
                               //то есть помечены только сдвигаемые биты
 while(pbyte<data+GetBufferSize())
 {
  //      <-биты младше удаляемого->     <-сдвигаемые биты->
  *pbyte=    (*pbyte)&(255^mask1)     |  ((*pbyte)&mask2)>>1;//кажется так
  //тепер нужно обработать остальную часть строки сдвигая вправо все биты
  //при чем если младший бит перед сдвигом вклюен, то у предыдущего байта нужно
  //включить старший бит, ну я думаю понятно почему
  unsigned char*pbyte2=pbyte+1;
  for(int i=_coltodelete/8+1;i<bufferwidth;i++)
  {
   if(*pbyte2&1)*(pbyte2-1)|=128;//сладший бит включен вкючаем старший у предыдущего
   *pbyte2=*pbyte2>>1;           //а в текущем сдвигаем всё
  };
  pbyte+=bufferwidth;          //к следующей строке!
 };
};
 
int main()
{
 
 STMATRIX m;
 m.Create(10000, 10000);
 for(int i=0;i<m.GetBufferSize();i++)
  m.data[i]=32;
 DWORD start=_GetTickCount();
 m.DeleteCol(5000);
 DWORD end=_GetTickCount();
 printf("%d ms", end-start);
 _getch();
}
Вот сырой вариант. Немного погонял в отладчике, вроде-бы работает как нужно, но неуверен. С матрицей 10000x10000 удаление 5000-го столбца заняло 22 миллисекунды (что-то самому не верится). Потестируй лучше.
1
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
10.08.2013, 22:07 #28
Цитата Сообщение от Praktolock Посмотреть сообщение
memcpy(matrix+cols*i+coltodelete, matrix+cols*i+coltodelete+1, cols-coltodelete);
Нехорошо так делать, тем более в пример ставить. Тут memove вместо memcpy должен быть.
2
Praktolock
65 / 65 / 1
Регистрация: 29.11.2011
Сообщений: 300
10.08.2013, 22:09 #29
Цитата Сообщение от Toshkarik Посмотреть сообщение
Тут memove вместо memcpy должен быть.
точно =(
0
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 22:53  [ТС] #30
Цитата Сообщение от Praktolock Посмотреть сообщение
Вот сырой вариант. Немного погонял в отладчике, вроде-бы работает как нужно, но неуверен. С матрицей 10000x10000 удаление 5000-го столбца заняло 22 миллисекунды (что-то самому не верится). Потестируй лучше.
о как! нихрена себе! спасибо большое за пример! буду осваивать

Добавлено через 54 секунды
Цитата Сообщение от Toshkarik Посмотреть сообщение
Тут memove вместо memcpy должен быть.
учту, почитаю еще и про memmove)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2013, 22:53
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
30
Yandex
Объявления
10.08.2013, 22:53
Ответ Создать тему
Опции темы

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