[Performance] Memory allocation and array structure


In most of the modern programming language I have learnt, such as C++ and Python, as well as Javascript, the memory allocation for array data structure is like this:

/* (e.g.) */ var a = [["a", "b", 'c"], [1, 2, 3], ["甲", "乙", "丙"]] //Java-script
// /* Memory allocation in order  */ "a" -->  'b" --> "c" --> 1 --> 2 --> 3 --> "甲" --> "乙" --> "丙"

Little thought

Suppose I am gonna store the following sets of data into an array, what’s the most best way to make it accessible most efficiently?

Name No Index
Peter

1

0

Mary

5

1

Lily

30

2

Jonathan 

25

3

Given that the items can be accessed by knowing the index, I have thought of 2 ways of storage

Method 1: The traditional way

var data = [["Peter", 1], ["Mary", 5], ["Lily", 30], ["Jonathan", 25]];
// /* Memory storage: */ "Peter" --> 1 --> "Mary" --> 5 --> "Lily" --> 30 --> "Jonathan" --> 25

This way is very clear and easy to understand, but may not be quite efficient to access the {No} of each element. For instance, the computer has to read pass all {Name}s of each item, and the memory access footprint is long.

Method 2: The “Split" way

var data = [["Peter", "Mary", "Lily", "Jonathan"], [1, 5, 30, 25]];
// /* Memory storage: */ "Peter" --> "Mary" --> "Lily" --> "Jonathan" --> 1 --> 5 --> 30 --> 25

To loop through all {No}s of all data items, just loop within data[1], and the memory access footprint is limited to number of data items.

To access {Name}s and {No}s, just need data[0][x] and data[1][x], where “x" is the index of the item.

There may be a problem associated with this kind of array structure, such as deleting a datum element, it has to loop through different parts of the data (can be understood as “columns" of data in a table). Nonetheless, for storing rare-updated data, I prefer the “split" way.

塗牆

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s