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

Set up a web server for learning HTTP headers

Motivation We all follow the client-server model using the HTTP protocol for most of our web apps today. In development, we simply may have a backend API server and a frontend (web pages or mobile apps) only. However, it seemed that a proxy server is always required for production. In fact, most of the hardest issues in production come from integration. The requests and responses might be modified by the proxy server. Therefore, the understanding of HTTP protocol is one of the key skills to resolve those issues. I wanted to dive deep into HTTP with some core concepts such as caching, cookies, and CORS. I didn't intend to go quickly rather than moved slowly to have a well understanding of what I do. Prepare a server The easiest way is to use my laptop as a server then I can just use "localhost". I can also use ngrok to make my web server online. Finally, I use an online tool such as RedBot to check the HTTP headers. To make it more excited though, I deployed the app on A...

What the heck is Meteor DDP?

I was using Meteor for my messenger project. I was so curious about the real time connection. I wanted to know how exactly this mechanism works. In this post, I will go through the DDP Specification, an overview of WebSocket, and a simple demo about how to subscribe a publication of Rocket.Chat (containing a DDP server) from an external webpage. At a glance, I knew that Meteor invented a protocol called DDP which uses for handling real time connection. So then, what is DDP? "DDP (Distributed Data Protocol) is the stateful WebSocket protocol that Meteor uses to communicate between the client and the server." [1] All right! Why does DDP matter? "DDP is a standard way to solve the biggest problem facing client-side JavaScript developers: querying a server-side database, sending the results down to the client, and then pushing changes to the client whenever anything changes in the database" . [2] In order to understand deeply the protocol, I decided ...

Merging source in SVN

My team has used Primefaces for our projects. We sometimes have several branches of the projects with a new Primefaces's release. For example, we currently have a project with two branches, a branch for using Primeface 4.0, a trunk for using Primeface 5.0, and we are working these parallel branches. Our project looks like the following: - myProject - branches + primefaces4 + tag + trunk (primefaces5) My problem is how to copy the same source from the trunk to the branch "primefaces4". That is where SVN Merging can help! Here is the steps those I have conducted in my project. Step 1 : open the project with the branch "primefaces4" Step 2 : Team > Merge... Chose the trunk's URL. For example: http://192.168.9.10/svn/myProject/trunk Step 3 : Select the revision from "trunk" to merge. For example: +--revision--+--date--------+--author----+--comment---+ + 10 + 03.10.2014 + vanhuong + f1: part 3 + + 9 ...

Validate date with Datejs

Datejs is an open source JavaScript Date library for parsing, formatting and processing. Website: http://www.datejs.com function isValid(date, pattern){ if(pattern == null){ return false; } var parseExact = Date.pareExact(date, pattern); if(parseExact !== null){ return true; } return false; } Another popular date library is Moment.js

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

vhandit

Search This Blog