Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.81/21: Рейтинг темы: голосов - 21, средняя оценка - 4.81
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25

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

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

Студворк — интернет-сервис помощи студентам
Доброго времени суток!
Есть матрица, у которой надо периодически удалять то столбец целиком, то строку.
Вариант "вектор векторов" дает возможность удалять либо строки, либо столбцы.
Если нужно и так и так, то приходится для чего-то одного(например, удаление строк) выбирать удаление вектора, а для другого(удаление столбцов) - создавать новую матрицу.
Собственно вопрос: существуют ли какие-то уже готовые структуры, с которыми можно осуществлять подобные операции над матрицами?
Собственно, принимаются любые варианты, лишь бы это было быстро и не тратило много памяти.
Поиск в гугле по ключевым словам, увы, ни к чему толковому не привел.
Заранее спасибо всем откликнувшимся!
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
10.08.2013, 01:31
Ответы с готовыми решениями:

Организация структуры для хранения данных
Всем Привет! Может быть ошибся веткой... Есть БД в которой разные поля по типу, int, String, bool и т.д. Нужно организовать...

Опишите переменную Tovar для хранения структуры данных
На картинке схема.

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

37
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
10.08.2013, 17:23
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от 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
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 19:55  [ТС]
Цитата Сообщение от 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
73 / 73 / 18
Регистрация: 29.11.2011
Сообщений: 356
10.08.2013, 20:27
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
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 21:09  [ТС]
Цитата Сообщение от 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
73 / 73 / 18
Регистрация: 29.11.2011
Сообщений: 356
10.08.2013, 21:13
Цитата Сообщение от miramentis Посмотреть сообщение
а не подскажите, каким образом memcpy можно приспособить для bool - копировать не байты а биты?
Никак. Щас пишу тебе подобный пример работы с битами без векторов. Там сложнее немного (на самом деле намного), но зато интереснее
0
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 21:20  [ТС]
Цитата Сообщение от Praktolock Посмотреть сообщение
Никак. Щас пишу тебе подобный пример работы с битами без векторов. Там сложнее немного (на самом деле намного), но зато интереснее
эх.. жаль, что никак...
я пробовал использовать bitset. но, как только доходило дело до работы со строками - тут возникают сложности.
Вы меня очень заинтриговали! с нетерпением жду)
0
 Аватар для Praktolock
73 / 73 / 18
Регистрация: 29.11.2011
Сообщений: 356
10.08.2013, 21:55
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
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
10.08.2013, 22:07
Цитата Сообщение от Praktolock Посмотреть сообщение
memcpy(matrix+cols*i+coltodelete, matrix+cols*i+coltodelete+1, cols-coltodelete);
Нехорошо так делать, тем более в пример ставить. Тут memove вместо memcpy должен быть.
2
 Аватар для Praktolock
73 / 73 / 18
Регистрация: 29.11.2011
Сообщений: 356
10.08.2013, 22:09
Цитата Сообщение от Toshkarik Посмотреть сообщение
Тут memove вместо memcpy должен быть.
точно =(
0
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
10.08.2013, 22:53  [ТС]
Цитата Сообщение от Praktolock Посмотреть сообщение
Вот сырой вариант. Немного погонял в отладчике, вроде-бы работает как нужно, но неуверен. С матрицей 10000x10000 удаление 5000-го столбца заняло 22 миллисекунды (что-то самому не верится). Потестируй лучше.
о как! нихрена себе! спасибо большое за пример! буду осваивать

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

Добавлено через 47 секунд
Я же писал, что это
Цитата Сообщение от Praktolock Посмотреть сообщение
сырой вариант
0
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
12.08.2013, 18:48  [ТС]
Цитата Сообщение от Praktolock Посмотреть сообщение
все биты в текущем байте. и он (текущий) действительно один
но ведь нужно пройтись по всем байтам левее того, в котором удаляем бит?
Цитата Сообщение от Praktolock Посмотреть сообщение
Да, он лежит мусором. Ну допили код, добавь туда, ну я не знаю, ну
ну дело не в этом. дело в том, правильно или нет я понял) никто от вас ни то что не требует, но даже не просит "готовый вариант", должен же я сам хоть что-то сделать )
0
 Аватар для Praktolock
73 / 73 / 18
Регистрация: 29.11.2011
Сообщений: 356
12.08.2013, 19:03
Цитата Сообщение от 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
1
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
12.08.2013, 19:46  [ТС]
спасибо большое за объяснения! все ясно теперь. приступлю к написанию "своего кода с нуля" )
0
 Аватар для Praktolock
73 / 73 / 18
Регистрация: 29.11.2011
Сообщений: 356
12.08.2013, 20:19
И таки да, в цикл нужно добваить
C++
1
pbyte2++;
:-)
0
3 / 0 / 0
Регистрация: 04.08.2013
Сообщений: 25
12.08.2013, 22:00  [ТС]
Цитата Сообщение от Praktolock Посмотреть сообщение
И таки да, в цикл нужно добваить
C++
1
pbyte2++;
:-)
я уже догадался) потому и спросил про остальные байты, что не понял, как без этой строчки код работает))

только, разве не
C++
1
pbyte2--;
?
мы же, вроде как влево от удаляемого бита идем
0
 Аватар для Praktolock
73 / 73 / 18
Регистрация: 29.11.2011
Сообщений: 356
13.08.2013, 05:04
смотря что считать за лево и что за право) Следующие столбцы находятся в байтах старше тех, в которых находятся предыдущие(в моем случае, в твоем примере может быть и наоборот).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
13.08.2013, 05:04

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

Создать запись для хранения. Для хранения данных использовать стек. Для группировки данных использовать очередь
Решил выложить свои лабораторные работы 1-10 за первый курс, первого семестра (01.09.2019-10.01.2020). Искренне надеюсь, что они...

Структуры данных для работы со звуком
Где можно найти информацию по структурам и методам работы со звуком, а именно, как организовать работу с аудипортами компьютера. Или...

Использование данных из структуры для работы с time.h
Всем привет, гляньте плиз приведенный код. В двух словах суть программки такова - создаем файл с данными(массив структур), заполняем,...

Класс: Разработать класс для работы с матрицами(операции над матрицами)...
Добрый вечер, хочу попросить о помощи с отловом проблемы. Сама задача: разработать класс для работы с матрицами(операции над...


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

Или воспользуйтесь поиском по форуму:
38
Ответ Создать тему
Новые блоги и статьи
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
Транслитерация текста с кириллицы на латиницу (вариант №1)
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru