kisara11235
@kisara11235

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

特定の文字を呼び出す辞書が作りたい

Q&A

Closed

解決したいこと

ket_libra_junbikiの方では5→1のようにある数字に特定の番号を振り分ける辞書になっており、ket_libra_gyakubikiでは逆に1→5のように索引のようになっている。
これらの辞書を完成させたい。

発生している問題・エラー

プログラム上のket_libra_gyakubikiについて、配列のサイズが大きすぎてコアダンプしてしまう。原因はサイズを変数として指定しているのだが、Nが大きすぎるとコアダンプすることです。
サイズをしては現状size=pow(2,N)としており、N=20ぐらいで当たり前だがコアダンプしてしまう。
この辞書を作る上で特定の番号を振り分けていない数字もket_libra_gyakubikiに入ってしまうのでそこを解決するアイデアがほしい。

該当するソースコード

#include <stdio.h>
#include <math.h>

#define N 3      // サイト数
#define L N   // half-filling
#define NUM_KET N *(N - 1) / 2

// ケットベクトルを2進法で保存する配列
int ket[NUM_KET][N] = {0};    // half-filledのケットが入る [index][binary]
int ket_libra_junbiki[NUM_KET] = {0};    // 辞書 [index]⇒decimal 順引き
int ket_index = 0;

// 二進数から10進数への変換関数
int binaryToDecimal(int *binary, int length) {
    int decimal = 0;
    for (int i = 0; i < length; i++) {
        decimal = (decimal << 1) | binary[i];
    }
    return decimal;
}

void decimalToBinary(int decimal, int *binary, int length) {
    for (int i = length - 1; i >= 0; i--) {
        binary[i] = decimal & 1;
        decimal >>= 1;
    }
}

int countLeftOnes(int *binary, int length, int index, int currentIndex) {     
    int sign = 1;   
    decimalToBinary(ket_libra_junbiki[index], binary, N);
    int count = 0;
    for (int i = currentIndex - 1; i >= 0; i--) {
        count += binary[i];
    }
    sign *= pow(-1, count);
    return sign;
}

// ケットベクトルを2進法でket配列に保存する関数
void fillKet(int ones, int *binary, int binary_length, int binary_index, int size, int ket_libra_gyakubiki[size]) {
    if (ket_index >= NUM_KET) {
        return;
    }

    if (binary_index >= binary_length) {
        return;
    }

    if (ones > 0) {
        // 1を配置してみる
        binary[binary_index] = 1;
        fillKet(ones - 1, binary, binary_length, binary_index + 1, size, ket_libra_gyakubiki);
        if (ones - 1 == 0) {
            // onesの分だけ1が埋まったのでketに追加保存
            for (int i = 0; i < binary_length; i++) {
                ket[ket_index][i] = binary[i];
            }
            ket_libra_junbiki[NUM_KET - ket_index - 1] = binaryToDecimal(binary, binary_length) ;
            ket_libra_gyakubiki[ket_libra_junbiki[NUM_KET - ket_index - 1]] = NUM_KET - ket_index ;
            ket_index++;
        }
    }

    // 0を配置してみる (onesが0でも残りの桁を0で埋める必要がある)
    binary[binary_index] = 0;
    fillKet(ones, binary, binary_length, binary_index + 1, size, ket_libra_gyakubiki);
    /*printf("ket_libra_junbiki:\n");
    for (int i = 0; i < NUM_KET; i++) {
        printf("%d\n", ket_libra_junbiki[i]);
    }

    printf("ket_libra_gyakubiki:\n");
    for (int i = 0; i < (1 << N); i++) {
        printf("%d %d\n", i,ket_libra_gyakubiki[i]);
    }*/
}

void make_hamiltonian(double hamiltonian[NUM_KET][NUM_KET], int sign, int index, int decimal, int size, int ket_libra_gyakubiki[size], double t, double U) {
    hamiltonian[ket_libra_gyakubiki[decimal] - 1][index] += -t * sign;
}

void convert(int *binary, double hamiltonian[NUM_KET][NUM_KET], int length, int index, int size, int ket_libra_gyakubiki[size], double t, double U) {
    for (int i = 1; i < N; i++) {
        int binary_copy[N];
        for (int j = 0; j < N; j++) {
            binary_copy[j] = binary[j];
        }

        decimalToBinary(ket_libra_junbiki[index], binary_copy, N);
        int sign = countLeftOnes(binary_copy, N, index, i);
        binary_copy[i] = binary_copy[i] ^ 1;
        binary_copy[i - 1] = binary_copy[i - 1] ^ 1;
        int decimal = binaryToDecimal(binary_copy, N);

        if (ket_libra_gyakubiki[decimal] != 0) {
            make_hamiltonian(hamiltonian, sign, index, decimal, size, ket_libra_gyakubiki, t, U);
            // printf("%d %d %d %d\n", decimal, index, sign, ket_libra_gyakubiki[decimal]);
            // printf("%d %d %d %d\n", ket_libra_junbiki[index], index, decimal, ket_libra_gyakubiki[decimal]);
        }
    }
}

