2

我正在尝试返回一个字典，该字典按最近的州中心聚合推文。我正在遍历所有推文，并且对于每条推文，我正在检查所有状态以查看哪个状态最接近。

有什么更好的方法来做到这一点？

def group_tweets_by_state(tweets):
    """

    The keys of the returned dictionary are state names, and the values are
    lists of tweets that appear closer to that state center than any other.

    tweets -- a sequence of tweet abstract data types """


    tweets_by_state = {}
    for tweet in tweets:
        position = tweet_location(tweet)
        min, result_state = 100000, 'CA'
        for state in us_states:
            if geo_distance(position, find_state_center(us_states[state]))< min:
                min = geo_distance(position, find_state_center(us_states[state]))
                result_state = state
        if result_state not in tweets_by_state:
            tweets_by_state[result_state]= []
            tweets_by_state[result_state].append(tweet)
        else:
            tweets_by_state[result_state].append(tweet)
    return tweets_by_state
4

1 回答 1

4

当推文的数量非常大时，这个巨大的 for 循环中的每一个小改进都会导致时间复杂度的巨大性能提升，我能想到的事情很少：

1. 只需调用geo_distance()一次，尤其是在成本高昂的情况下

distance = geo_distance(position, find_state_center(us_states[state]))
if distance < min:
     min = distance

而不是

if geo_distance(position, find_state_center(us_states[state]))< min:
    min = geo_distance(position, find_state_center(us_states[state]))

2. 如果位置倾向于经常重复：

position_closest_state = {}  # save known result 
tweets_by_state = {}
for tweet in tweets:
    position = tweet_location(tweet)
    min, result_state = 100000, 'CA'

    if position in position_closest_state:
        result_state = position_closest_state[position]
    else:
        for state in us_states:
            distance = geo_distance(position, find_state_center(us_states[state]))
            if distance < min:
                min = distance
                result_state = state
                position_closest_state[position] = result_state

因此，假设您有来自 200 个不同位置的 1000 条推文，并且us_states是 50，那么您的原始算法将调用geo_distance()1000*50*2 次，现在它可以减少到 200*50*1 次调用。

3.减少调用次数find_state_center()

与 #2 类似，现在每个状态的每条推文都会重复调用它。

state_center_dict = {}
for state in us_states:
    state_center_dict[state] = find_state_center(us_states[state])

position_closest_state = {}  # save known result 
tweets_by_state = {}
for tweet in tweets:
    position = tweet_location(tweet)
    min, result_state = 100000, 'CA'

    if position in position_closest_state:
        result_state = position_closest_state[position]
    else:
        for state in us_states:
            distance = geo_distance(position, state_center_dict[state])
            if distance < min:
                min = distance
                result_state = state
                position_closest_state[position] = result_state

现在find_state_center()只调用 50 次（状态数）而不是 50*1000（推文数），我们又做了一个巨大的改进！

业绩成果汇总

通过#1，我们将性能提高了一倍。#2 我们通过（推文数/职位数）倍来增强它。#3 是三者中最大的，与原始代码相比，我们将时间复杂度降低到只有 1/（推文数）。

于 2014-12-26T18:53:19.877 回答