массивы

← →
Asker (2003-02-13 01:37) [0]

У меня есть огромный динамический массив (до 2-3мб). Как эффективнее организовать вставку/удаление пары байт в произвольном месте?
Ведь если делать сдвигами, то придётся выделять память под временный массив, что как-то не хорошо.

← →
Palladin © (2003-02-13 01:41) [1]

ИМХО
в данном случае следует использовать TList

← →
Asker (2003-02-13 01:42) [2]

так он же медленно работать будет

← →
Palladin © (2003-02-13 01:50) [3]

TList хранит ссылки по принципу дин. массива, и совсем не медленнее если запись у тебя занимает больше 4 байт

считай сам, TList вставляет записи при помощи Move, толи мувить массив ссылок по 4 байта толи по SizeOf(здоровая запись).

Но если у тебя запись меньше 4 то придется сдвигами.

← →
Asker (2003-02-13 01:52) [4]

массив байт в виде PChar

← →
Palladin © (2003-02-13 01:57) [5]

под временный массив выделять не надо
просто сделай ReallocMem
а потом Move начиная с вставляемой позиции на +1

хм... интересно сработает или нет... :)
сейчас попробую скажу...

← →
Palladin © (2003-02-13 02:10) [6]

все нормально отработало, так что забудь про временные массивы

← →
Ihor Osov'yak © (2003-02-13 02:19) [7]

А мне кажется, что нужно модель менять. Как-то не здорово из-за 4 байт 2-3 мегабайта гонять...

← →
Palladin © (2003-02-13 02:23) [8]

> Ihor Osov"yak © (13.02.03 02:19)

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

← →
Ihor Osov'yak © (2003-02-13 02:32) [9]

Asker = Palladin ????

Если не так, то откуда Вам это известно, что в чела там обрабатывается ?

Имхо, в большинстве случаев при работе с большими обьемами информации/массивами очень полезно делать некую кластеризацию.. И как правило, это возможно...

← →
Palladin © (2003-02-13 02:35) [10]

есть мысль хранить не одним массивом а несколькими ограничеными скажем по 1000 записей
сами массивы хранить в TList
и шоб скажем вставить в произвольное место, нужно будет всего лишь найти тот массив где это место имеет место :)

схемка

TList of dynamic array
1: 1 1 1 1 1
2: 1 1 1 1 1
3: 1 1 1 1 1

три дин массива
вставить в 7 место

побежали по массивам складывая их размер, добрались до 7 и добавили "2" таким образом что у нас получилось так

TList of dynamic array
1: 1 1 1 1 1
2: 1 2 1 1 1
3: 1
4: 1 1 1 1 1

думаю такая модель увеличит многократно производительность

← →
Palladin © (2003-02-13 02:37) [11]

ну и подозрения :)

> Если не так, то откуда Вам это известно, что в чела там
> обрабатывается ?

Asker (13.02.03 01:52)
массив байт в виде PChar

← →
Palladin © (2003-02-13 02:39) [12]

я ведь не знаю :)
я всего лишь предполагаю на основе сказаного челом

← →
Ihor Osov'yak © (2003-02-13 03:12) [13]

2 Palladin © (13.02.03 02:39)

:-).

2 Palladin © (13.02.03 02:35)

Схем может быть много. В том числе, и предложенная Вами.

← →
Radionov Alexey © (2003-02-13 07:40) [14]

>Asker (13.02.03 01:37)
Если необходимо вставлять элементы именно внутрь огромного массива, значит в массиве определен некоторый порядок (некоторая отсортированность имеется). Для таких кабанских данных имхо подходят структуры а-ля B-дерево, в которых сохраняется отсортированность => быстрый поиск и весьма дешевая вставка нового элемента в нужное место.

← →
alexanderK2 (2003-02-13 09:31) [15]

Если на C++Builder, то можно использовать STL.
Очень удобная библиотека, для такого вида операций.

← →
REA © (2003-02-13 10:54) [16]

Можно создать кэш и писать все изменения в него и работать с ним сначала, а потом с массивом. После нажатия кнопки Commit changes сделать синхронизацию кэша и данных. Сложновато реализовать конечно. Проще наверно как сказано выше разбить на блоки.

← →
Leshiy © (2003-02-13 11:40) [17]

Можно попробовать указатели.

← →
Чих-пых © (2003-02-13 13:38) [18]

А чем указатели помогут?

Указатели (особенно двухсторонние) могут увелитичь размер более чем в 2-3 раза... Если данные короткие (типа integer). Хотя вставлять и убирать из такого массива действительно намного дешевле.

Для массива могу посоветовать, не менять динамически после каждого изменения, а иметь динамический массив с некоторым запасом свободного места, например +10% размера массива на запас. После заполнения свободного места, увеличение массива на следующие 10% и т.д. При этом накладные расходы на добавления одной записи уменьшаются.

Я думаю нужно ( важно ) определиться что нужно скорость или
размер данных увеличение в 3 раза ( 2 указателя ) памяти даст
увеличение скорости ну и сделай тестовые примеры и определись

← →
Asker (2003-02-13 23:10) [22]

у меня есть насущная необходимость файл целиком помещать в память (2-3мб - это логический предел, в среднем будет прим. 500-700кб). Разбиение на блоки, пожалуй, будет самым приемлимым решением исходя из трудоёмкости и эффективности.
Искренне благодарен =)

> Asker (13.02.03 01:42)
> так он же медленно работать будет

А какие скоростные параметры нужны? Очень часто народ в скорости заблуждается. Я вот писал прогу в ней был логический и грфический пункт в цикле( %-))). По скорости я сильно грешил на логику, а оказалось что логика в 1000 раз быстрее обрабатывалась чем графика - тут и было самое слабое место.

В данном случае, автор просил подсказать более оптимальную методику работы с массивом бинарных данных. Сказано же было в начале

Asker (13.02.03 01:52)
массив байт в виде PChar

Причем тут указатели, и одно/двусторонние списки? Про записи и размер записи было так же обговорено в начале.

Опять же посоветую книгу.
Род Стивенс. "Delphi. Готовые алгоритмы."

Там Вы сами выберите наиболее подходящее для конкретной ситуации решение. Есть и другие книги на эту тему.

массивы Найти похожие ветки