在C中进行重复数据删除的高效最近集合成员测试？
我有无限数量的12字节消息到达。 内容可以被视为随机和无结构的。 （长度很重要，因为它比大多数哈希短。）
我想重复删除它们。
一种方法是将最后1,000条消息存储在循环缓冲区中，并在接受消息之前检查所有1,000条消息以进行匹配（并将其插入循环缓冲区以供将来检查）。
还有哪些其他方法可以提高CPU和内存效率？
12个字节看起来很小。 您可以通过利用strcmp()将字节数组转换为字符串，然后使用基于字符串的树结构。
-
将字节数组转换为字符串的方法
-
基于字符串的树结构
除非你形成一个偏斜的树，否则O（logn）将是重复数据删除的最坏情况。 在这种情况下，也不难改变为自平衡树。
这里我的BST实现使用字符串类型键：
#include #include #include 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; }