«

Op 9-2-2010 13:42, Dimilar Zhu schreef:
> I have 10000 numbers. Now i need to choose a kind of data structure to save them.
> of 1-dimension and 2-dimension array, which is faster? does it depend
> on factors such as degree of order, correlation, operations?

if yu write a threaded application, than the number of threads will make
the speed.

so if you have a dual-core processor, take a 2-dimensional array




--
Luuk

Op 9-2-2010 13:42, Dimilar Zhu schreef:
> ....., which is faster? ......

btw, why do you care about speed,
you are living in the FUTURE!

--
Luuk

I have 10000 numbers. Now i need to choose a kind of data structure to save them.
of 1-dimension and 2-dimension array, which is faster? does it depend
on factors such as degree of order, correlation, operations?

Luuk <> writes:

> Op 9-2-2010 13:42, Dimilar Zhu schreef:
>> ....., which is faster? ......
>
> btw, why do you care about speed,
> you are living in the FUTURE!

just a question, yesterday my boss asked me. he is a doctor, and do not know
much about detail of computer language. but at that time i do not know how
to answer it. so I said, "it depends....blablabla".

later a guy told me that there were distinct performance result for large
scale of data if taking account of memory cache and memory access.

for 2-dimension array, it is necessary to do much multiplication to obtain the
index of element. compared to the addition of 1-dimension array, it consumes
more time.

but I did not do any experiment to verify it.

dimilar <> writes:
> Luuk <> writes:
>
>> Op 9-2-2010 13:42, Dimilar Zhu schreef:
>>> ....., which is faster? ......
>>
>> btw, why do you care about speed,
>> you are living in the FUTURE!
>
> just a question, yesterday my boss asked me. he is a doctor, and do not know
> much about detail of computer language. but at that time i do not know how
> to answer it. so I said, "it depends....blablabla".

Good answer, though you could have said that data structures aren't
fast or slow, it is algorithms that have certain performance
characteristics. In particular, it is the pattern of accesses that
determines what the best data structure is for a particular problem.

If this is something that needs a fuller answer, then post on
comp.programming with an outline of what it is you are trying to do
(at the highest level -- invert a matrix, find a clique in a graph
etc.) because this is not really a C question.

--
Ben.

In article <>,
dimilar <> wrote:

>for 2-dimension array, it is necessary to do much multiplication to obtain the
>index of element.

Certainly accessing a 2d array *conceptually* involves multiplication.
But if you can straightforwardly use a 1d array instead, then quite
likely so can the compiler. For example, in

int a[n1][n2];

for(i=0; i<n1; i++)
for(j=0; j<n2; j++)
... do something with a[i][j] ...;

a reasonable compiler will not calculate i*n2+j from scratch each time
round the inner loop. It can compute i*n2 once each time round the
outer loop, and may not even do that.

-- Richard
--
Please remember to mention me / in tapes you leave behind.

(Richard Tobin) writes:

> In article <>,
> dimilar <> wrote:
>
>>for 2-dimension array, it is necessary to do much
> multiplication to obtain the
>>index of element.
>
> Certainly accessing a 2d array *conceptually* involves
> multiplication.
> But if you can straightforwardly use a 1d array instead,
> then quite
> likely so can the compiler. For example, in
>
> int a[n1][n2];
>
> for(i=0; i<n1; i++)
> for(j=0; j<n2; j++)
> ... do something with a[i][j] ...;

for the case you described here, multiplication is not a problem because you are
accessing elements in a certain order. but if we randomly access
many elements from a large 2d array. many multiplication is
inevitable. although I am also not sure it is a bottleneck.

however, I think it is really an algorithms dependent problem.
Thanks for you reply

> a reasonable compiler will not calculate i*n2+j from scratch
> each time
> round the inner loop. It can compute i*n2 once each time
> round the
> outer loop, and may not even do that.
>
> -- Richard

On 9 Feb, 12:42, Dimilar Zhu <z...@in.tum.de> wrote:
> I have 10000 numbers. Now i need to choose a kind of data structure to save them.
> of 1-dimension and 2-dimension array, which is faster? does it depend
> on factors such as degree of order, correlation, operations?

As I think others have said, this really isn't that much of a C
question. It's more a general computing question, and even then you
haven't given us enough information to go on.

What do your 10000 numbers represent? How do you expect to populate
the data structure and how do you expect to access it?

If the natural representation of your data is as a two-dimensional
array, I don't see how it would be any advantage for you to flatten it
to one dimension and do the maths to access your target cells.

Equally, if the natural representation is one dimensional, why would
you do anything else?

On Feb 9, 2:42*pm, Dimilar Zhu <z...@in.tum.de> wrote:
> I have 10000 numbers. Now i need to choose a kind of data structure to save them.
> of 1-dimension and 2-dimension array, which is faster? does it depend
> on factors such as degree of order, correlation, operations?

In C a 2-dimensional array is stored as a flat structure continuously
in memory. So the only performance difference is (potnetially) due to
the difference between accessing array[y][x] as opposed to
array[y*width+x]. It's hard to think of circumstances where the first
would be slower, but often the second mght be slower because it is
harder for the compiler to optimise out constants.
However typically the dimensions of a 2d array are either not known at
compile time, or are undesireable to hardcode into low-level
functions. So the 1d method is usually the way to go, in C.

Dimilar Zhu <> writes:
>I have 10000 numbers. Now i need to choose a kind of data structure to save them.

If you have 10000 number you already /have/ a data structure
to hold them, otherwise you would not /have/ them.

If you want to /save/ them to a file, you do not need a data
structure but a data language (aka a file format) to
serialize (marshal, pickle, shelve) them to.

>of 1-dimension and 2-dimension array, which is faster?

Arrays do not have a speed at all. Only operations
have a speed.