Is it possible to access a row in a datatable in constant time?

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

Is there a way to configure\create a datatable (strongly typed or untyped)
that can have a row accessed in constant time if you are searching on the
primary key?

If there isn't a way, then what is the quickest way to access a row when
using datatables?

Thanks,

Ryan
 
I don't believe it is possible to guarantee processing time in Windows
environment.

Because search time depends on data size you can't guarantee constant time
when searching either. You can hope to have more or less same time when your
data has fixed size. But there will be no guarantee.

I believe fastest way is by row index. But also no guarantee for processing
time.
 
I don't believe it is possible to guarantee processing time in Windows
environment.
Click to expand...

arrays don't provide constant access time? that seems wrong to me. I think
it is possible, if nothing else you could do it in unmanaged C++ but I would
be very supprised if arrays didn't offer constant time access.
I believe fastest way is by row index. But also no guarantee for processing
time.
Click to expand...

can someone please at least speak to the Big O analasys of this access or
point me to what algorythm is used so that I can calculate it. Is it a b
tree, linked list, etc...

thanks
 
You need to factor in other processes and threads, OS kernel etc.. Any
thread could be interrupted at arbitrary moment.
 
Ok, it seems like we are having difficulties with semantics here as your
answer is not speaking to the type of complexity analsys that I am familar
with. Could you please tell me which complexity as described on this
wikipedia page that talks about BigO notation maps to the various ways of
acessing rows in a data table (this will have the side effect of pointing out
the quickest access method).

link to article:
http://en.wikipedia.org/wiki/Big_O_notation#Common_orders_of_functions (see
the definitions in the Common orders of functions)

My understanding is that big O analasys is only concerned with the algorithm
at hand and doesn't take into account enviromental concerns. So if
algorithmically the time it takes to access an element is independent of the
number of elements in the list (like array access in C++) then it is constant
time or big O(1).
 
Yes, O analysis is concerned mostly with theory. If you plan to implement
for specific hardware, you do complexity analysis in specific operations and
under very specific limiting conditions.

As you might know, theoretical limit for accessing any array element by
index or by value (key) is O(1). All list-based structures will have higher
access complexity I believe.

I might have misinterpreted your question because you asked about data
tables and mentioned managed C++, which are not theoretical objects in .Net
group. If you are looking only for theoretical discussion you can ignore my
posts,

Theoretically it is possible to access arbitrary array element in constant
time (I believe limit is 2 theoretical operations per access, or O(1) for
single instruction control flow). Practically it is O(f(n)), where f(x) is
realization-dependent function and n is size of array..Function could be
anything - depends on the skills of implementing person, compiler, hardware
and environment conditions.

Did you look at generated assembler codes for some samples? You can see that
in debugger disassembler window. You can estimate JIT-compiled code
complexity then using specific hard facts

"The theory is gray, my friend, and only tree of life is evergreen"
<Faust>
 
OK, now that we are speaking the same langauge, can you please tell me what
the various ways of accessing rows in a datatable are and what each ones
theoretical complexity is.

Thanks
 
can someone please at least speak to the Big O analasys of this access or
point me to what algorythm is used so that I can calculate it. Is it a b
tree, linked list, etc...
Click to expand...

Are you familiar with Lutz Roeder's Reflector? It allows you to
decompile assemblies, including the supplied .Net ones, and examine
the code. The DataRowCollection is implemented in terms of a red-black
tree.
 
Thanks Philip,

So, as far as you know is DataTable.Row[<index>]

The quickest access method resulting in O(log n) complexity?
 
Back
Top