Skip to main content

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

Post a Comment

Popular posts from this blog

AngularJS - Build a custom validation directive for using multiple emails in textarea

AngularJS already supports the built-in validation with text input with type email. Something simple likes the following:
<input name="input" ng-model="email.text" required="" type="email" /> <span class="error" ng-show="myForm.input.$error.email"> Not valid email!</span>
However, I used a text area and I wanted to enter some email addresses that's saparated by a comma (,). I had a short research and it looked like AngualarJS has not supported this functionality so far. Therefore, I needed to build a custom directive that I could add my own validation functions. My validation was done only on client side, so I used the $validators object.

Note that, there is the $asyncValidators object which handles asynchronous validation, such as making an $http request to the backend.

This is just my implementation on my project. In order to understand that, I supposed you already had experiences with Angular…

Creating a Chatbot with RiveScript in Java

Motivation"Artificial Intelligence (AI) is considered a major innovation that could disrupt many things. Some people even compare it to the Internet. A large investor firm predicted that some AI startups could become the next Apple, Google or Amazon within five years"
- Prof. John Vu, Carnegie Mellon University.

Using chatbots to support our daily tasks is super useful and interesting. In fact, "Jenkins CI, Jira Cloud, and Bitbucket" have been becoming must-have apps in Slack of my team these days.

There are some existing approaches for chatbots including pattern matching, algorithms, and neutral networks. RiveScript is a scripting language using "pattern matching" as a simple and powerful approach for building up a Chabot.
Architecture Actually, it was flexible to choose a programming language for the used Rivescript interpreter like Java, Go, Javascript, Python, and Perl. I went with Java.


Used Technologies and ToolsOracle JDK 1.8.0_151Apache Maven 3.5…

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: absolut…

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 equationsSolving 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:x2−4=45x2−4+4=45+4x2=49x=49∣x∣=7x=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}x2−4x2−4+4x2x​∣x∣x=7​=45=45+4=49=49​=7 or x=−7​2. NumbersDefinitions
Mathematicians like to classify the d

Applying pipeline “tensorflow_embedding” of Rasa NLU

According to this nice article, there was a new pipeline released using a different approach from the standard one (spacy_sklearn). I wanted to give it a try to see whether it can help with improving bot’s accuracy.

After applying done, I gave an evaluation of “tensorflow_embedding”. It seemed to work better a bit. For example, I defined intents “greet” and “goodbye” with some following messages in my training data.
## intent:greet- Hey! How are you? - Hi! How can I help you? - Good to see you! - Nice to see you! - Hi - Hello - Hi there ## intent:goodbye- Bye - Bye Bye - See you later - Take care - Peace In order to play around with Rasa NLU, I created a project here. You can have a look at this change from this pull request. Yay!

When I entered message “hi bot”, then bot with “tensorflow_embedding” could detect intent “greet” with better confidence scores rather than bot with “spacy_sklearn”. The following are responses after executing curl -X POST localhost:5000/parse -d '{&qu…