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

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

How to convert time between timezone in Java, Primefaces?

I use the calendar Primefaces component with timeOnly and timeZone attributes for using only hour format (HH:mm). Like this: <p:calendar id="xabsOvertimeTimeFrom" pattern="HH:mm" timeOnly="true" value="#{data.dateFrom}" timeZone="#{data.timeZone}"/> We can convert the value of #{data.dateFrom} from GMT/UTC time zone to local, conversely, from local time zone to GMT/UTC time zone. Here is my functions: package vn.nvanhuong.timezoneconverter; import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.Calendar; import java.util.Date; import java.util.TimeZone; public class TimeZoneConverter { /** * convert a date with hour format (HH:mm) from local time zone to UTC time zone */ public static Date convertHourToUTCTimeZone(Date inputDate) throws ParseException { if(inputDate == null){ return null; } Calendar calendar = Calendar.getInstance(); calendar.setTime(inputDate); int ...

4 Remarkable Notes for JSF Apps Using HTML5

In the previous post , I've already shared with you how my team consults clients by using a HTML prototype. This post is about the used technologies for reusing the provided HTML template and communicating with backend. What is the issue when using HTML elements with Primefaces components? Primefaces is a great extension for developing JSF web apps. However, it is really frustrating in case we have to make it work with an existing HTML template. Why? - Primefaces has its own theme for styling. - Primefaces changes the HTML structure. Therefore, that would be a huge effort to use the Primefaces' components to replicate the elements of the HTML template; especially it is impossible for images drawing by " canvas " tag. That requires us to find a better approach. Since Java EE 7 (introducing JSF 2.2 included), it supports to use HTML5 elements . The idea is that JSF components don't effect the style and HTML structure, so we can easily reuse the provided HTM...

Updates to the Scrum Guide - The 5 Scrum Values

This article is available at blog.scrum.org , here I just quote my favorite points and give my comment at the end of this post. Ken Schwaber and Jeff Sutherland, the creators of Scrum delivered a webinar on their latest update to the Scrum Guide . The update was a simple one, adding the 5 values of Scrum to the Guide: These values sound easy? Well, there are many misunderstandings and common problems when applying these values. Here are some example: Value Misunderstanding Getting the value right Commitment Committing to something that you don’t understand because you are told to by your boss. Committing yourself to the team and Sprint Goal. Focus Focusing on keeping the customer happy Being focused on the sprint and its goal. Openness Telling everyone everything about all your work Highlighting when you have challenges and problems that are stopping you from success Respect Thinking you are helping the team by being a hero Helping peop...

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

vhandit

Search This Blog