[C言語] 06 ハッシュ関数 FNVの外部関数化

FNVをPythonでも使えるようにするため、まずは外部関数化しました。

64バイトハッシュ値のフォーマット指定子は%luです。

#include <stdio.h>
#include <stdint.h>

uint32_t fnv_1_hash_32(char *s)
{
    unsigned int hash=2166136261U;

    while (*s) {
        hash*=16777619U;
        hash^=*(s++);
    }
    return hash;
}

uint64_t fnv_1_hash_64(char *s)
{
    long unsigned int hash=14695981039346656037U;

    while (*s) {
        hash*=1099511628211LLU;
        hash^=*(s++);
    }
    return hash;
}
#include <stdio.h>
#include <stdint.h>
#include "fnv_1.c"

int main(void)
{
    char *s = "シャフリヤール";

    printf("%u\n",fnv_1_hash_32(s));
    printf("%lu\n",fnv_1_hash_64(s));
}
--------------------------------------------------

出力
--------------------------------------------------
3687658616
7203286604922561048

[C言語] 05 簡易なハッシュ関数 FNV

[Python] 283の記事あたりまで取り組んでいたデータベース検索の高速化ですが、文字列比較ではなくハッシュ値比較でも試してみました。

ハッシュ関数によるハッシュ値算出の時間が余計に掛かっているものの、これまでの最速記録80秒に対して84秒となかなかの健闘でした。正確性も問題ありません。

その他では機械語変換手前のアセンブリ言語コードをチェックしたりもしましたが初級者にいじれるはずもなく、また最近の文字列比較機能(strcmpなど)は優秀のようで小手先の自作関数では歯が立ちませんでした。

ハッシュ関数についてはスキルアップのための余興みたいなもので、ここらで高速化検討は打ち切りにするつもりです。

#include <stdio.h>
#include <stdint.h>

uint32_t fnv_1_hash_32(char *s)
{
    unsigned int hash=2166136261UL;

    while (*s) {
        hash*=16777619UL;
        hash^=*(s++);
    }
    return hash;
}
<該当箇所のみ>
#include "fnv_1.c"

if (i != 0){
    if (fnv_1_hash_32(horse_name) - fnv_1_hash_32(horse_name_in) == 0){
        fp3 = fopen(fname3, "a");
        fprintf(fp3,"%s,%9s\n",horse_name_in,horseID);
        fclose(fp3);
        b ++;
        break;
    }
}

[C言語] 04 pre K&Rコードのコンパイル&実行 K&R初版 5章2

K&R第2版から遡ること10年、K&R初版が出版された1978年当時のC言語コードいわゆるpre K&Rコードをコンパイル&実行してみました。

手順
1. K&R初版訳本P87のgetch関数ファイルをgetch.cとする。
2. K&R初版訳本P101のgetint関数ファイルをgetint.cとする。
3. main.cを作成する(過去記事[C言語]03参照)。
4. main.cをコンパイルし、a.outを実行する。

[C言語] 03 C89コードのコンパイル&実行 K&R第2版 5章2

K&R第2版が出版された1988年当時のC言語コードをコンパイル&実行してみました。YouTubeの演習解説動画が非常に役に立ちました。

手順
1. K&R第2版訳本P96のgetch関数ファイルをgetch.cとする。
2. K&R第2版訳本P118のgetint関数ファイルをgetint.cとする。
3. 以下のコードをmain.cとする。
4. main.cをコンパイルし、a.outを実行する。

#include <stdio.h>
#include "getch.c"
#include "getint.c"

main()
{
    int ret,c;

    if ((ret= getint(&c))==0)
        printf("not a valid number\n");
    else if (ret > 0)
        printf("valid number\n");
    else
        printf("End of file\n");

    printf("return value: %d\n",ret);

    return 0;
}

[C言語] 02 数値のコピー

変数への数値のコピーは等式による代入で可能です。

sscanfによる読み込みにおいて3番目の引数は格納先のポインタであり、数値の場合は変数名に&を付け(&horseID)、文字列の場合は変数名(horse_name)そのままとなります。

正確には&horse_name[0]ですが、horse_nameは同じ内容とのことです。また&horse_nameとしてもエラーにはなりません。

<過去コードの該当箇所>

int horseID;
int id;
char horse_name[50];

while(fgets(buf,100, fp ) != NULL ) {
    sscanf(buf, "%d, %s",&horseID,horse_name) ; // &horse_nameでも可

    if (i != 0){
        if (strcmp(horse_name,horse_name_in)==0){
            id = horseID; // 数値のコピー
            printf("コピー完了 %d %s\n",id,horse_name);
            break;
        }
    }
    i ++ ;
}

[C言語] 01 文字列のコピー strcpy

文字列のコピーにはstrcpyを使います。末尾の\0も含まれるので文字数は1つ以上多くしないとエラーになります。

当初はこれを知らなくて等式でコピーしようとしていました。コンピュータの仕組みを分かっていないと手詰まりになりますね。

<過去コードの該当箇所>

char horseID[10]; // horseIDは9文字だが末尾の\0も入れて10文字とする
char id[10]

if (i != 0){
    if (strcmp(horse_name,horse_name_in)==0){
        strcpy(id,horseID);
        printf("コピー完了 %s\n",id);
		}
}

[Python] 286 スクレイピング速度検証 curlコマンド

色々検証してきましたが、htmlのダウンロードについてはRequestsやseleniumを知らなくてもcurlコマンド1つでできるようです。あとはBeautifulSoupで解析すればOKです。

処理時間は私の検証条件ではhtml解析を経てcsv作成まで1件あたり0.23sでした。Requestsやlibcurlが0.35sなのでcurlコマンドが最速になります。

