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

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

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

Creating a Chatbot with RiveScript in Java

Motivation "Artificial Intelligence (AI) is considered a major innovation that could disrupt many things. Some people even compare it to the Internet. A large investor firm predicted that some AI startups could become the next Apple, Google or Amazon within five years"   - Prof. John Vu, Carnegie Mellon University. Using chatbots to support our daily tasks is super useful and interesting. In fact, "Jenkins CI, Jira Cloud, and Bitbucket" have been becoming must-have apps in Slack of my team these days. There are some existing approaches for chatbots including pattern matching, algorithms, and neutral networks. RiveScript is a scripting language using "pattern matching" as a simple and powerful approach for building up a Chabot. Architecture Actually, it was flexible to choose a programming language for the used Rivescript interpreter like Java, Go, Javascript, Python, and Perl. I went with Java. Used Technologies and Tools Oracle JDK 1.8...

Safari (older than 14.1.1) rejects TLS connections of TURN with Let's Encrypt certificates

Summary We could not make a video call successfully on Safari older than 14.1.1. The call kept disconnecting for some seconds. We got the following error in Nginx’s log SSL: error:14094418:SSL routines:ssl3_read_bytes:tlsv1 alert unknown ca:SSL alert number 48   Root cause The Safari didn’t trust our TLS certificates (certified by Let’s Encrypt) when establishing a TLS connection into our TURN server. It is a known issue that could be found at Bug 219274 - ICE does not resolve for `turns` relay candidates rooted in LetsEncrypt CA . The issue was just recently fixed (end of 2020), therefore old versions of Safari still meet the issues.   Solution In our development environment, we replaced the untrusted certificate with a trusted one. We will warn our customers about this issue in our installation guide. Technical explained WebKit is a browser engine developed by Apple and primarily used in its Safari web browser, as well as all iOS web browsers. The WebRTC of WebKit relied on ...

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