問題タブ [oeis]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
database - データベースのクエリ時間は、データベースのサイズに応じてどのように変化しますか?
私は最近、OEIS (整数シーケンスのオンライン百科事典) に参加していて、自分が持っていた特定のシーケンスを調べようとしていました。
さて、このデータベースはかなり大きいです。ウェブサイトによると、2006 年版 (! 5 年前) が印刷された場合、750 巻のテキストを占めることになります。
これは、Google が対処しなければならないのと同じ種類の問題だと確信しています。ただし、負荷分散を利用する分散システムもあります。
ただし、負荷分散を無視すると、データベースのサイズと比較して、クエリを実行するのにどれくらいの時間がかかりますか?
言い換えれば、DB サイズに対するクエリの時間計算量はどれくらいですか?
編集：物事をより具体的にするために、入力クエリが次のような数字の文字列を単に検索していると仮定します。
python - A010784 シーケンスをフィルター処理する最速の方法
OEIS の A010784 シーケンスは、数字が異なる数字のみを含むシーケンスです。これは有限の量です。
私がやろうとしてきたのは、このシーケンスで特定の属性を持ついくつかの数字を見つけることです。
例: 6 はマグニチュード 10 の個別の数です。これは次のように見つけることができます。
- 6×1＝6
- 6×2＝12
- 6×3＝18
- 6×4＝24
- 6×5＝30
- 6×6＝36
- 6×7＝42
- 6×8＝48
- 6×9＝54
- 6×10＝60
- 6 x 11 = 66 (2 つの 6。これらは両方とも異なる数字ではありません。)
今、私はいくつかの大きさのオーダーで利用可能な最大数を試しています。
1 から 20 までのすべての注文を考えてみましょう。
私が現在行っているのは、9,876,543,210 である可能な最大の個別の番号と、マグニチュード 1 の最大の一意の番号から、非常に低い番号までのループです。この方法は非常に効率が悪い
と感じます。少なくとも、私にはそうです。
物事をもっと速くできるはずの因数分解について、いくつかのことを見逃していると確信しています。
recursion - このシーケンスの一般的な用語を見つける
このシーケンスの一般的な用語または漸化式を見つけることに挑戦しました
5,18,44,96,195 ....私が持っている唯一のヒントは、このシーケンスが適用されたフィボナッチ数列であるということです。誰かが再発またはn番目の用語を見つける方法を提案できますか？私はOEISを調べましたが、この特定の整数シーケンスについてはこれに注意する必要はありません。私は多くの場所を検索しましたが、成功しませんでした。また、このシーケンスの項は対数時間で決定できると思います。どんな助けでも大歓迎です。
haskell - "cabal install happy" はメモリ オーバーフローを引き起こします。(GHC 7.8.2)
私は過去数日間、正しくインストールすることに満足しようとしてきました.cabal install happyエラーだけでなく ( をインストールhappy-1.19しapt-getてに追加/opt/happy/1.19.3/binすることによってPATH) に到達するのは難しいと感じましたが、今ではProduceCode(15 /18) となり、無限ループに陥っているようです。Ctrl+Cシステム全体が応答しなくなったときに、ヒットするか電源を切るまで、メモリが蓄積されます。
これは GHC-HEAD ではまったく問題にならなかったことを覚えていると思いますが、head は数日ごとに更新されるように見えるため、使用したくありません。トリックがない限り、常にパッケージを再ビルドする必要があります。からheadへの移行については不明head+1です。
algorithm - OEIS はどのようにサブシーケンス検索を行いますか?
Online Encyclopedia of Integer Sequences は、クエリをサブシーケンスとして含むシーケンスの検索をサポートしています。を検索するsubseq:212,364,420,428と、シーケンスが返され8*n+4ます。( http://oeis.org/search?q=subseq:212,364,420,428 )
この驚くべき機能は、Russ Cox によってhttp://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Featuresとして実装されたようですが、これがどのアルゴリズムで実装されているかは指定されていません。
どうやって作っているのか気になります。1 回の検索で 100 万近くのシーケンスを処理することは、検索エンジンにとって明らかに非現実的です。最初の数字のインデックス (Russ Cox が Google Code Regex Search を行ったのと同じ方法) を保持するだけでは、数字のようなもの0はほとんどすべてのシーケンスにあるため、残りをブルート フォースしても機能しません。実際、一部のクエリ0 1はデータベース全体の高いパーセンテージと一致するため、アルゴリズムは目的の出力サイズに敏感な実行時間を必要とします。
この機能がどのように実装されているか知っている人はいますか?