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

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

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

Attribute 'for' of label component with id xxxx is not defined

I got the warning in the log file when I have used the tag <h:outputLabel> without attribute " for " in xhtml file. It was really polluting my server log files. The logged information actually makes sense anyway! We could find an answer as the following: "Having h:outputLabel without a "for" attribute is meaningless. If you are not attaching the label, you should be using h:outputText instead of h:outputLabel." However, these solutions are not possible just for my situation. Instead of using h:outputText for only displaying text, my team has used h:outputLabel too many places. We were nearly in our release time (next day) so it is quite risky and takes much efforts if we try to correct it. Because the style (with CSS) is already done with h:ouputLabel . The alternative by adding attribute " for " the existing h:outputLabel is not reasonable either. I really need to find another solution. Fortunately, I came across a way if I cha...

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

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

vhandit

Search This Blog