C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[2]: メモリを上回るデータをソート


(過去ログ 132 を表示中)

[トピック内 13 記事 (1 - 13 表示)]  << 0 >>

■77935 / inTopicNo.1)  メモリを上回るデータをソート
  
□投稿者/ メモリ節約し隊 (8回)-(2015/12/02(Wed) 06:29:02)

分類:[C#] 

Windows7以降のOS C# .NetFramework4.0 に関する質問です。

メモリ容量を超える大量の16進数文字列データ(ファイル名)を扱うことになりました。(例 ABC13.txt)

文字列データをファイル名として大量にファイルを生成して10000件ほどでフォルダに区切りたいと思います。
フォルダ名はフォルダ内の一番昇順で上に来るファイル名の名前を付けます。

できそうにみえたのですが、なかなか難しくて苦戦しております。
どなたかよい方法を知っている方はいらっしゃるでしょうか。
引用返信 編集キー/
■77936 / inTopicNo.2)  Re[1]: メモリを上回るデータをソート
□投稿者/ 774RR (343回)-(2015/12/02(Wed) 08:32:08)
メモリに収まらないほどのファイル名・・・って 2GB とかの量になりそうだけど・・・
1ファイル名が 256 文字として 800 万個超のファイルを生成する、ってこと?
となるとディスク容量/アクセス待ち時間のほうも半端ないことになりそう。

64bit OS + 大量の実メモリ + 超高速ディスク装置がないと実用的時間で終わりそうにない気のせいがする。
オイラなら案件を見直すほうをお勧めしたい。

64bit OS に 32GB RAM が載ってれば 2GB 程度のデータ、オンメモリソートも可能なように思う。
32bit OS でも動く必要があるなら、とりあえずソートだけならヒープソートでできそう。
でも組んでみました、性能出ませんでした、ではかなり悲しい。

適当なデーターベースソフトにファイル名文字列データをぶっこんで SELECT * ORDER BY ... ってのが
手間がなさそうな気がするっす。

引用返信 編集キー/
■77940 / inTopicNo.3)  Re[1]: メモリを上回るデータをソート
□投稿者/ furu (39回)-(2015/12/02(Wed) 11:03:37)
No77935 (メモリ節約し隊 さん) に返信
> できそうにみえたのですが、なかなか難しくて苦戦しております。

どのへんが難しいですか?
引用返信 編集キー/
■77946 / inTopicNo.4)  Re[2]: メモリを上回るデータをソート
□投稿者/ メモリ節約し隊 (9回)-(2015/12/02(Wed) 19:25:28)
皆様回答ありがとうございます。

難しいところは、普通にリストをメモリに押し込んでも入らないところです。
後は、1フォルダに10000件を超えたときに、他のフォルダへ移し替えて必要であればフォルダ名を変える必要があるので
そこらへんがややこしそうなところです。

確かに、ファイル生成には時間がかかると思いますが、
今回はファイル参照の回数が大幅に多いのでフォルダ検索→ファイル検索ができる2段階のソート方法を考えました。

データベースだと制限とかいろいろありそうなんで今は保留の方向で考えています。
おそらくこれだけ大量のデータを扱うとすると有料になりそうですし。

引用返信 編集キー/
■77948 / inTopicNo.5)  Re[3]: メモリを上回るデータをソート
□投稿者/ furu (40回)-(2015/12/02(Wed) 21:47:02)
No77946 (メモリ節約し隊 さん) に返信
> 確かに、ファイル生成には時間がかかると思いますが、
> 今回はファイル参照の回数が大幅に多いのでフォルダ検索→ファイル検索ができる2段階のソート方法を考えました。

かなり大きそうなので2段階では厳しいですね。

テキストファイルの中で行単位で文字列を管理する
フォルダ検索→ファイル検索→行検索ができる3段階のソート方法か
タブ区切りテキストファイルの中で項目単位で文字列を管理する
フォルダ検索→ファイル検索→行検索→項目検索ができる4段階のソート方法
にすれば、かなり高速になると思います。

4段階で1000ずつなら1000×1000×1000×1000で最大1兆個管理できます。

リレーションを使わなければ、データベースにする必要もないです。

作り方(ソートの仕方)はアイデア次第です。
引用返信 編集キー/
■77949 / inTopicNo.6)  Re[4]: メモリを上回るデータをソート
□投稿者/ もりお (2回)-(2015/12/02(Wed) 22:38:13)
2015/12/03(Thu) 05:07:11 編集(投稿者)

