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

[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-position&quo

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<

Styling Sort Icons Using Font Awesome for Primefaces' Data Table

So far, Primefaces has used image sprites for displaying the sort icons. This leads to a problem if we want to make a different style for these icons; for example, I would make the icon "arrow up" more blurry at the first time the table loading because I want to highlight the icon "arrow down". I found a way that I can replace these icons with Font Awesome icons. We will use "CSS Pseudo-classes" to achieve it. The hardest thing here is that we should handle displaying icons in different cases. There is a case both "arrow up" and "arrow down" showing and other case is only one of these icons is shown. .ui-sortable-column-icon.ui-icon.ui-icon-carat-2-n-s { background-image: none; margin-left: 5px; font-size: 1.1666em; position: relative; } .ui-sortable-column-icon.ui-icon.ui-icon-carat-2-n-s:not(.ui-icon-triangle-1-s)::before { content: "\f106"; font-family: "FontAwesome"; position:

Selenium - Use Explicit Waits for checking elements quickly disappear like loading icon

I have a table that is displayed a list of competence groups. When I click on a competence group, it will display a table that contains a lot of criteria belong to the competence group. Each times I click on a competence group, a "loading" icon is displayed while waiting for all criteria is fully displayed. <div id="loading" style="display: none;"> <div></div> <div></div> I tried to write a Selenium test to make sure this behavior is covered. I saw that the loading icon element is always available on DOM tree because I just used Jquery to handle its displaying. Beside that, the loading icon is appeared dynamically and quickly disappear afterwards. It is hard to checking the visibility on GUI of loading icon. By normal way that I frequently used, the code looks like: public boolean isLoadingIconDisplayed() { List<WebElement> loadingIcons = driver.findElements(By.id("loading")); if(!loadingIcons.isE

BarcampSaigon 2015

Barcamp Saigon is one of my most expected events of the year. This year, it took place at RMIT university. As usual, it brought many useful topics to the community. Here is all topics that I have attended. Scale it! - Lars Jankowfsky Lars is founder of 8bitrockr.com How do we make a decision correctly? It is hard to know that until we try and measure it. He gave an example about how good an app was. And, most of people thought that the app with nice user interfaces is good at the first look. But it is not correct because it is only true until we try to use it, even the nice GUI app sometime is not good at UX, functionalities, etc. The key of success for working in team is collaboration. We can not only base on the experience of members likes: "In my opinions| As I know.... this is the best way..bla..bla.." but we should test it. Therefore, manually testing as well as automation testing is more and more necessary nowadays. "Don't think, just try&q