我有这个程序需要对数组中的字符串进行一些比较。第一个想法当然是使用 strcmp 来检查数组中的两个字符串是否相同。现在考虑您只需要比较指针与字符串的选项。这将涉及一些准备工作,将每个实际上相同的元素映射到内存中的同一位置。
我已经完成了这一切,通过使用 strcmp
进行准备,现在使用 strstr
(我认为它更快)。
但是因为我需要检查每个字符串以将它们映射到第一次出现的位置,所以我的准备时间非常长。我应该提到这个数组有几 MB 大。
这是我想要做的示例:
[0x0: "I", 0x1: "am", 0x2: "done", 0x3: "here.", 0x4: "I", 0x5: "have", 0x6: "done", 0x7: "everything!"]
[0x10: 0x0, 0x11: 0x1, 0x12: 0x2, 0x13: 0x3, »0x14: 0x0«, 0x15: 0x5, »0x16: 0x2«, 0x17: 0x07]
现在的问题是:是否有其他方法可以比我已经做的更快地完成这种映射?
最佳答案
如果只是为了查看是否存在重复项...您可以在字符串数组上运行 qsort()
,如果您的排序函数发现重复项,您可以提前退出。或者,如果您需要删除重复项,则让排序完成并从列表底部开始线性迭代,并在找到它们时将它们拉出(因为所有重复项将彼此相邻)。
如果字符串相对不同,则 strcmp()
实际上只需要在匹配失败之前检查前几个字符。所以情况可能没有你想象的那么糟糕。
当然,执行此操作的难易程度完全取决于字符串在内存中的实际存储方式。
更新:
好的,根据您的更新...Matt 关于哈希表的建议可能效果最好:
- 逐一迭代您的列表
- 对字符串进行哈希处理
- 检查表中是否已存在
- 如果没有,请将其添加到表中并继续
- 如果是,请使用表中的现有索引
- ...然后继续下一步。
总体而言,我想这应该会给你带来相对不错的性能。
关于c - 优化的数组列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18117478/