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 ループを少しずつ強化すると、時間の複雑さに対するパフォーマンスが大幅に向上します。私が考えることができることはほとんどありません。

geo_distance()1.特に費用がかかる場合は一度だけ電話してください

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_states50 の場合、オリジン アルゴリズムは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*1000 (つぶやきの数) ではなく 50 回 (状態の数) だけが呼び出されるようになり、さらに大きな改善が行われました!

業績実績概要

#1 で、パフォーマンスが 2 倍になります。＃2（ツイート数/位置数）倍に強化します。#3 は 3 つの中で最大で、元のコードと比較して時間の複雑さをわずか 1/(ツイート数) に減らします。

于 2014-12-26T18:53:19.877 に答える