I've seen several different definitions by googling, but I am still not sure. David kept saying "array gives us random access, and trie, too". What does 'random access' mean?
Add a comment
|
3 Answers
Random acccess, in this case, refers to having the "ability" of accessing any element in particular at a given point in time.
You simply "ask" for a certain element, as in array[2] and get the value stored in such position in constant time. There's no need to perform a search for such value, since the indexed structure provides you with access to any particular point in such array at any moment.
The name "random" is thought of from the computer's POV: any random position in the array the user asks for, he/she/it ;) is able to access it and return it by performing a (hopefully few) definite amount of steps (aka: constant time). He/she/it doesn't need to rely on any search algorithm.
HTH!
From Wikipedia,
In computer science, random access (more precisely and more generally called direct access) is the ability to access an item of data at any given coordinates in a population of addressable elements.
In terms of arrays, this basically means that, given the index of an element that you want to get/access from an array, you can directly access this element.
This is a constant-time operation — it always takes you a fixed number of steps to get it done.
If you're curious to know how, given an array a that starts at location 100 in memory, if you're trying to access a[120] (assuming the array has at least 121 elements), this index (i.e., 120) is added to the starting location of the array (i.e., 100) and you get 220 which is the location of a[120] in memory.
This clearly relies on the fact that array elements are contiguous in memory — they live next to each others in order.
When you deal with recursive data structures (e.g., linked-lists, hash tables, etc.) you use dynamic memory allocation. Unlike arrays, the elements of these data structures could be in different locations in memory. So you can never rely on a fact that these elements are contiguous as it's the case with arrays. Therefore, to access an element, you need to access it through a previous/next element. This clearly means that this is not a constant-time operation and thus, you don't have random/direct access.
As for tries, they use a combination of dynamic memory allocation and arrays. We can probably think of them as having random-access either in case we know the maximum length a word could have assuming the process of allocating memory is a constant operation. If we don't know the maximum length that a word could have however, then accessing a word mainly depends on its length.
-
Thanks @Kareem for (once again) such thoughtful answer. At risk of sliding a bit off-topic: dynamic memory allocation (i.e.:
malloc()andfree(), rigth?) is "only" necessary when the amount of memory needed is not known in advance, and therefore has to be defined at runtime, right? If you know (or can estimate) in advance how much memory you need, it's always safer and more efficient to let the OS manage it all by itself.. Am I correct? Could this be sort of a "rule of thumb"?– abelinuxCommented Dec 8, 2014 at 14:05 -
@abelinux you're welcome! And yes, we use dynamic memory allocation when we don't know the amount of memory that we need in advance. And I'm actually not sure what you mean by "safer", but if you at least have an upper-bound to the amount of memory that you need, then you can use arrays which are probably more efficient to use. But here's something, AFAIK, the operating system isn't directly responsible for managing memory in such situation. The compiler is the one that allocates memory and the runtime system takes care of freeing it.– kzidaneCommented Dec 8, 2014 at 14:32
-
Uhm... OK, I may have small-talked when referring to "OS". I didn't know specifically who is responsible, all I meant was "it's not me" =P. By "safer" I meant that, since I'm not responsible for alloc and free mem, since someone takes care of that for me, there's less risk (or really no risk at all) of a memory leak.– abelinuxCommented Dec 8, 2014 at 14:41
-
-
OK, was re-reading some of my "foobar.c" experiments and recalled one more use of mem alloc: to overcome "scope issues"! When you call, e.g. from
main()a new function whose purpose is to create an array of (given) size, fill it with random data, and return it to main. If you declare the array as usual, it's created on thestack, and therefore destroyed when leaving this new function's scope. But, if you allocate mem for such array on theheap, it "stays" there and you can return it to main.– abelinuxCommented Dec 8, 2014 at 14:59
A trie does not have random access because you have to iterate over the nodes of the trie before you can find a word (for example). You would only find it by following pointers.
On the other hand, an array does have random access. For example, if you stored the char 'a' in position 3 of the array, then you would have random access because you could get at 'a' by simply asking for array[2].
