0

スキップリストを実装しています。それが何であるかは重要ではありませんが、現在 1000 ノードでは機能しますが、10000 ノードでは機能しません。驚いたことに、変わってはいけない多くのことがゴミの値に変わっていました。たとえば、関数 insertNode の前後に inputValue を出力しました。常にインクリメントする必要がある場合でも、ゼロにリセットされることがあります。コードを見てみましょう (読み取りファイルの入力をスキップします。問題は while サイクルで発生します):

int main(int argc, char** argv) {
    string filename = "";

    if( argc == 2 )
      filename = argv[1];
    else
        return 0;

    list = new skiplist();

    fstream inputFile(filename.c_str(), ios_base::in);

    inputFile >> numberofnodes;
    inputFile >> list->minimumKey;
    inputFile >> list->maximumKey;

    printf("%d\n", numberofnodes);
    printf("%d\n", list->minimumKey);
    printf("%d\n", list->maximumKey);

    list->Maxlevel = 1;

    list->header = new node();
    list->tail = new node();
    list->header->key = list->minimumKey;
    list->tail->key = list->maximumKey;


    for ( int i=1; i<=MAXIMUMLEVEL; i++ ) {
       list->header->forward[i] = list->tail;
       list->tail->forward[i] = NULL;
    }

    int sanityCheck = 134153;
    // insert nodes
    int inputKey;
    int inputValue = 0;
    int * keys = new int[numberofnodes];
    while (inputFile >> inputKey)
    {
        inputValue++;
        keys[inputValue] = inputKey;
        insertNode(inputKey, inputValue);  
        if(sanityCheck != 134153)       // dark magic changes this value
            keys[9999999999999999999999]++;  // program crashes here
                                             // it would otherwise crash on while
    }
    printf("\n\nNodes inserted: %d\n\n",inputValue);

ヴァルグリンドを走らせました。無効なメモリの書き込み/読み取りが発生した後、変数が変更されたため、少なくとも私はそう信じています。そのため、サニティ チェックを追加しました。そして、私が思ったように、キーにアクセスしようとする前に無効なメモリの書き込み/読み取りはありませんでした[9999999999999999999999]。しかし、その行は int sanitycheck is changed しか実行できませんが、私は決して実行しません。

最後に、insertNode のコードを次に示します。これを引き起こす可能性のあるものは何もありません：

void insertNode(int newKey, int newValue){
    node * update[MAXIMUMLEVEL];
    node * auxNode = list->header;
    for(int i=list->Maxlevel; i >=1; i--) {
        while ( auxNode->forward[i]->key < newKey ) {
            auxNode = auxNode->forward[i];
        }
        update[i] = auxNode;
    }
    auxNode = auxNode->forward[1];
    if ( auxNode->key == newKey ) {
        auxNode->value = newValue;
    } else {
        int randomLevel = 1;
        while ( (rand() / double(RAND_MAX)) < LEVELPROBABILITY && randomLevel < MAXIMUMLEVEL ) {
            randomLevel++;
        }

        if ( randomLevel > list->Maxlevel ) {
            for ( int i = list->Maxlevel+1; i <= randomLevel; i++ ) {
                update[i] = list->header;
            }
            list->Maxlevel = randomLevel;
        }
        node * newNode = new node();
        newNode->key = newKey;
        newNode->value = newValue;
        for ( int i=1; i<=MAXIMUMLEVEL; i++ ) {
            newNode->forward[i] = NULL;
        }

        for ( int i=1; i<=list->Maxlevel; i++ ) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }
}

そして構造：

typedef struct node {
    int key;
    int value;
    node * forward[MAXIMUMLEVEL+1];
}node;

struct skiplist {
    int minimumKey;
    int maximumKey;
    int Maxlevel;
    node * header;
    node * tail;
};

EDIT:
#define MAXIMUMLEVEL 16 
#define LEVELPROBABILITY 0.5

私はmallocも使用していません。ポインター操作はありますが、valgrind は私が何か悪いことをしたかどうかを検出する必要がありますよね? メモリが不足している場合は、例外が発生します。私が作成し、決してアクセス/書き込み/変更しない int が変更される可能性はありますか? 長文で申し訳ありませんが、どこに問題があるのか​​わかりません。

健全性チェックなしの Valgrind 出力 (keys[999...9]): http://pastebin.com/hWH3fri2

155 行目は while (inputFile >> inputKey) です。

4

1 に答える 1