コードも簡潔になりますし、htmlをダウンロードする場合は馴染みのあるRequestsではなくcurlコマンドを採用します。

ただし、これまでと同様ループする場合はtime.sleep等で速度を制御しないとスクレイピング先に迷惑がかかるので要注意です。

ダウンロードせずにhtml解析&テキスト取り出しであれば、これまで通りRequestsになります。

<該当箇所のみ>
proc = subprocess.run("curl 'スクレイピング先のurl' > [出力先ファイル] ; echo '出力完了'", shell=True, stdout= subprocess.PIPE, stderr = subprocess.PIPE)
print(proc.stdout.decode('UTF-8'))

with open(出力先ファイル,encoding='EUC-JP',errors='ignore') as f:
    contents= f.read()
soup = BeautifulSoup(contents, "html.parser")

[Python] 285 スクレイピング速度検証 Requests

前回の続きです。

Requests+BeautifulSoupでスクレイピング の速度を測ったところlibcurlと同等でした。

通常はRequests、クリックやページ遷移などブラウザ操作する場合はselenium、好事家はlibcurlというのが結論です。

<該当箇所のみ>
response = requests.get(url)

soup = BeautifulSoup(response.text.encode('utf-8'), "html.parser")

[Python] 284 C言語併用によるスクレイピング高速化 libcurl

seleniumの動きがもっさりしているため、C/C++のlibcurlというライブラリで高速化を試みました。スクレイピング先のhtmlをまるごとダウンロードして解析し、テキストを抽出してcsvファイルにまとめるという流れです。

その結果、こちらが引くくらい速くなったので全編C言語で書く必要はなくなり、html解析はPythonライブラリのBeautifulSoupで実施しました。スクレイピング先に負荷をかけないようtime.sleepでループの速度を遅くしています。

C言語の方は参考サイトのコードに少しだけ手を入れて完成させました。

今思えばここまでやらなくてもRequests + BeautifulSoupであればPythonだけで高速化できていたかもしれません。時間があれば検証します。

21/07/17追記:C言語にこだわらなければ、以下のコマンドをsubprocessモジュールで走らせてhtmlをダウンロードするのが最も簡単だと思います。
curl “スクレイピング先のurl” > 出力先

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <curl/curl.h>

#define EXIT_SUCCESS 0

FILE *fp; // 入力ファイル
FILE *fp2; // 出力ファイル
char fname[] = "horse_url.txt";
char fname2[] = "curl.html";
char buffer[100];
char horse_url[100];

struct Buffer {
    char *data;
    int data_size;
};

size_t buffer_writer(char *ptr, size_t size, size_t nmemb, void *stream) {
    struct Buffer *buf = (struct Buffer *)stream;
    int block = size * nmemb;
    if (!buf) {
        return block;
    }

    if (!buf->data) {
        buf->data = (char *)malloc(block);
    }
    else {
        buf->data = (char *)realloc(buf->data, buf->data_size + block);
    }

    if (buf->data) {
        memcpy(buf->data + buf->data_size, ptr, block);
        buf->data_size += block;
    }

    return block;
}

int main(void) {

    CURL *curl;
    struct Buffer *buf;

    buf = (struct Buffer *)malloc(sizeof(struct Buffer));
    buf->data = NULL;
    buf->data_size = 0;

    fp = fopen(fname, "r");
	while(fgets(buffer,100, fp) != NULL ) {
        sscanf(buffer,"%s",horse_url);
    }
    fclose(fp);

    curl = curl_easy_init();
    curl_easy_setopt(curl, CURLOPT_URL, horse_url);
    curl_easy_setopt(curl, CURLOPT_SSL_VERIFYPEER, 0);
    curl_easy_setopt(curl, CURLOPT_WRITEDATA, buf);
    curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, buffer_writer);

    curl_easy_perform(curl);
    curl_easy_cleanup(curl);

    fp2 = fopen(fname2, "w");
    fprintf(fp2, "%s", buf->data);
    fclose(fp2);

    free(buf->data);
    free(buf);

    return EXIT_SUCCESS;
}
<C言語コンパイル&実行とBeautifulSoup処理の箇所のみ>

proc = subprocess.run("gcc [ソースコード] -I/usr/local/opt/curl/include -lcurl ; ./a.out ; ECHO 'C言語実行完了'", shell=True, stdout= subprocess.PIPE, stderr = subprocess.PIPE)
print(proc.stdout.decode('UTF-8'))

with open(html,encoding='EUC-JP',errors='ignore') as f:
    contents= f.read()
soup = BeautifulSoup(contents, "html.parser")

参考サイト

[Python] 283 C言語実行ファイルの併用 その3 若干の時間短縮

前回の続きです。

どう考えても検索ヒットした馬名のデータが2行になるのは無駄なので、1行になるよう修正しました。

この修正により処理時間が87秒から80秒に短縮されました。

<修正箇所>

while(fgets(buf,2000, fp ) != NULL ) {
    sscanf(buf, " %9s, %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %s",horseID,horse_name,horse_name0,status,gender,hair,birthday,trainer,owner,info,breeder,area,price,prize_money,result,wining_race,relatives ) ;

    if (i != 0){
        if (strcmp(horse_name,horse_name_in)==0){
	        fp3 = fopen(fname3, "a");
	        fprintf(fp3, "%s,%9s\n", horse_name,horseID);
	        fclose(fp3);
	        b ++;
	        break;
        }
    }
    i ++ ;
}
if (b == 0){
	fp3 = fopen(fname3, "a");
	fprintf(fp3, "%s,100000000\n", horse_name_in);
	fclose(fp3);
}