hashを用いた高速化を実現する

Question

前提・実現したいこと

Wikipediaの題名とカテゴリを用いてカテゴリから題名を出力するプログラムを作成したいです、
現在hashを使わずにソースを作成したのですが実行が遅いのでhashを使って高速にしたいです。

発生している問題・

hashで1つの題名に１つのカテゴリなら作成できると思うのですが
複数のカテゴリを付与する場合どのようにすればいいのでしょうか？

該当のソースコード・現状

ソースコード
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <string.h>

using namespace std;

// 機能：引数として渡されたカテゴリが割り当てられているページのタイトルを検索する
// 引数：カテゴリ名
// 戻値：検索結果　タイトル１,タイトル2,...のような , で区切られた文字列

string search_page(string query)
{
    ifstream f_data("data.txt"); 

    string result = "";
    string line;

    // data.txtから１行ずつ読み込み
    while(f_data >> line)
    {
        // 記事タイトルとカテゴリ（category1,category2,...）のデータに分割
        int index = line.find(","); 
        string title = line.substr(0,index); 
        string c_str = line.substr(index+1); 
	
	// カテゴリ列のデータからカテゴリを１つずつ取り出し（split）
	int n;
	for(int i=0; i <= c_str.length(); i=n+1 )
	{
	    n = c_str.find_first_of(",", i);
	    if( n == string::npos ) 
	    {
		n = c_str.length();
	    }

	    string cw = c_str.substr(i, n-i );

	    if(query == cw)
	    {
	        result += title+",";
	    }
	}
   }
   f_data.close();

   return result;
}

int main(int argc, char *argv[])
{     
    ifstream fc_data("category.list"); 

    string result;
    string line;

    // data.txtから１行ずつ読み込み
    while(fc_data >> line)
    {
        cout << line << " -> ";
	
        string result = search_page(line);

	if(result != "")
	{
	   cout << result << endl;
        }
	
	cout << endl;
    }
    fc_data.close();
   
   return 0;
}

###改善版/ぐちゃぐちゃです

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <string.h>
#include<cmath>
#define HashSize 1000;
using namespace std;

///////////ここでカテゴリの複数化を図りたい
struct cell
{
   string name;   // 記事
   string categori;    // カテゴリ

   struct cell *next;	// 次のデータへのポインタ
};
// ハッシュ表 
struct hashhash
{
  int    size;           // ハッシュ表の大きさ 
  struct cell **table; 
};
// ハッシュ関数（keyのハッシュ値を返す）
// 文字列の1文字ごとの文字コードを加算するハッシュ関数
int hash1(string key, int size) 
{
  unsigned int v=0;

  for(int i=0;i<key.length();i++) 
    {
      v+=key[i]*pow(2,i);
    }

  return v%size;
}
/*--- ハッシュ表の初期化 ---*/
int initialize(struct hashhash *h, int size)
{
  h->table=(cell**)new struct cell[size];
  h->size=size;

  for(int i=0;i<size;i++)
    {
      h->table[i]=NULL;
    }
  return 1;
}
// データの追加 
int add(struct hashhash *h, string name, string categori)
{
  //  追加するデータのハッシュ値 
  int hash_value=hash1(name, h->size);	

  // 接続するデータを格納する要素を生成
  struct cell *temp;
  temp=new struct cell;
  temp->name=name;
  temp->categori=categori;

  // 要素をハッシュに追加（上書きで追加）
  temp->next=h->table[hash_value]; 
  h->table[hash_value]=temp;
  return 0; 
}

struct cell *search_tel(struct hashhash *head, string name)
{
  int hash_value=hash1(name,head->size);
  struct cell *buf=head->table[hash_value];
  while(buf!=NULL)
    {
      if(buf->name == name)
	{
	  return buf;
	}
      buf=buf->next;
    }
  return NULL;
}


/*string search_page(string query)
{
    ifstream f_data("data.txt"); 

    string result = "";
    string line;

    // data.txtから１行ずつ読み込み
    while(f_data >> line)
    {
        // 記事タイトルとカテゴリ（category1,category2,...）のデータに分割
        int index = line.find(","); 
        string title = line.substr(0,index); 
        string c_str = line.substr(index+1); 
	
	// カテゴリ列のデータからカテゴリを１つずつ取り出し（split）
	int n;
	for(int i=0; i <= c_str.length(); i=n+1 )
	{
	    n = c_str.find_first_of(",", i);
	    if( n == string::npos ) 
	    {
		n = c_str.length();
	    }

	    string cw = c_str.substr(i, n-i );

	    if(query == cw)
	    {
	        result += title+",";
	    }
	}
   }
   f_data.close();

   return result;
   }*/

