Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Работа с битовыми масками.

Страницы: 1 2 >
Riply © (2008-01-22 16:06:00)
Здравствуйте !
Допустим, у нас есть две битовые маски.
Нам надо их сравнить и, если они различны, то выкинуть из каждой
те биты, которые есть в другой. Т.е. оставить только "отличающиеся".
У меня вот что получилось:
function DeleteEqualBits(const pBitMap1, pBitMap2: PRTL_BITMAP): DWord; var i: integer; DWordCount, Tmp: DWord; pdw1, pdw2: PULONG; begin Result := 0; DWordCount := min(pBitMap1.SizeOfBitMap, pBitMap2.SizeOfBitMap) div 8; if DWordCount > 0 then begin pdw1 := pBitMap1.Buffer; pdw2 := pBitMap2.Buffer; for i := 0 to Pred(DWordCount) do if pdw1^ <> pdw2^ then begin Tmp := pdw1^ xor pdw2^; pdw1^ := pdw1^ and Tmp; pdw2^ := pdw2^ and Tmp; inc(Result); end; end; end;
Помогите, пожалуйста оптимизировать это безобразие,
если, конечно, оно того заслуживает :)

guav (2008-01-23 15:26:00) [1]
Я тоже посмотрел свою ссылку, предлагаю вот что:
Раз ты всё равно исходишь из предположения, что файлов меньше MAXDWORD, использовать обычный THashSet оттуда, и приводить FILE_REFERENCE к TObject.

Riply (2008-01-23 14:47:00) [2]
> [22] guav © (23.01.08 14:34)
> Я понимаю. Я просто предлагаю как вариант попробовать,
> мож скорость не потеряешь, а память выиграешь.

Уже скачала. Буду смотреть.

> Кстати, теоретически, памяти в любом случае может не хватить.
> для номера в MFT зарезервировано 6 байт. 2^48 div 8 больше
> размера 32разрядного адресного пространства 2^32.

Очень хочется увидеть диск, сожержащий более MAXDWORD "файловых" объектов.
Простое любопытство :)
А уж поработать на нем ! Например поискать файлы содежащие определенное слово :)

guav (2008-01-23 14:34:00) [3]
> [21] Riply © (23.01.08 14:24)

> А кто это такие ?

Контейнеры, которые упорядочены не произвольно, а таким образом, чтобы элементы можно было находить по ключу.
У set'ов ключ и есть элемент, у map'ов элемент содержит ключ и значение. У сортированных с помощью дерева элемент ищется за логарифмическое время, и все эелементы идут в порядке, определяемом стравнением ключей. У hash контейнеров - за константное время, но элементы идут не в порядке, определяемом стравнением ключей.

> Максимальное количество битов в bitmape заранее
> известно: MftValidDataLength div BytesPerFileRecordSegment

Я понимаю. Я просто предлагаю как вариант попробовать, мож скорость не потеряешь, а память выиграешь.
Кстати, теоретически, памяти в любом случае может не хватить. для номера в MFT зарезервировано 6 байт. 2^48 div 8 больше размера 32разрядного адресного пространства 2^32.

Riply (2008-01-23 14:24:00) [4]
> [19] guav © (23.01.08 14:11)
> Я в подобных случаях использовал бы ассоциативные контейнеры.

А кто это такие ?

> Дело в том, что единиц в bitmape я так понял предполагается не очень много,
> поэтому памяти потребуется меньше.

Максимальное количество битов в bitmape заранее
известно: MftValidDataLength div BytesPerFileRecordSegment
(если правильно помню названия полей)

guav (2008-01-23 14:15:00) [5]
THashSet отсюда http://sourceforge.net/projects/dclxприкрутить попробуй

guav (2008-01-23 14:11:00) [6]
> [18] Riply © (23.01.08 13:03)

Я в подобных случаях использовал бы ассоциативные контейнеры. Дело в том, что единиц в bitmape я так понял предполагается не очень много, поэтому памяти потребуется меньше.
Даже если не хочешь смешивать массивы, сами номера я бы помещал не в bitmap а в ассоциативный контейнер.
Если нужна сортировка, то set, иначе вообще hash set.

