Performance of a Data Structure

Why data structures matter

The fact is that programs are all about processing data. Data structures are referred to how data is organized which affects the time of executing a program.

How to measure the performance of a data structure

In order to measure "how fast"/efficiency/performance of a data structure, we measure the performance of its operations. There are four basic operations including reading, searching, insertion, and deletion. A pure time consuming is not used for the measuring because it is not reliable depending on the hardware that it is run on. But instead, we use the term time complexity which refers to how many steps an operation takes.

An example of how a single rule can affect efficiency

Let's compare two data structures: Array and Set (with N elements).

1. Array

- Reading: 1 step (because the computer has the ability to jump to any particular index in the array)
- Searching: N steps (the worst case with linear search)
- Insertion: N + 1 steps (the worst case inserting at index 0: N steps of right-shifts + 1 step of insertion)
- Deletion: N steps (the worst case deleting at index 0: N-1 steps of left-shifts + 1 step of deletion)

2. Set

- Reading: 1 step
- Searching: N steps
- Insertion: best case: N + 1 steps; worst case: 2N + 1 steps (every insert first requires a search)
- Deletion: N steps

NOTE: I mentioned the set by setting up from an array. There is another way to set up a set by a hash table.

Reference:

[1]. Jay Wengrow | A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills

Comments

Styling Sort Icons Using Font Awesome for Primefaces' Data Table

So far, Primefaces has used image sprites for displaying the sort icons. This leads to a problem if we want to make a different style for these icons; for example, I would make the icon "arrow up" more blurry at the first time the table loading because I want to highlight the icon "arrow down". I found a way that I can replace these icons with Font Awesome icons. We will use "CSS Pseudo-classes" to achieve it. The hardest thing here is that we should handle displaying icons in different cases. There is a case both "arrow up" and "arrow down" showing and other case is only one of these icons is shown. .ui-sortable-column-icon.ui-icon.ui-icon-carat-2-n-s { background-image: none; margin-left: 5px; font-size: 1.1666em; position: relative; } .ui-sortable-column-icon.ui-icon.ui-icon-carat-2-n-s:not(.ui-icon-triangle-1-s)::before { content: "\f106"; font-family: "FontAwesome"; position: ...

Java Core - Top 10 Questions Every Developer Should Know

#RandomlyPickedByMe What is the difference between Javascript and Java? Difference between StringBuilder and StringBuffer? Why do I get "SomeType@a3fde" when I print my code? Why is String immutable? Why "equals" method when we have "==" operator? Is List<Dog> a subclass of List<Animal>? Why shouldn't we use raw type? Is Java “pass-by-reference” or “pass-by-value”? What's the advantage of a Java enum versus a class with public static final fields? Why "double x = 0.1 + 0.2" and result of print(x) is 0.30000000000000004? 1. What is the difference between Javascript and Java? Holy crap! (Vietnamese: Thế quái nào lại có câu hỏi ngớ ngẩn vậy chứ?) "Java and Javascript are similar like Car and Carpet are similar." - Greg Hewgill (on StackOverflow) 2. Difference between StringBuilder and StringBuffer String is immutable. StringBuilder and StringBuffer are mutable. StringBuffer is thread-safe. String...

BIRT - Fix the size of an image

I use a dynamic image as a logo my report in pdf. At the beginning, I use table to align the logo in left or right. I meet a problem with some images with a large width or height. My customer requires that the logo should be displayed in original size. These following steps solves my problem: 1. Use Grid instead of Table 2. Set Grid "Height" is 100% and "Width" is blank 3. Set "Fit to container" for images are "true". Download the the template here .

Math fundamentals and Katex

It was really tough for me to understand many articles about data science due to the requirements of understanding mathematics (especially linear algebra). I’ve started to gain some basic knowledges about Math by reading a book first. The great tool Typora and stackedit with supporting Katex syntax simply helps me to display Math-related symbols. Let’s start! The fundamental ideas of mathematics: “doing math” with numbers and functions. Linear algebra: “doing math” with vectors and linear transformations. 1. Solving equations Solving equations means finding the value of the unknown in the equation. To find the solution, we must break the problem down into simpler steps. E.g: x 2 − 4 = 4 5 x 2 − 4 + 4 = 4 5 + 4 x 2 = 4 9 x = 4 9 ∣ x ∣ = 7 x = 7 or x = − 7 \begin{aligned} x^2 - 4 &= 45\\ x^2 - 4 + 4 &= 45 + 4\\ x^2 &= 49\\ \sqrt{x}&=\sqrt{49}\\ |x| &= 7\\ x=7 &\text{ or } x=-7 \end{aligned} x 2 − 4 x 2 − 4 + 4 x 2 x ∣ x ∣ x = 7 = 4 5 = 4 ...

My must-have apps for daily work

There is no doubt that cool apps can help us be more productive and enjoyable at work. For the time being, I really love the following apps which are used by me almost every day. 1. A personal Kanban In fact, a personal kanban is the most useful app for me. Why does it matter? It is not just a to-do list, but it keeps me motivated every day because it helps me be able to know what my "big picture" is. I usually set up my plans together with a path to reach them. KanbanFlow is my preferred tool. KanbanFlow 2. A terminal Needless to say, a terminal is a must-have app for every developer, especially the ones use macOS/Linux. Due to its importance, I love to decorate and enhance it to be super exciting with various tools such as iTerm , oh-my- zsh , and thefuck . ;) iTerm + oh-my-zsh 3. A documentation "ecosystem" As a developer, I can not remember all things that I have experimented a day. Moreover, a document is really useful for sharing an...

vhandit

Search This Blog