If I have a large array 10,000+ elements then how do I reserve memory
for this ? Currently I get a segmentation fault. Dynamic reservation
is good, but allowing a chunk for the program is an acceptable
alternative.
49  3113  vf***@talktalk.net wrote:
If I have a large array 10,000+ elements then how do I reserve memory
for this ?
What do you mean by "reserve memory"? You either declare a static array,
or an automatic array, or a dynamic array. All those "reserve memory"
in some sense.
Currently I get a segmentation fault.
Read FAQ 5.8.
Dynamic reservation
is good, but allowing a chunk for the program is an acceptable
alternative.
What's "allowing a chunk for the program"?
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Victor Bazarov wrote:
What do you mean by "reserve memory"? You either declare a static array,
or an automatic array, or a dynamic array. All those "reserve memory"
in some sense.
Currently I get a segmentation fault.
Read FAQ 5.8.
Believe me! It is caused by the array, because if I only reduce the
size it does not occur. It is some kind of stack overflow, someone
told me words to that effect.
Dynamic reservation
is good, but allowing a chunk for the program is an acceptable
alternative.
What's "allowing a chunk for the program"?
In other compilers / platforms / languages I've used there is usually
one or more numeric (hex) settings which allows you to reserve a
"chunk" of memory for your program (executable), like fixed stack size
or initial stack size and a max stack size. Perhaps I am making
assumptions that C++ compilers work the same way. vf***@talktalk.net wrote:
mlimber wrote:
>>
Use std::vector (cf.
http://www.parashift.com/c++-faq-lit...html#faq-34.1).
Cheers! --M
But does standard vector do O(1) access ?
Yes. Inside it has a dynamic array, but you supposedly don't know
or don't care about it.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask vf***@talktalk.net wrote:
Victor Bazarov wrote:
>What do you mean by "reserve memory"? You either declare a static
array, or an automatic array, or a dynamic array. All those
"reserve memory" in some sense.
>>Currently I get a segmentation fault.
Read FAQ 5.8.
Believe me! It is caused by the array, because if I only reduce the
size it does not occur. It is some kind of stack overflow, someone
told me words to that effect.
It has nothing with believing you or not believing you. You say
your code doesn't work. Post the code.
Stack overflow is a real problem when your program doesn't have
enough memory to organize its stack. But no *language* feature
exists to help you organize your program's stack, it's a compiler
feature, not the language.
>> Dynamic reservation
is good, but allowing a chunk for the program is an acceptable
alternative.
What's "allowing a chunk for the program"?
In other compilers / platforms / languages I've used there is usually
one or more numeric (hex) settings which allows you to reserve a
"chunk" of memory for your program (executable), like fixed stack size
or initial stack size and a max stack size. Perhaps I am making
assumptions that C++ compilers work the same way.
They might work the same way, or they might not. C++ has no notion
of "reserving a chunk of memory", that's all. Any settings your C++
compiler has are off-topic because they are compiler- and platform-
specific. You need to read the FAQ to learn where to post your
questions depending on what part of your process you need to figure
out. For example, C++ compilers (most of them, anyway) are discussed
in their own newsgroups, like 'gnu.g++.help' or 'microsoft.public.vc.*'
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
<vf***@talktalk.netwrote in message
news:11**********************@d34g2000cwd.googlegr oups.com...
>
Victor Bazarov wrote:
>What do you mean by "reserve memory"? You either declare a static array,
or an automatic array, or a dynamic array. All those "reserve memory"
in some sense.
Currently I get a segmentation fault.
Exactly what code gave this behavior? If the code is large,
try to reduce it to something smaller (but still compilable)
that still gives the behavior, and post it here.
>Read FAQ 5.8.
Did you read that?
Believe me! It is caused by the array, because if I only reduce the
size it does not occur. It is some kind of stack overflow, someone
told me words to that effect.
That's a possibility, but note that different compilers can and do
produce different behavior for whatever the trouble really is.
>
Dynamic reservation
is good, but allowing a chunk for the program is an acceptable
alternative.
What's "allowing a chunk for the program"?
In other compilers / platforms / languages I've used there is usually
one or more numeric (hex) settings which allows you to reserve a
"chunk" of memory for your program (executable), like fixed stack size
or initial stack size and a max stack size.
Yes, these some of common ways to configure a compiler, but note that
each compiler has its own configuration capabilities.
Perhaps I am making
assumptions that C++ compilers work the same way.
Yes, you are, and those assumptions are invalid.
A (imo preferred) way to implement an array in C++ is to use
the 'std::vector' type, declared by the standard header <vector>.
This type will handle all memory management for you automatically,
e.g. it can 'grow' and 'shrink' to accomodate the storage requirements.
-Mike vf***@talktalk.net wrote:
mlimber wrote:
Use std::vector (cf.
http://www.parashift.com/c++-faq-lit...html#faq-34.1).
Cheers! --M
But does standard vector do O(1) access ?
In theory:
Bottom line, you cannot have dynamic structure and O(1) access without
some kind of garbage collection / defragmentation. And garbage
collection / defragmentation / paging algorithms imply greater than
O(1) complexity so at some point either it will multiply the
complexity. Which is why I want to use a fixed size structure.
In practice:
Try and convince us that the std::vector management is faster than a
single multiplication with memory access. vf***@talktalk.net wrote:
vf***@talktalk.net wrote:
>mlimber wrote:
>>>
Use std::vector (cf.
http://www.parashift.com/c++-faq-lit...html#faq-34.1).
Cheers! --M
But does standard vector do O(1) access ?
In theory:
Bottom line, you cannot have dynamic structure and O(1) access without
some kind of garbage collection / defragmentation. And garbage
collection / defragmentation / paging algorithms imply greater than
O(1) complexity so at some point either it will multiply the
complexity. Which is why I want to use a fixed size structure.
But std::vector *is* a fixed size structure at every point in time.
You don't have to change it if you know what size you need to begin with.
In practice:
Try and convince us that the std::vector management is faster than a
single multiplication with memory access.
WTF are you talking about? There is no such thing as "dynamic structure"
unless you mean a UDT instance with dynamic storage duration. And in
that case yes, access to its members (or elements, if it's an array) is
O(1). Amortized for creation/destruction of the structure itself, but
still O(1). How much faster do you need?
What book on C++ are you reading that doesn't explain how and when to use
std::vector?
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
But does standard vector do O(1) access ?
>
Yes. Inside it has a dynamic array... <snip>
Now you really are talking gibberish. Dynamic structures cannot have
O(1) random access (aka direct access), the best you can hope to get is
O(log n). vf***@talktalk.net wrote:
vf***@talktalk.net wrote:
mlimber wrote:
>
Use std::vector (cf.
http://www.parashift.com/c++-faq-lit...html#faq-34.1).
>
Cheers! --M
But does standard vector do O(1) access ?
In theory:
Bottom line, you cannot have dynamic structure and O(1) access without
some kind of garbage collection / defragmentation. And garbage
collection / defragmentation / paging algorithms imply greater than
O(1) complexity so at some point either it will multiply the
complexity. Which is why I want to use a fixed size structure.
In practice:
Try and convince us that the std::vector management is faster than a
single multiplication with memory access.
You are mistaken.
So long as the size of the structure will not change and you use
std::vector::reserve when you first create the vector, there is no
complexity issue. Nor is there any issue re garbage
collection/defragmentation/paging algorithm. The vector is guaranteed
to be contiguous in memory, will not move, will not be garbage
collected, will not be defragmented, etc.
Best regards,
Tom vf***@talktalk.net schrieb:
>>But does standard vector do O(1) access ?
Yes. Inside it has a dynamic array... <snip>
Now you really are talking gibberish. Dynamic structures cannot have
O(1) random access (aka direct access), the best you can hope to get is
O(log n).
Huh? Gibberish, as well.
std::vector allocates an array on the free store. The elements in this
array can be accessed in constant time, just as a plain array can.
It is a dynamic array, because std::vector handles resizeing of the array
automatically.
--
Thomas http://www.netmeister.org/news/learn2quote.html vf***@talktalk.net wrote:
>>But does standard vector do O(1) access ?
Yes. Inside it has a dynamic array... <snip>
Now you really are talking gibberish. Dynamic structures cannot have
I believe you're utterly confused. "Dynamic" in C++ has most likely
a different meaning than you are used to in your "dynamic structure"
expression. Learn C++ terminology, then we will be on the same page.
At this point it seems gibberish to you because you are still learning
C++. It will pass, but you have to make an effort.
O(1) random access (aka direct access), the best you can hope to get
is O(log n).
You're probably correct considering whatever meaning you put in your
"dynamic structures" term. You could begin by explaining your terms
or learning ours.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Thomas Tutone wrote:
vf***@talktalk.net wrote:
vf***@talktalk.net wrote:
mlimber wrote:
Use std::vector (cf.
http://www.parashift.com/c++-faq-lit...html#faq-34.1).
Cheers! --M
>
But does standard vector do O(1) access ?
In theory:
Bottom line, you cannot have dynamic structure and O(1) access without
some kind of garbage collection / defragmentation. And garbage
collection / defragmentation / paging algorithms imply greater than
O(1) complexity so at some point either it will multiply the
complexity. Which is why I want to use a fixed size structure.
In practice:
Try and convince us that the std::vector management is faster than a
single multiplication with memory access.
You are mistaken.
lol, it is not that simple as that...
>
So long as the size of the structure will not change and you use
std::vector::reserve when you first create the vector, there is no
complexity issue. Nor is there any issue re garbage
collection/defragmentation/paging algorithm. The vector is guaranteed
to be contiguous in memory, will not move, will not be garbage
collected, will not be defragmented, etc.
So below and at the initial size it (reserved std::vector) is "fixed"
and no longer "dynamic", hmm suspiciously like a fixed size array at
least to start with. And as soon as you append to this you are going
to get >O(1) complexity issues.
BTW I am using the word dynamic in the ordinary computer science sense
and I am not refering to the C++ reserved word.
Thomas J. Gritzan wrote:
vf***@talktalk.net schrieb:
>But does standard vector do O(1) access ?
Yes. Inside it has a dynamic array... <snip>
Now you really are talking gibberish. Dynamic structures cannot have
O(1) random access (aka direct access), the best you can hope to get is
O(log n).
Huh? Gibberish, as well.
I mean overall, including the "dynamic" processing...
std::vector allocates an array on the free store. The elements in this
array can be accessed in constant time, just as a plain array can.
OK, but then you say...
It is a dynamic array, because std::vector handles resizeing of the array
automatically.
So you are saying this resizing algorithm is done in O(1) time. In
theory that is not possible. vf***@talktalk.net wrote:
But does standard vector do O(1) access ?
Yes. Inside it has a dynamic array... <snip>
Now you really are talking gibberish. Dynamic structures cannot have
O(1) random access (aka direct access), the best you can hope to get is
O(log n).
You appear to be quite confused, and very unclear on the concept.
There are a couple of possibilities here.
One is that you are a troll.
The second is that you are simply very misguided. Assuming for the
sake of argument that it is the second, then I'm curious - where on
earth did you read that?
Best regards,
Tom vf***@talktalk.net wrote:
Thomas Tutone wrote:
vf***@talktalk.net wrote:
vf***@talktalk.net wrote:
>
mlimber wrote:
>
Use std::vector (cf.
http://www.parashift.com/c++-faq-lit...html#faq-34.1).
>
Cheers! --M
But does standard vector do O(1) access ?
>
In theory:
Bottom line, you cannot have dynamic structure and O(1) access without
some kind of garbage collection / defragmentation. And garbage
collection / defragmentation / paging algorithms imply greater than
O(1) complexity so at some point either it will multiply the
complexity. Which is why I want to use a fixed size structure.
>
In practice:
Try and convince us that the std::vector management is faster than a
single multiplication with memory access.
You are mistaken.
lol, it is not that simple as that...
So long as the size of the structure will not change and you use
std::vector::reserve when you first create the vector, there is no
complexity issue. Nor is there any issue re garbage
collection/defragmentation/paging algorithm. The vector is guaranteed
to be contiguous in memory, will not move, will not be garbage
collected, will not be defragmented, etc.
So below and at the initial size it (reserved std::vector) is "fixed"
and no longer "dynamic", hmm suspiciously like a fixed size array at
least to start with.
That's the point.
And as soon as you append to this you are going
to get >O(1) complexity issues.
You apparently do not understand what O(1) means.
>
BTW I am using the word dynamic in the ordinary computer science sense
and I am not refering to the C++ reserved word.
There is no such C++ reserved word.
Best regards,
Tom vf***@talktalk.net wrote:
>
Thomas Tutone wrote:
>vf***@talktalk.net wrote:
vf***@talktalk.net wrote:
mlimber wrote:
Use std::vector (cf.
http://www.parashift.com/c++-faq-lit...html#faq-34.1).
Cheers! --M
But does standard vector do O(1) access ?
In theory:
Bottom line, you cannot have dynamic structure and O(1) access without
some kind of garbage collection / defragmentation. And garbage
collection / defragmentation / paging algorithms imply greater than
O(1) complexity so at some point either it will multiply the
complexity. Which is why I want to use a fixed size structure.
In practice:
Try and convince us that the std::vector management is faster than a
single multiplication with memory access.
You are mistaken.
lol, it is not that simple as that...
>>
So long as the size of the structure will not change and you use
std::vector::reserve when you first create the vector, there is no
complexity issue. Nor is there any issue re garbage
collection/defragmentation/paging algorithm. The vector is guaranteed
to be contiguous in memory, will not move, will not be garbage
collected, will not be defragmented, etc.
So below and at the initial size it (reserved std::vector) is "fixed"
and no longer "dynamic", hmm suspiciously like a fixed size array at
least to start with. And as soon as you append to this you are going
to get >O(1) complexity issues.
Yes, there are complexity issues, but not at all with element access: that
is always O(1). However, you pay for it in the push_back() procedure:
whenever the vector needs to grow beyond its current capacity, it will
reallocate and possibly move (via copy construction followed by destruction
of originals) all its current objects. One can arrange that the *amortized*
time for an individual push_back() is still O(1), but some push_back()
calls will take linear time.
Best
Kai-Uwe Bux
In article <11**********************@k70g2000cwa.googlegroups .com>, vf***@talktalk.net says...
[ ... ]
In theory:
Bottom line, you cannot have dynamic structure and O(1) access without
some kind of garbage collection / defragmentation.
That's a theory I've never heard before. Do you have some support for
it, or is it an unsupported theory you've just formulated, or what
exactly?
And garbage
collection / defragmentation / paging algorithms imply greater than
O(1) complexity so at some point either it will multiply the
complexity. Which is why I want to use a fixed size structure.
The size of the structure and the method you use for allocating it are
entirely separate questions.
In practice:
Try and convince us that the std::vector management is faster than a
single multiplication with memory access.
Is that the royal "us", or do you have a mouse in your pocket? I haven't
seen any posts in this thread that seem to agree with you, so (at most)
somebody might be convincing you, not a group of people.
In any case, if you have a situation where a fixed-size allocation is
adequate, then std::vector will normally provide essentially equivalent
performance. You reserve that fixed amount of memory, and from there
about all it adds is (possibly) the fixed overhead of a pointer
dereference. This has no effect whosoever on the computation complexity
of its use.
std::vector can reallocate its memory, and doing so typically consumes
at least some time, though, contrary to the theory you give above, it
can still be O(1). I.e. it takes time, but the time can be constant,
regardless of the size of collection being managed (though, admittedly,
such an implementation won't be portable).
I'm not sure how multiplication came into the question, but generally
speaking, pointer dereferencing has lower overhead than multiplication.
It's a bit difficult to give a general proof of that, since it depends
on the CPU involved rather than any characteristic of the language.
Documentation on typical CPUs can be found at such places as
developer.intel.com, developer.amd.com, and so on (pick a site
appropriate the processor(s) that interest you).
--
Later,
Jerry.
The universe is a figment of its own imagination.
Victor Bazarov wrote:
vf***@talktalk.net wrote:
>But does standard vector do O(1) access ?
Yes. Inside it has a dynamic array... <snip>
Now you really are talking gibberish. Dynamic structures cannot have
I believe you're utterly confused. "Dynamic" in C++ has most likely
a different meaning than you are used to in your "dynamic structure"
expression. Learn C++ terminology, then we will be on the same page.
At this point it seems gibberish to you because you are still learning
C++. It will pass, but you have to make an effort.
O(1) random access (aka direct access), the best you can hope to get
is O(log n).
You're probably correct considering whatever meaning you put in your
"dynamic structures" term. You could begin by explaining your terms
or learning ours.
OK, I will spell it out for you, in computer science there are some
fundamental structures
- a linked list
- a fixed array
- a heap (or priority queue)
I use n to refer to the number of elements in the structure and O for
the complexity read as "of the order of".
A linked list has O(n) operations per random (direct) access, O(1)
operations per insert or append.
The array has O(1) operations per random (direct) access, O(1)
operations per insert.
The link list is a dynamic structure so it can grow and shrink, but is
stricly linear and cannot be accessed any faster (in general.) If you
use markers on it then stricly speaking it becomes something else like
a skip list or a heap.
A heap can be accessed faster than a list but still not as fast as an
array. http://en.wikipedia.org/wiki/Fibonacci_heap
Of course it is always possible to sort a structure, index it and then
subsequently get O(1) access. But sorting is O(n log n). Mainatining
a sorted structure implies a greater than O(1) operations per insert,
like O(log n).
Bottom line there is only one data structure that always has O(1)
access without any other overhead and that is a sorted linear
structure.. so an array or something equivalent like a hash table with
one element per bucket.
Probably the best overall general structure is a B-tree. Do you have
std::btree ?
In article <ef*********@murdoch.acc.Virginia.EDU>, jk********@gmx.net
says...
[ ... ]
One can arrange that the *amortized*
time for an individual push_back() is still O(1), but some push_back()
calls will take linear time.
In fact, the amortized constant complexity is required by the standard.
It's not necessarily true that some push_back calls will take linear
time -- with some constraints, it's possible to avoid even that (though
such an implementation isn't portable).
For example, using the virtual memory mechanism on most processors, you
can allocate address space and memory separately. You pre-allocate a
contiguous address space for the largest possible array size, and then
allocate memory to back it only when an address is actually accessed.
This way, you never need to copy data from one place to another -- you
just allocate more pages as the controlled vector grows.
The constraints on this are that (for example) there is ultimately some
maximum size of the array being controlled. Depending on the system that
may be the size of the physical memory in the system, or (in theory)
could be substantially larger, such as using virtual memory. There are
practical limits to that as well, of course, but they _are_ practical,
not theoretical -- with enough hard drive space of sufficient speed, for
at least some usage patterns, access speed doesn't _have_ to suffer at
all (though of course, few (if any) real systems allow using thousands
of disks in parallel to provide bandwidth close to that of solid-state
memory.
--
Later,
Jerry.
The universe is a figment of its own imagination. vf***@talktalk.net schrieb:
Thomas J. Gritzan wrote:
>std::vector allocates an array on the free store. The elements in this
array can be accessed in constant time, just as a plain array can.
OK, but then you say...
>It is a dynamic array, because std::vector handles resizeing of the array
automatically.
So you are saying this resizing algorithm is done in O(1) time. In
theory that is not possible.
No, I said that accessing elements is O(1).
Say we have a fixed array of size 100. You can access all 100 elements
randomly like this in constant time: arr[index].
Same with std::vector, it's like a fixed array.
Lets say you need 100 more elements in your fixed array. For that, you
would need to allocate an array of size 200, copy all 100 elements into the
new array, delete the old array. Exactly this does std::vector for you.
--
Thomas http://www.netmeister.org/news/learn2quote.html vf***@talktalk.net wrote:
>
Thomas J. Gritzan wrote:
>vf***@talktalk.net schrieb:
>>But does standard vector do O(1) access ?
Yes. Inside it has a dynamic array... <snip>
Now you really are talking gibberish. Dynamic structures cannot have
O(1) random access (aka direct access), the best you can hope to get is
O(log n).
Huh? Gibberish, as well.
I mean overall, including the "dynamic" processing...
>std::vector allocates an array on the free store. The elements in this
array can be accessed in constant time, just as a plain array can.
OK, but then you say...
>It is a dynamic array, because std::vector handles resizeing of the array
automatically.
So you are saying this resizing algorithm is done in O(1) time. In
theory that is not possible.
It is done in *amortized constand time* that is, if you start with an empty
vector and you do n insertions, the time c(n) to do all of them is still
bounded from above by a linear function in n. The way this works is roughly
as follows: at any given moment, the vector holds contiguous memory to
accommodate an array of 2^k elements of which the first m are used. If
m<2^k, push_back will just construct a new object in the m+1 slot. This
takes constant time. If m=2^k, the vector will allocate memory for 2^(k+1)
objects, copy the existing 2^k objects, destroy their originals and
construct a new object. The costs for this operation are roughly 2*m+1.
However, these additional costs occur only when m is a power of two. Thus,
we have the following costs:
m cost of push_back() within a vector of size m.
0 1
1 3
2 5
3 1
4 9
5 1
6 1
7 1
8 17
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 33
... ...
In this example, the total cost c(n) is bounded from above by 3n. Thus,
the "average" complexity for push_back is 3, i.e., constant.
Best
Kai-Uwe Bux vf***@talktalk.net wrote:
[..]
OK, I will spell it out for you, in computer science there are
[..blah blah blah..]
Stop.
You initially asked for a replacement for an automatic array. You
have been suggested 'std::vector'. To declare an array you need its
size to be a compile-time constant. Use the same constant to declare
your 'std::vector' object. Then, if you never cause the vector to
resize itself (there are known actions that can lead to reallocation),
you are *guaranteed* to have O(1) access to the elements of the vector.
And you don't have to "maintain" it in any way. It maintains itself.
If you don't believe me, I can't help it. I can only suggest testing
it. But I am not going to dispute this with you (although it seems
that it is what you're looking for, not a solution for your alleged
"10,000+" problem).
Probably the best overall general structure is a B-tree. Do you have
std::btree ?
I have *nothing*. Get a good book and learn what standard containers
exist, what for, and how to use them.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jerry Coffin wrote:
In article <11**********************@k70g2000cwa.googlegroups .com>,
vf***@talktalk.net says...
[ ... ]
In theory:
Bottom line, you cannot have dynamic structure and O(1) access without
some kind of garbage collection / defragmentation.
That's a theory I've never heard before. Do you have some support for
it, or is it an unsupported theory you've just formulated, or what
exactly?
And garbage
collection / defragmentation / paging algorithms imply greater than
O(1) complexity so at some point either it will multiply the
complexity. Which is why I want to use a fixed size structure.
The size of the structure and the method you use for allocating it are
entirely separate questions.
Why be pedantic ? I meant to say which is why I want to use a fixed
structure, yes fixed in size and position.
In practice:
Try and convince us that the std::vector management is faster than a
single multiplication with memory access.
Is that the royal "us", or do you have a mouse in your pocket? I haven't
seen any posts in this thread that seem to agree with you, so (at most)
somebody might be convincing you, not a group of people.
Ah, there is no need for personal insults. Yes, there are lots of
people that are educated enough to see through myths of the commercial
world.
In any case, if you have a situation where a fixed-size allocation is
adequate, then std::vector will normally provide essentially equivalent
performance. You reserve that fixed amount of memory, and from there
about all it adds is (possibly) the fixed overhead of a pointer
dereference.
Fine, now I know that you can reserve std::vector and use it as a fixed
structure, I am feeling that you are implying that it is "practically
isomorphic to a fixed array"
provided I don't go and append to it.. which is fine I don't believe in
magic.
This has no effect whosoever on the computation complexity
of its use. That is
std::vector can reallocate its memory, and doing so typically consumes
at least some time, though, contrary to the theory you give above, it
can still be O(1). I.e. it takes time, but the time can be constant,
regardless of the size of collection being managed
Is that the same sort of "O(1)" like the "O(1) multiplication" on Intel
chips, until someone points out that numbers can have more than 64
digits, and then you say well 128bit multiplication can be done in 0(8)
and by then by some sort of magic computer engineer fuzzy logic O(1) =
O(8)...
Oh you did say...
(though, admittedly,
such an implementation won't be portable).
Sorry but usually O refers to something general, which is why
Complexity Analysis does not have a little "TM" after it.. at least not
yet, lol.
(though, admittedly,
such an implementation won't be portable).
As soon as you resize this std::vector (in general) either it will
loose its contigous property
in which case it will take more than O(1) to access or the second
possibility is that it gets collection / defrag / sifting (whatever)
which implies an algorithm which implies >O(1) complexity.
I'm not sure how multiplication came into the question, but generally
speaking, pointer dereferencing has lower overhead than multiplication.
It's a bit difficult to give a general proof of that, since it depends
on the CPU involved rather than any characteristic of the language.
Documentation on typical CPUs can be found at such places as
developer.intel.com, developer.amd.com, and so on (pick a site
appropriate the processor(s) that interest you).
collection / defrag / sifting (whatever) requires more than a few
pointer dereferences.
Integer multiplication (or some mathematically equivalent operation) is
used to determine the memory address of an array element from its
index. If you know of some faster way than multiplication, which can
be done in
O(n ln(n) ln(ln(n))) here n denotes the number of digits (~64) and not
the size.. so in very fast.
Jerry Coffin wrote:
In article <ef*********@murdoch.acc.Virginia.EDU>, jk********@gmx.net
says...
[ ... ]
>One can arrange that the *amortized*
time for an individual push_back() is still O(1), but some push_back()
calls will take linear time.
In fact, the amortized constant complexity is required by the standard.
It's not necessarily true that some push_back calls will take linear
time -- with some constraints, it's possible to avoid even that (though
such an implementation isn't portable).
[interesting details snipped]
Thanks for catching that, I was a little sloppy there.
Best
Kai-Uwe Bux vf***@talktalk.net wrote:
>
>This has no effect whosoever on the computation complexity
of its use. That is
std::vector can reallocate its memory, and doing so typically consumes
at least some time, though, contrary to the theory you give above, it
can still be O(1). I.e. it takes time, but the time can be constant,
regardless of the size of collection being managed
Is that the same sort of "O(1)" like the "O(1) multiplication" on Intel
chips, until someone points out that numbers can have more than 64
digits, and then you say well 128bit multiplication can be done in 0(8)
and by then by some sort of magic computer engineer fuzzy logic O(1) =
O(8)...
Now it's clear that you don't know what you're talking about. O(1) *is*
the same as O(8). Perhaps you should review the precise meaning of the
big Oh symbol?
>
As soon as you resize this std::vector (in general) either it will
loose its contigous property
in which case it will take more than O(1) to access or the second
possibility is that it gets collection / defrag / sifting (whatever)
which implies an algorithm which implies >O(1) complexity.
Implies >O(1) complexity of *what*? Accessing an element of a vector is
guaranteed to be O(1). Always. Resizing a vector may be O(n) however,
as Kai-Uwe Bux explained already, if the vector is only resized to
accommodate insertions and is always resized my a multiplicative factor,
then this is amortized O(1).
Mark
"vf***@talktalk.net" <vf***@talktalk.netwrites:
[...]
Why be pedantic ? I meant to say which is why I want to use a fixed
structure, yes fixed in size and position.
I think one of the problems we're all having here is that you are
using some very strange English syntax. No criticism, many people
here only speak English as their second or third language. But be
aware that many of us are having a very hard time understanding you.
For example...
Ah, there is no need for personal insults. Yes, there are lots of
people that are educated enough to see through myths of the
commercial world.
This comment is very strange. "Myths of the commercial world" has
not entered in this conversation. When you make staments like this,
people are inclined to think you're a troll.
And BTW the correct response to an insult in these forums is _not_
to return it.
Fine, now I know that you can reserve std::vector and use it as a
fixed structure, I am feeling that you are implying that it is
"practically isomorphic to a fixed array" provided I don't go and
append to it.. which is fine I don't believe in magic.
Again, I don't know what your last comment about magic means. But
yes, as long as you don't do anything that changes the size of the
vector, it _is_ isomorphic with a built-in, dynamically allocated,
array. Or even a built-in, static array.
When you append to a std::vector, you're doing something that no
sort of built-in array supports.
Is that the same sort of "O(1)" like the "O(1) multiplication" on
Intel chips, until someone points out that numbers can have more
than 64 digits, and then you say well 128bit multiplication can be
done in 0(8) and by then by some sort of magic computer engineer
fuzzy logic O(1) = O(8)...
Sir, I think you are very confused or mistaken about what the "Big
Oh" notation means. O(8) is not exactly nonsensical, but
meaningless. O(1) means exactly the same thing as O(8) which means
exactly the same thing as O(1e17).
It is not a statement about how many clock cycles it takes something
to happen. It is a statement about the asymptotic run-time of an
operation as a function of the size of the input data.
O(1), O(8), and O(1e17) mean "constant time". The time to carry out
the operation is independent of the number of elements in the
container. Accessing an element for built-in arrays, and for
std::vector, under all circumstances, is O(1), meaning it doesn't
depend on how many elements are in the container.
The "Big O" notation is meant to be used to compare O(1)
(e.g. constant) to O(log N), or O(N), or O(N^2), and so forth.
As soon as you resize this std::vector (in general) either it will
loose its contigous property
in which case it will take more than O(1) to access or the second
possibility is that it gets collection / defrag / sifting (whatever)
which implies an algorithm which implies >O(1) complexity.
The standard guarantees that vectors never loose their contiguity.
Resizing a vector may, repeat _may_, trigger reallocation and
copying. These operations are generally O(N) (although they may be
faster on some hardware), regardless of whether they are done by
std::vector, or by you personally. If you don't want to pay this
run-time cost, don't resize your arrays.
These issues, by the way, are clearly documented by the C++ standard
and any decent textbook, and common knowledge in the C++ community,
which is approximately what you're talking to in this forum. When
all the experts say you're confused, it's generally a sign to go
read the textbooks more carefully.
----------------------------------------------------------------------
Dave Steffen, Ph.D.
Software Engineer IV Disobey this command!
Numerica Corporation - Douglas Hofstadter
dgsteffen at numerica dot us vf***@talktalk.net schrieb:
Jerry Coffin wrote:
>This has no effect whosoever on the computation complexity
of its use. That is
std::vector can reallocate its memory, and doing so typically consumes
at least some time, though, contrary to the theory you give above, it
can still be O(1). I.e. it takes time, but the time can be constant,
regardless of the size of collection being managed
Is that the same sort of "O(1)" like the "O(1) multiplication" on Intel
chips, until someone points out that numbers can have more than 64
digits, and then you say well 128bit multiplication can be done in 0(8)
and by then by some sort of magic computer engineer fuzzy logic O(1) =
O(8)...
Yeah, O(8) equals O(1) equals O(100000). O(1) (or constant time) doesn't
mean that it is fast. It just says that it is independet of the number of
elements.
>(though, admittedly,
such an implementation won't be portable).
As soon as you resize this std::vector (in general) either it will
loose its contigous property
in which case it will take more than O(1) to access or the second
possibility is that it gets collection / defrag / sifting (whatever)
which implies an algorithm which implies >O(1) complexity.
std::vector stays contiguous.
The resizing will usually copy all elements to a new storage position,
which is O(n). But it is possible, on some platforms, to implement it
without copying and without fragmenting the memory. But since it depends on
the operation system and the architecture, it is offtopic in this C++ group.
collection / defrag / sifting (whatever) requires more than a few
pointer dereferences.
Integer multiplication (or some mathematically equivalent operation) is
used to determine the memory address of an array element from its
index. If you know of some faster way than multiplication, which can
be done in
O(n ln(n) ln(ln(n))) here n denotes the number of digits (~64) and not
the size.. so in very fast.
Huh? I can't follow the discussion flow here.
It's time that you stop assuming things and start reading a good C++ book.
Looking back to the original posting, the problem was that a large array in
automatic storage results in a segmentation fault. The cause is the small
default stack size on actual operation systems. You can solve it by
allocating the array on the free store, which does std::vector for you,
managing the new[] and delete[].
--
Thomas http://www.netmeister.org/news/learn2quote.html
Thomas Tutone wrote:
There are a couple of possibilities here.
One is that you are a troll.
You guys may want to review this thread, at which time I plonked the
individual in question:
< http://groups.google.com/group/comp....hread/307f580f
5b5fb1b7>
This probably wrapped in some unpleasant fashion. Sorry.
Brian
"Default User" <de***********@yahoo.comwrites:
Thomas Tutone wrote:
There are a couple of possibilities here.
One is that you are a troll.
You guys may want to review this thread, at which time I plonked the
individual in question:
<http://groups.google.com/group/comp.lang.c++/browse_frm/thread/307f580f5b5fb1b7>
Ah, yes. Thanks. OP PLONKed.
----------------------------------------------------------------------
Dave Steffen, Ph.D.
Software Engineer IV Disobey this command!
Numerica Corporation - Douglas Hofstadter
dgsteffen at numerica dot us
Thomas J. Gritzan wrote:
vf***@talktalk.net schrieb:
Jerry Coffin wrote:
This has no effect whosoever on the computation complexity
of its use. That is
std::vector can reallocate its memory, and doing so typically consumes
at least some time, though, contrary to the theory you give above, it
can still be O(1). I.e. it takes time, but the time can be constant,
regardless of the size of collection being managed
Is that the same sort of "O(1)" like the "O(1) multiplication" on Intel
chips, until someone points out that numbers can have more than 64
digits, and then you say well 128bit multiplication can be done in 0(8)
and by then by some sort of magic computer engineer fuzzy logic O(1) =
O(8)...
Yeah, O(8) equals O(1) equals O(100000). O(1) (or constant time) doesn't
mean that it is fast. It just says that it is independet of the number of
elements.
(though, admittedly,
such an implementation won't be portable).
As soon as you resize this std::vector (in general) either it will
loose its contigous property
in which case it will take more than O(1) to access or the second
possibility is that it gets collection / defrag / sifting (whatever)
which implies an algorithm which implies >O(1) complexity.
std::vector stays contiguous.
The resizing will usually copy all elements to a new storage position,
which is O(n). But it is possible, on some platforms, to implement it
without copying and without fragmenting the memory. But since it depends on
the operation system and the architecture, it is offtopic in this C++ group.
collection / defrag / sifting (whatever) requires more than a few
pointer dereferences.
Integer multiplication (or some mathematically equivalent operation) is
used to determine the memory address of an array element from its
index. If you know of some faster way than multiplication, which can
be done in
O(n ln(n) ln(ln(n))) here n denotes the number of digits (~64) and not
the size.. so in very fast.
Huh? I can't follow the discussion flow here.
OK I'll do some substitution and make it easier for you to compare.
My point is that multiplication of two numbers x and y less than m is
much faster than O(m).
It is actually O(m ln(m) ln(ln(m))) where m~log(n)
So in theory for a general test we should be comparing
O(n) (re std::vector) and O(ln(n)*ln(ln(n))*ln(ln(ln(n)))) (re array)
Also an operation of "copying elements" as you call it is theoretically
and practically more complex than the bitwise operations involved in
multiplication.
The right hand expression is practically a constant. OK, the fetch time
is probably slower in practice...but a whole O(n) slower I doubt.
>
It's time that you stop assuming things and start reading a good C++ book.
My only assumption was that std::vector is dynamic and now I've learnt
that it is not dynamic if you program it with a fixed initial size and
then you don't append to it.
The C++ books I've seen (admittedly I've not seen many) don't cover
complexity analysis in reference to the STL.
Looking back to the original posting, the problem was that a large array in
automatic storage results in a segmentation fault. The cause is the small
default stack size on actual operation systems. You can solve it by
allocating the array on the free store, which does std::vector for you,
managing the new[] and delete[].
--
Thomas
http://www.netmeister.org/news/learn2quote.html
Great but you won't convince people that O(n) <
O(ln(n)*ln(ln(n))*ln(ln(ln(n))))
not now or in the future, which is what you are implying by saying that
std::vector is in general better than a fixed array. Here is even a
table for you...
n ln(n)*ln(ln(n))*ln(ln(ln(n)))
50 21.1743
100 64.6642
150 115.357
200 170.494
250 228.83
300 289.655
350 352.511
400 417.079
450 483.124
500 550.466
550 618.963
600 688.5
650 758.983
700 830.331
750 902.478
800 975.366
850 1048.94
900 1123.17
950 1198
1000 1273.4
1050 1349.34
1100 1425.8
1150 1502.74
1200 1580.15
1250 1658
1300 1736.27
1350 1814.96
1400 1894.03
1450 1973.47
1500 2053.28
1550 2133.44
1600 2213.93
1650 2294.74
1700 2375.87
1750 2457.3
1800 2539.03
1850 2621.04
1900 2703.33
1950 2785.89
2000 2868.71
No one here said that a reserved std::vector is as fast as fixed array.
In article <11**********************@h48g2000cwc.googlegroups .com>, vf***@talktalk.net says...
[ ... ]
Why be pedantic ? I meant to say which is why I want to use a fixed
structure, yes fixed in size and position.
You start talk about things like the time taken to carry out
multiplication of n-bit numbers, and then turn around and say "Why be
pedantic?"
I honestly don't care whether you want to be practical or pedantic, but
you really do need to make up your mind: if you want to be pedantic,
then it's a pedantic discussion, and I'll be pedantic too. If you want
a practical discussion, I have no problem with being practical as well.
Which do you really want?
Is that the same sort of "O(1)" like the "O(1) multiplication" on Intel
chips, until someone points out that numbers can have more than 64
digits, and then you say well 128bit multiplication can be done in 0(8)
and by then by some sort of magic computer engineer fuzzy logic O(1) =
O(8)...
Pardon me, but if you think O(1) is NOT equal to O(8), then you simply
don't understand big-O notation at all. O(K) (where K is any constant)
means constant complexity, which in big-O terms means the two ARE equal.
Ultimately, multiplication is quadratic -- i.e. to multiply two k bit
numbers requires no more than k**2 operations. If you honestly want to
get into serious detail about things like this, I'd suggest _A Course in
Number Theory and Cryptography (Second Edition)_ by Neal Koblitz
[Springer-Verlag, ISBN: 0-387-945293-9].
Converting from pure computational complexity to time, however, is
somewhat tricky. For an obvious example, a digital computer typically
has a clock, and any operation takes a minimum of one clock. Depending
on the clock speed, you can carry out a more or less arbitrary number of
operations during a single clock, and since you can't get any result in
less than one clock, a variable number of operations up to some limit
take (or at least appear to take) constant time.
Oh you did say...
(though, admittedly,
such an implementation won't be portable).
Sorry but usually O refers to something general, which is why
Complexity Analysis does not have a little "TM" after it.. at least not
yet, lol.
Big-O notation is used for all sorts of things, with varying levels of
portability. The algorithms involved in this particular case are quite
general, but difficult or impossible to express portably in most current
programming languages.
(though, admittedly,
such an implementation won't be portable).
As soon as you resize this std::vector (in general) either it will
loose its contigous property
in which case it will take more than O(1) to access or the second
possibility is that it gets collection / defrag / sifting (whatever)
which implies an algorithm which implies >O(1) complexity.
No, that's simply not correct. Access to items in a vector is always O
(1) -- no matter what. Inserting an item into a vector is required to be
no worse than amortized constant time as well, but may be constant time,
with no "amortization" needed. Your belief that something involved
implies greater than constant complexity is simply incorrect and
unfounded.
I'm not sure how multiplication came into the question, but generally
speaking, pointer dereferencing has lower overhead than multiplication.
It's a bit difficult to give a general proof of that, since it depends
on the CPU involved rather than any characteristic of the language.
Documentation on typical CPUs can be found at such places as
developer.intel.com, developer.amd.com, and so on (pick a site
appropriate the processor(s) that interest you).
collection / defrag / sifting (whatever) requires more than a few
pointer dereferences.
There's no requirement for "collection /defrag /sifting" involved, so
your comment is simply a non-sequiter.
Integer multiplication (or some mathematically equivalent operation) is
used to determine the memory address of an array element from its
index.
Sometimes, under some circumstances. Then again, there's not necessarily
any requirement for any such thing.
From a theoretical viewpoint, nearly all of your arguments lack
foundation and the way you're arguing them shows ignorance of at least
the usual notation used in the area.
From a practical viewpoint, your whole point is basically nonsense: for
any situation in which a fixed-size allocation is adequate, a vector
provides performance nearly indistinguishable from a built-in array.
For one example, here's a small test I originally put together back when
vector was new and I had some doubts about it:
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
const int size = 200000;
typedef unsigned long ul;
void report(char const *title, clock_t ticks) {
printf("%s took %f seconds\n",
title,
ticks/(double)CLOCKS_PER_SEC);
}
void wait() {
while (clock() == clock())
;
}
using namespace std;
int main(void) {
static int array1[size];
static int array2[size];
srand(time(NULL));
for (int i=0; i<size; i++)
array1[i] = rand();
const int iterations = 100;
clock_t total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
sort(array2, array2+size);
total += clock()- start;
}
report("sort", total);
total = 0;
for (int i=0; i<iterations; i++) {
vector<intarray3(array1, array1+size);
wait();
clock_t start = clock();
sort(array3.begin(), array3.end());
total += clock()-start;
}
report("sort (vector)", total);
return 0;
}
This originally included a comparison to qsort, but you don't seem
interested in that, so I pulled it out. I'd also note that this is OLD
code -- I would NOT code it this way anymore. Among other things, it
predated the addition of namespaces, so when they came along I just
added the 'using namespace std;' directive. It also uses the <*.hC
headers instead of the <c*headers. If I was doing it today, I'd
probably work at eliminating the duplication of code between the two
sorts.
Anyway, the result is what we're after in this case. On my machine, the
output is:
sort took 1.582000 seconds
sort (vector) took 1.566000 seconds
While I doubt that using a vector is consistently faster than using an
array, it seems pretty clear to me that it's not enough slower to care
about either.
--
Later,
Jerry.
The universe is a figment of its own imagination. vf***@talktalk.net schrieb:
Thomas J. Gritzan wrote:
>Huh? I can't follow the discussion flow here.
OK I'll do some substitution and make it easier for you to compare.
My point is that multiplication of two numbers x and y less than m is
much faster than O(m).
It is actually O(m ln(m) ln(ln(m))) where m~log(n)
So in theory for a general test we should be comparing
O(n) (re std::vector) and O(ln(n)*ln(ln(n))*ln(ln(ln(n)))) (re array)
Also an operation of "copying elements" as you call it is theoretically
and practically more complex than the bitwise operations involved in
multiplication.
You compare apples with cars. What have "copying elements" to do with
multiplications?
Well, I'll go learning how to set up my killfile.
--
Thomas http://www.netmeister.org/news/learn2quote.html
Overall I agree.
Jerry Coffin wrote:
In article <11**********************@h48g2000cwc.googlegroups .com>,
vf***@talktalk.net says...
[ ... ]
Why be pedantic ? I meant to say which is why I want to use a fixed
structure, yes fixed in size and position.
You start talk about things like the time taken to carry out
multiplication of n-bit numbers, and then turn around and say "Why be
pedantic?"
Because multiplication is entirely relevant to a discussion about
direct access.
I honestly don't care whether you want to be practical or pedantic, but
you really do need to make up your mind: if you want to be pedantic,
then it's a pedantic discussion, and I'll be pedantic too. If you want
a practical discussion, I have no problem with being practical as well.
Which do you really want?
A less condescending tone.
Is that the same sort of "O(1)" like the "O(1) multiplication" on Intel
chips, until someone points out that numbers can have more than 64
digits, and then you say well 128bit multiplication can be done in 0(8)
and by then by some sort of magic computer engineer fuzzy logic O(1) =
O(8)...
Pardon me, but if you think O(1) is NOT equal to O(8), then you simply
don't understand big-O notation at all. O(K) (where K is any constant)
means constant complexity, which in big-O terms means the two ARE equal.
I know O(c)=O(1), but I thought some people here did not, sorry my
mistake.
Ultimately, multiplication is quadratic -- i.e. to multiply two k bit
numbers requires no more than k**2 operations.
Yes. k is O(ln(n)).
Fast multiplication such as using discrete FFT is
O(ln(n)*ln(ln(n))*ln(ln(ln(n))) < O(ln(n)*ln(n)) http://en.wikipedia.org/wiki/Multiplication_algorithm
If you honestly want to
get into serious detail about things like this, I'd suggest _A Course in
Number Theory and Cryptography (Second Edition)_ by Neal Koblitz
[Springer-Verlag, ISBN: 0-387-945293-9].
I've written FFT multiplication of polynomials over a ring or field
(sorry I forget which ,it was is was about 15 years ago) so I know the
basics.
Converting from pure computational complexity to time, however, is
somewhat tricky. For an obvious example, a digital computer typically
has a clock, and any operation takes a minimum of one clock. Depending
on the clock speed, you can carry out a more or less arbitrary number of
operations during a single clock, and since you can't get any result in
less than one clock, a variable number of operations up to some limit
take (or at least appear to take) constant time.
Oh you did say...
(though, admittedly,
such an implementation won't be portable).
>
Sorry but usually O refers to something general, which is why
Complexity Analysis does not have a little "TM" after it.. at least not
yet, lol.
Big-O notation is used for all sorts of things, with varying levels of
portability. The algorithms involved in this particular case are quite
general, but difficult or impossible to express portably in most current
programming languages.
(though, admittedly,
such an implementation won't be portable).
As soon as you resize this std::vector (in general) either it will
loose its contigous property
in which case it will take more than O(1) to access or the second
possibility is that it gets collection / defrag / sifting (whatever)
which implies an algorithm which implies >O(1) complexity.
No, that's simply not correct. Access to items in a vector is always O
(1) -- no matter what. Inserting an item into a vector is required to be
no worse than amortized constant time as well, but may be constant time,
with no "amortization" needed. Your belief that something involved
implies greater than constant complexity is simply incorrect and
unfounded.
Amortized O(1) is not the same as non amortized O(1). Amortized means
you divide by n, lol, that is commonly known as cheating.
I'm not sure how multiplication came into the question, but generally
speaking, pointer dereferencing has lower overhead than multiplication.
It's a bit difficult to give a general proof of that, since it depends
on the CPU involved rather than any characteristic of the language.
Documentation on typical CPUs can be found at such places as
developer.intel.com, developer.amd.com, and so on (pick a site
appropriate the processor(s) that interest you).
>
collection / defrag / sifting (whatever) requires more than a few
pointer dereferences.
There's no requirement for "collection /defrag /sifting" involved, so
your comment is simply a non-sequiter.
Don't be pedantic, "copying elements" then, how was I to know the
process used by std::vector. Besides which "collection" is close
enough, argueing this you conveniently miss my point:
All such operations ARE >O(1), usually at least O(log n) or O(n) and
that is the "real macoy" big oh and not the "cheaters" amortised one.
In this case copying elements is O(n).
Integer multiplication (or some mathematically equivalent operation) is
used to determine the memory address of an array element from its
index.
Sometimes, under some circumstances. Then again, there's not necessarily
any requirement for any such thing.
From a theoretical viewpoint, nearly all of your arguments lack
foundation and the way you're arguing them shows ignorance of at least
the usual notation used in the area.
I do have a good understanding of big oh.
From a practical viewpoint, your whole point is basically nonsense: for
any situation in which a fixed-size allocation is adequate, a vector
provides performance nearly indistinguishable from a built-in array.
For one example, here's a small test I originally put together back when
vector was new and I had some doubts about it:
<snip>
Thanks for the code, although I get compilation errors with mine.
sort took 1.582000 seconds
sort (vector) took 1.566000 seconds
While I doubt that using a vector is consistently faster than using an
array, it seems pretty clear to me that it's not enough slower to care
about either.
Fair enough, while the std::vector is not resized I believe you. vf***@talktalk.net wrote :
If I have a large array 10,000+ elements then how do I reserve memory
for this ? Currently I get a segmentation fault. Dynamic reservation
is good, but allowing a chunk for the program is an acceptable
alternative.
Such a big array should probably be on the freestore rather than on
automatic memory.
You can dynamically allocate arrays using the new[] operator, but then
you need to free them with delete[].
Or you can use std::vector, which wraps new[], automatically calls
delete[] in its destructor, and that also allows smart resizing and
other stuff.
Thomas J. Gritzan wrote:
vf***@talktalk.net schrieb:
Thomas J. Gritzan wrote:
Huh? I can't follow the discussion flow here.
OK I'll do some substitution and make it easier for you to compare.
My point is that multiplication of two numbers x and y less than m is
much faster than O(m).
It is actually O(m ln(m) ln(ln(m))) where m~log(n)
So in theory for a general test we should be comparing
O(n) (re std::vector) and O(ln(n)*ln(ln(n))*ln(ln(ln(n)))) (re array)
Also an operation of "copying elements" as you call it is theoretically
and practically more complex than the bitwise operations involved in
multiplication.
You compare apples with cars. What have "copying elements" to do with
multiplications?
In a way yes, I am being "devils advocate" worst case using std::vector
(dynamically) vs worst case using a fixed array. But it is valid to
compare such operations, because they both compile down to O(1) CPU
instructions. I admit it is not valid to compare timings of those, but
then you would not do that would you, you would time the overall code.
Well, I'll go learning how to set up my killfile.
--
Thomas
http://www.netmeister.org/news/learn2quote.html vf***@talktalk.net wrote:
Amortized O(1) is not the same as non amortized O(1).
True.
Amortized means you divide by n, lol, that is commonly known as cheating.
Yes, but what you divide by n is the cost for a total of n operations. That
is not cheating, it's called averaging.
Best
Kai-Uwe Bux
In article <11**********************@e3g2000cwe.googlegroups. com>, vf***@talktalk.net says...
[ ... ]
Because multiplication is entirely relevant to a discussion about
direct access.
No, it's really not. In particular, if scaling via multiplication needs
to be done, it'll be the same for a vector as for an array. As such,
multiplication really isn't worth discussing under the circumstances.
[ ... ]
Which do you really want?
A less condescending tone.
Then quit acting in a way that demands it.
I know O(c)=O(1), but I thought some people here did not, sorry my
mistake.
This seems (to me) a direct contradiction of your earlier statements.
[ ... ]
Amortized O(1) is not the same as non amortized O(1).
This much is true.
Amortized means
you divide by n, lol, that is commonly known as cheating.
No, it is known as averaging. Cheating implies breaking some kind of
rules -- and this doesn't do anything of the sort. Your claim that it's
cheating implies that you have the authority to make all the rules, and
anything you don't like is cheating. That's simply not the case. In
computer science (as with math in the more general sense) the rules are
simply a set of precepts. In a mathematical proof, they're stated as
axioms -- and it's generally agreed that they're unprovable. The
accuracy of a proof depends only on whether the axioms can be combined
in a way that leads inexorably to the final conclusion.
Depending on the axioms you start from, you get different kinds of math.
For example, the greeks agreed on one set of axioms that defined what is
now known as plane geometry. Since then, other sets of axioms have been
devised that have led to different types of geometry -- but neither set
is right or wrong. They're merely used to describe different systems.
The real question here is whether a mathematical system that includes
amortized constant time is sufficiently close to what you work with in
the real world that it is interesting or not. Many of us have found that
given the size of memory in current computers (among other things) that
it is a useful measurement. It might not be particularly applicable to
other circumstances -- but "inapplicable" is hardly synonymous with
"cheating."
[ ... ]
collection / defrag / sifting (whatever) requires more than a few
pointer dereferences.
There's no requirement for "collection /defrag /sifting" involved, so
your comment is simply a non-sequiter.
Don't be pedantic, "copying elements" then, how was I to know the
process used by std::vector.
You started by asking about a replacement for a fixed-size array. For
that situation, the time taken to resize a vector is totally, entirely,
100% irrelevant -- a fixed-size array can't be resized, and when used as
a direct replacement for a fixed-size array, the vector obviously won't
be resized either.
Under these circumstances, no copying of elements in the vector is ever
necessasry. On the theoretical side, there is NO difference in
computational complexity between accessing an element in a vector versus
accessing an element in an array. On the practical side, there seems to
be no difference in measured speed between accessing elements in a
vector versus an array.
You originally claimed that you could not replace a fixed-size array
with a vector because the computational complexity in accessing an
element in an vector was unavoidably higher than the computatinoal
complexity of accessing an element in an array. You can try to avoid it
and obfuscate it all you want, but the simple fact is that you were dead
wrong. Under the circumstances you described, the two operate with
identical computational complexity. period. full stop. Whatever
expression you prefer.
From a practical viewpoint, it's possible for there to be a minute
difference in speed. On most machines, this is likely to be immeasurably
small, if it exists at all. The place you'd be most likely to see it
would be an _extremely_ small machine in which the main memory is
roughly the same speed as the CPU itself (e.g. an embedded CPU using
only static RAM). IME, such a machine is unlikely to be a suitable
target for C++ in any case.
All such operations ARE >O(1), usually at least O(log n) or O(n) and
that is the "real macoy" big oh and not the "cheaters" amortised one.
In this case copying elements is O(n).
I've already addressed this. You're not in a position to set by fiat the
rules by which all must live, or anything on that order. In any case,
when you're using an vector as a replacement for a fixed-size array,
this all entirely irrelevant in any case.
[ ... ]
I do have a good understanding of big oh.
Not to put too fine a point on it, the posts I've seen you make thus far
do not make this claim particularly believable.
[ ... ]
Thanks for the code, although I get compilation errors with mine.
Please post the exact errors you're receiving, and identify the compiler
you're using. If you can't get that to compile, I'm reasonably certain
there's a fairly serious problem either with your compiler, or with how
you're using it.
--
Later,
Jerry.
The universe is a figment of its own imagination.
The amortized term is still a bullshit term. Just because someone
coined a term does not mean we should all use it.
Jerry Coffin wrote:
In article <11**********************@e3g2000cwe.googlegroups. com>,
vf***@talktalk.net says...
"copying elements"
All such operations ARE >O(1), usually at least O(log n) or O(n) and
that is the "real macoy" big oh and not the "cheaters" amortised one.
In this case copying elements is O(n).
<snip>
If you disagree with that then you must agree with the converse which
is that
copying elements is <= O(1) non-amortized.
That is last statement is cleary false.
You agree with false statement, so you are wrong.
I do have a good understanding of big oh.
Not to put too fine a point on it, the posts I've seen you make thus far
do not make this claim particularly believable.
I've just shown that I have a better understanding than you, by proving
you wrong.
I refer to cheaters, being people that confuse others by conveniently
dropping terms like "amortized" to make things look better than they
really are, for their own personal gain. Imagine how preposterous it
would be if some athletes went around saying "my time for the 100m is
0.1", then when someone said that is impossible they conveniently
turned around and changed their tune to "my amortized time for the 100m
is 0.1, you are wrong."
Please post the exact errors you're receiving, and identify the compiler
you're using. If you can't get that to compile, I'm reasonably certain
there's a fairly serious problem either with your compiler, or with how
you're using it.
--
I will look elsewhere in future. vf***@talktalk.net wrote:
I refer to cheaters, being people that confuse others by conveniently
dropping terms like "amortized" to make things look better than they
really are, for their own personal gain. Imagine how preposterous it
would be if some athletes went around saying "my time for the 100m is
0.1", then when someone said that is impossible they conveniently
turned around and changed their tune to "my amortized time for the 100m
is 0.1, you are wrong."
This impression on your part is due to the fact that you first asked very
specifically about *access* in std::vector. That is constant time (not
amortized!). Then the discussion went on to other operations and there we
find amortized complexity bounds. It's not like you have been cheated by
someone who at a later point told you: "oh, did I forget to mention that it
was amortized". Access to elements in std::vector is constant time --
indepentend of the length of the vector. Always and not amortized!
Best
Kai-Uwe Bux vf***@talktalk.net wrote:
Where on this page does it mention amortized ?
http://en.wikipedia.org/wiki/Big-O_notation
Why should a page on O-notation mention amortized time? The notion of
amortized time is completely independent from O-notation, which is a purely
mathematical concept: given two real-valued functions f and g defined on
positive integers (or positive reals), one says f = O(g) if there is are
constants C and K such that f(x) <= C*g(x) + K for all x sufficiently
large. As such, this does not, in any way relate to some meanings that f an
g may or may not have outside mathematics. In particular, you can use
O-notations to describe relate all sorts of cost functions that occur in
computer science to all sorts of complexity functions for inputs
* worst case runtime as O( f( input-length ) )
* expected/average runtime
* amortized runtime
* worst case space consumption
* ...
In particular, it makes sense to describe the amortized run-time of
push_back() in std::vector and the worst-case run-time for operator[] in
std::vector as O(1).
"Amortized" is a misleading and non standard term.
It is a standard term in computer science (not in math). Also, it is not
misleading since it is a purely technical term that has a precise
definition and lacks any connotations. You may prefer constant time
algorithms to amortized constant time algorithms for whichever reasons, but
that does not mean that amortized constant time is false advertising.
Best
Kai-Uwe Bux
In article <11**********************@h48g2000cwc.googlegroups .com>, vf***@talktalk.net says...
Where on this page does it mention amortized ?
http://en.wikipedia.org/wiki/Big-O_notation
In the references. This page refers to _Introduction to Algorithms
(Second Edition)_ by Cormen, Leiserson, Rivest and Stein. Chapter 17 of
that book is titled "Amortized Analysis", and is devoted (surprise,
surprise) to amortized analysis of algorithms. Of course, amortized
analysis is used elsewhere in the book as well (the index entry of
"amortized analysis" has 19 sub-entries in addition to the reference to
chapter 17).
The authoritative reference for C++ is the ISO 14882, 2003 (second
edition). It uses the term in about a half dozen places, some of which
(e.g. section 23.1.1/12) apply to a rather large number of containers.
"Amortized" is a misleading and non standard term.
Nonsense!
It is a well-known term of art among computer scientists, and used in
leading references on the subject. With respect specifically to C++ it
is not only well-known, but officially and formally standardized as a
requirement in the C++ standard.
--
Later,
Jerry.
The universe is a figment of its own imagination.
In article <11*********************@m73g2000cwd.googlegroups. com>, vf***@talktalk.net says...
[ ... ]
You agree with false statement, so you are wrong.
You're putting words in my mouth. Your previous statements were wrong,
and now you've descended to outright lies to try to cover them up.
I do have a good understanding of big oh.
Not to put too fine a point on it, the posts I've seen you make thus far
do not make this claim particularly believable.
I've just shown that I have a better understanding than you, by proving
you wrong.
Still more nonsense!
I refer to cheaters, being people that confuse others by conveniently
dropping terms like "amortized" to make things look better than they
really are, for their own personal gain. Imagine how preposterous it
would be if some athletes went around saying "my time for the 100m is
0.1", then when someone said that is impossible they conveniently
turned around and changed their tune to "my amortized time for the 100m
is 0.1, you are wrong."
First of all, people have been very careful to state that insertion into
a vector has amortized constant complexity from the beginning. You are
simply badly confused: you originally asked about _access_ to the array,
which has constant complexity -- NOT amortized constant, but simply
constant.
You then went on to confuse the two, and don't seem to have sorted
things out yet.
Please post the exact errors you're receiving, and identify the compiler
you're using. If you can't get that to compile, I'm reasonably certain
there's a fairly serious problem either with your compiler, or with how
you're using it.
--
I will look elsewhere in future.
Just for grins, I'll even suggest on place elsewhere that you can look.
Comeau C++ is widely regarded as having the best conformance of any
compiler available. Nicely enough, Greg Comeau is kind enough to make a
version of it available via his web site. Running it over the code I
posted gives the following results:
-----------snip--------------------
Your Comeau C/C++ test results are as follows:
Comeau C/C++ 4.3.8 (Aug 19 2006 13:36:48) for ONLINE_EVALUATION_Alpha1
Copyright 1988-2006 Comeau Computing. All rights reserved.
MODE:strict errors C++
In strict mode, with -tused, Compile succeeded (but remember, the Comeau
online compiler does not link).
-----------end snip------------------
The URL for the test compiler is: http://www.comeaucomputing.com/tryitout/
So anybody who cares to verify the code I posted can do so. Of course,
the compiler has far more uses than that. Since you claim to have had
difficulty getting your compiler to work with my code, after you try it
out, you should send Greg $50 and get a copy of his compiler, which
obviously works a lot better than whatever you've been using.
--
Later,
Jerry.
The universe is a figment of its own imagination.
Jerry Coffin wrote:
In article <11*********************@m73g2000cwd.googlegroups. com>,
vf***@talktalk.net says...
[ ... ]
You agree with false statement, so you are wrong.
You're putting words in my mouth. Your previous statements were
wrong, and now you've descended to outright lies to try to cover them
up.
He's a troll, plonk him or ignore him.
Brian
"Default User" <de***********@yahoo.comwrites:
Jerry Coffin wrote:
In article <11*********************@m73g2000cwd.googlegroups. com>,
vf***@talktalk.net says...
[ ... ]
You agree with false statement, so you are wrong.
You're putting words in my mouth. Your previous statements were
wrong, and now you've descended to outright lies to try to cover them
up.
He's a troll, plonk him or ignore him.
Furthermore, he tends to respond to this kind of post (I posted a
similar comment over on one of the GCC help forums) with an
extraordinarily profane and insulting email. I'll probably get
another from this post. Gents, he really isn't worth the time.
----------------------------------------------------------------------
Dave Steffen, Ph.D.
Software Engineer IV Disobey this command!
Numerica Corporation - Douglas Hofstadter
dgsteffen at numerica dot us This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: anon856525 |
last post by:
Hi
I recently downloaded Turbo C v2.01 from the borland web site where
its being given out for free. Has anyone else tried this?
Ive been using it for some months now and hav'nt noted any...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |
