Skip to main content

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

Popular posts from this blog

Selenium - Override javascript functions to ignore downloading process

I have got an issue with downloading process on IE 8. This browser blocks my automatic-download functionality on my app so that I could not work with my test case any more after that. In my case, I didn't care about the file is downloaded or not, I just focus on the result after downloading process finished successfully. Therefore, I found a solution to ignore this process so that I can work normally. I use Primefaces, here is the remote command to trigger the download process <p:remoteCommand name="cmdGenerateDocument" actionListener="#{logic.onGenerateDocument}" update="xrflDocumentCreationPanel" oncomplete="clickDownloadButton();"/> The following is my test case: @Test public void shouldUpdateStep6ToWarningIfStep1IsValidAfterFinished(){ MainPage mainPage = new MainPage(); waitForLoading(mainPage.getDriver()); EmployeeDetailPage empDetailPage = new EmployeeDetailPage(); waitForLoading(empDetailPage.getDriver()); e...

[Snippet] CSS - Child element overlap parent

I searched from somewhere and found that a lot of people says a basic concept for implementing this feature looks like below: HTML code: <div id="parent">  <div id="child">  </div> </div> And, CSS: #parent{   position: relative;   overflow:hidden; } #child{   position: absolute;   top: -1;   right: -1px; } However, I had a lot of grand-parents in my case and the above code didn't work. Therefore, I needed an alternative. I presumed that my app uses Boostrap and AngularJs, maybe some CSS from them affects mine. I didn't know exactly the problem, but I believed when all CSS is loaded into my browser, I could completely handle it. www.tom-collinson.com I tried to create an example to investigated this problem by Fiddle . Accidentally, I just changed: position: parent; to position: static; for one of parents -> the problem is solved. Look at my code: <div class="modal-body dn-placeholder-parent-positi...

Generating PDF/A From HTML in Meteor

My live-chat app was a folk of project Rocket.Chat which was built with Meteor. The app had a feature that administrative users were able to export the conversations into PDF files. And, they wanted to archive these files for a long time. I happened to know that PDF/A documents were good for this purpose. It was really frustrated to find a solution with free libraries. Actually, it took me more than two weeks to find a possible approach. TL, DR; Using Puppeteer to generate a normal PDF and using PDFBox to load and converting the generated PDF into PDF/A compliance. What is PDF/A? Here is a definition from Wikipedia: PDF/A  is an  ISO -standardized version of the  Portable Document Format  (PDF) specialized for use in the  archiving  and long-term  preservation  of  electronic documents . PDF/A differs from PDF by prohibiting features unsuitable for long-term archiving, such as  font  linking (as opposed to  font em...

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

[Snippet] Generate a new unique "name" string from an existing list

Suppose that we have a list of employees. Everytime, we want to add new employee into this list, the name of the employee will be generated with the following rules: - the name of the new one is set to " [originalname] 1 " - in case the name already exist, " [originalname] 2 " is used, and so on. Here is my code snippet by Javascript: var employees =[ {id: 1, name: 'name'}, {id: 2, name: 'name 1'}, {id: 3, name: 'name 2'}, {id: 5, name: 'name 4'} ]; var commonUtils = { isExistName: function(_name, _collection, _prop) { for(var i = 0; i< _collection.length; i++){ if(_collection[i][_prop].localeCompare(_name)==0){ return true; } } return false; }, generateNewName: function(_name, _collection, _prop){ var i = 1; var searching = true; while (searching) { var newName = _name+ " " + i; if (!this.isExistName(newName, _collection, _pro...