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

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

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

Re[4]: 配列の要素を検索する方法


(過去ログ 53 を表示中)

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

■29471 / inTopicNo.1)  配列の要素を検索する方法
  
□投稿者/ ナツ (7回)-(2008/12/10(Wed) 11:02:15)

分類:[C/C++] 

お願いします。
VC++2003です。

char型の配列があります。
この配列には値が入っていて、その中から検索をかけ、位置(要素)を表示したいと思っています。
順番が大事なのでソートはかけたくありません。
また、要素数は10万を超えるので時間短縮の為ループは避けたいと思っています。
よい方法がありましたら教えてください。

イメージ)
char a[] = {'m','o','u','n','t','a','i','n'};

〜'n'はありますか?〜の処理

while(結果でループ)
{
cout << "nの位置は" << 結果 << endl;
}
実行結果:
nの位置は3
nの位置は7
引用返信 編集キー/
■29473 / inTopicNo.2)  Re[1]: 配列の要素を検索する方法
□投稿者/ .SHO (350回)-(2008/12/10(Wed) 11:11:16)
2008/12/10(Wed) 11:11:59 編集(投稿者)

No29471 (ナツ さん) に返信

> char a[] = {'m','o','u','n','t','a','i','n'};

a とは別に index 配列を持つのはどうですか?
引用返信 編集キー/
■29474 / inTopicNo.3)  Re[2]: 配列の要素を検索する方法
□投稿者/ ナツ (8回)-(2008/12/10(Wed) 11:16:09)
No29473 (.SHO さん) に返信

お返事有難うございます。
またお世話になります。

> > a とは別に index 配列を持つのはどうですか?

例えばどのような形になるのでしょう?
mapのようなイメージでしょうか?

今いろいろ調べていて、iteratorとか使えないかなぁと思ってみたりしてるのですが、VectorやDequeでの使い方しか見つかりません…
引用返信 編集キー/
■29475 / inTopicNo.4)  Re[1]: 配列の要素を検索する方法
□投稿者/ επιστημη (1442回)-(2008/12/10(Wed) 11:18:19)
επιστημη さんの Web サイト
> また、要素数は10万を超えるので時間短縮の為ループは避けたいと思っています。

10万回のループっていまどきそんなに遅くないんちゃう?
実測したほがよろしいかと。

さもなくば文字と位置のペアを辞書に投げ込むかなー

#include <iostream>
#include <algorithm>
#include <iterator>
#include <map>
using namespace std;

int main() {
  const int N = 8;
  char a[N] = {'m','o','u','n','t','a','i','n'};

  // アタマから舐めて探す
  for ( char* p = a; (p = std::find(p, a+N, 'n')) != a+N; ++p ) {
    cout << "nの位置は" << std::distance(a,p) << endl;
  }

  // 文字と位置のペアを辞書に投げ込む
  typedef multimap<char,int> map_type;
  map_type m;
  for ( int i = 0; i < N; ++i ) {
    m.insert(make_pair(a[i],i));
  }
  for ( pair<map_type::iterator,map_type::iterator> range = m.equal_range('n');
        range.first != range.second;
        ++range.first ) {
    cout << "nの位置は" << range.first->second << endl;
  }
}

引用返信 編集キー/
■29476 / inTopicNo.5)  Re[3]: 配列の要素を検索する方法
□投稿者/ .SHO (351回)-(2008/12/10(Wed) 11:22:06)
No29474 (ナツ さん) に返信

> 例えばどのような形になるのでしょう?

επιστημηさんが書いてくれました^^;

> 10万回のループっていまどきそんなに遅くないんちゃう?
> 実測したほがよろしいかと。

確かに。

引用返信 編集キー/
■29479 / inTopicNo.6)  Re[2]: 配列の要素を検索する方法
□投稿者/ ナツ (9回)-(2008/12/10(Wed) 11:26:35)
No29475 (επιστημη さん) に返信

お返事有難うございます。
先日は有難うございました。またよろしくお願いします。

> > 10万回のループっていまどきそんなに遅くないんちゃう?
> 実測したほがよろしいかと。

そうなんです、遅い訳じゃないんです。
ただ、時間短縮できる部分は極力したくて。
これが解決すれば、2秒かかっている処理がさらに短くなってくれるかなと。
実際に方法がないのであればループでもそんなに問題はないと思っています。

まぁ、知識欲というか、「できると思うんだけどなぁ」という部分がどうしても抜けなくて…
引用返信 編集キー/
■29480 / inTopicNo.7)  Re[1]: 配列の要素を検索する方法
□投稿者/ 倉田 有大 (386回)-(2008/12/10(Wed) 11:27:01)
No29471 (ナツ さん) に返信
> お願いします。
> VC++2003です。
>
> char型の配列があります。
> この配列には値が入っていて、その中から検索をかけ、位置(要素)を表示したいと思っています。
> 順番が大事なのでソートはかけたくありません。
> また、要素数は10万を超えるので時間短縮の為ループは避けたいと思っています。
> よい方法がありましたら教えてください。
>
> イメージ)
> char a[] = {'m','o','u','n','t','a','i','n'};
>
> 〜'n'はありますか?〜の処理
>
> while(結果でループ)
> {
> cout << "nの位置は" << 結果 << endl;
> }
> 実行結果:
> nの位置は3
> nの位置は7

確認すると、アルファベットの入ったcharの一次元配列が10万以上あるということですね?

ハッシュ使うのはどうでしょうか?
hash["n"]とすると、nの位置のintの配列を帰ってくるようにするとか。

って、もうεπιστημη さんがよさげなサンプル出してくれていますね。
引用返信 編集キー/
■29482 / inTopicNo.8)  Re[3]: 配列の要素を検索する方法
□投稿者/ .SHO (352回)-(2008/12/10(Wed) 11:31:07)
No29479 (ナツ さん) に返信

