Почему определенный алгоритм занимает значительно больше времени через ctypes? - PullRequest
Новая
       9

Почему определенный алгоритм занимает значительно больше времени через ctypes?

1 голос
/ 08 ноября 2019

У меня есть программа на C, которая измеряет время, необходимое определенным алгоритмам для вставки элемента в структуру данных с помощью clock ()

Все мои различные функции .. закрытая таблица хеширования, открытая таблица хеширования, дерево двоичного поиска, красное черное дерево ... кажется, что все они выполняются автономно так же долго, как и при вызове через ctypes

EXCEPT one. Мое дерево AVL. Требуется около 100 мс для 200000 элементов в C, но 3600 мс только для 10000 элементов в ctypes. Что может быть виновником? Почему это обычно происходит? Я думал, что вызов func через ctypes - это то же самое, что запуск скомпилированного исполняемого файла.

Мое дерево AVL: 

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <time.h>
#include "funcs.h"

struct node_m{
    unsigned long int val;
    struct node_m * left;
    struct node_m * right;
    int height;
};

struct node_m * root;
unsigned char flag_g;

int max(struct node_m * x, struct node_m * y){
    int a;
    int b;
    if(x == NULL){
        a = 0;
    } else
        a = x->height;
    if(y == NULL){
        b = 0;
    } else
        b = y->height;
    return (a > b) ? a : b;
}

struct node_m * r_rot(struct node_m * temp){
    struct node_m * temp_d = temp->left;
    struct node_m * temp_dd = temp_d->right;

    temp_d->right = temp;
    temp->left = temp_dd;
    temp->height = 1 + max(temp->left, temp->right);
    temp_d->height = 1 + max(temp_d->left, temp_d->right);

    return temp_d;
}

struct node_m * l_rot(struct node_m * temp){
    struct node_m * temp_d = temp->right;
    struct node_m * temp_dd = temp_d->left;

    temp_d->left = temp;
    temp->right = temp_dd;
    temp->height = 1 + max(temp->left, temp->right);
    temp_d->height = 1 + max(temp_d->left, temp_d->right);

    return temp_d;
}

struct node_m * insert_m(struct node_m * node, unsigned long int val){
    if(node == NULL){
        struct node_m * leaf = malloc(sizeof(struct node_m));
        leaf->height = 1;
        leaf->val = val;
        leaf->left = NULL;
        leaf->right = NULL;
        return leaf;
    }else if(node->val > val){
        node->left = insert_m(node->left, val);
    } else if(node->val < val){
        node->right = insert_m(node->right, val);
    } else {
        return node;
    }

    if(!flag_g) {
        node->height = 1 + max(node->left, node->right);
        int l, r;

        if (node->left == NULL) {
            l = 0;
        } else
            l = node->left->height;

        if (node->right == NULL) {
            r = 0;
        } else
            r = node->right->height;

        int balance = l - r;

        if (balance < -1 && val > node->right->val) {
            node = l_rot(node);
            return node;
        }

        if (balance < -1 && val < node->right->val) {
            node->right = r_rot(node->right);
            node = l_rot(node);
            return node;
        }

        if (balance > 1 && val < node->left->val) {
            node = r_rot(node);
            return node;
        }

        if (balance > 1 && val > node->left->val) {
            node->left = l_rot(node->left);
            node = r_rot(node);
            return node;
        }
    }

    return node;
}

float driver_mytree(int x, unsigned char flag) {
    unsigned long int * randlist = malloc(x * sizeof(int));
    floyd_rand(&randlist, x);
    flag_g = 0;
    root = malloc(sizeof(struct node_m));
    root->height = 1;
    root->left = NULL;
    root->right = NULL;
    root->val = randlist[0];
    clock_t start = clock();
    for(int i = 1; i < x; i++){
        root = insert_m(root, randlist[i]);
    }
    if(flag){
        flag_g = flag;
        start = clock();
        for(int i = x - 1; i > 0; i--){
            root = insert_m(root, randlist[i]);
        }
    }
    clock_t end = clock();

    return (float) (end - start) / CLOCKS_PER_SEC * 1000;
}

Мой файл тестирования Python 

import ctypes

testlib = ctypes.CDLL("./lib.so")

testlib.driver_mytree.argtypes = [ctypes.c_uint64, ctypes.c_int]
testlib.driver_mytree.restype = ctypes.c_float
my_tree = testlib.driver_mytree

x = my_tree(10000, 0)
print(x)

Этокак я скомпилировал отдельные файлы: 

gcc -c -std=c11 -fPIC bvs.c    -o mybuild/bvs.o
gcc -c -std=c11 -fPIC my_hash.c    -o mybuild/my_hash.o
gcc -c -std=c11 -fPIC my_tree.c    -o mybuild/my_tree.o
gcc -c -std=c11 -fPIC rand.c    -o mybuild/rand.o
gcc -c -std=c11 -fPIC pcg_basic.c -o mybuild/pcg_basic.o
gcc -c -std=c11 -fPIC their_hash.c    -o mybuild/their_hash.o
gcc -c -std=c11 -fPIC their_tree.c    -o mybuild/their_tree.o


gcc -shared mybuild/pcg_basic.o mybuild/rand.o mybuild/bvs.o mybuild/my_hash.o mybuild/my_tree.o mybuild/their_tree.o mybuild/their_hash.o -o lib.so

pause

Примечание: я знаю, что передаю int в флаг unsigned char, но он отлично работает с другими

1 Ответ

0 голосов
/ 08 ноября 2019

Проблема найдена.

Она заключалась в том, как работает функция генерации случайных чисел, называемая PCG. Поскольку он генерировал случайные числа и имел «память» для равномерного распределения, поскольку я объединил его с моим алгоритмом кнута для создания массивов уникальных случайных чисел, он застрял в длинном цикле.

...