問題タブ [memory-efficient]

私はインタビューでこの質問をされ、さまざまな解決策を示しましたが、インタビュアーは納得していませんでした。私は解決策を見つけることに興味があります。あなたの意見を投げてください：

Q：iPodにシャッフルを実装するための効率的なデータ構造を記述してください。すべての曲を再生する必要があります。毎回異なるランダムな順序で、同じ曲を繰り返さないでください。（主にO（n））

1つの解決策は、インタビューの後で考えました。再帰なしでランダム化されたクイックソートを実行できます。ランダムに、1つのピボットO（1）を選択してから、クイックソートO（n）を実行します。これで曲が順番に並べ替えられ、最後まで再生します。それが終わりに達したら、私は再びランダムなピボットを選択し、このプロセスを何度も繰り返します。

よろしく、セトゥー

次の単純化されたケースを考えてみましょう。

最初の2つのパラメーターに基づいて、このリストのリストをリストのリストのリストに変換するためのpythonicでメモリ+速度の効率的な方法は次のとおりです。

実際には、正しい階層がある限り、他のデータ構造でも問題ありません。たとえば、次の辞書構造が思い浮かびますが、それを作成しても速度効率が十分ではないようで、メモリはおそらく lolol ソリューションよりも高くなります。

非常に大きなタブ区切りファイル（数百万行を含む）を繰り返し処理し、そのファイル内のフィールドの値に基づいて、そのファイルのさまざまな行をペアリングしています。

「mydict」は非常に大きくなるので、イテレータにしたいので、すべてをメモリに保持する必要はありません。ディクショナリにデータを入力する代わりに、ループして同じフィールド値を持つ行のリストをすべて取得できるイテレータを作成するにはどうすればよいですか？

ありがとう。

高次元配列と 1 次元配列の使用効率に興味があります。次のように配列を定義して反復処理すると、何かが失われますか?

または、次のように配列を定義して反復します。

違いはないだろうというのが私の傾向ですが、私はまだ高効率プログラミングについて学んでいます (これまで、この種のことを気にする必要はありませんでした)。

ありがとう！

20組の座標があり、そのx値とy値は次のようになります。

ここで、15ペアの座標（x、y）をランダムに生成し、上記の20ペアの座標と比較したい場合、ネストされたループなしでこれを最も効率的に行うにはどうすればよいですか？

だから私は85項目のリストを持っています。このリストを継続的に半分に減らしたいと思っています (基本的にはアイテムのバイナリ検索です)。私の質問は、リストを減らす最も効率的な方法は何ですか? リスト内包表記は、理想的ではないリストのコピーを継続的に作成します。1 つの要素が残るまで、リストの範囲をその場で削除したいと考えています。

これが関連しているかどうかはわかりませんが、標準のリストの代わりに collections.deque を使用しています。おそらく多かれ少なかれ同じように機能するので、これが問題になるとは思えません。

ベクトル x があるとします。

これをすばやく単一の文字列「a b」に変換したいと思います。ループなしでこれを行う方法はありますか? 私はループでこれを行うことができることを知っています:

しかし、これを何回も繰り返す必要があり、これをループして、毎回オリジナルを新しいものに置き換える必要があると、非常に時間がかかります。私はいつも次のようなことができるようになりたいと思っています:

paste() がベクトル自体の要素をスマートに分割できるかのようですが、それができないことはわかっています。これを効率的に達成できる別の関数、または paste() を使用するより創造的な方法はありますか?

私はチュートリアルに従って Java でボンバーマンをプログラミングしています (これは私の最初のゲームです)。チュートリアルでは、衝突を検出するための次のコードを提案しています。

ここまでで、entitiesは敵とプレイヤーを含む配列リストです。プレイヤーが壁に衝突したことも検出したいので、レベル内のすべての壁またはレンガ タイルをエンティティ配列リストに入れる必要がありますか? もしそうなら、このアルゴリズムは非常に非効率的ではありませんか? これらのタイルは他のタイルと衝突することはないので、ゲーム エンティティを別のリストで管理することを考えていました。何を指示してるんですか？それを行うためのより効率的なアルゴリズムはありますか?

注: 2D ゲームでの衝突に関する他の質問は既に読みました。どうもありがとう。

メモリコストは明らかにモジュールの正確な大きさに依存しますが、私は一般的な答えを探しているだけです：Pythonでモジュールをインポートするのは一般的に高価ですか、それとも安価ですか？アプリケーションの全期間にわたってメモリに残る可能性のある小さなスクリプトが数十個ある場合、それはメモリをどれだけ占有しますか？

テキスト分析についてアドバイスが必要です。プログラムはphpで書かれています。

私のコードは、URL を受け取り、DB に対してサイトの単語を照合し、一致を探す必要があります。

注意が必要な部分は、テキストに表示される単語が常に DB に書き込まれるとは限らないことです。

例：

私のDBにこれらの値があるとしましょう：単語=​​文字

このサイトには次のようなものがあります。

私は出力することになっています：文字のこと

私のコードは、検索された単語をDBと照合しようとするたびに、いくつかの正規表現を作成します。

見つからない単語ごとに、DB に対して 8 つのクエリを作成します。ほとんどの単語は一致しないため、何百もの単語を含む Web サイト全体について話すと、CPU レベルが急上昇します。

私は、DB に見つからないすべての単語を出現時にグローバルに保存すること (HD は CPU よりもコストが低い)、またはそのすべてを保存するための配列または辞書を作成することを考えました。

私はこのプロジェクトと本当に混乱しています。多くのユーザーにサービスを提供することになっていますが、現在のコードでは、サーバーは 10 ～ 20 のユーザー リクエストで停止します。

何かご意見は？

編集: 検索された単語は英単語ではなく、コードは Windows 2008 サーバーで実行されます