定義のルックアップ速度:パフォーマンスの問題

1
zorank 2011-08-30 12:01.

私は次の問題を抱えています。

次のような非常に多くの定義(*)を作成する必要があります

f[{1,0,0,0}] = 1
f[{0,1,0,0}] = 2
f[{0,0,1,0}] = 3
f[{0,0,0,1}] = 2
...
f[{2,3,1,2}] = 4
...
f[{n1,n2,n3,n4}] = some integer
...

これはほんの一例です。引数リストの長さは4である必要はありませんが、何でもかまいません。引数リストの長さが長くなると、各値のルックアップが指数関数的に複雑になることに気づきました。Mathematicaが保存する必要のある定義の数に原則として組み合わせ爆発があることは明らかなので、おそらくこれはそれほど奇妙なことではありません。

しかし、私はMathematicaが賢く、その値の抽出は一定の時間計算量でなければならないと思っていました。どうやらそうではありません。

ルックアップ時間を短縮する方法はありますか?これはおそらくMathematicaがシンボル定義ルックアップを内部的に処理する方法と関係があります。一致するものが見つかるまでリストにフレーズを付けますか?そうしているようです。

すべての提案は高く評価されています。よろしくゾラン

(*)システムのすべての構成を生成し、各構成が発生した回数を保存する必要がある確率シミュレーションソフトウェアに取り組んでいます。その意味で、リスト{n1、n2、...、nT}は、タイプ1のn1粒子、タイプ2のn2粒子、...、タイプTのnT粒子があることを示すシステムの特定の構成を記述します。そのような構成は指数関数的に多くなる可能性があります。

2 answers

9
acl 2011-08-30 19:26.

ルックアップ時間が指数関数的であることをどのように計算したかについて詳しく教えてください。

それが実際に指数関数的である場合はHash、キー(構成)を使用し、キーと値のペアをのようなリストに格納し、{{key1,value1},{key2,value2}}並べ替えてkeyからバイナリ検索(ログ時間)を使用することで、処理を高速化できます。これはコーディングが非常に速いはずですが、速度の点では最適ではありません。

それが十分に速くない場合は、適切なハッシュテーブルの実装を設定することを考えることができます(これf[{0,1,0,1}]=3は、チェックせずにアプローチが行ったことだと思いました)。

しかし、減速のおもちゃの例は、さらに先に進むのに役立ちます...

編集:私はちょうど試しました

test[length_] := Block[{f},
  Do[
   f[RandomInteger[{0, 10}, 100]] = RandomInteger[0, 10];,
   {i, 1, length}
   ];
  f[{0, 0, 0, 0, 1, 7, 0, 3, 7, 8, 0, 4, 5, 8, 0, 8, 6, 7, 7, 0, 1, 6,
      3, 9, 6, 9, 2, 7, 2, 8, 1, 1, 8, 4, 0, 5, 2, 9, 9, 10, 6, 3, 6, 
     8, 10, 0, 7, 1, 2, 8, 4, 4, 9, 5, 1, 10, 4, 1, 1, 3, 0, 3, 6, 5, 
     4, 0, 9, 5, 4, 6, 9, 6, 10, 6, 2, 4, 9, 2, 9, 8, 10, 0, 8, 4, 9, 
     5, 5, 9, 7, 2, 7, 4, 0, 2, 0, 10, 2, 4, 10, 1}] // timeIt
  ]

timeIt次のように、短時間でも正確に時間を計るように定義されています。

timeIt::usage = "timeIt[expr] gives the time taken to execute expr,
  repeating as many times as necessary to achieve a total time of \
1s";

SetAttributes[timeIt, HoldAll]
timeIt[expr_] := Module[{t = Timing[expr;][[1]], tries = 1},
    While[t < 1.,
    tries *= 2;
    t = Timing[Do[expr, {tries}];][[1]];
    ];
    Return[t/tries]]

その後

