c - 最近在 C 中进行高效的集合成员测试以进行重复数据删除？

Question

我有无限数量的 12 字节消息到达。内容可以被视为随机且无结构的。 (长度很重要，因为它比大多数哈希值都短。)

我想对它们进行重复数据删除。

一种方法是将最后 1,000 条消息存储在循环缓冲区中，并在接受消息之前检查所有 1,000 条消息是否匹配(并将其插入循环缓冲区以供将来检查)。

还有哪些其他方法可以提高 CPU 和内存效率？

Answer 1

12 字节看起来相当短。您可以将字节数组转换为字符串，然后通过利用 strcmp() 使用基于字符串的树结构。

1. Way to cast byte array to string

2. 基于字符串的树结构

除非您形成倾斜树，否则 O(logn) 将是重复数据删除的最坏情况。这种情况下，改成自平衡树也不难。

这是我使用字符串类型键的 BST 实现:

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


struct Node
{
  char *key;
  char *value;
  struct Node *left;
  struct Node *right;
};

struct Node* newNode(char *strKey,char *strValue)
{
  struct Node *tmp = (struct Node*) malloc(sizeof(struct Node));
  tmp->key = strdup(strKey);
  tmp->value = strdup(strValue);
  tmp->left = NULL;
  tmp->right = NULL;
  return tmp;
}

struct Node* insert(struct Node* node, char *newKey, char *newValue)
{
  if (node == NULL)
    return newNode(newKey,newValue);

  int comparison = strcmp(newKey,node->key); 
  if (comparison < 0)
    node->left  = insert(node->left, newKey, newValue);
  else if (comparison > 0)
    node->right = insert(node->right, newKey, newValue);  
  else
  {
    printf("Error occured while insert to BST\n");
    return NULL;
  }

  return node;
}

struct Node* deleteNode(struct Node* node, char *key2del)
{
  if (node == NULL)
    return node;

  int comparison = strcmp(key2del,node->key);
  if (comparison < 0)
    node->left = deleteNode(node->left, key2del);
  else if (comparison > 0)
    node->right = deleteNode(node->right, key2del);
  else // where deletion occurs
  {
    if (node->left == NULL)
    {
      struct Node *tmp = node->right;
      free(node);
      return tmp;
    }
    else if (node->right == NULL)
    {
      struct Node *tmp = node->left;
      free(node);
      return tmp;
    }

    struct Node *tmp = node->right;
    while(tmp->left != NULL)
      tmp = tmp->left;

    node->key = tmp->key;
    node->right = deleteNode(node->right, tmp->key);
  }

  return node;
}