Riply (2008-01-23 13:03:00) [7]
> [17] guav © (23.01.08 11:43)
> Т.е. надо просто добавлять сразу все объекты в одну сруктуру :)

Саш, думала я об этом.
Дело в том, что уж слишком велико различие между способами
сканирования и структурами с которыми они работают.
Создавать еще один вариант записи данных, пригодный и там и там ?
Получится монстр какой-то :) Ибо у каждого способа есть параметры, нужные только ему.

В первозданном виде первая "струтура" это смесь
FILE_ID_BOTH_DIR_INFORMATION и FILE_STREAM_INFORMATION,
которые заполнялись Nt - функциями с запросом на возвращение
"не единственного" вхождения и записывались в память
последовательно, по мере их поступления.
Добавлять в эту кашу (без преобразования ее в удобоворимый вид)
что-то другое не представляется возможным (или не очень просто).
Совсем другое дело - выдернуть из нее по маске
только нужные нам элементы.
Так мы избавляемся от любых ее преобразований и
поиска в ней элеменов на вхождение (что тоже не просто учитывая ее "несортированность").
Даже эта операция может понадобиться только в том случае,
если в ней окажутся элементы, не найденные вторым способом,
а это нам станет известно из сравнения масок.

guav (2008-01-23 11:43:00) [8]
> Надо сравнить результаты. (Т.е. объект такой-то есть в первом
> SnapShort-е и отсутствует во втором. И наоборот.)
> Если они одинаковы, то все хорошо, иначе создаем структуру,
> содержащую их объеденение.

Т.е. надо просто добавлять сразу все объекты в одну сруктуру :) (разумеется, структура д.б. такова, чтобы дупликаты не добавлялись).

Riply (2008-01-23 08:10:00) [9]
> [15] Zeqfreed © (23.01.08 07:30)
> Позволю себе тоже попридираться к эстетике, если позволите :)

Спасибо.

P.S.
Мне кажется, что в результате получится, пусть даже "не рабочая",
но зато очень эстетичная функция :)

Zeqfreed (2008-01-23 07:30:00) [10]
Позволю себе тоже попридираться к эстетике, если позволите :)

Во-первых, в слове «снапшот» нет буквы р.
А во-вторых, DeleteEqualBits вообще никак не отображает сути функции, потому что «удалить» биты нельзя. На мой взгляд можно обозвать функцию как-нибудь наподобие SnapshotsDifference или DifferentiateSnapshots.

Riply (2008-01-23 04:57:00) [11]
> [12] Sapersky (22.01.08 19:44)
> Если уж придираться к эстетике - то...
"придираться к эстетике" нужно !
Спасибо. :)

> [11] oldman © (22.01.08 18:23)
> И что на выходе???
> [13] guav © (22.01.08 23:14)
> Что за задача ?

Для некого файлового объекта, двумя различными способами,
делается SnapShort дерева его "детей".
Надо сравнить результаты. (Т.е. объект такой-то есть в первом
SnapShort-е и отсутствует во втором. И наоборот.)
Если они одинаковы, то все хорошо, иначе создаем структуру,
содержащую их объеденение.
Предполагается поиск вхождений элементов одной структуры в
другую (любым способом), заменить работой с битовыми масками.
(Их можно создать на этапе сканирования, взяв за основу номер записи в MFT)
После сравнения двух масок, в них остаются только биты соответствующие
номерам записей "лишних" объектов.
Используя их легко создается наше "объеденение" SnapShort-ов.
Первые эксперименты по использованию масок впечатляют.
Они дают выигрыш по времени не в разы, а на порядки.
Плюс к этому они могут и помочь сэкономить память,
которая требуется для привеления SnapShort-ов в вид, "пригодный для сравнения" :)

guav (2008-01-22 23:14:00) [12]
А что тут делает ветвление ?
> if pdw1^ pdw2^ then

> else
> begin
> pdw1^ := 0;
> pdw2^ := 0;
> end;

разве то что до else не справится с равными значениями ?

