电话呼叫路由费用检查器

Question

呼叫路由问题

这个项目的灵感来自于一家电话API公司的现实世界问题--让我们称之为Teleo。

主要任务是实现一个国际呼叫路由系统，通过多个运营商找到成本最低的路由。这个项目的目标之一是演示各种各样的解决方案，并比较每种方案之间的权衡。

背景

电话号码

电话号码是分层结构的，并揭示了呼叫路由网络的地理位置。国际电话号码以+开头，然后是国家代码、区号、本地代码和代表依次较小区域设置的其他组。例如，美国的电话号码使用+1-222-333-4444格式，而英国的号码看起来像+44-222-3333-4444，而日本的号码被写成+81-22-333-4444。幸运的是，电话号码可以标准化为标准格式，以“+”开头，后面只有数字(没有连字符、点或空格)。标准化的美国数字看起来如下：+12223334444。对于这个项目，您只需要使用规范化的数字。

路由

路由是通过运营商的电话网络的一条路径。较长的路线连接特定的地理区域，而较短的路线则到达较大的区域。分级电话号码允许简单地用简短的电话号码前缀来表示路由。例如，+1415234标识旧金山的一个社区，+1415代表大旧金山，+1覆盖整个美国，+4420覆盖伦敦的大部分地区。

载波

Teleo与不同地理区域的多个电话运营商签订了合同，但它们往往是重叠的。因此，他们的竞争优势是，他们可以选择哪一家运营商通过发送电话，以尽量减少成本。在单个运营商的路由列表中查找要使用的路由时，必须使用最长的匹配前缀，因为它是最具体的路由。一些电话号码可能与多个载波线路列表中的前缀匹配，在这种情况下，您可以选择最便宜的一个。在价格相同的罕见情况下，两者都是可以接受的。

输入数据

输入数据包含几个纯文本文件。一些代表运营商路线列表，而另一些则包含电话号码，你需要找出成本最低的路线。

载波线路

每一承运人的路线及其相关费用在一个文件中列出。每一行都是以逗号分隔的对格式的单个路由:一个路由的规范化前缀(从一个+开始)，然后以美元(一个浮点数)表示它的成本。例如：

+1512,0.04
+1415,0.02
+1415234,0.03
+1415246,0.01

这些文件被命名为“载波路由-N.txt”，其中N是一个整数。(载体1、2、3、.)

使用上面的载波路由列表，调用+14152345678的成本为0.03美元，因为它与前缀+1415和+1415234 (最长匹配)匹配，但与+1415246不匹配。

电话号码

查找路由成本所需的电话号码是标准化的，并且是在文件的不同行上提供的。例如：

+15124156620
+14152345678
+19876543210

这些文件名为“电话号码-N.txt”，其中N是整数。

输出数据

找到每个电话号码的最小成本路线后，在新文本文件的逗号分隔行上写下号码及其成本。如果没有一个数字的路径，写0。例如，使用上面给出的载波路线列表和电话号码，输出如下：

+15124156620,0.04
+14152345678,0.03
+19876543210,0

将这些文件命名为“路由-成本-N.txt”，其中N是方案号(见下文)。

场景:检查

的路由成本列表

您有一个包含100,000 (100 K)条目(按任意顺序排列)的载波路由列表和一个包含1000个电话号码的列表。如何操作路由成本查找问题？

我有一份载列一条航线的前缀和适用于该航线的费率的承运人路线清单，看上去有点像这样：

+86153,0.84
+449275049,0.49
+8130,0.68
+4928843955,0.40
+449187847,0.48
+8197753,0.75
+449916707,0.58
+64655676,0.40
+34924199,0.39
+1941613,0.05

我将这些输入文本文件命名为“路由-成本-N.txt”，其中N是电话呼叫路由的场景编号。

输出文件生成如下：

找到每个电话号码的最小成本路线后，在新文本文件的逗号分隔行上写下号码及其成本。如果没有一个数字的路径，写0。