int main() {
    int binary[N];  // 二進法が入る
    int M;
    int size = pow(2, N);
    int ones; // 1の個数

    int ket_libra_gyakubiki[size];   // 辞書 [decimal]⇒index 逆引き
    double hamiltonian[NUM_KET][NUM_KET] = {0.0};
    double t = 1.0, U = 3.0;
    
    // ket_libra_gyakubiki配列を0で初期化
    for (int i = 0; i < size; i++) {
        ket_libra_gyakubiki[i] = 0;
    }

    if (N % 2 == 0) {
        M = N / 2;
    } else {
        M = N / 2 + 1;
    }

    // ケットベクトルの生成と表示
    fillKet(M, binary, N, 0, size, ket_libra_gyakubiki);

    for (int index = 0; index < NUM_KET; index++) {
        convert(binary, hamiltonian, N, index, size, ket_libra_gyakubiki, t, U);
    }
    
    for (int i = 0; i < NUM_KET; i++) {
        for (int j = 0; j < NUM_KET; j++) {
            printf("%d, %d, %lf ", i, j, hamiltonian[i][j]);
        }
        printf("\n");
    }

    return 0;
}

自分で試したこと

ここに問題・エラーに対して試したことを記載してください。

0

4Answer

ket_libra_gyakubiki[]は、順引き数値を添字(index)にする事で高速な探索をする(多分一番早い)ためにありますが、その代償としてメモリーを多く消費します。今回の場合だと メモリの節約を行うには、ket_libra_junbiki[]の中を探索するのが一番かな? と考えます。多くのプログラムはこの探索処理に工夫がされていて速度を高速化してます。(プログラムは遅い遅い総当たり探索で残念ですが、いろんな探索方法があるので調べて考えたら良いと思います。)

変更内容は  ket_libra_gyakubiki[] と 取っ払って ket_libra_gyakubiki()に置き換えてます。

#include <stdio.h>
#include <math.h>

#define N 3      // サイト数
#define L N   // half-filling
#define NUM_KET N *(N - 1) / 2

// ケットベクトルを2進法で保存する配列
int ket[NUM_KET][N] = {0};    // half-filledのケットが入る [index][binary]
int ket_libra_junbiki[NUM_KET] = {0};    // 辞書 [index]⇒decimal 順引き
int ket_index = 0;

// 二進数から10進数への変換関数
int binaryToDecimal(int *binary, int length) {
    int decimal = 0;
    for (int i = 0; i < length; i++) {
        decimal = (decimal << 1) | binary[i];
    }
    return decimal;
}

void decimalToBinary(int decimal, int *binary, int length) {
    for (int i = length - 1; i >= 0; i--) {
        binary[i] = decimal & 1;
        decimal >>= 1;
    }
}

int countLeftOnes(int *binary, int length, int index, int currentIndex) {
    int sign = 1;
    decimalToBinary(ket_libra_junbiki[index], binary, N);
    int count = 0;
    for (int i = currentIndex - 1; i >= 0; i--) {
        count += binary[i];
    }
    sign *= pow(-1, count);
    return sign;
}


// ket_libra_gyakubiki[]の代用関数
int ket_libra_gyakubiki_func( int decimal ) {
    for( int i = 0; i < N; i++ )
    {
        if( ket_libra_junbiki[i] == decimal )
        {
          return i+1;
        }
    }
    return 0;
}

// ケットベクトルを2進法でket配列に保存する関数
void fillKet(int ones, int *binary, int binary_length, int binary_index) {
    if (ket_index >= NUM_KET) {
        return;
    }

    if (binary_index >= binary_length) {
        return;
    }

    if (ones > 0) {
        // 1を配置してみる
        binary[binary_index] = 1;
        fillKet(ones - 1, binary, binary_length, binary_index + 1);
        if (ones - 1 == 0) {
            // onesの分だけ1が埋まったのでketに追加保存
            for (int i = 0; i < binary_length; i++) {
                ket[ket_index][i] = binary[i];
            }
            ket_libra_junbiki[NUM_KET - ket_index - 1] = binaryToDecimal(binary, binary_length) ;
            ket_index++;
        }
    }

    // 0を配置してみる (onesが0でも残りの桁を0で埋める必要がある)
    binary[binary_index] = 0;
    fillKet(ones, binary, binary_length, binary_index + 1);
    /*printf("ket_libra_junbiki:\n");
    for (int i = 0; i < NUM_KET; i++) {
        printf("%d\n", ket_libra_junbiki[i]);
    }

    printf("ket_libra_gyakubiki:\n");
    for (int i = 0; i < NUM_KET; i++) {
        printf("%d %d\n", i,ket_libra_gyakubiki_func(i));
    }*/
}

void make_hamiltonian(double hamiltonian[NUM_KET][NUM_KET], int sign, int index, int decimal, double t, double U) {
    hamiltonian[ket_libra_gyakubiki_func(decimal) - 1][index] += -t * sign;
}