> まぁ、知識欲というか…

そういう意味では、倉田さんのハッシュを勉強するのも面白いですね。
実際、自分も1回質問を読んですぐ、ハッシュじゃんと思いました。
引用返信 編集キー/
■29483 / inTopicNo.9)  Re[3]: 配列の要素を検索する方法
□投稿者/ 倉田 有大 (387回)-(2008/12/10(Wed) 11:32:17)
> そうなんです、遅い訳じゃないんです。
> ただ、時間短縮できる部分は極力したくて。
> これが解決すれば、2秒かかっている処理がさらに短くなってくれるかなと。
> 実際に方法がないのであればループでもそんなに問題はないと思っています。
>
> まぁ、知識欲というか、「できると思うんだけどなぁ」という部分がどうしても抜けなくて…

最初にindex作ってしまえば出来ますよ。
後はどういう風に実装するかです。

STLはC#に移行してから完璧に忘れた。επιστημη さんのソースも読めない/( ^o^ )\ なんてこったい

引用返信 編集キー/
■29490 / inTopicNo.10)  Re[2]: 配列の要素を検索する方法
□投稿者/ επιστημη (1444回)-(2008/12/10(Wed) 11:47:36)
επιστημη さんの Web サイト
> ハッシュ使うのはどうでしょうか?

ほい。

// VC++9 でやったなり。
#include <iostream>
#include <unordered_map> // ココと
using namespace std;

int main() {
  const int N = 8;
  char a[N] = {'m','o','u','n','t','a','i','n'};

  typedef tr1::unordered_multimap<char,int> map_type; // ココいぢっただけ。
  map_type m;
  for ( int i = 0; i < N; ++i ) {
    m.insert(make_pair(a[i],i));
  }
  for ( pair<map_type::iterator,map_type::iterator> range = m.equal_range('n');
        range.first != range.second;
        ++range.first ) {
    cout << "nの位置は" << range.first->second << endl;
  }

}

引用返信 編集キー/
■29505 / inTopicNo.11)  Re[3]: 配列の要素を検索する方法
□投稿者/ あんどちん (31回)-(2008/12/10(Wed) 12:32:36)
キーはcharなんだし素直に配列で参照した方が早いと思うんですけどそういうもんでもないんでしょうか?
charをハッシュにした方が早くなるってのがよくわからなくて^^;

#include <iostream>
#include <vector>
using namespace std;

int main() {
const int N = 8;
char a[N] = {'m','o','u','n','t','a','i','n'};

// 文字に対応する配列要素に位置を入れる
typedef vector<int> position;
position m[256];
for ( int i = 0; i < N; ++i ) {
m[static_cast<unsigned char>(a[i])].push_back(i);
}

for(position::iterator it = m[static_cast<unsigned char>('n')].begin();
it != m[static_cast<unsigned char>('n')].end();
++it) {
cout << "nの位置は" << *it << endl;
}
}

要素位置をpush_backするときにメモリを再確保されるのが気に入らなければreserveしておけば防ぐことも可能です。
入れる文字がアルファベットと数字だけなら配列は256も要らないでしょうが10万文字分の位置を保存することを考えたら誤差の範囲かな?オフセットの計算減らせるし

引用返信 編集キー/
■29506 / inTopicNo.12)  Re[4]: 配列の要素を検索する方法
□投稿者/ .SHO (359回)-(2008/12/10(Wed) 12:37:20)
No29505 (あんどちん さん) に返信

> キーはcharなんだし素直に配列で参照した方が早いと思うんですけどそういうもんでもないんでしょうか?

スレ主さんは、早さではなく知識欲だと言ってます。

> charをハッシュにした方が早くなるってのがよくわからなくて^^;

ハッシュ関数が不要になるだけで、端から全部検索するよりは
はるかに早くなります。

引用返信 編集キー/
■29507 / inTopicNo.13)  Re[4]: 配列の要素を検索する方法
□投稿者/ επιστημη (1447回)-(2008/12/10(Wed) 12:38:47)
επιστημη さんの Web サイト
> キーはcharなんだし素直に配列で参照した方が早いと思うんですけどそういうもんでもないんでしょうか?

あー確かに。wchar_tとかintとかならともかくも、charだから高々256だもんねー。

> charをハッシュにした方が早くなるってのがよくわからなくて^^;

早くなりそにないっすね ^^;;;;;;;

引用返信 編集キー/
■29508 / inTopicNo.14)  Re[3]: 配列の要素を検索する方法
□投稿者/ 初心者 (201回)-(2008/12/10(Wed) 12:40:35)
素朴な疑問なのですが
わざわざindesの配列を作ってまでlist(of T)ではなく配列を使用する理由ってあるのですか?
index of を繰り返せば予想される動きも実現できそうな気がするのですが
引用返信 編集キー/
■29511 / inTopicNo.15)  Re[4]: 配列の要素を検索する方法
□投稿者/ επιστημη (1448回)-(2008/12/10(Wed) 12:49:11)
επιστημη さんの Web サイト
2008/12/11(Thu) 11:27:49 編集(投稿者)

> わざわざindesの配列を作ってまでlist(of T)ではなく配列を使用する理由ってあるのですか?

native屋さんは時間と空間に五月蝿いから ^^; (←半分本当)

> index of を繰り返せば予想される動きも実現できそうな気がするのですが

「順次検索より速い手段はないか?」って相談なんだもんしゃーないやん♪

list(of T) て何? vector<T> のこと? list<T> のこと?
vector<T>のことだとすれば、実質配列と同じなので「理由なんてない」が答かも。

引用返信 編集キー/


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

このトピックに書きこむ

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

管理者用

- Child Tree -