在JavaScript中以大字符串查找重复行的最佳方法

Question

在包含超过1000万行的字符串中查找重复行（重复一次以上）的最佳方法是什么？ （我只是尝试将数组保留为字符串以节省内存）

例如：

输入：

userId256
userId512
userId64
userId256
userId128
userId128
userId128
userId8
userId4
...

输出：

userId256
userId128

我会使用split("\n")，然后使用数组，但是可能存在使用较大字符串值的最佳方法。

Answer 1

我不确定性能是否会更好，您需要检查它的性能，并与基于阵列的解决方案进行比较。

您可以使用带有capture group，positive lookahead和back reference的RegExp查找重复的行，然后将其转换为Set，然后扩展到数组以获取唯一的行：

const str = `userId256
userId512
userId64
userId256
userId128
userId128
userId128
userId8
userId4`

const result = [...new Set(str.match(/^(.+)$(?=[\s\S]+\1)/gm))]

console.log(result)

Answer 2

编辑

没有一种方法可以在不访问每个元素的情况下神奇地识别出重复项。现在，这是您要在哪里做的问题。由于用户体验不会受到影响，因此在后端上做得特别好。如果仍要在浏览器上使用它，则可以使用setTimeout或使用webworkers来减少对用户界面的影响。

实际答案

您必须对此可以使用reduce函数。

const str = `your big string`;
const data = str.split("\n");
let duplicate = data.reduce((acc,currentValue,index, array) => {
  if(array.indexOf(currentValue)!=index && !acc.includes(currentValue)) acc.push(currentValue);
  return acc;
}, []);
console.log(`Duplicates are now in the array ${duplicate}`);

Answer 3

您可以找到类似的重复项：

const result = a.reduce((a, c)=> {
    a[c] = a[c] || {data:[]};
    a[c].data.push(c);
    return a;
}, {});

const duplicates = Object.entries(result).filter(([k, v]) => v.data.length > 1 );

const a = [
    'userId256',
    'userId512',
    'userId64',
    'userId256',
    'userId128',
    'userId128',
    'userId128',
    'userId8',
    'userId4'
      ];

const result = a.reduce((a, c)=> {
    a[c] = a[c] || {data:[]};
    a[c].data.push(c);
    return a;
}, {});

const duplicates = Object.entries(result).filter(([k, v]) => v.data.length > 1 );


console.log(duplicates);

Answer 4

取决于您要优化的内容（时间/空间/代码复杂度）以及某些情况：

• 简单方法：遍历所有行，并进行详尽的indexOf搜索。每当获得多个结果时，请记住行内容。这几乎不需要额外的空间，但是运行时间为O（n²）。]
• 运行时优化：遍历所有行并建立频率表。在O（n）中运行，但是需要一个临时表对象，您可以在其中计算发生次数（最坏的情况是加倍的空格）。
• 两者的混合物：使用bloomfilter。基本上以O（n）运行（如果找到匹配项，则需要一些额外的工作），并且不需要太多的额外空间。但是请注意，bloomfilters设置起来很棘手，如果存储大小错误或哈希函数不正确，它将恢复为O（n²）。这具有最高的代码复杂性，但可能会为如此大量的数据带来回报。如果重复的可能性很高，那么Bloomfilter可能会表现不佳。

Answer 5

为了避免数据的中间副本，您可以创建一个生成器函数，该函数将使您返回一个可迭代的对象：