Algorithm "sort except zero"

Question

Task:

Sort the integers in sequence in sequence. But the position of zeros should not be changed.

Input: List of integers (int).

Output: List or another Iterable (tuple, generator, iterator) of integers (int).

Examples:

[5, 3, 0, 0, 4, 1, 4, 0, 7] => [1, 3, 0, 0, 4, 4, 5, 0, 7]

[0, 2, 3, 1, 0, 4, 5] => [0, 1, 2, 3, 0, 4, 5]

[0, 0, 0, 1, 0] => [0, 0, 0, 1, 0]

[4, 5, 3, 1, 1] => [1, 1, 3, 4, 5]

Precondition:

All numbers are non-negative.

My code:

from collections.abc import Iterable

def except_zero(items: list[int]) -> Iterable[int]:
    without_z = [i for i in items if i != 0]
    place_z = [i[0] for i in enumerate([i if i == 0 else 1 for i in items]) if i[1] == 0]
    without_z = sorted(without_z)
    for i in place_z: without_z.insert(i, 0)
    return without_z

How can I make this faster?

Answer 1

Most of the work will be done by your call to sorted. You just need to make sure to not make too much extra fluff around that call.

One particular call that may greatly impact performances, especially on large lists with lots of zeroes is your without_z.insert which needs to move memory around. Instead, I’d rather use this result and pull elements out from it to build a whole new list with zeroes inserted as necessary.

The name of the function does not convey anything sort-related, please change it and consider using a docstring to document its particular behavior.

Lastly, your type hints are off as you are explicitly returning a list[int] but your code can accept any Sequence[int] iterables which allow you to iterate over them twice.

from typing import Sequence


def sort_except_zeroes(items: Sequence[int]) -> list[int]:
    non_zeroes = iter(sorted(i for i in items if i != 0))
    return [next(non_zeroes) if i != 0 else 0 for i in items]

Answer 2

301_Moved_Permanently's answer is great and changes the performance from \$O(nk\log(n))\$ to \$O(n\log(n))\$. The change results in a measurable impact on performance.

To satiate both my curiosity and the site's need for at least one IO I have explored two micro-optimisations. Firstly I want to note micro-optimisations are not typically a good approach only use micro-optimisations for when you need improvements in the micro level -- \$10^{-6}\$s. Which is pretty rare.

1. sorted builds a new list where list.sort mutates an existing list. list.sort is typically faster because we remove the copy operation.

   def test_peil__sort(items: Iterable[int]) -> list[int]:
       items = [i for i in items if i != 0]
       items.sort()
       non_zeroes = iter(items)
       return [next(non_zeroes) if i != 0 else 0 for i in items]
   

2. Python is typically slower than C, so offloading to C is a common micro-optimisation technique. Here we can offload to filter's C loop.
   Thanks @duckboycool for reminding me of filter over itertools.filterfalse.

   def test_peil__filter(items: Iterable[int]) -> list[int]:
       non_zeroes = iter(sorted(filter(None, items)))
       return [next(non_zeroes) if i != 0 else 0 for i in items]
   

3. Assuming 1 & 2 are faster, combining the two together may result in faster code.

   def test_peil__filter_sort(items: Iterable[int]) -> list[int]:
       items = list(filter(None, items))
       items.sort()
       non_zeroes = iter(items)
       return [next(non_zeroes) if i != 0 else 0 for i in items]
   

Note: To test the performance of the functions we need to build sample data. I'm using the following function to do so:

random.seed(42401)


@functools.cache
def args_conv(size: int) -> list[int]:
    arr = list(range(int(size)))
    random.shuffle(arr)
    return arr

We can see:

• test_mathias is faster than the test_orig.
• test_peil__sort's micro-optimisation is faster than test_mathias in the micro section, getting quite close otherwise.
• test_peil__filter's micro-optimisation is marginally better than test_mathias throughout.
• test_peil__filter_sort seems virtually indistinguishable from test_peil__filter.
• test_cris shows NumPy is much better than Python when working with numbers.
• test_cris__py shows converting between Python and NumPy can greatly diminish the benefit of using NumPy.

