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

Google I/O 2017 Notes

WOW! How meaningful this below video explains about the name of "I/O". Sundar Pichai talked a lot of Machine Learning Machine Learning is a very hot trend these days. Google uses it for their products. Google Assistant: Easily booking an online meal by talking with Google Assistant like a staff of partners, for example. Google Home: Hands-free calling. Google Photos: sharing suggestion, shared library, photo books and google lens. Youtube: 360 degree video, live stream. Kotlin became an official programming language for Android https://kotlinlang.org I'm on the way to Kotlin! ^^ Reference: [1]. https://www.youtube.com/watch?v=Y2VF8tmLFHw

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

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

Only allow input number value with autoNumeric.js

autoNumeric is a jQuery plugin that automatically formats currency and numbers as you type on form inputs. I used autoNumeric 1.9.21 for demo code. 1. Dowload autoNumeric.js file from https://github.com/BobKnothe/autoNumeric 2. Import to project <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js"></script> <script type="text/javascript" src="js/autoNumeric.js"></script> 3. Define a function to use it <script type="text/javascript"> /* only number is accepted */ function txtNumberOnly_Mask() { var inputOrgNumber = $("#numberTxt"); inputOrgNumber.each(function() { $(this).autoNumeric({ aSep : '', aDec: '.', vMin : '0.00' }); }); } </script> 4. Call the function by event <form> <input type="text" value="" id="numberTxt"/>(only number) </form> <script ty...

How I did customize "rasa-nlu-trainer" as my own tool

Check out my implementation here Background I wanted to have a tool for human beings to classify intents and extract entities of texts which were obtained from a raw dataset such as Rocket.chat's conversation, Maluuba Frames or here . Then, the output (labeled texts) could be consumed by an NLU tool such as Rasa NLU. rasa-nlu-trainer was a potential one which I didn't need to build an app from scratch. However, I needed to add more of my own features to fulfill my needs. They were: 1. Loading/displaying raw texts stored by a database such as MongoDB 2. Manually labeling intents and entities for the loaded texts 3. Persisting labeled texts into the database I firstly did look up what rasa-nlu-trainer 's technologies were used in order to see how to implement my mentioned features. At first glance rasa-nlu-trainer was bootstrapped with Create React App. Create React App is a tool to create a React app with no build configuration, as it said. This too...

vhandit

Search This Blog