我的代码片段可以找到这里。

对有效电话号码的测试文件可以找到这里。

import sys
from datetime import datetime

_end = '_end_'


def phone_route_cost_check(filename, number):
    open_file = open(filename, 'r')
    data = open_file.readlines()

    number_cost = []
    for line in data:
        print(line)
        for i in range(0, len(line)):
            if line[i] == ',':
                print(i)
                number = line[0:i]
                price = line[i+1:-1]
                number_cost.append((number, price))

    print( number_cost)
    trie = make_dictionary_trie(number_cost)

    open_file.close()


def make_dictionary_trie(all_tups):
    trie_root = dict()

    for tup in all_tups:
        current_node = trie_root
        number = tup[0]
        price = tup[1]

        for letter in number:
            current_node = current_node.setdefault(letter, {})
        current_node[_end] = price
    # print trie_root
    return trie_root


def search_trie_for(trie, prefix):
    current_node = trie
    for letter in prefix:
        if letter in current_node:
            current_node = current_node[letter]
        else:
            return False
    else:
        if _end in current_node:
            return current_node[_end]
        else:
            return False


def autocomplete_for(trie, prefix):
    current_node = trie
    for letter in prefix:
        if letter in current_node:
            current_node = current_node[letter]
        else:
            return False


def print_trie(trie, prefix):
    current_node = trie
    word = prefix
    for key in current_node:
        if key == _end:
            print (str(word))
        else:
            word = prefix + key
phone_route_cost_check('route-costs-10.txt', '+14152345678')

我的输出显示了电话号码和成本的列表：

+86153,0.84

6
+449275049,0.49

10
+8130,0.68

5
+4928843955,0.40

11
+449187847,0.48

10
+8197753,0.75

8
+449916707,0.58

10
+64655676,0.40

9
+34924199,0.39

9
+1941613,0.05

8
[('+86153', '0.84'), ('+449275049', '0.49'), ('+8130', '0.68'), ('+4928843955', '0.40'), ('+449187847', '0.48'), ('+8197753', '0.75'), ('+449916707', '0.58'), ('+64655676', '0.40'), ('+34924199', '0.39'), ('+1941613', '0.05')]

Answer 1

处理文件

在处理文件时，始终使用上下文管理器with。而不是这样：

open_file =打开(文件名，'r') #.open_file.close()

像这样写：

with open(filename, 'r') as open_file:
    # ...

这样您就不需要调用open_file.close()了。

使用Python类实现抽象数据类型

一组函数以trie作为参数对其执行各种操作。这是实现抽象数据类型的一种方法。Python提供了一种更好的方法，使用类。这将提供更好的语法执行的封装，以及更简单的用法。

程序组织

我不知道怎么用这个程序。

• phone_route_cost_check函数读取输入文件，构建一个(数字，价格)元组列表，打印它，构建一个trie，而不对它做任何事情。
• 根本不使用search_trie_for、autocomplete_for和print_trie函数。
• sys和datetime是导入的，但不使用。
• phone_route_cost_check打印的东西看起来对任何东西都没有用。

我建议重新考虑如何使用这个程序。一个好的开端可能是枚举预期的用例和预期的输出。

断裂print_trie

这个函数的名称似乎意味着它打算打印一个trie，但是它已经坏了。

断裂autocomplete_for

此函数将返回False或None。我想你不是故意这么做的。

解析逗号分隔值

这是在line上拆分,的一种非常糟糕的方法：

对于范围内的i(0，len(line))：if line我 == '，'：number = line0:i price = linei+1:-1

一种更自然的方法是使用split：

number, price = line.strip().split(',')

对对列表的迭代

而不是这样：

用于all_tups中的tup : number = tup0 price = tup1 #.

对对进行迭代的一种更简单、更自然的方法是：

for number, price in all_tups:
    # ...