Быстрое удаление байта в TMemoryStream

← →
ArtemESC (2005-08-13 20:02) [0]

Какой наиболее быстрый алгоритм удаление n-го байта
с использованием TMemoryStream?

← →
Eraser © (2005-08-13 20:59) [1]

ArtemESC (13.08.05 20:02)

Создать второй TMemoryStream и скопировать в него все данные, кроме данного байта.

← →
begin...end © (2005-08-13 20:59) [2]

Если порядок байтов имеет значение, то сдвинуть участок потока, расположенный после n-го элемента, на 1 элемент "влево", и уменьшить длину потока на единицу. Лучшего алгоритма не вижу, поэтому, на мой взгляд, здесь следует думать не столько об алгоритме, сколько о способе его реализации.

Если порядок байтов не имеет значения, то обменять местами n-й байт с последним и уменьшить длину потока на единицу.

← →
Defunct © (2005-08-14 08:24) [3]

begin...end © (13.08.05 20:59) [2]

> то сдвинуть участок потока, расположенный после n-го элемента, на 1 элемент "влево", и уменьшить длину потока на единицу.
> Лучшего алгоритма не вижу,

Сдвиг "влево" понятие растяжимое. И если при сдвиге влево на "1", копирование будет происходить "побайтово", в то время как машина умеет оперировать 32-х битными словами, получится что алгоритм [1] лучше, для всех случаев когда удаляемый байт расположен не дальше 3/4 * Size от начала стрима.

← →
begin...end © (2005-08-14 09:25) [4]

> Defunct © (14.08.05 08:24) [3]

> И если при сдвиге влево на "1", копирование будет происходить "побайтово", в то время как машина умеет оперировать 32-х битными словами...

Я думаю, что это как раз не изменение алгоритма, а изменение способа его реализации. Алгоритм остаётся тем же самым -- сдвиг влево на 1 элемент (ведь я не написал конкретно, КАК нужно сдвигать). А реализовать этот сдвиг можно, конечно, по-разному. Поэтому я и написал, что думать нужно не об алгоритме, а о способе его реализации. К тому же, думать особенно и не надо -- стандартная процедура Move будет копировать по 4 байта.

> ...получится что алгоритм [1] лучше, для всех случаев когда удаляемый байт расположен не дальше 3/4 * Size от начала стрима

Оценка, очевидно, взята с потолка. Если данных в потоке совсем немного, то время на создание ещё одного экземпляра TMemoryStream может превысить время самого перемещения данных.

← →
Defunct © (2005-08-14 10:28) [5]

begin...end © (14.08.05 09:25) [4]
> Оценка, очевидно, взята с потолка.

Очевидно ты считаешь, что Move способна творить чудеса.
Приведика реализацию с Move где бы не потребовалось выделять доп. память.

← →
begin...end © (2005-08-14 11:15) [6]

> Defunct © (14.08.05 10:28) [5]

> Очевидно ты считаешь, что Move способна творить чудеса.

Нет, я так не считаю.

> Приведика реализацию с Move где бы не потребовалось выделять доп. память.

Я не знаю, что Вы имеете в виду под "не потребовалось выделять доп. память". Для решения поставленной задачи с Move я использовал бы примерно такой код:

var MS: TMemoryStream; N: Cardinal; // <-- Номер байта, который нужно удалить. begin MS := TMemoryStream.Create; try ... Move(Pointer(Cardinal(MS.Memory) + N + 1)^, Pointer(Cardinal(MS.Memory) + N)^, MS.Size - N - 1); MS.SetSize(MS.Size - 1); finally MS.Free end end.

← →
Defunct © (2005-08-14 11:55) [7]

begin...end © (14.08.05 11:15) [6]

Стоит только разработчикам borland изменить алгоритм работы процедуры move (копировать с конца, что эффективнее), и код [6] станет неработоспособным. В случае же использования директивы PUREPASCAL, копирование в процедуре Move выполняется побайтово.

← →
begin...end © (2005-08-14 12:10) [8]

> Defunct © (14.08.05 11:55) [7]

> Стоит только разработчикам borland изменить алгоритм работы процедуры move...

Если непонятно, я поясню: в коде [6] имелась в виду Move из Delphi 7. Что и естественно -- достаточно посмотреть на заголовок ветки.

В следующих версиях Delphi, разумеется, может измениться всё, что угодно (теоретически). Что именно -- неизвестно. Поэтому делать выводы о том, какой вариант -- мой или поддержанный Вами -- будет быстрее работать в следующих версиях, нет оснований.

> ...(копировать с конца, что эффективнее), и код [6] станет неработоспособным.

Вообще-то и сейчас там при некоторых обстоятельствах идёт копирование с конца. Что не делает неработоспособным код [6].

-------------------------

Я сейчас уезжаю в отпуск, поэтому продолжить дискуссию (если в этом будет необходимость) смогу, скорее всего, не ранее чем через неделю.

← →
Defunct © (2005-08-14 13:38) [9]

begin...end © (14.08.05 12:10) [8]
> Если непонятно, я поясню

К чему нужны эти колкости?

> при некоторых обстоятельствах идёт копирование с конца. Что не делает неработоспособным код [6].

Копирование с конца по четыре байта. По смещению -1 перетрет по 1 байту в каждом слове значением по адресу (Size - 4), и в результате получится такая картина:

до копирования
00 01 02 03 04 05 06 07 08 09 ... 13 14 15 16
после копирования (считаем что удаляется байт 00)
01 02 03 13 05 06 07 13 09 0A 0B 13 ... 14 15 16 (16)

но, к счастью для тебя, Move ни при каких обстоятельствах не копирует с конца.

> Я сейчас уезжаю в отпуск
Счастливого отдыха.

← →
Anatoly Podgoretsky © (2005-08-14 14:19) [10]

Defunct © (14.08.05 13:38) [9]
но, к счастью для тебя, Move ни при каких обстоятельствах не копирует с конца.

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

if Cardinal(D) > Cardinal(S) then for I := count-1 downto 0 do D[I] := S[I] else for I := 0 to count-1 do D[I] := S[I];
В ассемблерном варианте тоже самое.

> Defunct © (14.08.05 13:38) [9]

> К чему нужны эти колкости?

Если хотите, чтобы колкостей не было, разговаривайте более вежливо -- тогда и с Вами будут разговаривать так же.

> но, к счастью для тебя

См. предыдущий абзац.

> Move ни при каких обстоятельствах не копирует с конца.

Неверно. См. [10]. В этом как раз и состоит преимущество Move перед стандартной API-функцией CopyMemory: последнюю можно использовать только для случая неперекрывающихся блоков памяти, в противном случае следует использовать MoveMemory (см. справку по API или MSDN). А вот дельфийскую Move можно использовать в обоих случаях. Более того, дельфийские CopyMemory и MoveMemory не импортированы из стандартных библиотек Windows, а вызывают Move (см. модуль Windows).

begin...end © (20.08.05 14:26) [11]

Как отдохнули?

> Неверно. См. [10]. В этом как раз и состоит преимущество Move
к сожалению, мне эта тема уже не интересна

begin...end © (20.08.05 17:59) [13]

хех.. бывает.. лучше б здесь остались. А то скучно так было и поругаться не с кем ;>

Быстрое удаление байта в TMemoryStream Найти похожие ветки