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

Building a Wizard with Chain of Responsibility Pattern

What is the Idea? We want to create a page that there are some steps and each step has its own business. Users are able to click on a step and its status could be changed. Primefaces owns a component " Wizard " but it it quite hard for us in order to apply our very specific and complicated business domain logic on each step; even we cannot click on a step of this component. We somehow are able to use the component " TabView " works with a strong back-end mechanism. A backend mechanism! what do I mean? Yes, we need it because we want to abstract the behaviors of each step otherwise we will get trouble with many events handling. Obviously, each step has some behaviors such as "next", "back" and "switch' are the same and they are related to each other; but the business of these behaviors can be different totally. That is where the pattern "Chain of Responsibility" can be applied. Step by Step Building It! In this simple pr...

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

A Template for Software Engineering Standards

Software engineering standard template A well-structured standard acts as a blueprint that guides engineers in their daily tasks and long-term goals. Below, I will outline a template for creating a comprehensive software engineering standard. Header The header serves as the document's identifier. It contains the following: Authors : The people who have contributed to the creation of the standard. Created Date : The date when the document was initially created. Version : The version of the standard. It is typically updated with significant changes. Status : The current status of the document, whether it's in draft, in-review, or official. Next Review Date : The date when the standard will be reviewed for relevancy and accuracy. Table of Contents A table of contents provides an overview of what the document contains, making it easier for readers to navigate through the document. Body The body of the standard comprises: Values : The core beliefs that guide the decision-maki...

Junit - Test fails on French or German string assertion

In my previous post about building a regex to check a text without special characters but allow German and French . I met a problem that the unit test works fine on my machine using Eclipse, but it was fail when running on Jenkins' build job. Here is my test: @Test public void shouldAllowFrenchAndGermanCharacters(){ String source = "ÄäÖöÜüß áÁàÀâÂéÉèÈêÊîÎçÇ"; assertFalse(SpecialCharactersUtils.isExistSpecialCharater(source)); } Production code: public static boolean isExistNotAllowedCharacters(String source){ Pattern regex = Pattern.compile("^[a-zA-Z_0-9_ÄäÖöÜüß áÁàÀâÂéÉèÈêÊîÎçÇ]*$"); Matcher matcher = regex.matcher(source); return !matcher.matches(); } The result likes the following: Failed tests: SpecialCharactersUtilsTest.shouldAllowFrenchAndGermanCharacters:32 null A guy from stackoverflow.com says: "This is probably due to the default encoding used for your Java source files. The ö in the string literal in the J...

Strategy Design Pattern

For example, I have a program with an Animal abstract class and two sub-classes Dog and Bird. I want to add new behavior for the class Animal, this is "fly". Now, I face 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 interface with method "fly" inside. The same issue to an 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.pr...

vhandit

Search This Blog