We can also see all Python based algorithms are tending towards the same worst case. To make comparing user's suggestions easier, here is the graph again with only one algorithm per user.

I said at the beginning of the answer 301_Moved_Permanently's answer "changed the performance from \$O(nk\log(n))\$ to \$O(n\log(n))\$." However we can't see the improvement in the graph. In args_conv I used a sampling method which only has one 0, so \$k = 1\$. If we change the sampling method to have \$n / 2\$ 0s we can show test_orig pulling away from test_mathias with a curve.

Full code:

final/__init__.py

from collections.abc import Iterable

import numpy
from numpy.typing import NDArray


def test_orig(items: list[int]) -> Iterable[int]:
    without_z = [i for i in items if i != 0]
    place_z = [i[0] for i in enumerate([i if i == 0 else 1 for i in items]) if i[1] == 0]
    without_z = sorted(without_z)
    for i in place_z: without_z.insert(i, 0)
    return without_z


# Derived https://codereview.stackexchange.com/a/287025
# By 301_Moved_Permanently
def test_mathias(items: Iterable[int]) -> list[int]:
    non_zeroes = iter(sorted(i for i in items if i != 0))
    return [next(non_zeroes) if i != 0 else 0 for i in items]


# Derived https://codereview.stackexchange.com/a/287029
# By Cris Luengo
def test_cris(items: NDArray[numpy.int_]) -> NDArray[numpy.int_]:
    items = items.copy()  # can leave this out if you want to work in-place
    nonzeros = items != 0
    items[nonzeros] = numpy.sort(items[nonzeros])
    return items


# Derived https://codereview.stackexchange.com/a/287029
# By Cris Luengo
def test_cris__py(items: Iterable[int]) -> list[int]:
    items = numpy.array(items)
    nonzeros = items != 0
    items[nonzeros] = numpy.sort(items[nonzeros])
    return list(items)


# Derived https://codereview.stackexchange.com/a/287025
# By 301_Moved_Permanently
def test_peil__sort(items: Iterable[int]) -> list[int]:
    items = [i for i in items if i != 0]
    items.sort()
    non_zeroes = iter(items)
    return [next(non_zeroes) if i != 0 else 0 for i in items]


# Derived https://codereview.stackexchange.com/a/287025
# By 301_Moved_Permanently
def test_peil__filter(items: Iterable[int]) -> list[int]:
    non_zeroes = iter(sorted(filter(None, items)))
    return [next(non_zeroes) if i != 0 else 0 for i in items]


# Derived https://codereview.stackexchange.com/a/287025
# By 301_Moved_Permanently
def test_peil__filter_sort(items: Iterable[int]) -> list[int]:
    _items = list(filter(None, items))
    _items.sort()
    non_zeroes = iter(_items)
    return [next(non_zeroes) if i != 0 else 0 for i in items]

plot.py

import functools
import random
from typing import Any

import matplotlib.pyplot
import numpy
from numpy.typing import NDArray
import graphtimer

from . import final

random.seed(42401)


@functools.cache
def args_conv(size: int) -> list[int]:
    arr = list(range(int(size)))
    random.shuffle(arr)
    return arr


def args_conv__np(size: int) -> NDArray[numpy.int_]:
    return numpy.array(args_conv(size))


@functools.cache
def args_conv__k(size: int) -> list[int]:
    arr = list(range(int(size))) + [0] * int(size / 2)
    random.shuffle(arr)
    return arr


def args_conv__k__np(size: int) -> NDArray[numpy.int_]:
    return numpy.array(args_conv__k(size))


