私はこの巨大な2次元データ配列を持っています。非常に大きな行列の転置を見つける
A（1,1）A（1,2）A（1,3）..... A（n-2、n）A（n-1、n） （nは、n個）
私は列の順序
A（1,1）A（2,1）A（3,1）···A（nは、n個にそれを再配置したいです-2）A（n、n-1）A（n、n）
データセットはかなり大きく、コンピュータのRAMに収まるものよりも大きくなります。 （nは約10,000ですが、各データ項目には約1Kのスペースが必要です）
これを行うには、滑らかで効率的なアルゴリズムを知っている人はいますか？
n空のファイルを作成します（できる場合は、n要素のための十分な領域を確保してください）。オリジナルの行列を繰り返します。要素(i,j)をファイルjに追加します。これで完了したら、今書き込んだファイルを追加してください。
"空でない"ファイルはあまり良い考えではないと思います。約10,000のファイルを作成する必要があります。ファイルシステムの中には、ディレクトリ内の多くのファイルを許可しないものもあれば、あまり知られていないデータベース手法を使ってディレクトリ内のファイルを一覧表示するものもあります。ですからまず、Bツリーやそのようなものを使ってディレクトリをリストする非常にスマートなファイルシステムを使う必要があります。 （Linuxのファイルシステムの中にはこれがあるかもしれません） –
次に、ファイルに書き込むと、ラウンドロビン方式でハードドライブ上の約10,000の異なる場所に書き込みます。これは、オペレーティングシステムまたはディスクハードウェアのいずれかで使用されるディスクキャッシュ方式を完全に壊滅させる可能性が最も高いです。この問題は、n個の空きスロットがあらかじめ予約されているファイルが1つでもあっても保持されます。 –
一方、私の友人が実際にこの方法を試したメールを私に送ってくれました。それは本当に私が思っていたより速く進みました。だから私は私が言ったことを取り戻す - あなたのソリューションは間違いなく試してみる価値がある。 –
あなたのアプリケーション全体がクラスのインスタンスを通じて行列にアクセスするように、Matrixクラスが必要です。次に、転置は要素にアクセスするときにインデックスを逆転させるフラグを設定するだけです。インスタントトランスポーズ！
データはハードドライブ上のファイルに保存されます。このファイルを読み込んで、データの転置を別のファイルに書き込むプログラムが必要です。 –
また、私はおそらくファイルのサイズ仕様を誇張しています。おそらく100GBよりも10GBに近いでしょう。しかし確かに4GB以上。 –
最後に、私はこのプログラムをC++で書くことを考えています。 –
単純な方法は、ファイルを10000回読み取って、各行に対応する列を見つけることです。これは実装が簡単なはずですが、プログラムを実行するのにどれくらいの時間がかかるかわかりません。
あなたのコメントでは、別のファイルを出力してから
sortでソートする必要があります。このような大きなファイルをソートするのは永遠にかかりますので、それは悪い考えです。ソートは複雑な（または少なくともリソースが重い）問題であるため、トランスポーズをソートに一般化することはおそらく間違った方法です。
ソートのアイデアについて - 私はそれを使って実験を行いました。そして、ソートのソートプログラムはかなり洗練されています。たとえば、ファイルが信じられないほど巨大であれば、それは小さなファイルに分割し、それぞれをソートしてからマージします。私はそれをコンピュータ上のRAMよりも大きいファイルでテストしましたが、それはむしろうまく機能します。 –
これは分裂征服法と呼ばれ、基本的にはmergesortとquicksortがやっていることです（ディスク上ではなくメモリ上の問題を分割するのがほとんどですが、基本原理は同じです）。 –
ところで、私は線形時間について私が言ったことを取り戻します。ファイルを横断する時間は2倍の時間になります（より長いファイルに繰り返しを掛けたもの）。ソート方法は結局実行可能な解決策のように思えます。 –
どのようなプログラミング言語/アプリケーションですか？ – SuperTron
RAMに格納するには大きすぎる場合、マトリックスはどこに保存されていますか？物は実行中にRAMに保存されます。 – Dimme
n = 10000は10000x10000x1KB = 100GBを意味します。 –