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

How to apply Lean - Kanban for your business

This is the topic of Scrum Breakfast meetup this time, speaker: Ms. Phuong Bui - Technical Project Manager of YOOSE Pte. Ltd. http://www.meetup.com/Scrum-Breakfast-Vietnam-Agile-and-Scrum-Meetup/events/230313727/ Lean comes from Lean manufacturing is a method that focuses on elimination of wastes. In other words, this is a set of principles for archiving the quality, speed and customer alignment. The first time I knew about the term "Lean" is from the book Software Craftsmanship . Sandro recommends if we want to transform our pet projects into a real business, we should get familiar with Lean Startup concepts. In this talk, Ms. Phuong pointed out some major wastes includes information (ex: unclear requirements), processes (ex: waiting), physical environment and people. Knowing what the problems should be the best way to eliminate them. The difference between Single item flow and Batch processing is the second main point; and it is the Lean's idea. Batch pr...

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

From JSP to AngularJS

Our team maintained a project that was used a quite old web technology JSP . Our project likes a web portal that can contain some other smaller projects, I called it a module. Now, our customers want to add a new module into it. We met a problem is the current projects can't be testable and hard to maintain because both the logic and GUI are mixed together by using JSP and JSTL. It was really a messy project structure. Therefore, we didn't want to continue this approach. Testing is very important, as well as a good structure for maintenance. We would like to apply MVC pattern for testable and maintainable ability purpose. Yeah, that was actually time for changes. Our project structure can't be testable and has poor structure. We listed out some options: Refactoring all current modules -- terrible approach, too much efforts, too risky due to a lot of modules. Using MVC just for the new modules with Servlet for C ontroller, Java class for M odel and JSP for V i...

Improving the execution time of CI pipelines

Executing a large number of tests, especially integration tests, takes a lot of time. For instance, the pipeline of one of our projects for each Pull Request previously took nearly 30 minutes, including over 1 thousand test cases. This article guides you through several good techniques that we have discovered and applied to improve the time-consuming process. Parallel stages Analyze the current phases in your pipeline and categorize them in parallel. For example, we can separate the build and verify code of Node.js and Maven modules simultaneously in our Jenkins pipelines. Please mind using the setting failFast whether you want to abort the pipeline immediately. Read more: Parallel stages with Declarative Pipeline 1.2 (jenkins.io) Parallel test execution If you use Maven, t he plugin maven-failsafe-plugin is used to execute integration tests during phases integration-test and verify the build lifecycle. It allows us to execute tests in parallel. There are many settings related ...

Sharing a virtualenv across several Python projects using Pipenv

There is a standard library for all projects in Python. However, several projects don’t always have the same dependencies all the time. That is where virtual environments come to play. You can follow this official document to use two separated tools virtualenv and pip to fulfill that need. My preferred alternative is to use pipenv . Pipenv is easy to use and convenient. The following are my steps to make a shared virtualenv for my all projects which requires the same dependencies. Step 1. Create an isolated virtualenv. python -m venv my-shared-env Step 2. Create a symbolic link to the created virtualenv. cd project_1 ln -s ~/.local/share/virtualenvs/my-shared-env .venv I have encountered the following issue at step 1. FileNotFoundError: [Errno 2] No such file or directory: '{my_project_path}/.venv/bin/pip': '{my_project_path}/.venv/bin/pip' The root cause was I tried to create virtualenv by running pipenv install and renaming the generated virtualenv to ...

vhandit

Search This Blog