int main(int argc, char *argv[])
{     
    ifstream fc_data("category.list"); 

    string result;
    string line;

    // data.txtから１行ずつ読み込み
    while(fc_data >> line)
    {
        cout << line << " -> ";
	
        string result = search_page(line);

	if(result != "")
	{
	   cout << result << endl;
        }
	
	cout << endl;
    }
    fc_data.close();
   
   return 0;
}

試したこと

未だ初心者でhashを使うとよくわからなくなってしまいます

Answer 1

カテゴリを複数にするなら、もうテキストファイルをやめてsqlite等でデータベース化してしまった方が良いかもしれません。

• 記事テーブル（記事ID,記事タイトル）
• カテゴリテーブル（記事ID、カテゴリ）

のように分けてテーブルを作成しておけば、複数のカテゴリも対応出来ますし、
タイトル、カテゴリのインデックスを作成しておけば、高速に検索出来ます。

Comments

[Amateur0845]

確かにデータベース化することでメリットが多いですね。
もう少しそちらの方向性で試行錯誤してみます。
ありがとうございます。

Answer 2

正直hash化してもそんなに速くならないんじゃないですかね。どちらかというとメモリー確保を減らすほうがいいと思います。

        string title = line.substr(0,index); 
        string c_str = line.substr(index+1); 

string cw = c_str.substr(i, n-i );

これらは全部新規にメモリーを確保します。std::string_viewを使うようにするとメモリー確保がいらなくなります。

    string raw_line;

    // data.txtから１行ずつ読み込み
    while(f_data >> raw_line)
    {
        std::string_view line = raw_line;
        // 記事タイトルとカテゴリ（category1,category2,...）のデータに分割
        int index = line.find(","); 
        auto title = line.substr(0,index); 
        auto c_str = line.substr(index+1); 

        // カテゴリ列のデータからカテゴリを１つずつ取り出し（split）
        int n;
        for(int i=0; i <= c_str.length(); i=n+1 )
        {
            n = c_str.find_first_of(",", i);
            if( n == string::npos ) 
            {
            n = c_str.length();
            }
    
            auto cw = c_str.substr(i, n-i );

            if(query == cw)
            {
                result += title+",";
            }
        }
   }

あとはハッシュ化はstd::hashを使えばいいと思います。

Answer 3

[ご参考] 要素の重複を許すハッシュ表(unordered_multimap)を使った例

#include <unordered_map>
#include <string>
#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>

int main() {
  using dict_type = std::unordered_multimap<std::string,std::string>;
  using key_value = dict_type::value_type;
  dict_type dict; // 辞書
  // (カテゴリ,題名) を辞書に登録
  dict.insert(key_value("赤","りんご"));
  dict.insert(key_value("果物", "りんご"));
  dict.insert(key_value("赤", "さくらんぼ"));
  dict.insert(key_value("果物", "さくらんぼ"));
  dict.insert(key_value("赤", "信号機"));
  dict.insert(key_value("黄", "信号機"));
  dict.insert(key_value("緑", "信号機"));
  std::cout << "辞書 : ";
  for ( auto item : dict ) {
    std::cout << '(' << item.first << ',' << item.second << ") ";
  }
  std::cout << std::endl;

  std::set<std::string> result1;
  auto matches = dict.equal_range("赤");
  while ( matches.first != matches.second ) result1.insert( matches.first++->second);

  std::set<std::string> result2;
  matches = dict.equal_range("果物");
  while (matches.first != matches.second) result2.insert(matches.first++->second);

  std::cout << "赤 または 果物 : ";
  std::set_union(result1.begin(), result1.end(), result2.begin(), result2.end(),
                 std::ostream_iterator<std::string>(std::cout, " "));
  std::cout << std::endl;

  std::cout << "赤 かつ　 果物 : ";
  std::set_intersection(result1.begin(), result1.end(), result2.begin(), result2.end(),
      std::ostream_iterator<std::string>(std::cout, " "));
  std::cout << std::endl;
}

実行結果

辞書 : (赤,りんご) (赤,さくらんぼ) (赤,信号機) (黄,信号機) (果物,りんご) (果物,さくらんぼ) (緑,信号機)
赤 または 果物 : さくらんぼ りんご 信号機
赤 かつ　 果物 : さくらんぼ りんご