reserving memory for an array

[vfunc]

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.


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 ?

 

[Kai-Uwe Bux]

I mean overall, including the "dynamic" processing...


OK, but then you say...


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

 

[Jerry Coffin]

[ ... ]

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.

 

[Thomas J. Gritzan]

OK, but then you say...


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.

 

[Victor Bazarov]

[..]
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

 

[Kai-Uwe Bux]

[ ... ]

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

 

[vfunc]

[ ... ]

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.

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.

 

[Mark P]

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

 

[Dave Steffen]

[...]

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.

 

[Thomas J. Gritzan]

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.

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[].

 

[Default User]

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/307f580f
5b5fb1b7>

This probably wrapped in some unpleasant fashion. Sorry.




Brian

 

[Dave Steffen]

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.

 

[vfunc]

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.


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.


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[].

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.

 

[Jerry Coffin]

[ ... ]

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...


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.

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.

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 = 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<int> array3(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 <*.h> C
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.

 

[Thomas J. Gritzan]

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.

 

[vfunc]

Overall I agree.

[ ... ]

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.

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.


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.


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.

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).

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.

 

[loufoque]

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.

 

[vfunc]

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.

 

[Kai-Uwe Bux]

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

 

[Jerry Coffin]

[ ... ]

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.

[ ... ]

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."

[ ... ]

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.