配列の中に重複文字列があるか否かをチェックしたいのですが、アルゴリズムを教えてください。

質問

配列10000個の中に次のように文字列が入っているとします。
（実際に使うのはもっとずっと長い文字列が配列内に格納されています。）
Data_Array[1] = "GRZRMZCOMKMSG"
Data_Array[2] = "DCUIROTLUMWBC"
Data_Array[3] = "RGLBMILRPBSMY"
.
.
.
Data_Array[9998] = "RSKFDHAHMOESI"
Data_Array[9999] = "AQVOXBVNILGOP"
Data_Array[10000] = "YNYRUPEXYOGFN"

配列Data_Array[10000]の中に重複文字列がないか探索したいと考えています。

～普段の手順～
配列中身を一度テキストに吐き出し、そのテキストをExcelに貼り付ける。
そして、Excelのフィルタ機能で重複文字列を排除。
その後、重複文字列を排除した文字列を保存したものをテキストファイルに保存する。
それをプログラムで読み込んで配列内に格納してから次の処理を続ける

といった、効率の悪い方法をとっています。
そこで、プログラム内で処理する方法を次のように考えてみました。

～思いつく方法～
dim DataArrayTemp[10000]
for i = 1 to 10000
flag = 0
// 重複文字がないかチェック
for j = i+1 to 10000
ifb Data_Array[i] = Data_Array[j] then
// 重複があった場合はflag = 1にする
flag = 1
break // 内ループ脱出
endif
next
// flag = 0であれば重複がない項目　(flag = 1のときは、重複がある)
ifb flag = 0 then
DataArrayTemp[temp_i] = Data_Array[i]
temp_i = temp_i + 1
endif
next

これは、力技なので配列内の量が多くなると計算時間がかかってしまいます。

ですので、重複しない文字列だけを抽出する効率の良い方法がありましたらどなたか知恵を貸してください。

回答No.5

aton · ベストアンサー

ハッシュ(連想配列)を使ってはどうでしょうか？

～Perlの例～
#$dataArrayTemp[0 .. 9999]には既に値が格納されていると仮定
%temp = ();
%nodup = ();
for ($i = 0; $i <1000; $i++) {
if (defined($temp{$dataArrayTemp[$i]})) {
if (defined($nodup{$dataArrayTemp[$i]})) {
push(@dups, delete($nodup{$dataArrayTemp[$i]}));
}
next;
}
$temp{$dataArrayTemp[$i]} = $i;
$nodup{$dataArrayTemp[$i]} = $i;
}

ソートすると，例えば（一般に最速と言われている）クイックソートならO(N logN)の計算量になりますが，ハッシュを使えば（少なくとも見かけ上の）計算量はO(N)で済みます。

ただ123456zennsinnさんの使っている言語（BASIC系？）にハッシュがあるかどうかは？　VB.NETだとHashtableクラスとかありそうですが。

http://www.atmarkit.co.jp/fdotnet/dotnettips/125hashtable/hashtable.html

お礼

ありがとうございました。

回答No.4

SpiralGalaxy

↓ここ打ち間違ってました。正しくは
Dim data2 As String() = CType(list.ToArray(GetType(String)), String())

回答No.3

SpiralGalaxy

以下のようにコーディングすればスッキリ書けます。
data が元データで data2 が処理後データとなります。
効率は ArrayList や Vector の実装によるので、速いかどうかはよくわかりませんが…。
オブジェクトの再拡張を防止するために、件数がわかっているならNew ArrayList(15000) とか初期容量を十分に取っておく方が望ましいです。

☆ ＶＢなら
　Dim data As String() = {"ABC", "123", "ABC", "ABCD"}
　Dim list As New ArrayList
　For i = 0 To data.Length - 1
　　If Not list.Contains(data(i)) Then
　　　list.Add(data(i))
　　End If
　Next
　Dim data2 As String() = CType(list.ToArray(GetType,String)), String())

☆ Ｊａｖａなら
　String[] data = {"ABC", "123", "ABC", "ABCD"};
　Vector<String> vc = new Vector<String>();
　for(int i = 0; i < data.length; i ++) {
　　if(!vc.contains(data[i])) {
　　　vc.add(data[i]);
　　}
　}
　String[] data2 = vc.toArray(new String[0]);

回答No.2

SheetFit00

ヒントというか、私ならソートしてから比較します。
そうすると配列の前後を比較するだけで、内側のループがいらなくなりますね。

重複が１個なのか２個以上あるのかとか、配列の並びに意味があるなら、順番をどこかに保存しておかなければいけないとか細かいことは多々あると思いますがデータ量が多いなら幾分早いんじゃないでしょうか。

回答No.1

Tacosan

多分, 本質的にソートするのが最速だと思います. ソートすれば, 「重複した文字列」は必ず隣合いますからね.
可能なら直接 Data_Array を使ってソートすればいいですし, ダメでも「Data_Array への添字」の配列をソートするように書けばいい.