与Python相比，具有动态分配的结构数组在C中的运行速度非常慢

Question

我（在其他SO用户的帮助下）“粘合”了一个小型C程序，该程序将字符串标签映射到边缘列表数据结构中的整数标签。例如，对于输入文件

Mike Andrew
Mike Jane
John Jane

程序输出

1 2
1 3
4 3

但是，我映射了巨大的边缘列表文件，不幸的是，与Python相比，该程序运行非常慢。下面，我用C和Python粘贴了这两个程序。请问如何提高C程序速度的指针。

#include <stdio.h>
#include <stdlib.h>

// Initial number of maximal lines in a file
enum { MAXL = 200};

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

typedef struct {
    unsigned int hashed;
     char **map;
} hash;


int insertInMap(hash *map, char *entry)
{
  int i =0;
  for (i=0;i<map->hashed;i++)
  {
    if (strcmp(map->map[i],entry) == 0)
    return i+1;
  }
  /* Warning no boundary check is added */
  map->map[map->hashed++] = strdup(entry);   
  return map->hashed;
}

int main() {
  FILE *fp = NULL;
  char node1[30];
  char node2[30];
  int idx = 0;
  int i, n = 0, maxl = MAXL;

  edge *edges;
  hash map;

  edges = malloc(MAXL * sizeof(edge));
  map.map = malloc(MAXL * sizeof(char*));
  map.hashed = 0;

  fp = fopen("./test.txt", "r");

  while (fscanf(fp, "%s %s", &node1, &node2) == 2) {
    if (++n == maxl) { /* if limit reached, realloc lines  */
      void *tmp = realloc (edges, (maxl + 40) * sizeof *edges);
      void *tmp1 = realloc (map.map, (maxl + 80) * sizeof(char*));
      if (!tmp) {     /* validate realloc succeeded */
        fprintf (stderr, "error: realloc - virtual memory exhausted.\n");
        break;      /* on failure, exit with existing data */
      }
      edges = tmp;    /* assign reallocated block to lines */

      map.map = tmp1;
      maxl += 40;     /* update maxl to reflect new size */
    }
    edges[idx].first = insertInMap(&map,node1);
    edges[idx].second = insertInMap(&map,node2);
    idx++;
  }

  fclose(fp);

  for (int i = 0; i < idx; i++) {
    printf("%d -- %d\n", edges[i].first, edges[i].second);
  }


  free(edges);

  return 0;
}

相应的Python替代方法：

import fileinput

i = 0
cui2int = {}

for line in fileinput.input():    
    (cui1, cui2) = line.split()
    if cui1 in cui2int:
        int1 = cui2int[cui1]
    else:
        i += 1
        cui2int[cui1] = i
        int1 = i

    if cui2 in cui2int:
        int2 = cui2int[cui2]
    else:
        i += 1
        cui2int[cui2] = i
        int2 = i

    print(int1, int2)

编辑和添加

以下是使用GLib哈希实现的修改后的代码。我提高了性能，但是很遗憾，输出仍然有问题

1 2
1 3
4 3

代替

0 0
0 1
1 1

有人可以看看。

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

int main() {
  GHashTable *table;
  table = g_hash_table_new(g_int_hash, g_int_equal);

  FILE *fp = NULL;
  char node1[30];
  char node2[30];

  fp = fopen("./test.txt", "r");
  int i = 0;
  while (fscanf(fp, "%s %s", &node1, &node2) == 2) {
    char *key1 = malloc(sizeof(char)*1024);
    char *key2 = malloc(sizeof(char)*1024);
    uint32_t* value = (uint32_t *)malloc(sizeof(uint32_t));
    key1 = g_strdup(node1);
    key2 = g_strdup(node2);
    *value = i;

    uint32_t *x;
    if (g_hash_table_contains(table, key1)) {
      x = (uint32_t *)g_hash_table_lookup(table, key1);
    } else {
      i++;
      g_hash_table_insert(table, (gpointer)key1, (gpointer)value);
      x = (uint32_t *)value;
    }

    uint32_t *y;
    if (g_hash_table_contains(table, key2)) {
      y = (uint32_t *)g_hash_table_lookup(table, key2);
    } else {
      g_hash_table_insert(table, (gpointer)key2, (gpointer)value);
      y = (uint32_t *)value;
    }
    printf("%d -- %d\n", *x, *y);
  }

  fclose(fp);

  g_hash_table_destroy(table);
  table = NULL;
  return 0;
}

Answer 1

C语言中的“哈希”操作更像是一个链表，具有线性插入和查找功能。另一方面，Python的字典具有O（1）个平均插入和查找（in运算符）的工业强度。如果您是用C从头开始编写哈希图，则需要大量理论才能付诸实践，以便开始在性能方面接近Python的实现。

我认为，最好的办法是尽可能使用C ++编写代码，并使用unordered_map。这是两全其美的方法：已经为您完成了所有工作，但您无需牺牲性能。

如果您使用C语言（或使用C语言），则Internet上有很多资源，但是由于我无法保证其质量，因此我很犹豫在此处发布任何链接。这应该是一种教育上的努力。

Answer 2

这两个程序使用的是根本不同的数据结构，具有不同的时间复杂度。python程序使用的字典是高度优化的哈希表，具有O（1）摊销后的性能，用于查找和删除。

因此，python程序以O（单词数）渐近复杂度运行。

现在，谈论您要尝试创建的C程序，本质上只是一个键值对数组。插入或检索键在这里需要O（数组的大小），因为您可以循环遍历数组直到最后找到匹配项。

如果您做一些数学运算，结果将是O（（单词数）²）。

C ++具有名为unordered_map的内置哈希表实现，如果在切换到C ++时没有问题，可以使用该实现。或在SO上检查此问题，以学习在C中编写自己的哈希表。什么是哈希表，以及如何在C 中创建哈希表？