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

JSF 2 - Dynamically manipulating the component tree with system events

Let's suppose we want to modify the metadata (attributes) of elements such as render , requried , maxlength but we do not define in JSF tags. The manipulating components can be conducted in Drools files, for example. How could we do? I think that is what we need to change something of component tree during JSF life-cycle. JSF supports event handling throughout the JSF life-cycle. In this post, I use two events: postAddToView for scanning components tree and preRenderView for manipulating the meta of components before rendering to GUI. I modified my own project from previous post for this example. This is my first further JSF trying out with the project as I said before. :) We define the tags f:event below the form - a container component of the components which we want to work on. The valid values for the attribute type for f:event can be found from tag library document of JSF 2. <!DOCTYPE html> <html xmlns="http://www.w3.org/1999/xhtml" x...

Make simple music program with beep(freq, duration) with Pascal

Pascal is my first programing language when I have studied in high school. It was really exciting for me. :) The Pascal programming language was created by Niklaus Wirth in 1970. It was named after Blaise Pascal, a famous French Mathematician. It was made as a language to teach programming and to be reliable and efficient. Pascal has since become more than just an academic language and is now used commercially . I tried to make a simple music program by using Lazarus IDE on MS Window 7, 64-bit. It frustrated me a few times how difficulty to use Sound command to make a sound. Sound did not work on my compiler and my platform anymore. So far, I just could use beep(freq, duration) from window unit to implement my work. Here is my code. ;) program mysong; uses Windows, crt; const C: Integer = 512; { x = A * EXP(LN(2)/12)} C_: Integer = 542; D: Integer = 574; D_: Integer = 608; E: Integer = 644; F: Integer = 682; F_: Integer = 723; G: Integer = ...

AngularJS - Build a custom validation directive for using multiple emails in textarea

AngularJS already supports the built-in validation with text input with type email. Something simple likes the following: <input name="input" ng-model="email.text" required="" type="email" /> <span class="error" ng-show="myForm.input.$error.email"> Not valid email!</span> However, I used a text area and I wanted to enter some email addresses that's saparated by a comma (,). I had a short research and it looked like AngualarJS has not supported this functionality so far. Therefore, I needed to build a custom directive that I could add my own validation functions. My validation was done only on client side, so I used the $validators object. Note that, there is the $asyncValidators object which handles asynchronous validation, such as making an $http request to the backend. This is just my implementation on my project. In order to understand that, I supposed you already had experiences with ...

Books Read in 2022

My bookshelf Technical - Operating System: Three Easy Pieces. Andrea Arpaci-Dusseau, Remzi Arpaci-Dusseau. - The Effective Engineer. Edmond Lau. - English Grammar in Use. Raymond Murphy - Mythical Man-Month, The: Essays on Software Engineering. Brooks Jr., Frederick P. - Peopleware: Productive Projects and Teams (3rd edition). Tom DeMarco, Timothy Lister. - A Philosophy of Software Design. John Ousterhout. - Modern Computer Architecture and Organization: Learn x86, ARM, and RISC-V architectures and the design of smartphones, PCs, and cloud servers. Jim Ledin. Thought Provoking - Đúng Việc. Giản Tư Trung. - A Brief History of Time. Stephen Hawking. - Một đời như kẻ tìm đường. Phan Văn Trường. - Một đời thương thuyết. Phan Văn Trường. - Tinh hoa xử thế - Dám bị ghét. Kishimi Ichiro, Koga Fumitake. - Phép màu để vượt lên chính mình. Nhan Húc Quân. - Scouting for Boys: A Handbook for Instruction in Good Citizenship Through Woodcraft. Robert Baden-Powell. - Thay Đổi Cuộc Sống Với Nhân ...

A Template for Software Engineering Standards

Software engineering standard template A well-structured standard acts as a blueprint that guides engineers in their daily tasks and long-term goals. Below, I will outline a template for creating a comprehensive software engineering standard. Header The header serves as the document's identifier. It contains the following: Authors : The people who have contributed to the creation of the standard. Created Date : The date when the document was initially created. Version : The version of the standard. It is typically updated with significant changes. Status : The current status of the document, whether it's in draft, in-review, or official. Next Review Date : The date when the standard will be reviewed for relevancy and accuracy. Table of Contents A table of contents provides an overview of what the document contains, making it easier for readers to navigate through the document. Body The body of the standard comprises: Values : The core beliefs that guide the decision-maki...

vhandit

Search This Blog