Есть некоторый массив P указателей на int. В некоторые ячейки массива P были внесены указатели на элементы массива A (int), однако валидные значения были внесены не во все элементы P, и в некоторых ячейках массива P находятся неинициализированные, случайные значения ( то, что было на этом месте в памяти)

Можно ли, взяв произвольный указатель x из P (x = P[i]), проверить указывает ли он на (какой-либо) элемент
массива (т.е. проверить указывает ли он в интервал памяти &a[0], &a[n-1]).

С одной стороны, вроде можно, обставив проверку exception-ом ( на нем будут выявляться те указатели, которые вообще указывают неизвестно куда).

С другой стороны, где-то слышал, что память вроде как не comparable.

Здравствуйте, flax, Вы писали:

F>С одной стороны, вроде можно, обставив проверку exception-ом ( на нем будут выявляться те указатели, которые вообще указывают неизвестно куда).

F>С другой стороны, где-то слышал, что память вроде как не comparable.

Фунукции IsBad*Ptr() не подойдут?

flax wrote:

> Есть некоторый массив P указателей на int. В некоторые ячейки массива P были внесены указатели на элементы массива A (int), однако валидные значения были внесены не во все элементы P, и в некоторых ячейках массива P находятся неинициализированные, случайные значения ( то, что было на этом месте в памяти)

А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема?

--
Maxim Yegorushkin

Здравствуйте, flax, Вы писали:

F>Можно ли, взяв произвольный указатель x из P (x = P[i]), проверить указывает ли он на (какой-либо) элемент
F>массива (т.е. проверить указывает ли он в интервал памяти &a[0], &a[n-1]).

Ну а тупо-глупо как:

assert(
   x >= &a[0] && 
   x <  &a[n]);

Здравствуйте, MaximE, Вы писали:


ME>А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема?

Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)

Здравствуйте, flax, Вы писали:

F>Здравствуйте, MaximE, Вы писали:


ME>>А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема?

F>Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)

Гм. А что Вам мешает обнулить массив 1 вызовом функции memset?

flax wrote:

> Здравствуйте, MaximE, Вы писали:
>
>
> ME>А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема?
>
> Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)

Сложность зануления можно принять как c * n, где с — константа. Тогда сложность будет O(x + c * n), т.е. зануление не должно оказать значительного влияния.

--
Maxim Yegorushkin

Здравствуйте, MaximE, Вы писали:

>>
>> Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)

ME>Сложность зануления можно принять как c * n, где с — константа.

Мне n-раз надо такую вещь делать. Т.е. (c*n)*n — если занулять.


ME>Тогда сложность будет O(x + c * n), т.е. зануление не должно оказать значительного влияния.

На одном шаге.

ME>--
ME>Maxim Yegorushkin

flax wrote:

>>> Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)
>
> ME>Сложность зануления можно принять как c * n, где с — константа.
>
> Мне n-раз надо такую вещь делать. Т.е. (c*n)*n — если занулять.

Ты меня не понял. Сложность зануления массива — c (memset), сложность зануления массива n раз — с * n.

--
Maxim Yegorushkin

Здравствуйте, flax, Вы писали:

F>Занулять нельзя...

по-моему обнулять все-таки придется — ведь нет никакой гарантии, что "неинициализированные, случайные значения" никогда не будут иметь допустимое значение ( x >= &a[0] && x < &a[n] ).

может лучше вместо массива указателей использовать какой-нибудь контейнер?

Здравствуйте, MaximE, Вы писали:


ME>Ты меня не понял. Сложность зануления массива — c (memset), сложность зануления массива n раз — с * n.

I як, братцы, это (за константу) реализовать???

MSDN::memset
LinuxManual::memset
Функция memset() заполняет первые n байтов той области памяти, на которую указывает s, постоянным байтом c.

Что-то не похоже на константу? (n — большое)


ME>--
ME>Maxim Yegorushkin

flax wrote:

> ME>Ты меня не понял. Сложность зануления массива — c (memset), сложность зануления массива n раз — с * n.
>
> I як, братцы, это (за константу) реализовать???
>
>
>

> [url=http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore98/HTML/_crt_memset.asp
> ]MSDN::memset[/url]
> LinuxManual::memset
> Функция memset() заполняет первые n байтов той области памяти, на которую указывает s, постоянным байтом c.

Это действительно не константа, но ее время исполнения можно принять за константу, так как на каждой итерации он будет выполняться за константное время (если, конечно, размер твоего массива постоянен). Только если время выполнения memset будет равно времени исполнения одной итерации (что, как мне кажется, маловероятно), memset сможет повысить степень выражения асимптоматической сложности алгоритма.

--
Maxim Yegorushkin

Здравствуйте, _grisha, Вы писали:

_>по-моему обнулять все-таки придется — ведь нет никакой гарантии, что "неинициализированные, случайные значения" никогда не будут иметь допустимое значение ( x >= &a[0] && x < &a[n] ).

Пусть случайные значения очень похожи на допустимые...
Массив А — весьма специальный, так что все вылавливается на следущем этапе.

Единственное (техническое) затруднение заключается в том, что

можно ли использовать в рабочем коде констукцию вида

Обвертка (exception){
 x >= &a[0] && x < &a[n]
}

чтобы выловить указывает x в А или нет .