> если, конечно, оно того заслуживает :)

Что за задача ?
Я вот тоже не так давно не с того конца подошел к оптимизации, в результате выяснилось, что на самом деле проблема решается применением правильной структуры ( http://www.delphimaster.ru/cgi-bin/forum.pl?n=5&id=1198141284).

Sapersky (2008-01-22 19:44:00) [13]
Riply © (22.01.08 17:19) [10]

Если уж придираться к эстетике - то const в списке параметров лишний, либо const TRTL_BITMAP, либо просто PRTL_BITMAP.
Тип DWordCount лучше сделать Integer, так же как и счётчика (i), тогда можно будет выкинуть начальную проверку на 0.

oldman (2008-01-22 18:23:00) [14]

> Допустим, у нас есть две битовые маски.
> Нам надо их сравнить и, если они различны, то выкинуть из
> каждой
> те биты, которые есть в другой. Т.е. оставить только "отличающиеся".

И что на выходе???

Riply (2008-01-22 17:19:00) [15]
Выложу ка я последний вариант, а то ошибки растут как грибы :)
Может кто еще найдет.
function DeleteEqualBits(const pBitMap1, pBitMap2: PRTL_BITMAP): DWord; var i: integer; DWordCount, Tmp: DWord; pdw1, pdw2: PULONG; begin Result := 0; DWordCount := min(pBitMap1.SizeOfBitMap, pBitMap2.SizeOfBitMap) div (8 * SizeOf(DWord)); if DWordCount > 0 then begin pdw1 := pBitMap1.Buffer; pdw2 := pBitMap2.Buffer; for i := 0 to Pred(DWordCount) do begin if pdw1^ <> pdw2^ then begin Tmp := pdw1^ xor pdw2^; pdw1^ := pdw1^ and Tmp; pdw2^ := pdw2^ and Tmp; inc(Result); end else begin pdw1^ := 0; pdw2^ := 0; end; inc(pdw1); inc(pdw2); end; end; end;

Riply (2008-01-22 17:13:00) [16]
> [7] Sapersky (22.01.08 17:04)
> SizeOfBitMap - размер в битах или байтах?

В битах.

> И в том, и другом варианте в DWordCount будет явно не кол-во DWord'ов.
Точно. Спасибо.

> Ещё, если размер в байтах не обязательно кратен DWord, нужно отдельно обработать байты в конце.
Будет кратен исходя из условий инициализации (они описаны для ф-ии RtlInitializeBitMap)

Riply (2008-01-22 17:05:00) [17]
> [6] Rouse_ © (22.01.08 16:33)
> Я даже не вижу что тут можно еще оптимизировать :) Все вроде логично выстроенно...

Тогда так и оставлю, записав ее в разряд готовых.
Правда, после исправления проверки одного и того же блока,
она стала выглядеть совсем "не эстетично" :)

Sapersky (2008-01-22 17:04:00) [18]
DWordCount := min(pBitMap1.SizeOfBitMap, pBitMap2.SizeOfBitMap) div 8;

SizeOfBitMap - размер в битах или байтах?
И в том, и другом варианте в DWordCount будет явно не кол-во DWord'ов.
Ещё, если размер в байтах не обязательно кратен DWord, нужно отдельно обработать байты в конце.

Rouse_ (2008-01-22 16:33:00) [19]

> Но вопрос не отпал.

Я даже не вижу что тут можно еще оптимизировать :) Все вроде логично выстроенно...

Riply (2008-01-22 16:19:00) [20]
> [1] DVM © (22.01.08 16:09)

> PRTL_BITMAP у меня нет такого типа - это откуда?

RTL_BITMAP = packed record SizeOfBitMap: ULONG; //0 Number of bits in bit map Buffer: PULONG; //4 Pointer to the bit map itself end; PRTL_BITMAP = ^RTL_BITMAP;

> [2] Rouse_ © (22.01.08 16:12)
> Тезка, а тебе не кажется что ты ксоришь только первые 4 байта масок в цикле? :)

:)
Вот к чему приводит спешка. Спасибо. :)
Но вопрос не отпал.

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »