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


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

How I did customize "rasa-nlu-trainer" as my own tool

Background I wanted to have a tool for human beings to classify intents and extract entities of texts which were obtained from a raw dataset such as Rocket.chat's conversation, Maluuba Frames or here. Then, the output (labeled texts) could be consumed by an NLU tool such as Rasa NLU.

rasa-nlu-trainer was a potential one which I didn't need to build an app from scratch. However, I needed to add more of my own features to fulfill my needs. They were:

1. Loading/displaying raw texts stored by a database such as MongoDB
2. Manually labeling intents and entities for the loaded texts
3. Persisting labeled texts into the database

I firstly did look up what rasa-nlu-trainer's technologies were used in order to see how to implement my mentioned features.
At first glancerasa-nlu-trainer was bootstrapped with Create React App. Create React App is a tool to create a React app with no build configuration, as it said. This tool is also recommended by the official React.js tutorial. I ac…

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…

The HelloWorld example of JSF 2.2 with Myfaces

I just did by myself create a very simple app "HelloWorld" of JSF 2.2 with a concrete implementation Myfaces that we can use it later on for our further JSF trying out. I attached the source code link at the end part. Just follow these steps below:

1. Create a Maven project in Eclipse (Kepler) with a simple Java web application archetype "maven-archetype-webapp". Maven should be the best choice for managing the dependencies, so far. JSF is a web framework that is the reason why I chose the mentioned archetype for my example.

2. Import dependencies for JSF implementation - Myfaces (v2.2.10) into file pom.xml. The following code that is easy to find from http://mvnrepository.com/ with key words "myfaces".

<dependency> <groupId>org.apache.myfaces.core</groupId> <artifactId>myfaces-api</artifactId> <version>2.2.10</version> </dependency> <dependency> <groupId>org.apache.myfaces.core</groupId&g…

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.
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 iTermoh-my-zsh, and thefuck. ;)

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 idea with other people. I use the set of tools for helping…

Strategy Design Pattern

For example, I have an program with an Animal abstract class and two sub-classes Dog and Bird. I want to add a new behavior for the class Animal, this is "fly".  Now, I face to two approaches to solve this issue:

1. Adding an abstract method "fly" into the class Animal. Then, I force the sub-classes should be implemented this method, something like:

public abstract class Animal{ //bla bla public abstract void fly(); } public class Bird extends Animal{ //bla bla public void fly(){ System.out.println("Fly high"); } } public class Dog extends Animal{ //bla bla public void fly(){ System.out.println("Cant fly"); } }
2. Creating an interfaces with method "fly" inside. The same issue to abstract class, I force the classes these implement this interface should have a method "fly" inside:

public interface Flyable{ public void fly(); } public class Bird implements Flyable{ //bla bla public void fly(){ System.out.println…