Здравствуйте, MaximE, Вы писали:
ME>Ok. Пусть количество итераций алгоритма i(n), сложность O(f(n)). Сложность memset на 32-битной платформе m(n) = c * n / 4. Добавление memset в каждую итерацию сделает O() алгоритма O(f(n) + i(n) * m(n)), т.е. не переводит алгоритм в (общую) группу с более высокой сложностью.
1) количество итераций = i(n) -пусть i(n) = тождественная, т.е. i(n)=n.
2) На каждой итерации что-то делалось, что в сумме давало n, т.е. если g(i) — количество операций на i-той итерации, то сумма по всем итерациям (т.е. сумма от 1 до i(n)=n выражений g(i)) равно n
3) Итак, на каждой итерации алгоритма создавался массив P длины n
-----------------------------------------------------------------
Если m(n) = c*n/4, то сложность алгоритма O(n*(c*n/4) + n)
Если m(n) = O(1), то O(n + n) = O(n)
Вот ещё один вопрос по архитектуре созрел.
Затраты на инициализацию справочника — это O(N).
Затраты на проверку валидности одного адреса — O(1).
Вопрос: сколько обращений к твоей таблице? Не дешевле ли единожды инициализировать, чем каждый раз проверять?
Профайлер покажет.
Впрочем, ты можешь действовать хитрым способом:
1) Если проверка выявила невалидный элемент, обнулить его.
Эта стратегия даст результат, когда промахов существенно больше, чем попаданий. Ведь невозможно отличить попадание от невалидного адреса, а вот повторный промах будет обработан гораздо быстрее.
2) Завести грубую карту инициализации. Скажем, разбить диапазон хеш-значений на 8N поддиапазонов, и каждому поддиапазону сопоставить 1 бит N-байтного массива признаков.
— Если бит =0 — значит, поддиапазон не инициализирован.
— — в случае чтения это означает заведомый промах.
— — в случае записи — выполняем инициализацию и взводим бит.
— Если бит =1 — значит, поддиапазон инициализирован.
— — чтение — никаких проверок
— — запись — установка единственного элемента.
flax wrote:
> Здравствуйте, MaximE, Вы писали: > > ME>Ok. Пусть количество итераций алгоритма i(n), сложность O(f(n)). Сложность memset на 32-битной платформе m(n) = c * n / 4. Добавление memset в каждую итерацию сделает O() алгоритма O(f(n) + i(n) * m(n)), т.е. не переводит алгоритм в (общую) группу с более высокой сложностью. > > 1) количество итераций = i(n) -пусть i(n) = тождественная, т.е. i(n)=n. > 2) На каждой итерации что-то делалось, что в сумме давало n, т.е. если g(i) — количество операций на i-той итерации, то сумма по всем итерациям (т.е. сумма от 1 до i(n)=n выражений g(i)) равно n > 3) Итак, на каждой итерации алгоритма создавался массив P длины n > > ----------------------------------------------------------------- > Если m(n) = c*n/4, то сложность алгоритма O(n*(c*n/4) + n) > Если m(n) = O(1), то O(n + n) = O(n)
Здравствуйте, Sergey, Вы писали:
S>Hello, flax! S>You wrote on Mon, 06 Dec 2004 10:12:50 GMT:
SDB>>> Фунукции IsBad*Ptr() не подойдут?
f>> Т.е. они помогут выловить, является ли значение в массиве P[i] вообще f>> указателем куда-либо или нет.
S>Они говорят ровно об одном — будет ли AV при записи/чтении по данному S>адресу.
http://weblogs.asp.net/larryosterman/archive/2004/05/18/134471.aspx
[quote]The way you check for bad pointers on Win32 is by calling the IsBadReadPtr and IsBadWritePtr API. Michael Howard calls these APIs “CrashMyApplication” and “CorruptMemoryAndCrashMySystem” respectively. The problem with IsBadReadPtr/IsBadWritePtr is that they do exactly what they’re advertised as doing: They read and/or write to the memory location specified, with an exception handler wrapped around the read/write. If an exception is thrown, they fail, if not, they succeed.[/quote]
Здравствуйте, flax, Вы писали:
F>Только тогда есть риск схватить что-то страшное при int x = P[i]: F> и надо иметь функцию Is_этавещь_Int() или просто ждать exception.
На какой архитектуре такие риски? Это с указателями ещё могут быть фокусы в сегментной модели... А тут всё просто — проверил диапазон, и настало тебе щастье.
Здравствуйте, flax, Вы писали:
F>Есть некоторый массив P указателей на int. В некоторые ячейки массива P были внесены указатели на элементы массива A (int), однако валидные значения были внесены не во все элементы P, и в некоторых ячейках массива P находятся неинициализированные, случайные значения ( то, что было на этом месте в памяти)
F>Можно ли, взяв произвольный указатель x из P (x = P[i]), проверить указывает ли он на (какой-либо) элемент F>массива (т.е. проверить указывает ли он в интервал памяти &a[0], &a[n-1]).
Нет, в рамках стандартного C/C++ эта задача неразрешима. Попытка доступа к значению неинициализированной переменной приводит к неопределенному поведению. Возможно получить доступ к внутреннему представлению такого объекта, трактуя его как массив байтов (unsigned char). Но стандарты C/C++ не дают никаких гарантий относительно внутреннего представления указателей. В частности, логически равные указатели (т.е. такие, для которых оператор = будет иметь значение true или 1) могут иметь различное внутреннее представление (т.е. memcmp для массивов байтов, представляющих эти указатели, может возвращать не ноль).
F>С одной стороны, вроде можно, обставив проверку exception-ом ( на нем будут выявляться те указатели, которые вообще указывают неизвестно куда).
Исключение вовсе не является стандартной реакцией на доступ к значению невалидного указателя. Здесь Вы говорите о какой-то конкретной реализации. Причем весьма экзотической.
F>С другой стороны, где-то слышал, что память вроде как не comparable.
Да, даже если бы в Вашем массиве P находились проинициализированные значения, указывающие на какие-то объекты, не входящие в массив A, то и в этом случае проверка их попадания в нужный диапазон была бы затруднена. Применение операторов <, >, <=, >= к указателям на объекты, не являющиеся подобъектами одного объекта или элементами одного массива, в C приводит к неопределенному поведению, а в C++ дает неспецифицированный результат. Остается лишь трудоемкое последовательное сравнение с адресами всех элементов массива при помощи операторов == или !=.
Hello, Centaur!
You wrote on Mon, 06 Dec 2004 17:10:16 GMT:
S>> Они говорят ровно об одном — будет ли AV при записи/чтении по данному S>> адресу.
C> http://weblogs.asp.net/larryosterman/archive/2004/05/18/134471.aspx C> [quote]The way you check for bad pointers on Win32 is by calling the C> IsBadReadPtr and IsBadWritePtr API. Michael Howard calls these APIs C> “CrashMyApplication” and “CorruptMemoryAndCrashMySystem” respectively. C> The problem with IsBadReadPtr/IsBadWritePtr is that they do exactly what C> they’re advertised as doing: They read and/or write to the memory C> location specified, with an exception handler wrapped around the C> read/write. If an exception is thrown, they fail, if not, they C> succeed.[/quote]
Да я в курсе, вообще-то Только сам проверял, а не Говарда читал.
With best regards, Sergey.
Posted via RSDN NNTP Server 1.9 delta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Перекуём баги на фичи!
Только сам проверял, а не Говарда читал.
