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

Gzip upload on browsers

Today, I faced a problem that I could not upload my archive file with gzip format on Firefox, even it worked on Chrome. I was using macOS. My application had a setting to whitelist accepted files. I’ve already added "application/gzip" to that list. "It’s strange!", I thought. I finally figured out that my uploaded file's type actually was "application/x-gzip" on Firefox. I also asked my colleagues to check their uploaded files on Window and Ubuntu. Hmm… they were totally different! It was "application/x-compressed" on Window, and was "application/x-compressed-tar" on Ubuntu. In fact, gzip is already standardized by IANA. There is a note in RFC-6713 as below: "Some applications have informally used media types such as application/gzip-compressed, application/gzipped, application/x-gunzip, application/x-gzip, application/x-gzip-compressed, and gzip/document to describe data compressed with gzip. The media types defin...

DevOps Toolchain Enhancement

Historically, our company ubitec had started with a customer project. Agile/Scrum was our proposal for working with customers. Time by time, Agile/Scrum also became our culture for software development. To be successful with this development approach, we somehow needed to have a fast release for customers (i.e. every one week). Back then, we had a build tool Jenkins which was responsible for having sprint release packages for our customers. The build job pipelines contain some steps such as gathering the artifacts, checking the code convention, running the tests, building docker images, and packaging an archived file (a zip file). The set of tools involved in a pipeline is roughly called a toolchain. It is just a part of a bigger process called the DevOps toolchain. Source: https://www.ibm.com/blogs/cloud-archive/2016/11/devops-architecture-available-on-bluemix-garage-method-site/ DevOps is a proven method that fits Agile. Today, it is even treated as a mandatory factor...

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

Fulfilling Your Contribution Needs

Human resource management motivation Managing human today is quite different from the industrial age which treats people as just "chickens". Rather than people now are very important to the success of an organization. People are an organization's special resource. They should be encouraged to grow to contribute their effort and creativeness to their beloved working environment because the contribution is one of their most needs in life. Training people: getting rid of the ineffective model and adopting the new one The ineffective model of training people: Hiring new people --> giving them a crash course once --> expecting them working effectively. That somehow makes sense but you're about to expect a luck because you do not really spend your effort for mentoring them. If they can work effectively, well...lucky you! Otherwise, you will blame that these people are ineffective and you let them go and hire the new ones. What a waste of time! The new effe...

vhandit

Search This Blog