Green's filter in Python
Green's 16-input sorting network with 60 comparators and depth 10, built from a hypercube filter of 32 comparators followed by 28 more.
- File
green_filter.py, 70 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/green-filter/. The authors are listed in prov/12PBRG.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
# Layers 5 to 10 of Green's network, after the four layers of the filter.
_LAYER5 = [(1, 2), (4, 8), (7, 11), (13, 14), (3, 12), (5, 10), (6, 9)] # @line L5
_LAYER6 = [(1, 4), (2, 8), (7, 13), (11, 14), (10, 12), (3, 5)] # @line L6
_LAYER7 = [(2, 4), (11, 13), (7, 9), (6, 8)] # @line L7
_LAYER8 = [(7, 10), (9, 12), (3, 6), (5, 8)] # @line L8
_LAYER9 = [(9, 10), (5, 6), (7, 8), (11, 12), (3, 4)] # @line L9
_LAYER10 = [(6, 7), (8, 9)] # @line L10
def green_16() -> list[tuple[int, int]]:
"""Return Green's 60 comparators on 16 wires, layer by layer."""
net: list[tuple[int, int]] = []
for b in (1, 2, 4, 8): # @line L1 @line L2 @line L3 @line L4: the filter
net.extend((i, i | b) for i in range(16) if not i & b)
for layer in (_LAYER5, _LAYER6, _LAYER7, _LAYER8, _LAYER9, _LAYER10):
net.extend(layer)
return net
def _merge(net: list[tuple[int, int]], lo: int, m: int, r: int) -> None:
"""Batcher's odd-even merge of the two sorted halves of the wires lo, lo + r, ..., lo + m - r."""
s = 2 * r
if s < m:
_merge(net, lo, m, s)
_merge(net, lo + r, m, s)
net.extend((i, i + r) for i in range(lo + r, lo + m - r, s))
else:
net.append((lo, lo + r))
def green_network(n: int) -> list[tuple[int, int]]:
"""Return a sorting network on n wires built on Green's network.
For n <= 16, drop the comparators of Green's network that touch a wire j >= n.
For n > 16, sort each block of 16 wires with Green's network, merge the
blocks with Batcher's odd-even merge up to the next power of 2, and drop
the comparators that touch a wire j >= n.
"""
size = 16
while size < n:
size *= 2
net: list[tuple[int, int]] = []
base = green_16()
for lo in range(0, size, 16):
net.extend((lo + i, lo + j) for i, j in base)
m = 32
while m <= size:
for lo in range(0, size, m):
_merge(net, lo, m, 1)
m *= 2
return [(i, j) for i, j in net if j < n]
def green_filter(a: list[T]) -> None:
"""Sort a in place, in non-decreasing order, with a network built on Green's network."""
for i, j in green_network(len(a)):
if a[j] < a[i]: # @line L11
a[i], a[j] = a[j], a[i]
test_green_filter.py 76 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/green-filter/. The authors are listed in prov/12PBRG.jsonl.
import random
from green_filter import green_16, green_filter, green_network
def depth(net: list[tuple[int, int]], n: int) -> int:
level = [0] * n
for i, j in net:
level[i] = level[j] = max(level[i], level[j]) + 1
return max(level, default=0)
def sorts_all_zero_one(net: list[tuple[int, int]], n: int) -> bool:
"""Run all 2^n inputs at once: bit v of wire[k] is item k of input v."""
full = (1 << (1 << n)) - 1
wire = []
for k in range(n):
block = (1 << (1 << k)) - 1
pattern = 0
period = 1 << (k + 1)
for start in range(0, 1 << n, period):
pattern |= block << (start + (1 << k))
wire.append(pattern & full)
for i, j in net:
wire[i], wire[j] = wire[i] & wire[j], wire[i] | wire[j]
return all(wire[k] & ~wire[k + 1] == 0 for k in range(n - 1))
def test_example() -> None:
a = [3, 8, 13, 12, 10, 2, 7, 15, 6, 0, 4, 5, 11, 9, 1, 14]
green_filter(a)
assert a == list(range(16))
def test_size_and_depth() -> None:
net = green_16()
assert len(net) == 60
assert depth(net, 16) == 10
assert all(i < j for i, j in net)
def test_filter_order() -> None:
rng = random.Random(16)
for _ in range(200):
x = [rng.randint(0, 99) for _ in range(16)]
for i, j in green_16()[:32]:
if x[j] < x[i]:
x[i], x[j] = x[j], x[i]
for w in range(16):
for v in range(16):
if w & v == w:
assert x[w] <= x[v]
def test_all_zero_one_inputs() -> None:
for n in range(1, 17):
assert sorts_all_zero_one(green_network(n), n)
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1], [5, 5, 4, 4, 3], list(range(40, 0, -1))):
b = list(a)
green_filter(b)
assert b == sorted(a)
def test_random_against_sorted() -> None:
rng = random.Random(1969)
for _ in range(600):
a = [rng.randint(-40, 40) for _ in range(rng.randint(0, 80))]
b = list(a)
green_filter(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build