out = {#, test[#]} & /@ {10, 100, 1000, 10000, 100000, 100000};
[email protected]

(大規模な実行の場合も)。ですから、ここでは一定の時間のようです。

3
Rolf Mertig 2011-08-31 05:22.

あなたが好きではないあなたの情報を入力するとします

f[{1,0,0,0}] = 1
f[{0,1,0,0}] = 2

しかし、次のmようなn1 x n2 x n3 xn4行列に

m[[2,1,1,1]] = 1
m[[1,2,1,1]] = 2

(あなたもないような値を入力することができf[{1,0,0,0}]=1ますが、ようf[{1,0,0,0},1]

  f[li_List, i_Integer] := Part[m, Apply[Sequence, li + 1]] = i;
  f[li_List] := Part[m, Apply[Sequence, li + 1]];

ここで、mたとえばm = ConstantArray[0, {4, 4, 4, 4}];)によって初期化する必要があります

タイミングを比較してみましょう:

testf[z_] := 
  (
   Do[ f[{n1, n2, n3, n4}] = RandomInteger[{1,100}], {n1,z}, {n2,z}, {n3,z},{n4,z}];
   First[ Timing[ Do[ f[{n2, n4, n1, n3}], {n1, z}, {n2, z}, {n3, z}, {n4, z} ] ] ]
  ); 
Framed[
   ListLinePlot[
       Table[{z, testf[z]}, {z, 22, 36, 2}], 
       PlotLabel -> Row[{"DownValue approach: ", 
                          Round[MemoryInUse[]/1024.^2], 
                          " MB needed"
                         }], 
       AxesLabel -> {"n1,n2,n3,n4", "time/s"},ImageSize -> 500
   ]
]
Clear[f]; 
testf2[z_] := 
  (
    m = RandomInteger[{1, 100}, {z, z, z, z}]; 
    f2[ni__Integer] := m[[Sequence @@ ({ni} + 1)]]; 
    First[ Timing[ Do[ f2[{n2, n4, n1, n3}], {n1, z}, {n2, z}, {n3, z}, {n4, z}] ] ]
  )
Framed[
   ListLinePlot[
       Table[{z, testf2[z]}, {z, 22, 36, 2}], 
       PlotLabel -> Row[{"Matrix approach: ", 
                         Round[MemoryInUse[]/1024.^2], 
                         " MB needed"
                        }], 
       AxesLabel -> {"n1,n2,n3,n4", "time/s"}, ImageSize -> 500
  ]
]

与える

したがって、より大きなセットアップ情報の場合、マトリックスアプローチが明らかに好ましいように思われます。

もちろん、本当に大きなデータがある場合、たとえばRAMよりもGBが多い場合は、データベースとDatabaseLinkを使用するだけです。

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

iOS9でSiriに尋ねることができるすべての新しいもの

iOS9でSiriに尋ねることができるすべての新しいもの

AppleがiOS9を発表したときの大きな話題の1つは、Siriがどのように改善され、より「プロアクティブ」になるかということでした。最初はそれが何を意味するのか実際にはわかりませんでしたが、iOSが1週間使用されたので、iOSに何を依頼できるかについてはるかに良いアイデアが得られました。

「食料品の請求書はあなたが絶対に管理できるものの1つです」

「食料品の請求書はあなたが絶対に管理できるものの1つです」

非常に多くのサービスと生活費には、たまにしか変わらない設定価格があります。ただし、食料品の請求書は、閉じ込められておらず、完全に管理できる唯一の場所の1つです。

デスティニーのエキゾチックな戦利品ドロップで何か奇妙な

デスティニーのエキゾチックな戦利品ドロップで何か奇妙な

Destinyにとって興味深い週末でした。新しいエクスプロイトのおかげで、プレイヤーはゲームの戦利品システムがどのように機能するかを通常よりも詳しく見ることができました。

Destinyの最新のエクスプロイトでエキゾチックな自分を殺すことができます[更新:パッチ]

Destinyの最新のエクスプロイトでエキゾチックな自分を殺すことができます[更新:パッチ]

今日Destinyをプレイし始めた場合、同じ古代の低レベルのミッションを実行している友人の数が異常に多いことに気付いたかもしれません。なぜ彼らはそうするのでしょうか?答えは-もちろんこれが答えです-ミッションはプレイヤーが新しい抜け穴を利用し、最小限の労力でたくさんの強力なエキゾチックなアイテムを獲得できるようにすることです。

アマゾンの買い物客はこれを「ホテル品質」の羽毛布団カバーと呼んでおり、価格はわずか22ドルです

アマゾンの買い物客はこれを「ホテル品質」の羽毛布団カバーと呼んでおり、価格はわずか22ドルです

何千人もの Amazon の買い物客が Bedsure Duvet Cover を推奨しており、現在セール中です。羽毛布団カバーにはいくつかの色があり、ツインからカリフォルニアキングまでのサイズがあります。Amazon で最大 52% オフの最高評価の羽毛布団カバーを購入する

バレンタインデーにユーカリのシャワースチーマーで「最高の睡眠」を贈りましょう。

バレンタインデーにユーカリのシャワースチーマーで「最高の睡眠」を贈りましょう。

BodyRestore ユーカリ シャワー スチーマーは、Amazon で 11,000 を超える 5 つ星の評価を得ています。セルフケアが必要な人へのバレンタインデーのギフトとして、ホームスパ製品を贈りましょう。

この「邪悪な吸引力」を備えたこの250ドルのハンドヘルド掃除機は、Amazonで75%オフになりました

この「邪悪な吸引力」を備えたこの250ドルのハンドヘルド掃除機は、Amazonで75%オフになりました

多くのAmazonの買い物客がUmlo H6ハンドヘルド掃除機を推奨しており、現在スーパーセール中です. ハンドヘルド デバイスには HEPA フィルターが装備されており、複数のアタッチメントが付属しています。Amazonで75%オフのときにハンドヘルド掃除機を購入する

オクタヴィア・スペンサー、「ザ・ヘルプ」共演者のシシー・スペイセクが17歳で映画のインターンをした後、彼女のことを「実際に」思い出したと語る

オクタヴィア・スペンサー、「ザ・ヘルプ」共演者のシシー・スペイセクが17歳で映画のインターンをした後、彼女のことを「実際に」思い出したと語る

オクタヴィア・スペンサーは、ヘルプで一緒に共演するずっと前に、シシー・スペイセク主演の 1990 年の映画「ロング・ウォーク・ホーム」でインターンとして働いていました。

メリック・ガーランドはアメリカに失敗しましたか?

バイデン大統領の任期の半分以上です。メリック・ガーランドは何を待っていますか?

メリック・ガーランドはアメリカに失敗しましたか?

人々にチャンスを与えることは、人生で少し遅すぎると私は信じています。寛大に。

良いものと醜いもの: 2022

良いものと醜いもの: 2022

もうわからない。何が「ヒット」かを正確に判断することは、もはやほとんど不可能に思えます。

楽しみのために — 2022 年のトップの新しい音楽再生

楽しみのために — 2022 年のトップの新しい音楽再生

ついに!私の 2022 年のトップ ニューミュージック プレイへようこそ。私は毎年これを共有して、友達とつながります。

ヒーズ・オール・アイヴ・ガット

ヒーズ・オール・アイヴ・ガット

あなたの心をチェックしてください。私たちの心はしばしば迷います。

Language