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

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

The HelloWorld example of JSF 2.2 with Myfaces

I just did by myself create a very simple app "HelloWorld" of JSF 2.2 with a concrete implementation Myfaces that we can use it later on for our further JSF trying out. I attached the source code link at the end part. Just follow these steps below: 1. Create a Maven project in Eclipse (Kepler) with a simple Java web application archetype "maven-archetype-webapp". Maven should be the best choice for managing the dependencies , so far. JSF is a web framework that is the reason why I chose the mentioned archetype for my example. 2. Import dependencies for JSF implementation - Myfaces (v2.2.10) into file pom.xml . The following code that is easy to find from http://mvnrepository.com/ with key words "myfaces". <dependency> <groupId>org.apache.myfaces.core</groupId> <artifactId>myfaces-api</artifactId> <version>2.2.10</version> </dependency> <dependency> <groupId>org.apache.myfaces.core<...

BIRT - Fix the size of an image

I use a dynamic image as a logo my report in pdf. At the beginning, I use table to align the logo in left or right. I meet a problem with some images with a large width or height. My customer requires that the logo should be displayed in original size. These following steps solves my problem: 1. Use Grid instead of Table 2. Set Grid "Height" is 100% and "Width" is blank 3. Set "Fit to container" for images are "true". Download the the template here .

Just another career path

As a software engineer, I recently have heard of a lot of feedback from my colleagues and friends that they don’t see their career path or they don’t know how to move to the new levels in their company. No exception, I used to have that thinking before. In my opinion, there is a very important reason why people are struggling to find the answer because “career path is not always the job titles”. Normally, each company has its own job titles such as junior-level developer, middle-level developer, senior-level developer, teach lead, software architect, CTO, etc. Hence, it is not true that a job title is reasonable for every company. The interview is often conducted hardly to find a candidate matching the company title. If we have a good enough job title standard, the interview would take place very easily, right? Therefore, I prefer to define my own career path through what skills are gained under a job title. But wait, why do I need a career path? To me, a career is an indispensabl...

vhandit

Search This Blog