c - BST 和链表 C 程序陷入大值

Question

我正在做一项大学作业，教授要求我们实现 BST 和链表，并计算插入和搜索大量随机生成的值时进行了多少次比较。我们应该从 10 个值开始，然后是 100 个，然后是 1000 个，直到 10^12。问题是，它总是卡在 100000 (10^5)。 RAM 使用率较低，但 CPU 处于最大状态。每一步后我都会释放树和列表。找到代码here (场外)及以下。

总结一些要点:每个值(节点的键)都是无符号的(最大 65535)，但最多应插入 10^12 个值并搜索另外 10^12 个值。

需要这么长时间吗？我的处理器是 i5-7200u

是否有可能是内存问题并且 GCC 以某种方式阻止了它？

非常感谢

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

typedef long long ll;
typedef unsigned long long ull;

// BST

typedef struct no_A_struct {
  unsigned int chave;
  struct no_A_struct *esquerda;
  struct no_A_struct *direita;
} no_A;

// new node
no_A *novo_no_A(unsigned int chave) {
  no_A *no = (no_A *) malloc(sizeof(no_A));
  no->chave = chave;
  no->esquerda = no->direita = NULL;
  return no;
}

// insert note
no_A *insere_A(no_A *raiz, unsigned int chave, ull *cont) {
  (*cont)++; if (raiz == NULL) return novo_no_A(chave);
  (*cont)++; if (chave < raiz->chave) raiz->esquerda = insere_A(raiz->esquerda, chave, cont);
  else {
    (*cont)++; if (chave > raiz->chave) raiz->direita = insere_A(raiz->direita, chave, cont);
  }
  return raiz; 
}

// search node
no_A *busca_A(no_A *raiz, unsigned int chave, ull *cont) {
  (*cont)++; if (raiz == NULL) return NULL;
  (*cont)++; if (chave == raiz->chave) return raiz;
  (*cont)++; if (chave > raiz->chave) return busca_A(raiz->direita, chave, cont);
  return busca_A(raiz->esquerda, chave, cont);
}

// free tree
void desaloca_A(no_A *raiz) { // TODO iterativa?
  if (raiz == NULL) return;
  desaloca_A(raiz->esquerda);
  desaloca_A(raiz->direita);
  free(raiz);
}

// LINKED LIST WITH IN ORDER INSERTION

typedef struct no_L_struct {
  unsigned int chave;
  struct no_L_struct *prox;
} no_L;

// new node
no_L *novo_no_L(unsigned int chave) {
  no_L *no = (no_L *) malloc(sizeof(no_L));
  no->chave = chave;
  no->prox = NULL;
  return no;
}

// insert node
void insere_L(no_L **inicio, unsigned int chave, ull *cont) {
  no_L *novo_no = novo_no_L(chave);
  (*cont)++; if (*inicio == NULL) { *inicio = novo_no; return; }
  (*cont)++; if (novo_no->chave <= (*inicio)->chave) {
    novo_no->prox = *inicio;
    *inicio = novo_no;
  } else {
    no_L *atual = *inicio;
    for (;;) {
      (*cont)++; if (atual->prox == NULL) break;
      (*cont)++; if (novo_no->chave <= atual->prox->chave) break;
      atual = atual->prox;
    }
    novo_no->prox = atual->prox;
    atual->prox = novo_no;
  }
}

// search node
no_L *busca_L(no_L *atual, unsigned int chave, ull *cont) {
  for (;;) {
    (*cont)++; if (atual == NULL) break;
    (*cont)++; if (atual->chave == chave) break;
    atual = atual->prox;
  }
  return atual;
}

// void printa_L(no_L *atual) {
//   if (atual == NULL) return;
//   printf("%u", atual->chave);
//   printa_L(atual->prox);
// }

// free list
void desaloca_L(no_L *atual) {
  no_L *no_apagar;
  while (atual != NULL) {
    no_apagar = atual;
    atual = atual->prox;
    free(no_apagar);
  }
}