def join_plots(
    base: graphtimer.plotter.PlotValues,
    *values: graphtimer.plotter.PlotValues,
) -> graphtimer.plotter.PlotValues:
    for value in values:
        if (base.kwargs["domain"] != value.kwargs["domain"]).any():
            raise ValueError("Can only merge PlotValues with the same domain.")
    data: list[list[graphtimer.plotter._DataValues]] = list(base.data)
    kwargs: dict[str, Any] = {
        "functions": list(base.kwargs["functions"]),
        "domain": base.kwargs["domain"],
    }
    for value in values:
        data += value.data
        kwargs["functions"] += value.kwargs["functions"]
    return graphtimer.plotter.PlotValues(data, kwargs)


def main():
    fig, axs = matplotlib.pyplot.subplots()
    axs.set_yscale('log')
    axs.set_xscale('log')
    join_plots(
        (
            graphtimer.Plotter(graphtimer.MultiTimer([final.test_orig, final.test_mathias, final.test_peil__filter, final.test_cris__py, final.test_peil__sort, final.test_peil__filter_sort]))
                .repeat(10, 10, numpy.logspace(0, 4, num=50), args_conv=args_conv)
                .min()
        ),
        (
            graphtimer.Plotter(graphtimer.MultiTimer([final.test_cris]))
                .repeat(10, 10, numpy.logspace(0, 4, num=50), args_conv=args_conv__np)
                .min()
        ),
    ).plot(axs, x_label='len(nums)')
    fig.show()

    fig, axs = matplotlib.pyplot.subplots()
    axs.set_yscale('log')
    axs.set_xscale('log')
    join_plots(
        (
            graphtimer.Plotter(graphtimer.MultiTimer([final.test_orig, final.test_mathias, final.test_peil__filter]))
                .repeat(10, 10, numpy.logspace(0, 4, num=50), args_conv=args_conv)
                .min()
        ),
        (
            graphtimer.Plotter(graphtimer.MultiTimer([final.test_cris]))
                .repeat(10, 10, numpy.logspace(0, 4, num=50), args_conv=args_conv__np)
                .min()
        ),
    ).plot(axs, x_label='len(nums)')
    fig.show()

    fig, axs = matplotlib.pyplot.subplots()
    axs.set_yscale('log')
    axs.set_xscale('log')
    join_plots(
        (
            graphtimer.Plotter(graphtimer.MultiTimer([final.test_orig, final.test_mathias, final.test_peil__filter]))
                .repeat(10, 10, numpy.logspace(0, 4, num=50), args_conv=args_conv__k)
                .min()
        ),
        (
            graphtimer.Plotter(graphtimer.MultiTimer([final.test_cris]))
                .repeat(10, 10, numpy.logspace(0, 4, num=50), args_conv=args_conv__k__np)
                .min()
        ),
    ).plot(axs, x_label='len(nums)')
    fig.show()
    input()


if __name__ == '__main__':
    main()

Answer 3

I would suggest you use NumPy for anything that manipulates collections of numbers of the same type. A NumPy array is a more efficient container than a list in this case, an the package contain a large collection of tools to manipulate these arrays very efficiently.

For example, your code can be written as:

import numpy as np
from numpy.typing import NDArray

def except_zero(items: NDArray[np.int_]) -> NDArray[np.int_]:
    output = items.copy()  # can leave this out if you want to work in-place
    nonzeros = output != 0
    output[nonzeros] = np.sort(output[nonzeros])
    return output

---

List comprehensions are powerful language constructs, but they tend to make code less readable. Especially if you nest them like this:

place_z = [i[0] for i in enumerate([i if i == 0 else 1 for i in items]) if i[1] == 0]

Separating such a line into two lines would improve readability:

binary = [i if i == 0 else 1 for i in items]
place_z = [i[0] for i in enumerate(binary) if i[1] == 0]

Though this doesn't really need two list comprehensions, the inner one doesn't add anything important, it just converts non-zeros to 1, but this is not required for the outer list comprehension logic, which only compares agains zero. So we can write this as:

place_z = [i[0] for i in enumerate(items) if i[1] == 0]

This last line is again better expressed as (thanks to J_H):

place_z = [i for i, v in enumerate(items) if v == 0]