通常の実装では、バケット法において数ヶ所余算を用いることとなる。
・点のポテンシャルから、バケットを決定する際
・空でないバケットを見つける操作(キューで実装しているため)
後者については、ループを分けることによって、すでに改善されている。
今回は1について。今まで手を付けなかったのは、単純に演算数・分岐が増えることになるためであっる。やはり余算コストの大きさを考えるとこちらも効いてくるだろうと思い、試してみることにした。
最短経路問題におけるバケット法(Dial's implementation)では、バケット内に格納されているポテンシャルの範囲はたかだか bucket_size しかないため、大きな変更もなく加算、減算で代用が可能である。
以下は、手持ちの中で最も大きなグラフである全米データに対しての改善比率である。
ランダムなクエリに対しての平均値である。
1、余算 1.645 [sec/query]
2、加算・減算 1.601 [sec/query]
これによって、2.67 % ほど高速化されたわけだが、演算のコストはアーキテクチャによって異なるので、注意が必要である。
・点のポテンシャルから、バケットを決定する際
・空でないバケットを見つける操作(キューで実装しているため)
後者については、ループを分けることによって、すでに改善されている。
今回は1について。今まで手を付けなかったのは、単純に演算数・分岐が増えることになるためであっる。やはり余算コストの大きさを考えるとこちらも効いてくるだろうと思い、試してみることにした。
最短経路問題におけるバケット法(Dial's implementation)では、バケット内に格納されているポテンシャルの範囲はたかだか bucket_size しかないため、大きな変更もなく加算、減算で代用が可能である。
以下は、手持ちの中で最も大きなグラフである全米データに対しての改善比率である。
ランダムなクエリに対しての平均値である。
1、余算 1.645 [sec/query]
2、加算・減算 1.601 [sec/query]
これによって、2.67 % ほど高速化されたわけだが、演算のコストはアーキテクチャによって異なるので、注意が必要である。