DEV Community: Ryo Light

Binary Insertion Sort

Ryo Light — Tue, 20 Sep 2022 20:39:49 +0000

Why do we sort?

Often the tasks we perform on arrays, e.g. searching, can be significantly optimized when the array is sorted.

The reason? Because we're able to find the relevant data so much faster.

Classic insertion sort looks like this.

public static void insertionSort(int[] nums) {

    for(int i=1; i < nums.length; ++i) {
        int current = nums[i], j;

        for(j=i-1; j >= 0 && current < nums[j]; --j)
            nums[j+1] = nums[j];

        nums[j+1] = current;
    }
}

We're creating a sorted window on the left side of the array, adding each new element to its correct position by linearly traversing from the window's inner (right) edge.

When an array is sorted in reverse, we observe the worst case time complexity of O(n^2) as every element needs to be compared to every other element.

Can we do better? Let's try!

Binary Insertion Sort

Analyzing the classic Insertion sort, we see it centers around 2 core steps:

Find the next element's proper insert position in the sorted window - O(n)
Make room by shifting all greater elements - O(n)

Both of these steps take linear time and are applied to every element (O(n)).

Classic Time Complexity = O(n (n + n)) = O(n^2 + n^2) = O(n^2)

Let's attempt to optimize the individual steps.

Step 1. Is there anyway we can find the insert position faster than O(n)?

Actually yes! Since the window is sorted, we can use binary search in place of linear search to improve this step exponentially.

Step 2. Is shifting elements one by one the only way?

Unfortunately so, however Java has a built-in System API, System.arraycopy(), which optimizes the process.

Let's look at the Java implementation for the Binary variant.

public static void insertionSortCoffeeless(int[] arr) {
    for(int i=1; i < arr.length; ++i) {
        current = arr[i];

        int j = findInsertPosition(arr, 0, i-1, current);
        System.arraycopy(arr, j, arr, j + 1, i - j);

        arr[j] = current;
    }
}

private static int findInsertPosition(int[] nums, int lB, int rB, int target) {
    int mid=(lB+rB)/2;

    while(lB<=rB) {
        mid=(lB+rB)/2;

        if(target < nums[mid]) rB=mid-1;
        else lB = mid+1;
    }

    return target < nums[mid] ? mid : mid+1;
}

Binary Time Complexity = O(n (log n + n)) = O(nlog n + n^2) = O(n^2)

After the improvements we still have a Big O of n-squared, however based on the derivation we see it should perform somewhat faster.

The bottleneck shifts from finding the correct position, to shifting all greater elements over by one.

How much faster is it practically?

Below are the results of comparing common sorts on 32-bit integer arrays of increasing size.

The Binary variant remains practical (under 5 ms) for lists of up ~20,000 elements.

And if in the future, computer architectures allow a variable-length block of memory to be overwritten in constant time, we have an in-place, stable sort with a guaranteed time complexity of O(nlog n).

Until Next Time,
Ryo

References

Test Naming Convention

Ryo Light — Thu, 28 Jul 2022 18:51:00 +0000

There are only two hard things in Computer Science: cache invalidation and naming things. –Phil Karlton

There may be nothing as subjective as a good name. Luckily we're naming tests, not children, so we'll get by.

The Class Name

There are 2 parts to a test name: the class name and the method name. It's important to remember the significance of the former.

The class name should provide clarity to the logical grouping of tests it contains. Some examples:

UsersApiTests
FileUploadTests
UserContractValidationTests

The Method Name

I've adapted 2 useful formats for the method name: the happy path, and the edge case.

These conventions are used above the unit test level in the testing pyramid, e.g. component, integration, e2e tests.

We'll cover unit test naming towards the end.

Format: Happy Path

A happy path test makes sure the functionality works as expected when given straightforward inputs.

<Functionality>_VERIFY_<Result>

Note: Writing connectors, e.g. "verify", in all CAPS allows us to visually parse the components more easily.

Composition

