Algos: RAM, Binary, Fixed-width Intergers

To really understand how data structures work, we’re going to derive each of them from scratch. Starting with bits.

• Random Access Memory
• Binary Numbers
• Fixed-Width Integers
• Arrays
• Strings
• Pointers
• Dynamic Arrays
• Linked Lists
• Hash Tables

Random Access Memory (RAM)

When a computer is running code, it needs to keep track of variables (numbers, strings. arrays, etc)

Variables are stored in random access memory(RAM). We sometimes call RAM working memory or just memory

RAM is not where mp3 and apps get stored, In addition to memory your computer has storage (sometimes called “persistent storage or “disc”) While memory is where we keep the variables of our functions allocate as they crunch data for us. storage is where we keep files like mp3, videos, Word documents, and even executable programs or apps.

Memory (or RAM) is faster but has less space, while storage (or “dics”) is slower but has more space. A modern laptop might have -500GB of storage but only -16GB of RAM.

Think of RAM like a really tall bookcase with a lot of shelves. Like billions of shelves

it keep going down. Again, picture billions of these shelves

These shelves are numbered

We call a shelf’s number its address.

Each shelf holds 8 bits. A bit is a tiny electrical switch that can be turned “on” or “off”. But instead of calling it “on” or “off” we call it 1 or 0.

8 bits is called a byte. So each shelf has one byte (8 bits) of stroage.

Of course, we also have a processor that does all real work inside our computer

It’s connected to a memory controller. The memory controller does the actual reading and writing to and from RAM. It has a direct connection to each shelf of RAM

The direct connection is important. It means we can access address 0 and then immediately access 918,873, without having to ‘climb down’ the massive bookshelf of RAM.

That’s why we call it Random Access Memory(RAM)- we can access the bits a any random address in memory right away

Spinning hardrives dont have this “random access” superpower, because there’s no direct connection to each byte on the disc. Instead, there’s a reader — called a head — that moves along the surface of a spinning storage disc(like a needle on a record player). Reading bytes that are far apart takes longer because you have to wait for the head to physically move along the disc.

Even though the memory controller can jump between far- apart memory addresses quickly programs tend to access memory thats nearby. So computers a re tuned to get an extra speed boost when reading memory addresses that are close to each other. Here’s how it works:

The processor has a cache where it stores a copy of stuff it’s recently read from RAM

Actually, it has series of caches. But we can picture them all lumped together as one cache like this

This cache is much fasted to read from than RAM, so the processor saves time whenever it can read something from the cache instead of going out to RAM

When the processor asks for the contents of a given memory address, the memory controller also send the contents of a handful of nearby memory address. And the processor puts all of it in the cache

So if the processor asks fort he contents of address 951, the 952, then 953, then 954… it’ll go out to RAM once for the first read, and the subsequent reads will come straight from the super-fast cache.

But if the processor asks to read address 951, then address 362, then address 419… then the cache won’t help, and it’ll have to go all the way out to RAM for each read.

So reading from sequential memory address is faster than jumping around

Binary Numbers

Let’s put those bits to use. Let’s store some stuff. Starting with numbers

The number system we usually use is called base 10, because each digit has ten possible values (1, 2, 3, 4, 5, 6, 7, 8, 9 and 0)

But computers don’t have digits with ten possible values. They have bits with two possible values. So they use base 2 numbers.

Base 10 is also called decimal. Case 2 is also called binary.

To understand binary. lets take a closer look at how decimal numbers work. Take the number “101”in decimal.

Notice we have two ‘1’s here, but they don’t mean the same thing . The leftmost “1” means 100 and the rightmost “1” means 1. Thats because the leftmost “1” is in the hundreds place, while the rightmost “1” is in the ones place. And the “0” between them is in the tens place.

So this “101” in base 10 is telling us we have “1 hundred, 0 tens and 1 one”

Notice how the places in base 10(ones place, tens place, hundreds pace, etc) are sequential powers of 10:

The places in binary (base 2) are sequential powers of 2:

So lets take that same “101” but this time lets read it as a binary number:

Reading this from right to left: we have a 1 in the ones place, a 0 in the twos place, and a 1 in the fours place. So our total is 4 + 0 + 1 which is 5.

Here’s how we’d count up to 12 in binary:

So far we’ve been talking about unsigned integers(“unsigned” means non-negative and “integer” means a whole number, not a fraction or decimal). Storing other numbers isn’t hard though. Here’s how some other numbers could be stored:

Fractions: Store two numbers : the numerator and denominator

Decimals: Also two numbers 1) the number with the decimal point taken out, and 2) the position where the decimal point goes (how many digits over from the leftmost digit)

Negative Numbers: Reserve the leftmost bit for expressing the sign of the number. 0 for the positive and 1 for negative.

In reality we usually do something slightly fancier for each of these. But these approaches work and they show we can express some complex stuff with just 1s and 0s.

We’ve talked about base 10 and base 2… you may have also sen base 16, also called hexadecimal or hex.

In hex, our possible values for each digit are 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e and . Hex numbers are often prefixed with “0x” or “#”

Fixed-width integers

How many different numbers can we express with 1 byte (8 bits)?

2*8 = 256 different numbers.

What happens if we have the number 255 in an 8-bit integer (1111 111 in binary) and we add 1? The answer (256) needs a 9th bit (1 0000 0000). But we only have 8bits!

This is called an integer overflow. At best, we might just get an error . At worst, our computer might compute the correct answer but then just throw out the 9th bit, giving us zero(ooo ooo) instead of 256 (1 0000 0000)(Javascript automatically converts the result Infinity it it gets too big)

The 256 possibilities we get with 1byte are pretty limiting. So we usually use 4 or 8 bytes (32 or 64 bits) for stroing intergers

• 32-bits integers have 2*33 possible values-more than 4 billion
• 64-bit integers have 2*64 possible values-more than 10 billion billion (10*19)

Most integers are fixed-width or fixed-length, which means the numbers of bits they take up doesn’t change.

Its usually safe to assume an integer is fixed-width unless you’re told otherwise. Variable-size numbers exist, but they’re only used in special cases.

If we have a 64-bit fixed-length integer, it doesn’t mater if that integer is 0 or 193,457 — it still takes up the same amount of space in RAM:64 bits

In big O notation we say fixed-width integers take up constant space or O(1)space

And because they have constant number of bits, most simple operations on fixed-width integers(addition, subtraction, multiplication, division) take constant time (O(1)time)

So fixed-width integers are very space efficient and time efficient

But the efficiency comes at a cost — -their values are limited. Specifically they’re limited to 2*n possibilites, where n is the number of bits.

So there’s a tradeoff. As we’ll see, thats a trend in data structures — to get a nice property, we’ll often have to lose something.