Смущения оттого, что вспоминается из книги какого-то гуру "Memory is not comparable!!!". Кстати почему? (только из-за возможности distributed размещения ресурсов памяти)

flax wrote:

> ME>А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема?
>
> Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)

Что за алгоритм?

--
Maxim Yegorushkin

Здравствуйте, flax, Вы писали:

F>Здравствуйте, MaximE, Вы писали:


ME>>Ты меня не понял. Сложность зануления массива — c (memset), сложность зануления массива n раз — с * n.

F>I як, братцы, это (за константу) реализовать???


F>

F>[url=http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore98/HTML/_crt_memset.asp
F>]MSDN::memset[/url]
F>LinuxManual::memset
F>Функция memset() заполняет первые n байтов той области памяти, на которую указывает s, постоянным байтом c.

F>Что-то не похоже на константу? (n — большое)
Там цепочечная команда рабьотает... До 256к на интеле одной командой...

Здравствуйте, MaximE, Вы писали:

ME>flax wrote:


ME>Это действительно не константа, но ее время исполнения можно принять за константу, так как на каждой итерации он будет выполняться за константное время (если, конечно, размер твоего массива постоянен). Только если время выполнения memset будет равно времени исполнения одной итерации (что, как мне кажется, маловероятно), memset сможет повысить степень выражения асимптоматической сложности алгоритма.

1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()).
2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим
3) Насколько я понимаю, memset есть (буквально)"оптимизированная версия пробежать первых n байт и заполнить их фиксированным значением". Т.е. ты говоришь, что он просто очень быстрый (если n-мало), не более того.

flax wrote:

> ME>Это действительно не константа, но ее время исполнения можно принять за константу, так как на каждой итерации он будет выполняться за константное время (если, конечно, размер твоего массива постоянен). Только если время выполнения memset будет равно времени исполнения одной итерации (что, как мне кажется, маловероятно), memset сможет повысить степень выражения асимптоматической сложности алгоритма.

> 1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()).
> 2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим

memset не работает на бесконечности

> 3) Насколько я понимаю, memset есть (буквально)"оптимизированная версия пробежать первых n байт и заполнить их фиксированным значением". Т.е. ты говоришь, что он просто очень быстрый (если n-мало), не более того.

Именно так. memset не увеличит количество итераций твоего алгоритма, лишь сделает каждую итерацию медленнее, поэтому memset не сделает из O(n * log(n)) алгоритма O(n^2) алгоритм.

--
Maxim Yegorushkin

Здравствуйте, MaximE, Вы писали:

>> 1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()).
>> 2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим

ME>memset не работает на бесконечности

Приколы приколами, а все же. Внутри все-равно цикл есть. Все-равно количество тактов процессора, которое тратится на выполнение memset, зависит от размера массива линейно.

Здравствуйте, LaptevVV, Вы писали:

F>>Что-то не похоже на константу? (n — большое)
LVV>Там цепочечная команда рабьотает... До 256к на интеле одной командой...

А вот хотелось бы поразвернутее услышать про это чудо. Вы утверждаете, что 256к и 100 байтов обнуляются одно и то же (константное) время?
И, кстати, даже если 256к за одну команду, то для N байтов нужно N/256К команд, что, очевидно, есть O(N).

Здравствуйте, MaximE, Вы писали:

ME>flax wrote:


>> 3) Насколько я понимаю, memset есть (буквально)"оптимизированная версия пробежать первых n байт и заполнить их фиксированным значением". Т.е. ты говоришь, что он просто очень быстрый (если n-мало), не более того.

ME>Именно так. memset не увеличит количество итераций твоего алгоритма, лишь сделает каждую итерацию медленнее, поэтому memset не сделает из O(n * log(n)) алгоритма O(n^2) алгоритм.

Можно подробнее... что-то я запутался.
1) Если мы говорим о O(n), то вообще говоря рассмативаем поведение lim
Т.е. фразу "время работы функции не константа, но сложность общего алгоритма использование этой функции не увеличит" я не понимаю. Я могу понять, что если функция не константа, то она ( в любом случае) увеличит сложность алгорима, другое дело, что O(n^2) равно O(n^2 + log(n)) по принципам сложения этих асимптотик.

Итак, если функция (вообще говоря) не константа, тогда сразу же хочется узнать какова ее сложность. Вполне возможно, что порядок ее роста может быть ассимптотически малым, что-то похожее на [ O(F(n)) "почти линейные",Ахо], т.е.почти еще какие-либо...Но в любом случае сложность O(какая-то оценка от n), если она не константа, должна быть.

2) Если я правильно понял Lapteva, то реализация этой функции зашита в Intel-процессоры и способна (так же как мы считаем cкорость выполнения адресации в RandomAccessMemory к произвольному элементу за O(1)) на масштабах до 256к делать зануление последовательного куска памяти за O(1).

3) Но на бескончености ведь это даст ( в таком случае)
(n=size_of A)*(type_of A)/256k
т.е. те же O(n)

так?

Кстати
1) Почему в RAM доступ по адресу за O(1)? (в RAM она как постулат, а в компах — тоже на уровне инструкций проца)

2) Почему memory вообще говоря noncomparable, только для предоставления возможности менеджеру памяти без головной боли выполнять масштабирование?