<Functionality>
: The general functionality to be tested; more granular than the class name, adds clarity

<Result>
: The expected test outcome or behavior, e.g. return value, response code, state change, action taken

Examples

FileUploadTests.DeviceUpload_VERIFY_PdfUploadToKindleSuccess
FileUploadTests.DeviceUpload_VERIFY_TxtUploadToKindleFails
FileUploadTests.CloudUpload_VERIFY_EpubUploadSuccess
UsersApiTests.UsersPost_VERIFY_Response201Created

Format: Edge Case

An edge case test makes sure the functionality is working as expected when the inputs are not ideal, e.g. out of bounds, on the fringe, or otherwise.

<Functionality>_WHEN_<Condition>_THEN_<Result>

Note: Including "when" and "then" clarifies the method name components for programmers and non-programmers alike.

Composition

<Condition>
: The condition, state, or branch of logic to be isolated

Examples

FileUploadTests.CloudUpload_WHEN_UserNotPremiumMember_THEN_PDFUploadFails
UsersApiTests.UsersPost_WHEN_InvalidRequestParams_THEN_Response400BadRequest
UsersApiTests.UsersPost_WHEN_NameLengthBelowMin_THEN_Response400BadRequest

It's a good idea for the scope of a test name to reflect the target code's level of abstraction. Compare these to the above UserApiTests.

UserCreationTests.ValidateContract_VERIFY_UserContractValidationSuccess
UserCreationTests.ValidateContract_WHEN_EmailFormatNotValid_THEN_ReturnFalse
UserCreationTests.ValidateContract_WHEN_PasswordHasNoSpecialChar_THEN_ThrowIllegalArgumentException
UserCreationTests.ValidateContract_WHEN_NameLengthExceedsMax_THEN_ThrowIllegalArgumentException

Lastly, well-written edge case tests are a succinct representation of the conditions which are important for the happy path of that functionality.

Test Type: Unit

Aren't these conventions a little overkill for unit tests? Maybe so. I tend to use a simpler variant for low-level tests.

<Method?>_<InputOrType>_<Output|PoD>

Composition

<Method?> (Optional)
: The purpose of the method being tested; it does NOT need to match the method name; not required if the test class name is clear about the target code

<InputOrType>
: Either the value of the input parameter OR type of input depending on input complexity

<Output|PoD>
: Either the expected output OR the point of difference (PoD) as compared to the happy path, i.e. what makes this edge case relevant

Examples

RomanNumeralTests.RomanToInt_MMCDLXVIII_2468
RomanNumeralTests.IntToRoman_1994_MCMXCIV
ReverseIntegerTests.Positive_Overflow
ReverseIntegerTests.Negative_DoubleOverflow

Quiz

Q: Which one is better?

DeviceUpload_VERIFY_TxtUploadToKindleFails
DeviceUpload_WHEN_TxtFile_THEN_UploadToKindleFails

A: Both are perfectly acceptable.

The happy path format is more concise and just as clear.
The edge case format is self-documenting; it tells us the file type is important to the happy path for device file upload.

There's a trade-off as with most things in CS and in life. The decision is up to you!

Final Thoughts

Remember that there's no silver bullet, nor do we need one. We have the power to use the right tool for the right job.

Until Next Time,
Ryo

TL;DR - Prefer verbose clarity over terse obscurity.

References:

2 Birds, 1 Stone – 10 Apps, 1 Node

Ryo Light — Fri, 25 Jun 2021 20:36:32 +0000

A Better Way to Node_Modules via Symlinking

Prerequisites:

A basic understanding of the 'node_modules' directory
The 'node_modules' problem | Leoat12 | Dev.to

Refresher:

When learning a new technology, I prefer to make multiple small projects focused on different concepts as opposed to cramming everything into one giga app.

I come from an Angular background where it's possible to create multiple projects using a single, root package.json; a single node_modules folder is shared across all the various projects under that Angular app.

A few days ago, I renewed my efforts to learn React and immediately ran into a major hurdle... the node_modules folder, or rather a growing hydra of node_modules folders.

