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

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

Regex - Check a text without special characters but German, French

Special characters such as square brackets ([ ]) can cause an exception " java.util.regex.PatternSyntaxException " or something like this if we don't handle them correctly. I had met this issue. In my case, my customers want our application should allow some characters in German and French even not allow some special characters. The solution is that we limit the allowed characters by showing the validation message on GUI. For an instance, the message looks like the following: "This field can't contain any special characters; only letters, numbers, underscores (_), spaces and single quotes (') are allowed." I used Regular Expression to check it. For entering Germany and French, I actually don't have this type of keyboard, so I referred these sites: * German characters: http://german.typeit.org/ * French characters: http://french.typeit.org/ Here is my code: package vn.nvanhuong.practice; import java.util.regex.Matcher; import java.util...

Tip for resolving the compile errors when importing a Maven project in Eclipse

Sometimes, I import a existing Maven project into Eclipse and I get some compile errors related to "pom.xml", "facet version of Web", and so on. It was really frustrating me because I even cleaned, built and updated the project many times but the errors still occurred. I accidentally found the following steps to resolve this issue but honestly I still don't know why. Step 1 : Delete the project that met the compile errors in Eclipse, but don't delete it on disk. Step 2 : Open the project (by Windows Explorer if you use Windows) and remove file/folder ".classpath", ".settings" and ".project" . Step 3 : Import the project back into Eclipse. ---^0^--- Maven is a build automation tool used primarily for Java projects. Eclipse is an integrated development environment (IDE).

Changing source code at run-time with Service Locator pattern

I have a service to get some data but the result can be different basing on where the implementation is. Technically, I have two or more concrete implementation of an interface and I am able to switch using these concrete classes at run-time. That means I have a place to configure it without re-deploying the application. In order to overcome this issue, I use Service Locator design pattern and here I only care about two advantages below: Encapsulating the specific implementation, we just declare the name and don't care about the implementation of the service. Changing the implementation at run-time. Client : an object that invokes the services via Service Locator Business services : services that is used by Client.

vhandit

Search This Blog