Форум программистов, компьютерный форум 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++ Класс для работы с матрицами
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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. если нет, то напишите что-нибудь свое. сэкономите немного памяти и, возможно, немного времени.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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 секунды
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
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.
Правда после удаления столбца остаётся мусорный байт в конце каждой строки. Но это для тебя ведь не проблема?
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 - копировать не байты а биты?
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
10.08.2013, 21:13     Структуры данных для хранения и работы с матрицами #25
Цитата Сообщение от miramentis Посмотреть сообщение
а не подскажите, каким образом memcpy можно приспособить для bool - копировать не байты а биты?
Никак. Щас пишу тебе подобный пример работы с битами без векторов. Там сложнее немного (на самом деле намного), но зато интереснее
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 21:20  [ТС]     Структуры данных для хранения и работы с матрицами #26
Цитата Сообщение от Praktolock Посмотреть сообщение
Никак. Щас пишу тебе подобный пример работы с битами без векторов. Там сложнее немного (на самом деле намного), но зато интереснее
эх.. жаль, что никак...
я пробовал использовать bitset. но, как только доходило дело до работы со строками - тут возникают сложности.
Вы меня очень заинтриговали! с нетерпением жду)
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
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 миллисекунды (что-то самому не верится). Потестируй лучше.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.08.2013, 22:07     Структуры данных для хранения и работы с матрицами #28
Цитата Сообщение от Praktolock Посмотреть сообщение
memcpy(matrix+cols*i+coltodelete, matrix+cols*i+coltodelete+1, cols-coltodelete);
Нехорошо так делать, тем более в пример ставить. Тут memove вместо memcpy должен быть.
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
10.08.2013, 22:09     Структуры данных для хранения и работы с матрицами #29
Цитата Сообщение от Toshkarik Посмотреть сообщение
Тут memove вместо memcpy должен быть.
точно =(
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 22:53  [ТС]     Структуры данных для хранения и работы с матрицами #30
Цитата Сообщение от Praktolock Посмотреть сообщение
Вот сырой вариант. Немного погонял в отладчике, вроде-бы работает как нужно, но неуверен. С матрицей 10000x10000 удаление 5000-го столбца заняло 22 миллисекунды (что-то самому не верится). Потестируй лучше.
о как! нихрена себе! спасибо большое за пример! буду осваивать

Добавлено через 54 секунды
Цитата Сообщение от Toshkarik Посмотреть сообщение
Тут memove вместо memcpy должен быть.
учту, почитаю еще и про memmove)
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
12.08.2013, 18:10  [ТС]     Структуры данных для хранения и работы с матрицами #31
Цитата Сообщение от Praktolock Посмотреть сообщение
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; //к следующей строке!
};
вот тут я немного не понял, как мы сдвигаем остаток строки.
"*pbyte2=*pbyte2>>1; //а в текущем сдвигаем всё" разве все? не один только байт?
и, на сколько я понял, мы свигаем левую часто матрицы вправо и удаленный столбец лежит "мусором" в самом левом крае матрицы?
не могли бы вы пояснить эти моменты?
извиняюсь, что туплю...
заранее спасибо
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
12.08.2013, 18:38     Структуры данных для хранения и работы с матрицами #32
Цитата Сообщение от miramentis Посмотреть сообщение
не один только байт?
все биты в текущем байте. и он (текущий) действительно один
Цитата Сообщение от miramentis Посмотреть сообщение
удаленный столбец лежит "мусором"
Да, он лежит мусором. Ну допили код, добавь туда, ну я не знаю, ну
C++
1
cols--;
что-ли например

Добавлено через 47 секунд
Я же писал, что это
Цитата Сообщение от Praktolock Посмотреть сообщение
сырой вариант
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
12.08.2013, 18:48  [ТС]     Структуры данных для хранения и работы с матрицами #33
Цитата Сообщение от Praktolock Посмотреть сообщение
все биты в текущем байте. и он (текущий) действительно один
но ведь нужно пройтись по всем байтам левее того, в котором удаляем бит?
Цитата Сообщение от Praktolock Посмотреть сообщение
Да, он лежит мусором. Ну допили код, добавь туда, ну я не знаю, ну
ну дело не в этом. дело в том, правильно или нет я понял) никто от вас ни то что не требует, но даже не просит "готовый вариант", должен же я сам хоть что-то сделать )
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
12.08.2013, 19:03     Структуры данных для хранения и работы с матрицами #34
Цитата Сообщение от miramentis Посмотреть сообщение
но ведь нужно пройтись по всем байтам?
Обрати внимание, что там вообще-то цикл
C++
1
2
3
4
5
for(int i=_coltodelete/8+1;i<bufferwidth;i++)
{
 if(*pbyte2&1)*(pbyte2-1)|=128;//сладший бит включен вкючаем старший у предыдущего
 *pbyte2=*pbyte2>>1; //а в текущем сдвигаем всё
};
Добавлено через 1 минуту
Цитата Сообщение от miramentis Посмотреть сообщение
не просит "готовый вариант", должен же я сам хоть что-то сделать )
То что я наваял, ни в коем случае не готовый вариант. Посмотри как работает мой и напиши свой, с нуля.

Добавлено через 7 минут
В общем, о мусорных битах. Мы не можем создать массив битов, поэтому мы создаем массив байтов. По моей задумке при создании матрицы в полях
C++
1
2
int rows;
int cols;
Запоминаются размеры матрицы. А в полях
C++
1
2
int bufferwidth;
int bufferheight;
размеры буфера выделенного под них. Ну и соответственно, даже безо всяких удалений мусорные биты присутствуют с вероятностью примерно 7:1, так как чтобы их не было, количество столбцов должно быть кратно 8 (для платформ оперирующих с восьмибитными байтами). То есть после удаления столбца нужно умельшить значение cols на 1(если 1 столбец удалили (с)ваш кэп).

Добавлено через 3 минуты
А мусорные биты - бог с ними, пусть будут, просто при операциях с матрицей нужно учитывать что реальный размер матрицы отличается от размера буфера, и брать его из полей rows и cols
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
12.08.2013, 19:46  [ТС]     Структуры данных для хранения и работы с матрицами #35
спасибо большое за объяснения! все ясно теперь. приступлю к написанию "своего кода с нуля" )
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
12.08.2013, 20:19     Структуры данных для хранения и работы с матрицами #36
И таки да, в цикл нужно добваить
C++
1
pbyte2++;
:-)
miramentis
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
12.08.2013, 22:00  [ТС]     Структуры данных для хранения и работы с матрицами #37
Цитата Сообщение от Praktolock Посмотреть сообщение
И таки да, в цикл нужно добваить
C++
1
pbyte2++;
:-)
я уже догадался) потому и спросил про остальные байты, что не понял, как без этой строчки код работает))

только, разве не
C++
1
pbyte2--;
?
мы же, вроде как влево от удаляемого бита идем
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2013, 05:04     Структуры данных для хранения и работы с матрицами
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
13.08.2013, 05:04     Структуры данных для хранения и работы с матрицами #38
смотря что считать за лево и что за право) Следующие столбцы находятся в байтах старше тех, в которых находятся предыдущие(в моем случае, в твоем примере может быть и наоборот).
Yandex
Объявления
13.08.2013, 05:04     Структуры данных для хранения и работы с матрицами
Ответ Создать тему
Опции темы

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