int main() {
  ll QTD_VALORES[] = {10, 100, 1000, // 10^: 1, 2, 3
              10000, 100000, 1000000, // 4, 5, 6
              1000000000, 10000000000, // 9, 10
              100000000000, 1000000000000}; // 11, 12
  int ITERACOES = 1; // TODO voltar pra 100
  unsigned int VALOR_MAX = 65535;

  int tamanho_qtd_valores = sizeof(QTD_VALORES)/sizeof(QTD_VALORES[0]);
  srand(time(0));

  for (int qtd_i=0; qtd_i<tamanho_qtd_valores; qtd_i++) {
    ll qtd = QTD_VALORES[qtd_i];
    printf("== QTD DE VALORES %lli ==\n", qtd);

    for (int i=0; i<ITERACOES; i++) {

      ull comp_A_insercao = 0, comp_A_busca = 0,
          comp_L_insercao = 0, comp_L_busca = 0;
      no_A *arvore = NULL;
      no_L *lista = NULL;

      // generates and insert values
      unsigned int valores_busca[qtd];
      for (ll v=0; v<qtd; v++) {
        // // insert values
        unsigned int valor_insercao = rand() % VALOR_MAX + 1;
        arvore = insere_A(arvore, valor_insercao, &comp_A_insercao);
        insere_L(&lista, valor_insercao, &comp_L_insercao);

        valores_busca[v] = rand() % VALOR_MAX + 1;
      }

      // search values
      for (ll v=0; v<qtd; v++) {
        busca_A(arvore, valores_busca[v], &comp_A_busca);
        busca_L(lista, valores_busca[v], &comp_L_busca);
      }

      // desaloca_A(arvore);
      // desaloca_L(lista);

      // TODO divisões retornar numero real?
      printf("INTERACTION %d: \n", i+1);
      printf("Tree insertion, total=%llu, avg=%llu\n", comp_A_insercao,
            comp_A_insercao / qtd);
      printf("Tree search, total=%llu, avg=%llu\n", comp_A_busca,
            comp_A_busca / qtd);
      printf("List insertion, total=%llu, avg=%llu\n", comp_L_insercao,
            comp_L_insercao / qtd);
      printf("List search, total=%llu, avg=%llu\n", comp_L_busca,
            comp_L_busca / qtd);    
    }
    printf("\n");
  }
}

Answer 1

您确定要插入列表中已有的项目吗？我认为您应该避免添加重复的键。

<小时/>

插入链表中的第一个节点将需要 0 次比较。第二个，1/2(平均)。第三个、2/2、第四个3/2等。所以插入N次，平均时间将与(0+1+2+...+(N-2)+(N-1))/成正比2 = N*(N-1)/4。

$ perl -e'printf "%d: %d\n", $_, (10**$_)*(10**$_-1)/4 for 1..5;'
1: 22
2: 2475
3: 249750
4: 24997500
5: 2499975000

插入 10⁵ 个节点平均需要 25 亿时间单位。例如，如果每次比较需要 100 ns，则平均插入 10⁵ 个节点将需要 4 分钟以上。

以同样的速度，插入 10¹² 个节点平均需要 8 亿年。

<小时/>

另一方面，如果您避免添加列表中已有的 key ，则平均时间将不超过 65,536*N/2

$ perl -e'printf "%d: %d\n", $_, 65536*(10**$_-1)/4 for 1..12;'
1: 147456
2: 1622016
3: 16367616
4: 163823616
5: 1638383616
6: 16383983616
7: 163839983616
8: 1638399983616
9: 16383999983616
10: 163839999983616
11: 1638399999983616
12: 16383999999983616

因此，按照上面假设的速率，插入 10¹² 个节点将平均“仅”19 天，而不是花费 8 亿年。即使我偏离了一个数量级，我们仍然在谈论 2 天。