アルゴリズムの設計 - 辞書を使用して値を追跡するリストを使用する場合

Question

次の問題については、提供された回答がリストを使用している間に値を追跡するために辞書を使用しました。このような問題の最も効率的なデータ構造を迅速に判断する方法はありますか？

ロボットは原点（0,0）から始まる平面内を移動します。 ロボットは、所定の手順でUP、DOWN、LEFT、RIGHTの方向に移動できます。 ロボットの動きの軌跡は次のようになります。UP 5 DOWN 3 LEFT 3 RIGHT 2.方向の後の数字はステップです。動きのあるシーケンス と元のポイントの後の現在の位置からの距離を計算するには、 プログラムを記述してください。距離が浮動小数点の場合、 は最も近い整数を出力します。例：次のタプルは、プログラムへの入力として を与えられている場合：最大5 DOWN 3 LEFT 3 RIGHT 2そして、プログラムの出力 あるべき：2

私の答えは、辞書（原点[」を使用しますxのX "]） "Yおよび原点用[]" Y：

direction = 0 
steps = 0 
command = (direction, steps) 
command_list = [] 
origin = {"x": 0, "y": 0} 
while direction is not '': 
    direction = input("Direction (U, D, L, R):") 
    steps = input("Number of steps:") 
    command = (direction, steps) 
    command_list.append(command) 
print(command_list) 

while len(command_list) > 0: 
    current = command_list[-1] 
    if current[0] == 'U': 
     origin["y"] += int(current[1]) 
    elif current[0] == 'D': 
     origin["y"] -= int(current[1]) 
    elif current[0] == 'L': 
     origin["x"] -= int(current[1]) 
    elif current[0] == 'R': 
     origin["x"] += int(current[1]) 
    command_list.pop() 
distance = ((origin["x"])**2 + (origin["y"])**2)**0.5 
print(distance) 

設け回答リスト（POS [0]、Y、およびPOS [1] xについて）を使用：

import math 
pos = [0,0] 
while True: 
    s = raw_input() 
    if not s: 
     break 
    movement = s.split(" ") 
    direction = movement[0] 
    steps = int(movement[1]) 
    if direction=="UP": 
     pos[0]+=steps 
    elif direction=="DOWN": 
     pos[0]-=steps 
    elif direction=="LEFT": 
     pos[1]-=steps 
    elif direction=="RIGHT": 
     pos[1]+=steps 
    else: 
     pass 

print int(round(math.sqrt(pos[1]**2+pos[0]**2))) 

Answer 1

私はあなたの質問にいくつかの点を提示します。近い勧告に強く同意する。あなたの質問には、意見ではないことがたくさんあります。

一般に、あなたの選択は適切ではありませんでした。このようなおもちゃプログラムの場合、大きな違いはありませんが、深刻なプログラムのベストプラクティスに興味があると思います。本番ソフトウェアでは、この選択をしません。どうして？

• エラーを起こしやすいらし。将来のコードの誤字。 origin["t"] = 3あなたがorigin["y"] = 3を意味したときは、厄介なバグです。見つけにくいかもしれません。 t = 3は、「高速障害」を引き起こす可能性が高くなります。 （C++やJavaのような静的型付けされた言語では、コンパイル時にエラーが発生します）

• スペースオーバーヘッド。単純なスカラー変数は本質的に値そのものを超えるスペースを必要としません。配列には、位置、現在、最大サイズを追跡する「ドープベクトル」の固定オーバーヘッドがあります。辞書は、公開アドレス指定、未使用のハッシュ・バケット、およびフィル・トラッキングのためにさらに余分なスペースを必要とします。

• スピード。

  • スカラー変数へのアクセスは非常に高速です。わずかなプロセッサ命令です。
  • インデックスを知っているタプルまたは配列要素にアクセスすると、非常に高速ですが、可変アクセスほど高速ではありません。配列の境界を調べるには余分な命令が必要です。配列に1つの要素を追加すると、現在の内容をより大きなメモリブロックにコピーするためにO（現在の配列サイズ）が使用されます。タプルと配列の利点は、計算された整数インデックスに基づいて素早く要素にアクセスできることです。スカラ変数はこれをしません。整数インデックスへのアクセスが必要な場合は、配列/タプルを選択します。正確なサイズを知っていて、変更する可能性が低い場合は、タプルを優先します。それらの不変性は、コードをより理解しやすくする（スレッドセーフにする）傾向があります。
  • ハッシュ値を計算し、バケットを可能な衝突解決で横断させる必要があるため、辞書要素にアクセスするのはさらに高価です。単一の要素を追加すると、表の再編成がトリガーされることもあります。これは、表の再編成よりもはるかに大きな定数を持つO（表のサイズ）です。すべての要素を再ハッシュしなければならないためです。辞書の大きな利点は、格納されているすべてのペアにアクセスするのに同じ時間がかかる可能性が高いことです。キーから値への「マップ」を格納する機能が必要な場合にのみ、dictを選択する必要があります。

は、上記のすべてのあなたの原点座標のための最良の選択だっただろうという単純な変数から結論付けています。後で(x, y)ペアをメソッドとの間でやり取りする必要がある方法でプログラムを拡張する場合は、Pointクラスと見なしてください。