| Schumi |
| Отправлено: 06.02.2005, 20:46 |
|
Машинист паровоза
Группа: Участник
Сообщений: 206
|
Представьте у меня есть большой объем информации в виде массива, где каждый элемент может принимать одно из трех значений.
Сейчас у меня этот массив сделан статически.
Хочу выделять память динамически. Но здесь возникает проблема
Представьте я объявляю char **Arr; потом выделяю память как надо:сперва строки,потом для каждой строки — столбцы. Все хорошо, но возникает необходимость удалять строки — с этим проблем нет.
А вот когда меняется число стоблцов — мне для каждой строки нужно будет снова выделять память под новый массив и для каждой строки копировать из исходного информацию побайтно. И это получится долго.
А можно целыми блоками копировать память?
К примеру есть:
| CODE |
char *Source=new char[100];
//потом чем-то заполняю Source информацией
// вариант 1
char *Dest=new char[200];
// ??????? нужно самым быстрым способом скопировать в первые 100
байт Dest содержимое Source, и сам Source удалить ?????????
// вариант 2
char *Dest=new char[50];
// аналогичный вариант
|
|
|
| Георгий |
| Отправлено: 06.02.2005, 23:01 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
можно попробовать использовать захват памяти с запасом — например в строке 13 элементов, а памяти захвачено на 20. это даст выигрышь при частых операциях добавления/удаления одного элемента
или использовать список блоков, например, по 15 элементов тогда, если в блоке не использовано ни одного элемента он удаляется из списка. выигрышь при частых добавлениях/удалениях нескольних элементов. проигрыш в скорости доступа — надает в N/(2L) раз где N число элементов L — размер блока
или использовать 2х уровневую адресацию в списках блоков — список блоков указателей на блоки.тогда индекс элемента / размер блока = номеру элемента хранящего указатель на блок, тогда со скоростью доступа будет так: N/(S*L) где S размер блока указателей на блоки, но чуть чуть замедляются операциидобавления столбцов — в худшем случае в 2 раза в среднем на 1+1/S раз
оценить что именно использовать поможет статистика — если
узнать примерное соотношение числа операций:
чтение элементов
запись элементов
удаление строк (и по сколько строк удаляется)
удаление столбцов (и по сколько строк удаляется)
аналогично про добавление
то будет видно что лучше из предложенных конструкций |
|
| olegenty |
| Отправлено: 07.02.2005, 07:58 |
|
Ветеран
Группа: Модератор
Сообщений: 2412
|
vector< vector < char>>
|
|
| Георгий |
| Отправлено: 07.02.2005, 12:21 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
| QUOTE (olegenty @ 07/02/2005, 09:00) | | vector< vector < char > > |
Возможно я вопрос не понял, но вроде спрашивали как эффективно организовать 2х мерную таблицу, с частыми операциями вставки, удаления строк и столбцов, чтением и записью отдельных элементов.
и чтоб памяти мало занимала и работала быстро. |
|
| Schumi |
| Отправлено: 07.02.2005, 19:18 |
|
Машинист паровоза
Группа: Участник
Сообщений: 206
|
Понимаете, мне не столь важно, как оптимально я использую память,а как быстро я с ней работаю.
Отсуда такой вопрос. Какой самый быстрый способ,чтобы:
1) скопировать один массив целиком в другой;
2) заполнить целиком массив некоторым значением;
|
|
| HKarel |
| Отправлено: 08.02.2005, 00:15 |
|
Не зарегистрирован
|
Сдается мне, что конструкция vector< vector < char>> будет не очень эфффективной, т.к. в какие-то моменты будут происходить значительные траты времени на перераспределение памяти, да и вставка элементов в "середину" будет приводить к проблемам. Возможно, больше подойдет вариант list< list< char>>, но у него свои недостатки: доступ к элементам можно осуществить только через итераторы, что не очень быстро. С моей стороны вот какое предложение: у меня есть темплит TList< T> — это аналог делфевого TList-a, если оставишь мыло — накидаю маленький примерчик, мне интересно посмореть как он будет работать с большими объемами. |
|
| Schumi |
| Отправлено: 08.02.2005, 08:05 |
|
Машинист паровоза
Группа: Участник
Сообщений: 206
|
Давай. Почтовый ящик: shyl@mail.ru
|
|
| Konstantine |
| Отправлено: 08.02.2005, 09:08 |
|
Мастер участка
Группа: Модератор
Сообщений: 545
|
| QUOTE (Schumi @ 07/02/2005, 20:20) | ...мне не столь важно, как оптимально я использую память,а как быстро я с ней работаю...
|
самые быстрые метод при этом:
1) выделение памяти в пару раз больше чем нада (чтоб меньше перераспределять)
2) для копирования данных использовать COPYMEMORY и подобные... эти макросы используют прямые инструкци процессора => быстрая работа
P.S.: но всё же интересно, что это за код такой и чего такого он сссчитает, что современнойй производительности не хватает и нужно низкоуровневая оптимизация (хотя сам бы я так и делал) 
|
|
| HKarel |
| Отправлено: 08.02.2005, 10:25 |
|
Не зарегистрирован
|
Требуется уточнение: насколько я понял, проблема перераспределения (копирования) памяти проистекает из потребности вставлять/добавлять/удалять столбцы. Если получится решить эту проблему без перераспределения памяти — это Вас устроит ? |
|
| olegenty |
| Отправлено: 08.02.2005, 11:06 |
|
Ветеран
Группа: Модератор
Сообщений: 2412
|
да, с вектором погорячился, но основная мысль там не столько вектор, сколько попытка обратить взор вопрошавшего на STL.
|
|
| HKarel |
| Отправлено: 08.02.2005, 17:17 |
|
Не зарегистрирован
|
Schumi, проверяй почту |
|
