1. The difference between “continuous” and “contiguous”.
2. What does it mean “Contiguous memory block”?
3. Data structures that are held in contiguous memory.
4. Computing time.
5. Several words about Contiguous Memory Allocation.
The difference between “continuous” and “contiguous”.
Sometimes people think that “continuous” and “contiguous” are the same.However, there is a slight difference between them.
Contiguous means elements are touching or adjacent to. Means each element has its own cell and border.
Whereas continuous means uninterrupted and ceaseless.
Probably both seems synonymous but it would be correct to use “contiguous memory” in programming terms.
So what does it mean “Contiguous memory block”?
It means that elements in contiguous chunk of memory are laid out end-to-end, with no gaps and no padding between them. There is a possibility of padding inside each element, but not between them. It’s depicted in the following images.
Contiguous memory block of 4 bytes
Non-contiguous memory block of 4 bytes
Data structures that are held in contiguous memory
The bright example of data structures which use contiguous chunk of memory are Arrays and Queue. We may also say about the String which can conform to contiguous memory. But do not hurry. We can definitely say that String uses contiguous memory in such languages like C++, Python2, Go and others but not in Swift. I would recommend to read this article by Mike Ash. He explained it really nice.
Let’s back to the data structures:
let arr = [1,2,3,4]
In Swift we can represent queue as an array where
enqueue → append(newElement) dequeue → removeObjectAtIndex(0) or popLast()
The computing time of the methods of these data structures are different. It explains by the requirements of shifting all elements after removing or inserting them from/in the middle of array.
For example it will be the constant time O(1) for methods like:
popLast() //if array is not bridget removeLast()
linear timeO(n) in methods for array like
removeAtIndex(index) insert(newElement, atIndex: index)
We can also notice the logarithmic time O(log n) in case you perform
Btw, you can always check the complexity time using Playground/Xcode. Press and hold ALT and click on some method or property.
Several words about Contiguous Memory Allocation
Contiguous Memory Allocation is one of the various approaches of memory allocation. It based on dividing all available memory into equal sized partitions, and to assign each process to their own partition.
This confine 2 things:
- the number of simultaneous processes
the maximum size of each process
There is the rule – only one process can be stored in one section. The OS keeps fresh table, like a map, which contains all of the statuses of each piece of memory. So when the system gets a new process it’s already know all available places where the new task can be stored.
Here is visual representation of Contiguous Memory Allocation
There are also several drawbacks of using contiguous allocation:
- Wasteful of space (dynamic storage-allocation problem).
Use first fit or best fit.
Leads to external fragmentation on disk.
Files cannot grow – expanding file requires copying.
Users tend to overestimate space – internal fragmentation.
I hope this topic was interesting for you. Feel free to contact me and provide more ideas for writing.