ようこそ ゲスト さん、新規登録（無料）して気になる疑問を解決しませんか？
はじめての方へ｜ヘルプ｜FAQ
スポンサーサイト（詳細）

質問
QNo.4007578 重複チェックプログラム
質問者：ring_rollo ご経験ある方いらっしゃいましたらアドバイスください。
環境：linux, gcc

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

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

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

同じような大量のデータに対して重複確認することは不可能なのでしょうか？
もし、linuxのファイル制限がなくてもHDDの容量制限に引っかかってしまいそうです。
このような制限に依存せず、重複確認できる方法がありましたら教えてください。
質問が不明、不足な点がある場合にもご指摘おねがいします。宜しくお願いします。
困り度：
  • 困っています
質問投稿日時：
08/05/08 21:25
この質問に対する回答は締め切られました。
最新から表示｜回答順に表示｜良回答のみ表示

回答
ANo.10 や, 「メモリ云々」はさておいて, 時間的に不可能でしょう＞#8. 2^64通りを全部計算させようとすると, 1Tops (1秒間に 1兆通り計算する) でまわしても 1000万秒 (4ヶ月くらい) かかります.
ということで, 「実際に全部出力して重複チェック」は事実上不可能です. その関数が完全に 1対1 の出力をすることを, 「アルゴリズム的に」証明するしかないと思います.
ちなみに「PC」のメモリ容量は, 今だと 128GB くらいが限界じゃないでしょうか＞#9. まあ, こんなに積もうとするといろいろ大変ですが.
回答者：Tacosan
種類：アドバイス
どんな人：一般人
自信：参考意見
回答日時：
08/05/09 17:14
この回答へのお礼この回答にお礼をつける(質問者のみ)

回答
ANo.9 #8です。補足
20bitという数には特に意味はありません。64bitOSにしてメモリを積めるだけ積めばもっと増やせますね。最近のPCって、いったい何GBくらい積めるんでしょうか。
回答者：titokani
種類：アドバイス
どんな人：専門家
自信：参考意見
回答日時：
08/05/09 10:07
この回答へのお礼この回答にお礼をつける(質問者のみ)

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

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

時間で解決する方法としては、下位20bitのみを比較して、それを2^44回繰り返すとかでしょうか。
2^(64+44)の計算が必要となるので、いったいどれだけかかるのか見当もつきませんが。
回答者：titokani
種類：アドバイス
どんな人：専門家
自信：参考意見
回答日時：
08/05/09 09:42
この回答へのお礼この回答にお礼をつける(質問者のみ)

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

無理だと思いますが・・・
回答者：masa6272
種類：アドバイス
どんな人：経験者
自信：自信あり
回答日時：
08/05/09 09:01
この回答へのお礼この回答にお礼をつける(質問者のみ)

回答
ANo.6 追加補足です。

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

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

基本的に出現した数値のマップにすれば、たいした大きさにはならないと思いますけど・・・
回答者：tig33
種類：アドバイス
どんな人：経験者
自信：参考意見
回答日時：
08/05/09 08:25
この回答へのお礼この回答にお礼をつける(質問者のみ)

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

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

ただ、２の６１乗バイトのファイルってできましたっけ・・？
回答者：tig33
種類：アドバイス
どんな人：経験者
自信：参考意見
回答日時：
08/05/09 08:18
この回答へのお礼この回答にお礼をつける(質問者のみ)

回答
ANo.4 a,b,c が何を意味するのか、不明ですが・・・

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

と考えていいのでしょうか?
はっきり言って、無理だと思いますが・・・
回答者：masa6272
種類：補足要求
どんな人：経験者
自信：参考意見
回答日時：
08/05/09 06:23
この回答へのお礼この回答にお礼をつける(質問者のみ)

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

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

前準備に入力データをなんらかの規則でフィルタできたら、重複傾向も
見つけやすいような気もしますが、ここはわかりません。
回答者：splwtr
種類：アドバイス
どんな人：一般人
自信：自信あり
回答日時：
08/05/09 02:12
この回答へのお礼この回答にお礼をつける(質問者のみ)

回答
ANo.2 テキストに書く目的・書かないといけない理由は何ですか？そもそも、何を調べる為のものなんでしょうか？では、初期のファイルはどうなっているんでしょう？本当に単純に書き出すファイルを分割するとかで対応できない理由って何なんでしょう？何がしたいかがイマイチ理解できません。更に補足ヨロシク！
回答者：POTATO_XP
種類：補足要求
どんな人：専門家
自信：参考意見
回答日時：
08/05/08 23:22
この回答へのお礼この回答にお礼をつける(質問者のみ)

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

的外れてたらすみません、条件をもう少し厳密に伝えて頂ければこちらとしても的確にアドバイスできるのですが・・・。Windowsでは専門知識多少アリ。
回答者：POTATO_XP
種類：回答
どんな人：専門家
自信：参考意見
回答日時：
08/05/08 21:55
この回答への補足ご回答ありがとうございます。
もしかしたら説明不足かもしれませんでしたので補足させてください。
たとえば、
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さん
＞単純にその関数を呼び出すスレッドを作成しその都度比較していけば良いのではないでしょうか？
テキストファイルにどうしてもデータを書き出す必要があり、こんな単純なことに気づきませんでした。ありがとうございます。
ファイルに書き出すのはどうがんばっても無理なんでしょうね。
この回答へのお礼この回答にお礼をつける(質問者のみ)
最新から表示｜回答順に表示｜良回答のみ表示
スポンサーサイト（詳細）
このページのトップへ