文字列の長さが10文字程度なら、文字ごとにディレクトリを掘ってトライ構造にしてしまえば、
検索は文字列に区切り文字を挟んでパスの存在チェックを行うのみなので楽チンです。
ソートは各階層のエントリをソート順に再帰的にたどればよいです。
引用返信 編集キー/
■77957 / inTopicNo.7)  Re[5]: メモリを上回るデータをソート
□投稿者/ メモリ節約し隊 (10回)-(2015/12/03(Thu) 23:22:58)
みなさまありがとうございます。
構造の再検討が必要ですね。
解決済み
引用返信 編集キー/
■77960 / inTopicNo.8)  Re[6]: メモリを上回るデータをソート
□投稿者/ 774RR (345回)-(2015/12/04(Fri) 10:25:59)
16進表記 + ".TXT" 形式しか存在しないのであれば
文字列をソートするのではなくて数値(16進表記の元の値)をソートすればよいに1票。
そうすると1データあたりせいぜい 128bit 程度で収まり、オンメモリソート可能となる気がする。

# 解決済みなのでこれ以上は突っ込まない
解決済み
引用返信 編集キー/
■77978 / inTopicNo.9)  Re[7]: メモリを上回るデータをソート
□投稿者/ メモリ節約し隊 (11回)-(2015/12/06(Sun) 08:30:11)
回答が遅くなりすみません。
ためしに16進文字列を数値に変換しなおそうとしたのですが、longでは数が大きすぎで変換できませんでした。
他の方法があるのでしょうか。

long.Parse("7007040001A002010005A840805424144152606A000A8A4140000049002010619101000080900000081A80100085500000091A400000406A00100AAA60000014410002819424200024A55200009028000000000000", System.Globalization.NumberStyles.HexNumber);
引用返信 編集キー/
■77981 / inTopicNo.10)  Re[8]: メモリを上回るデータをソート
□投稿者/ Azulean (553回)-(2015/12/06(Sun) 09:02:18)
No77978 (メモリ節約し隊 さん) に返信
> ためしに16進文字列を数値に変換しなおそうとしたのですが、longでは数が大きすぎで変換できませんでした。
> 他の方法があるのでしょうか。
>
> long.Parse("7007040001A002010005A840805424144152606A000A8A4140000049002010619101000080900000081A80100085500000091A400000406A00100AAA60000014410002819424200024A55200009028000000000000", System.Globalization.NumberStyles.HexNumber);

これだけ長いと、1つの整数型で扱うことは難しいでしょう。
何文字かで区切って整数化し、それらの整数配列を持って比較できるクラスを実装するかですが。
(区切り方や配列の扱い方によってはバグるので注意)
引用返信 編集キー/
■78001 / inTopicNo.11)  Re[9]: メモリを上回るデータをソート
□投稿者/ 774RR (347回)-(2015/12/07(Mon) 08:51:42)
単純に多倍長整数演算でよいのではないかと思うの心
https://msdn.microsoft.com/ja-jp/library/system.numerics.biginteger.aspx

byte[] から/へ、16進表記文字列が変換できればそれでよいのであれば
手書きしてもたいした内容ぢゃないし。
引用返信 編集キー/
■78019 / inTopicNo.12)  Re[1]: メモリを上回るデータをソート
□投稿者/ Jitta (2回)-(2015/12/08(Tue) 08:29:06)
No77935 (メモリ節約し隊 さん) に返信
例えば、ウェブ上で「東京までの行き方を教えてください」と質問されたら、どうおもいますか?
まずは「あなた今どこにいるの?」と思いませんか?
そういう様な、質問として成り立つ条件が整っていない様におもいます。
「例 abc123.txt」から、8桁くらいの文字列(ファイル名)を想像していたら、長い文字列が出てくるとか。

読む人は、何の情報も持っていないことを念頭に、書き直してもらえないですか?
引用返信 編集キー/
■78028 / inTopicNo.13)  Re[2]: メモリを上回るデータをソート
□投稿者/ メモリ節約し隊 (12回)-(2015/12/08(Tue) 19:25:33)
みなさまコメントありがとうございます。これで解決しそうです。

>Jittaさん
>質問として成り立つ条件が整っていない様におもいます。
すみません、そうですね。条件を把握しきれていないところがありました。申し訳ございません。
 次回からはスレッドを立て直して書き直します。
あとがきになってしまいますが、774RRさんが77960,78001で回答されていた内容を探しておりました。

>Azuleanさん
>これだけ長いと、1つの整数型で扱うことは難しいでしょう。
私もそう思っておりました。ただ、推測で長い整数を扱うクラスがありそうな気がしたので追記で質問しました。

>文字列をソートするのではなくて数値(16進表記の元の値)をソートすればよいに1票。
>そうすると1データあたりせいぜい 128bit 程度で収まり、オンメモリソート可能となる気がする。
774RRが上でこのように回答されていたので、このようなクラスがあることを把握して回答されていたと推測したためです。

>774RR
回答ありがとうございます。助かりました。
BigIntegerのようなものがあるとは知りませんでした。
整数型の種類は検索したのですが、自力でBigIntegerを見つけることはできませんでした。
もっとよく探さないといけませんね。

解決済み
引用返信 編集キー/


トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

管理者用

- Child Tree -