重複チェックプログラム

質問

ご経験ある方いらっしゃいましたらアドバイスください。
環境：linux, gcc

64bitの整数データ（符号なし）を入力とし、64bitの整数データを出力する関数を作成中です。
入力データに対して、出力データは絶対に重複しないという条件で関数を作成したのですが、
（入力と出力は1対1になる）
その条件のチェックができない状態で困っています。

試した方法は、以下のとおりです。
(1)すべての入力データに対する出力データをテキストファイルに書き出す。
(2)再びすべての入力データを計算するのだが、今度は出力データを(1)で作成したテキストファイルと比較していく。
そのときテキストファイル内に出力データと同じデータが２つ以上あれば重複が存在する。

しかし、(1)の時点でlinuxのファイル制限2.1GBに引っかかってしまい、
これ以上進めることができませんでした。

同じような大量のデータに対して重複確認することは不可能なのでしょうか？
もし、linuxのファイル制限がなくてもHDDの容量制限に引っかかってしまいそうです。
このような制限に依存せず、重複確認できる方法がありましたら教えてください。
質問が不明、不足な点がある場合にもご指摘おねがいします。宜しくお願いします。

回答No.10

Tacosan

や, 「メモリ云々」はさておいて, 時間的に不可能でしょう＞#8. 2^64通りを全部計算させようとすると, 1Tops (1秒間に 1兆通り計算する) でまわしても 1000万秒 (4ヶ月くらい) かかります.
ということで, 「実際に全部出力して重複チェック」は事実上不可能です. その関数が完全に 1対1 の出力をすることを, 「アルゴリズム的に」証明するしかないと思います.
ちなみに「PC」のメモリ容量は, 今だと 128GB くらいが限界じゃないでしょうか＞#9. まあ, こんなに積もうとするといろいろ大変ですが.

回答No.9

titokani

#8です。補足
20bitという数には特に意味はありません。64bitOSにしてメモリを積めるだけ積めばもっと増やせますね。最近のPCって、いったい何GBくらい積めるんでしょうか。

回答No.8

titokani

メモリが天文学的に必要となるか、時間が天文学的に必要となるかのどちらかですから事実上不可能でしょう。

あるいは、
http://www.kameson.com/climateprediction.htm
こういったやつとか・・・。

時間で解決する方法としては、下位20bitのみを比較して、それを2^44回繰り返すとかでしょうか。
2^(64+44)の計算が必要となるので、いったいどれだけかかるのか見当もつきませんが。

回答No.7

masa6272

2の45乗ですが・・・
ほぼ35テラバイトです。
それが、65,000個。

無理だと思いますが・・・

回答No.6

tig33

追加補足です。

２＊＊６１バイトのファイルができなくても、ファイル分割すれば、可能ですね。

２＊＊１６（＝６５５３６）個のファイルに分割すれば、一つのファイルは、２＊＊４５バイトのファイルになりますから、これで対応可能でしょう。

基本的に出現した数値のマップにすれば、たいした大きさにはならないと思いますけど・・・

回答No.5

tig33

２の６４乗個のビット列をマップとして、出現したかどうかをビットフラグとしてチェックすればいかがですか？

このマップをファイルにすれば、（２の６４乗÷８）バイトのファイルで実現できますね。

ただ、２の６１乗バイトのファイルってできましたっけ・・？

回答No.4

masa6272

a,b,c が何を意味するのか、不明ですが・・・

y = f(x)
定義域(xの範囲) 64ビット整数
値域(yの範囲) 64ビット整数
xは、系統的に発生できる

と考えていいのでしょうか?
はっきり言って、無理だと思いますが・・・

回答No.3

splwtr

ファイル・サイズの制限が２.1GＢとは、
ＮＦＳで１ファイルのサイズ制限でしょうか？

逆質問はおいといて、もしかして
出力ファイルが１ファイルが問題であって、出力ファイルを
検索しやすいように複数にしたら、今のままで十分な気がします。
時間はかかるでしょうけどね。

前準備に入力データをなんらかの規則でフィルタできたら、重複傾向も
見つけやすいような気もしますが、ここはわかりません。

回答No.2

POTATO_XP

テキストに書く目的・書かないといけない理由は何ですか？そもそも、何を調べる為のものなんでしょうか？では、初期のファイルはどうなっているんでしょう？本当に単純に書き出すファイルを分割するとかで対応できない理由って何なんでしょう？何がしたいかがイマイチ理解できません。更に補足ヨロシク！

回答No.1

POTATO_XP

入力データに対して、出力データが重複しない為の条件によりますが、単純にその関数を呼び出すスレッドを作成しその都度比較していけば良いのではないでしょうか？１回目と１回目は重複するとかなら、一回だけ空で回した後で比較するとか、スレッドの数に制限を設ける必要が無ければ、輪唱の様にスレッドを立てていきつつ、総当りで比較する様に作るなどイロイロやりようがあります。

的外れてたらすみません、条件をもう少し厳密に伝えて頂ければこちらとしても的確にアドバイスできるのですが・・・。Windowsでは専門知識多少アリ。

補足

ご回答ありがとうございます。
もしかしたら説明不足かもしれませんでしたので補足させてください。
たとえば、
y = x というような関数が存在するとし、
このとき入力データが（a, b, c）の3つだけだとします。
この関数で入力に対する出力が重複しないことをチェックする方法として、
(1)まず（a, b, c）の3つのデータを関数で計算し、出力データをテキストファイルに書き出します。
ここでは、テキストファイルには(a, b, c)と書かれているはずです。
(2)再び（a, b, c）の3つのデータを関数で計算するのですが、計算するたびに出力データをテキストファイルに書かれているデータと比較します。
そのときテキストファイル内に出力データと同じデータが２つ以上あれば重複が存在することになります。

うえの例では入力データが（a, b, c）の3つという条件で問題ありませんでしたが、
入力データが64bitの整数データ（符号なし）すべてのように大量になった場合には、
(1)でテキストファイルに書かれるデータも大量になり、
実際にlinuxのファイル制限2.1GBに引っかかってしまいます。

これを回避する方法が教えていただきたいところです。

POTATO_XPさん
＞単純にその関数を呼び出すスレッドを作成しその都度比較していけば良いのではないでしょうか？
テキストファイルにどうしてもデータを書き出す必要があり、こんな単純なことに気づきませんでした。ありがとうございます。
ファイルに書き出すのはどうがんばっても無理なんでしょうね。