42
votes
Accepted
Understanding serialization
If you have a complicated data structure, its representation in memory might ordinarily be scattered throughout memory. (Think of a binary tree, for instance.)
In contrast, when you want to write it ...
D.W.♦
- 156k
40
votes
Accepted
Why we still need Short Term Memory if Long Term Memory can save temporary data?
There's two simple reasons, one fundamental and one related to our current technology. First the technical one: volatile storage is (generally) faster than non-volatile storage. It has fewer ...
- 12.7k
28
votes
Understanding serialization
The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes? (Of course they are, because they are stored in registers, ...
- 421
21
votes
Why we still need Short Term Memory if Long Term Memory can save temporary data?
@orlp is already discussed speed. There's probably more than could be added (e.g., about latency vs. bandwidth), but let's leave that aside for now.
Write Endurance
Instead, let's start by considering ...
- 711
16
votes
What course in CS deals with the study of RAM, CPU, Storage?
The subject you're describing often goes under the names computer architecture, computer systems, computer organization and design, and the like. One example is Elements of computing systems, based on ...
- 275k
15
votes
Understanding serialization
The tricky is actually already described in the word itself: "serialization".
The question is basically: how can I represent an arbitrarily complex interconnected cyclic directed graph of arbitrarily ...
- 5,860
13
votes
Understanding serialization
The other answers already address complex object graphs, but it's worth pointing out that serializing primitives is also non-trivial.
Using C primitive type names for concreteness, consider:
I ...
- 231
11
votes
Accepted
Why does RAID-5 require an additional disk for parity blocks?
I think you've misunderstood what the parity data is. They're not parity checks, so it's not true that "each parity block is specific to each disc it belongs to." The parity data is to allow recovery ...
- 81.4k
9
votes
Why we still need Short Term Memory if Long Term Memory can save temporary data?
Others have talked about different technologies, like L1 caches, etc. so I thought I'd give a more theoretical explanation.
Memory access time scales with square root of capacity, i.e. random access ...
- 602
6
votes
Understanding serialization
In addition to what the other answers have said:
Sometimes you want to serialise things that are not pure data.
For instance, think of a file handle or a connection to a server. Even though the file ...
- 656
6
votes
Understanding serialization
There are multiple aspects:
Readability by the same program
Your program has stored your data somehow as bytes in the memory. But it might be arbitrarily scattered across different registers, with ...
- 169
6
votes
Accepted
Could a standardized ternary system be more efficient than the binary system?
Whether this is more efficient depends on the physical properties of the medium, not on any fundamental principle of computer science. And of course there's no reason to limit yourself to ternary ...
D.W.♦
- 156k
5
votes
Why did the concept of "write-protecting" not carry over from floppy disks to USB memsticks and especially external USB HDDs?
I'm not entirely sure that this question is on topic, but nonetheless, I suspect it has a simple answer.
Physical write protection mechanisms predate floppy disks. At my school holiday job in the ...
- 21.7k
4
votes
Accepted
Is there a name for "density" of information?
The classical measure of information is the entropy. Entropy measures the information content of a random source. Consider the case of text files: someone has generated some text, and she wants to ...
- 275k
4
votes
Why we still need Short Term Memory if Long Term Memory can save temporary data?
According to Google, the fastest SSD drive in 2020 has a 45 microsecond read access time. RAM access time is about 10 ns, that is 4,500 times faster. A factor of 4,500 is enough to make SSD without ...
- 28.4k
3
votes
time efficient key value store for fast lookup
Make a table with 2^22 entries to lookup the highest 22 bits of the key. Each entry is responsible for one value on average (but may contain up to 1024).
Entry #i in the table, which is responsible ...
- 28.4k
3
votes
time efficient key value store for fast lookup
Since the data structure is only created once, you can simply use an array ordered by the key. Each element in the array contains the key-value pair. Sorting the array is ...
- 261
3
votes
Understanding serialization
Let's define what a sequence of bytes actually is. A sequence of bytes consists of an non-negative integer called the length and some arbitrary function/correspondence that maps any integer i that is ...
- 131
3
votes
Accepted
How are the number of bytes less than the number of pixels in an image?
A colour image is typically digitalized using 256 levels for each of the 3 RGB channels. That gives 3 bytes per pixel. The trick to attain smaller file size is to apply some compression, to take ...
- 256
3
votes
Why we still need Short Term Memory if Long Term Memory can save temporary data?
When we talk about speed, we need to distinguish between latency and throughput. Latency is fundamentally restricted by physics; for example DRAM can be accessed in about 10 ns, flash can be accessed ...
- 881
3
votes
Accepted
Using B+Tree to implement index, when the index-key size and the data-block size are of the same order
Note: In what follows, I'm going to use the term "B-tree" to refer to the general idea of B-trees regardless of the variant, and "B+-trees" to refer specifically to B+-trees.
You'...
- 21.7k
2
votes
Accepted
Most Efficient Way to List All $n$-bit Permutations
Since $n$ is known from the start, you know that there are exactly $2^n!$ possible lists. Calculate the index of your list in a lexical ordering of all permutations, and then write that number using $...
- 484
2
votes
Determining HD Content
A parity determines whether the amount of particular occurrences for something is even or odd. In this case, since the parity is odd, that means HD 6 stores a 1 for ...
- 155
2
votes
Understanding serialization
The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes?
Yes, they are. The problem here is the layout of those bytes. ...
- 213
2
votes
Understanding serialization
The intricacies reflect the intricacies of data and objects themselves. These objects can be real world objects, or computer only objects. The answer is in the name. Serialisation is the linear ...
- 1,602
2
votes
time efficient key value store for fast lookup
The minimum possible size for such any such data structure is $\log_2{ 2^{32} \choose 4\times 10^6} \approx 4.6\times10^7$ bits, or around 5.5MB.
An array of 4 million 32-bit numbers is only 15.25MB. ...
- 21.7k
2
votes
What is the minimum required storage for a sparse, depth-first octree?
The number of octrees with $n$ nodes is OEIS sequence A007556:
$$T(n) = {8n \choose n}/(7n+1)$$
I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ ...
- 21.7k
2
votes
Accepted
How is the data stored in AVL tree in a memory?
If I wanted to be really pedantic, the question would be unanswerable, as it depends on the particular implementation.
In most cases, however, the individual nodes of the tree are stored in one ...
2
votes
Is ROM primary memory or secondary memory?
The terms “primary memory” and “secondary memory” are intended to distinguish between memory that is directly accessible from the main processor and memory that isn't. The basic idea is that the ...
2
votes
Is ROM primary memory or secondary memory?
The distinction between primary and secondary storage relies on several joint characteristics which the prototypical examples – RAM and hard drives – satisfy:
Primary storage can be accessed directly ...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible