Collections

Five problems written with ppy.Vec, ppy.Deque, ppy.Heap, ppy.LinkedList, ppy.HashMap, and ppy.TreeSet, with no pointers in sight. Every function goes native, and the program prints the same thing on all three paths.

Run it

python  graphs.ppy
ppy run graphs.ppy
ppy build --standalone graphs.ppy -o dist && ./dist/graphs

What it prints

python graphs.ppy, ppy run graphs.ppy, ppy build --standalone graphs.ppy -o dist && ./dist/graphs

68871776 18
27151 3276962 2

The problems

• shortest_paths: Dijkstra over 200,000 nodes with four weighted edges each. The frontier is a Heap[int] holding distance * NODES + node, so one integer carries both.
• hops: breadth-first search over the same graph with a Deque[int], reporting the farthest node in edges.
• josephus: 100,000 people in a circle, every seventh removed. The circle is a LinkedList[int], walked by node id with next and cut with remove.
• repeats: counts 2,000,000 keys in a HashMap[int, int] with get(key, 0) + 1, then walks the keys in insertion order.
• closest_gaps: the smallest gap between 200,000 values as they arrive, using a TreeSet[int]'s floor and ceiling for each value's neighbors.

dist and seen are Vec[int](NODES), which start with NODES zeros, as [0] * NODES would.

How it runs natively

ppy explain graphs.shortest_paths and the others each say llvm backend: native. A collection that a function makes is a handle into the C runtime in ppy_runtime/collections.py, freed when the function returns. A check CPython would raise for, such as an empty pop or a missing key, is a guard: under ppy run it hands the call back to Python, which raises, and a standalone binary stops.

Timing

One machine, five runs each, wall time for the whole program:

	seconds
python graphs.ppy (the reference classes under CPython)	4.3
idiomatic.py: the same algorithms with list, deque, heapq, dict, bisect	2.3
ppy run graphs.ppy, after the first run built the cache	0.39
./dist/graphs, the standalone binary	0.19

The reference classes are slower than Python's built-ins because every method is a Python call. idiomatic.py is there so the comparison is with code a Python programmer would write. Its josephus pops from a list rather than walking a linked list, which is the usual way to write it in Python.

Where the code comes from

graphs.ppy and idiomatic.py are hand-written.

Read on: the collections guide.

47_collections/graphs.ppy

"""Graph and sequence problems written with ppy's collections."""

from ppy import Deque, HashMap, Heap, LinkedList, TreeSet, Vec

NODES = 200000
EDGES = 4


def target(node: int, k: int) -> int:
    return (node * 7919 + k * 104729 + 13) % NODES


def weight(node: int, k: int) -> int:
    return (node * 31 + k * 17) % 97 + 1


def shortest_paths(source: int) -> int:
    dist = Vec[int](NODES)
    for i in range(NODES):
        dist[i] = -1
    frontier = Heap[int]()
    frontier.push(source)
    dist[source] = 0
    while frontier:
        packed: int = frontier.pop()
        node: int = packed % NODES
        here: int = packed // NODES
        if here > dist[node]:
            continue
        for k in range(EDGES):
            other: int = target(node, k)
            through: int = here + weight(node, k)
            if dist[other] < 0 or through < dist[other]:
                dist[other] = through
                frontier.push(through * NODES + other)
    total: int = 0
    for d in dist:
        total += d
    return total


def hops(source: int) -> int:
    seen = Vec[int](NODES)
    for i in range(NODES):
        seen[i] = -1
    queue = Deque[int]()
    queue.push_back(source)
    seen[source] = 0
    farthest: int = 0
    while queue:
        node: int = queue.pop_front()
        for k in range(EDGES):
            other: int = target(node, k)
            if seen[other] < 0:
                seen[other] = seen[node] + 1
                farthest = max(farthest, seen[other])
                queue.push_back(other)
    return farthest


def josephus(people: int, step: int) -> int:
    circle = LinkedList[int]()
    for i in range(people):
        circle.push_back(i)
    node: int = circle.head()
    while len(circle) > 1:
        for _ in range(step - 1):
            node = circle.next(node)
            if node == -1:
                node = circle.head()
        following: int = circle.next(node)
        circle.remove(node)
        node = following if following != -1 else circle.head()
    return circle.front()


def repeats(count: int) -> int:
    seen = HashMap[int, int]()
    for i in range(count):
        key: int = (i * i + 7 * i) % 65537
        seen[key] = seen.get(key, 0) + 1
    most: int = 0
    for key in seen:
        most = max(most, seen[key])
    return len(seen) * 100 + most


def closest_gaps(count: int) -> int:
    marks = TreeSet[int]()
    best: int = 1 << 40
    for i in range(count):
        value: int = (i * 2654435761) % 1000003
        if marks:
            if value >= marks.min():
                best = min(best, value - marks.floor(value))
            if value <= marks.max():
                best = min(best, marks.ceiling(value) - value)
        marks.add(value)
    return best


def main() -> None:
    print(shortest_paths(0), hops(0))
    print(josephus(100000, 7), repeats(2000000), closest_gaps(200000))


main()

Source: examples/47_collections.