void convert(int *binary, double hamiltonian[NUM_KET][NUM_KET], int length, int index, double t, double U) {
    for (int i = 1; i < N; i++) {
        int binary_copy[N];
        for (int j = 0; j < N; j++) {
            binary_copy[j] = binary[j];
        }

        decimalToBinary(ket_libra_junbiki[index], binary_copy, N);
        int sign = countLeftOnes(binary_copy, N, index, i);
        binary_copy[i] = binary_copy[i] ^ 1;
        binary_copy[i - 1] = binary_copy[i - 1] ^ 1;
        int decimal = binaryToDecimal(binary_copy, N);

        if (ket_libra_gyakubiki_func(decimal) != 0) {
            make_hamiltonian(hamiltonian, sign, index, decimal, t, U);
            // printf("%d %d %d %d\n", decimal, index, sign, ket_libra_gyakubiki_func(decimal));
            // printf("%d %d %d %d\n", ket_libra_junbiki[index], index, decimal, ket_libra_gyakubiki_func(decimal));
        }
    }
}

int main() {
    int binary[N];  // 二進法が入る
    int M;
    int size = pow(2, N);
    int ones; // 1の個数

    double hamiltonian[NUM_KET][NUM_KET] = {0.0};
    double t = 1.0, U = 3.0;

    if (N % 2 == 0) {
        M = N / 2;
    } else {
        M = N / 2 + 1;
    }

    // ケットベクトルの生成と表示
    fillKet(M, binary, N, 0 );

    for (int index = 0; index < NUM_KET; index++) {
        convert(binary, hamiltonian, N, index, t, U);
    }

    for (int i = 0; i < NUM_KET; i++) {
        for (int j = 0; j < NUM_KET; j++) {
            printf("%d, %d, %lf ", i, j, hamiltonian[i][j]);
        }
        printf("\n");
    }

    return 0;
}

コアダンプの件ですが、最大サイト数がわからないのですが、スタック領域で大きなメモリ確保しているのが問題なのでヒープ領域に配列を移動すれば、改善すると思います。

double hamiltonian[NUM_KET][NUM_KET] = {0.0};
をグルーバル変数で定義するように変更すれば、改善するのではないでしょうか?

1Like

Comments

  1. @kisara11235

    Questioner

    ありがとうございます。

C言語という縛りがなければ、例えばC++のunordered_mapあたりを使うのが手軽です。
生のCで作るならば、Mapの類を実現する良くできたアルゴリズムを手書きするか、どこかからもらってくる必要があります。

0Like

segmentation faultする理由は、main関数のローカル変数として大きな領域を宣言しているためです。
この2つの変数をstatic変数にすることで、$2^{22}$でも動きました。
ただし、static変数にはpowの結果を使用することができないため、定数を使用します。

- #define N 2      // サイト数
+ #define N 22      // サイト数
- int ket_libra_gyakubiki[size];   // 辞書 [decimal]⇒index 逆引き
+ #define SIZE 4194304 //2^22   
+ static int ket_libra_gyakubiki[SIZE];   // 辞書 [decimal]⇒index 逆引き
- double hamiltonian[NUM_KET][NUM_KET] = {0.0};
+ static double hamiltonian[NUM_KET][NUM_KET] = {0.0};

この辞書を作る上で特定の番号を振り分けていない数字もket_libra_gyakubikiに入ってしまうのでそこを解決するアイデアがほしい。

@ob_nullpo さんの回答の通り、mapを使う(実装する?)のが最善策かと思います。

0Like

Comments

  1. mallocを使ってヒープ領域からメモリ獲得する手もありますね。

「この辞書を作る上で特定の番号を振り分けていない数字もket_libra_gyakubikiに入ってしまうのでそこを解決する」で質問なのですが

例えば N=3の場合に
ket_libra_junbiki[]



ket_libra_gyakubiki[]
0番目 0
1番目 0
2番目 0
3番目 1
4番目 0
5番目 2
6番目 3
7番目 0
になるのですが

  1. 「振り分けていない数字」 とは
    ket_libra_gyakubiki[]の 0番目,1番目,2番目,4番目,7番目の部分とでしょうか?

  2. 「ket_libra_gyakubikiに入ってしまう」とは
    -1. 0番目,1番目,2番目,4番目,7番目が存在してしまうの意でしょうか?
    -2. ある条件下でket_libra_gyakubiki[]に振り分けていない数字が入ってしまう(例えば0番目,1番目,2番目,4番目,7番目に0以外が入る現象)問題を指すのでしょうか?

  3. 「そこを解決する」とは
    2-1のような領域を無くしてサイズを小さくしたい。例えばket_libra_gyakubiki[]の大きさを 3個にしたい( 何らかの方法で 3番目 1, 5番目 2, 6番目 3)なのでしょうか? 
    それとも、2-2の現象を解決したいとの意味でしょうか?

よろしくお願いします。

0Like

Comments

  1. @kisara11235

    Questioner

    1その通りです。
    2-1その通りです。特定の数字(順引きに存在する数字)以外の数字であるのに0を持つことが問題です。
    3-1順引きに入らない数字を無くして、メモリの節約を行いたいです。

Your answer might help someone💌