路由表优化

Question

我想解决的问题是，我有路由表

• \x{e76f}\x{e76f}
• A\x{e76f}b\x{e76f} p1 \x{e76f}\x{e76f}
• A\x{e76f}b\x{e76f} p2 \x{e76f}\x{e76f}
• A\x{e76f}b\x{e76f} p3 \x{e76f}\x{e76f}
• \x{e76f}\x{e76f}( p1 )
• \x{e76f}\x{e76f}( p2 )
• \x{e76f}\x{e76f} p3 \x{e76f}

这可以优化为

• \x{e76f}\x{e76f}
• \x{e76f}a，p2，p3，p3
• \x{e76f}\x{e76f}( p1 )
• \x{e76f}\x{e76f}( p2 )
• \x{e76f}\x{e76f} p3 \x{e76f}

它可以进一步优化为

• \x{e76f}\x{e76f}
• \x{e76f}\x{e76f}a，b，c，p1
• \x{e76f}\x{e76f}a，b，d，p2
• \x{e76f}\x{e76f}\x{e76f}a，b，e，p3

我想用三维表示法来解决这个问题，但是再一次的检索会很复杂。我需要使用最好的数据结构来解决这个用例。

Answer 1

数据结构是一组dest值，其中第一组由src值键控，第二组由port值键控。这将dest值按src和port分组。

src => port => [dest]

在python中，这可以通过字典来完成：

table = (
    ('a','b','p1'),
    ('a','b','p2'),
    ('a','b','p3'),
    ('a','c','p1'),
    ('a','d','p2'),
    ('a','e','p3'),
)

optimized = {}
for route in table:
    src, dest, port = route
    o = optimized.get(src, {})
    p = o.get(port, [])
    p.append(dest)
    o[port] = p
    optimized[src] = o

for src,route in optimized.iteritems():
    for port,dest in route.iteritems():
        print src, dest, port

结果(按未排序的顺序排列)是：

a ['b', 'd'] p2
a ['b', 'e'] p3
a ['b', 'c'] p1

查找可以使用以下方法完成：

dest = optimized[src][port]