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

My must-have apps for daily work

There is no doubt that cool apps can help us be more productive and enjoyable at work. For the time being, I really love the following apps which are used by me almost every day. 1. A personal Kanban In fact, a personal kanban is the most useful app for me. Why does it matter? It is not just a to-do list, but it keeps me motivated every day because it helps me be able to know what my "big picture" is. I usually set up my plans together with a path to reach them. KanbanFlow is my preferred tool. KanbanFlow 2. A terminal Needless to say, a terminal is a must-have app for every developer, especially the ones use macOS/Linux. Due to its importance, I love to decorate and enhance it to be super exciting with various tools such as iTerm , oh-my- zsh , and thefuck . ;) iTerm + oh-my-zsh 3. A documentation "ecosystem" As a developer, I can not remember all things that I have experimented a day. Moreover, a document is really useful for sharing an...

Coding Exercise, Episode 1

I have received the following exercise from an interviewer, he didn't give the name of the problem. Honestly, I have no idea how to solve this problem even I have tried to read it three times before. Since I used to be a person who always tells myself "I am not the one good at algorithms", but giving up something too soon which I feel that I didn't spend enough effort to overcome is not my way. Then, I have sticked on it for 24 hours. According to the given image on the problem, I tried to get more clues by searching. Thanks to Google, I found a similar problem on Hackerrank (attached link below). My target here was trying my best to just understand the problem and was trying to solve it accordingly by the Editorial on Hackerrank. Due to this circumstance, it turns me to love solving algorithms from now on (laugh). Check it out! Problem You are given a very organized square of size N (1-based index) and a list of S commands The i th command will follow t...

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

If We Want to Go Fast, We Need to Go Well

Have you ever thought that we won't need to code anymore because programs might be generated from specification? The answer can be yes or no; there is still arguing about it. The programming language is more and more closed to the requirements. The starting is from a very low level as Assembly to a very high level like Python. However, it doesn't make much sense when saying that we will eliminate coding. For me, we currently still need to express our ideas in exact words that tells the machine what we want. Otherwise, I hope in the future the machine is intelligent enough to understand our requirements directly from our words. ;) Take a look at the famous quote of Robert C.Martin about what I mentioned above: "Remember that code is really the language in which we ultimately express the requirements. We may create languages that are closer to the requirements. We may create tools that help us parse and assemble those requirements into formal structures. But we wi...

Installing NGINX on macOS

I have heard of a lot of NGINX recently. One of them was it can help for security issues; for sure, it much be more. It so happens that our team has got a ton of user stories from a security audit. It's time to delve into it. What is NGINX? In order to get a basic idea and have some fun , I've just picked some available posts from my favorite Vietnamese blogger communities as below: https://kipalog.com/posts/Cau-hinh-nginx-co-ban---Phan-1 https://viblo.asia/hoang.thi.tuan.dung/posts/ZabG912QGzY6 NGINX (pronounce: Engine-X) is a web server (comparing to IIS, Apache). It can be used as a reverse proxy ( this is what I need for security issues with configuration ), load balancer and more. How to get started? I found the below path for learning NGINX by googling "learn nginx": https://www.quora.com/What-are-some-good-online-resources-to-learn-Nginx In this post, I only went first step. This is installing NGINX on macOS and taking a first look at the confi...

vhandit

Search This Blog