__iter__/__next__与列表属性实现可迭代类：效率对比及基准测试

问题核心 #

直观上感觉用__iter__和__next__魔术方法实现的可迭代链表，比传统手动遍历的链表效率更高，但想明确：

• 这两个魔术方法的具体工作原理
• 如何通过基准测试对比两者的空间占用与运行时性能

两种实现示例 #

1. 带迭代器协议的链表实现 #

（注：原代码中prepend_node方法里的IntNode应为Node，已修正）

class Node(object):
    def __init__(self, value: int, next_node):
        self.value = value
        self.next = next_node

    def __repr__(self):
        return str(self.value)


class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
        self._current = None

    def __repr__(self):
        return '<{} {}>'.format(type(self).__name__, self.head)

    def __iter__(self):
        self._current = self.head
        return self

    def __next__(self):
        if self._current is None:
            raise StopIteration
        current, self._current = self._current, self._current.next
        return current

    @property
    def is_empty(self):
        return self.head is None

    def prepend_node(self, valuetoadd: int):
        self.head = Node(valuetoadd, self.head)

2. 传统手动遍历的链表实现 #

class ListNode:
    """
    A node in a singly-linked list.
    """
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

    def __repr__(self):
        return repr(self.data)


class SinglyLinkedList:
    def __init__(self):
        """
        Create a new singly-linked list.
        Takes O(1) time.
        """
        self.head = None


    def prepend(self, data):
        """
        Insert a new element at the beginning of the list.
        Takes O(1) time.
        """
        self.head = ListNode(data=data, next=self.head)

    def find(self, key):
        """
        Search for the first element with `data` matching
        `key`. Return the element or `None` if not found.
        Takes O(n) time.
        """
        curr = self.head
        while curr and curr.data != key:
            curr = curr.next
        return curr  # Will be None if not found

    def remove(self, key):
        """
        Remove the first occurrence of `key` in the list.
        Takes O(n) time.
        """
        # Find the element and keep a
        # reference to the element preceding it
        curr = self.head
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        # Unlink it from the list
        if prev is None:
            self.head = curr.next
        elif curr:
            prev.next = curr.next
            curr.next = None

技术细节解析 #

__iter__与__next__的工作原理 #

Python的迭代协议要求：

1. 可迭代对象必须实现__iter__方法，该方法返回一个迭代器对象
2. 迭代器对象必须实现__next__方法，每次调用返回下一个元素，直到抛出StopIteration异常终止迭代

在第一个链表实现中：

• __iter__方法重置内部的_current指针到链表头部，然后返回自身（因为LinkedList类同时实现了__next__，所以它本身就是迭代器）
• __next__方法每次移动_current指针，返回当前节点，直到指针为空时抛出StopIteration
• 这种方式是惰性迭代：不需要提前把所有节点加载到内存，每次迭代只生成一个节点

与传统实现的核心差异 #

• 传统链表遍历需要手动维护curr指针，编写while循环完成遍历，代码冗余且不符合Pythonic风格
• 迭代器实现兼容所有Python内置的可迭代对象API（如for循环、list()、map()等），无需手动编写遍历逻辑
• 迭代器支持多次迭代：每次调用__iter__都会重置指针，而传统遍历每次都要从头开始手动初始化指针

基准测试方案 #

1. 运行时性能测试（时间开销） #

使用Python内置的timeit模块测试两种实现的遍历速度：

import timeit

# 构造测试用的链表
def build_iterable_ll(n):
    ll = LinkedList()
    for i in range(n):
        ll.prepend_node(i)
    return ll

def build_traditional_ll(n):
    sll = SinglyLinkedList()
    for i in range(n):
        sll.prepend(i)
    return sll

# 测试参数
TEST_SIZE = 10000
ITERATIONS = 100

# 构建链表
iter_ll = build_iterable_ll(TEST_SIZE)
trad_ll = build_traditional_ll(TEST_SIZE)

# 测试迭代器遍历时间
def test_iter_traversal():
    list(iter_ll)

# 测试传统遍历时间
def test_trad_traversal():
    res = []
    curr = trad_ll.head
    while curr:
        res.append(curr)
        curr = curr.next

# 执行测试
time_iter = timeit.timeit(test_iter_traversal, number=ITERATIONS)
time_trad = timeit.timeit(test_trad_traversal, number=ITERATIONS)

print(f"迭代器遍历总时间（{ITERATIONS}次）：{time_iter:.4f}s")
print(f"传统遍历总时间（{ITERATIONS}次）：{time_trad:.4f}s")

2. 空间占用测试 #

使用Python内置的tracemalloc模块测试遍历过程中的内存开销：

import tracemalloc

# 测试迭代器遍历的内存
tracemalloc.start()
test_iter_traversal()
snapshot_iter = tracemalloc.take_snapshot()
tracemalloc.stop()

# 测试传统遍历的内存
tracemalloc.start()
test_trad_traversal()
snapshot_trad = tracemalloc.take_snapshot()
tracemalloc.stop()

# 打印内存统计
print("迭代器遍历内存开销（Top 3）：")
for stat in snapshot_iter.statistics('lineno')[:3]:
    print(f"  {stat}")

print("\n传统遍历内存开销（Top 3）：")
for stat in snapshot_trad.statistics('lineno')[:3]:
    print(f"  {stat}")

性能对比结论 #

• 时间性能：两者的遍历时间复杂度都是O(n)，实际运行差异极小。迭代器因为是Python内置协议实现，可能有微小的优化优势，但在大多数场景下可以忽略
• 空间性能：如果仅需遍历一次且不需要保存所有节点，迭代器的惰性特性可以节省大量内存（无需创建存储所有节点的列表）；如果需要保存遍历结果，两者的空间开销基本一致
• 代码可读性与兼容性：迭代器实现更符合Pythonic风格，兼容所有内置可迭代API，代码更简洁

内容的提问来源于stack exchange，提问作者jjbiggins