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

My 2017 Review

Passion for System Design After finishing a one year project, my longest stable team (lasted for 3 years) was separated into two smaller teams. Sadly, but that was a good chance for me to become a key member in my new team. My preferred skills were about system architectures; therefore most of the tasks of building the application structures were handled by me. In order to enhance my design system skills, I have spent much my time for reading books closely after work. These following books help me a lot. - Object-Oriented Thought Process | Matt Weisfeld - Head First Design Pattern | Elisabeth Freeman and Kathy Sierra - Java 8 in Action: Lambdas, Streams, and Functional-style Programming | Alan Mycroft and Mario Fusco Junior Technical Architect I was requested to join a technical architect team (aka Team. Alpha) where I actually had gained experiences almost on interviewing candidates for my company (lol). Besides, I noticed myself must improve the skills of convinci...

BarcampSaigon 2015

Barcamp Saigon is one of my most expected events of the year. This year, it took place at RMIT university. As usual, it brought many useful topics to the community. Here is all topics that I have attended. Scale it! - Lars Jankowfsky Lars is founder of 8bitrockr.com How do we make a decision correctly? It is hard to know that until we try and measure it. He gave an example about how good an app was. And, most of people thought that the app with nice user interfaces is good at the first look. But it is not correct because it is only true until we try to use it, even the nice GUI app sometime is not good at UX, functionalities, etc. The key of success for working in team is collaboration. We can not only base on the experience of members likes: "In my opinions| As I know.... this is the best way..bla..bla.." but we should test it. Therefore, manually testing as well as automation testing is more and more necessary nowadays. "Don't think, just try...

JSF, Primefaces - Invoking Application Code Even When Validation Failed

A use case I have a form which has requirements as follow: - There are some mandatory fields. - Validation is triggered when changing value on each field. - A button "Next" is enable only when all fields are entered. It turns to disabled if any field is empty. My first approach I defined a variable "isDisableNext" at a backend bean "Controller" for dynamically disabling/enabling the "Next" button by performing event "onValueChange", but, it had a problem: <h:form id="personForm"> <p:outputLabel value="First Name" for="firstName"/> <p:inputText id="firstName" value="#{person.firstName}" required="true"> <p:ajax event="change" listener="#{controller.onValueChange}" update="nextButton"/> </p:inputText> <p:outputLabel value="Last Name" for="lastName"/> <p:i...

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<...

A User Guide To Working With Huong

Introduction I write this user guide to help us (you and me) have a good collaboration at work. I hope you also share yours. How I view success We all feel passionate and happy at work. We all enjoy discussing transparently. We take it easy to give and receive feedback. After all, we together develop and bring valuable applications to users. How I communicate I mostly prefer a face-to-face conversation. Just leave me a message on Slack if you don't want to come to my desk. For a big topic which takes more than 30 minutes, we should have a meeting. Only send me emails only if stuff is very formal or out-of-office hours Things I do that may annoy you I do practice the Pomodoro technique so that sometimes you see me in the "do not disturb" mode. Often to make things clear, I am at ease talking frankly with you. What gains and loses my trust It is easy to gain my trust when you commit to what you say. You show your passion and endeavors to achieve that. It is easy to lo...

vhandit

Search This Blog