Every time I created an app with 'create-react-app' (CRA), a new dependency folder appeared.

Why is having multiple node_modules a problem?

For a Hello World React app with only the core dependencies, i.e. react, react-dom, and react-scripts, the node_modules folder is 218 MB on disk. Now the size doesn't sound too bad, but in this directory are 5,300 folders and 35,000 files. WHY?!?! Am I building an OS here?

This exorbitant amount is for the most basic of apps w/ no other dependencies. It climbs even higher on adding other deps, e.g. w/ Tailwind CSS, 363 MB on disk across 6,100 folders!

You want me to copy or redownload 40,200 files spread across 6,100 folders in order to compile and serve EVERY SINGLE Tailwind React app I create?!

I say not! ヽ(ಠ_ಠ)ノ

The Investigation

On closer examination, the source code of this Hello World app is only 18 files across 2 folders for a total of 700 KB. Great, now this I can work with!

That means the size of the app directory is a problem specific to how dependencies are handled in Node.js.

What if we could reuse a node_modules folder across multiple projects?

After some research, I found that when using require(), Node.js will look into the node_modules of parent folders if the module isn't found in the root node_modules of the project. While useful, it doesn't solve the problem of serving the compiled app.

The Solution – Symbolic Links

I looked a little deeper and found my solution at the OS level.

Windows and Linux both have a concept called symbolic links (symlinking), which you can think of as a local reference/pointer to a file or directory elsewhere on the system.

The benefit of symlinking is that the link looks and acts like the real file/directory, but takes up no extra storage! And of course, the symlink is set up instantaneously as there's no copying to be done.

Give you any ideas? Yes, exactly! We can create a single node_modules directory containing the dependencies for all our React apps, and use symlinking inside of each app to reference this 'root' node_modules.

Luckily, it worked just as expected. Now instead of 10 React apps costing my hard drive 4 GB, 61,000 folders, and 402,000 files, I need only 10% of that storage. The savings only grow as I add more apps!

Further, by copying a set of 18 Hello World files, I also save a few minutes on each new React app I create.

Imagine 100 React apps without symlinking... 4 million files! 😬

A Minimal Example

react-playground/
├─ node_modules/            (root)
├─ package.json
│
├─ react-app-1/
│  ├─ package.json
│  └─ *node_modules/        (symlinked)
│
├─ app-group/
│  ├─ react-app-2/
│  │  ├─ package.json
│  │  └─ *node_modules/     (symlinked)
│  └─ react-app-3/
│     ├─ package.json
│     └─ *node_modules/     (symlinked)
│
└─ .gitignore

Keep in Mind:

All dependency versions should be consistent between projects, e.g. react apps, using a shared node_modules.
Individual projects can use deps not used in other projects, but these deps will still be installed in the root node_modules.

I've left resources on the implementation of symlinking below. The terminal commands are as follows:

mklink (Windows)
ln (Linux)

You can also reference Configuration.md in my React repo for an example implementation.

Ryo112358/react-playground

Now get Symlinking, your computer will thank you!

Until Next Time,
Pulkit

P.S. Shout-out to my girlfriend (@laulina) for the title idea ^.^

References:

Published on Medium

A Better Way to Node_Modules | CoffeelessProgrammer | Medium

DEV Community: Ryo Light

Binary Insertion Sort

Why do we sort?

Binary Insertion Sort

How much faster is it practically?

References

Test Naming Convention

The Class Name

The Method Name

Format: Happy Path

Composition

Examples

Format: Edge Case

Composition

Examples

Test Type: Unit

Composition

Examples

Quiz

Final Thoughts

References:

Further Reading:

2 Birds, 1 Stone – 10 Apps, 1 Node

A Better Way to Node_Modules via Symlinking

Prerequisites:

Refresher:

Why is having multiple node_modules a problem?

The Investigation

The Solution – Symbolic Links

A Minimal Example

Keep in Mind:

References:

Further Reading:

Published on Medium