1

所以我有两个不同的列表，需要协调不同的格式和结构。本质上，集合 B 需要匹配集合 A 中的内容，但我想保留集合 B 中现有项目的状态，而不是用集合 A 中的内容覆盖它们。

作为参考，列表实际上并不意味着列表。“列表”有几种不同的形式，从直接数组到映射。都使用标准迭代器来访问元素。

我通常处理的方式是这样的......

for item in listA
  if listB contains item
     mark item in list B as visited
  else 
     add item to list b

 for item in listB
   if visited is true
      continue
   else
       add item to removeList

 for item in removeList
    remove item from list B

这是可行的，并且是我能想到的唯一真正的方法。我不喜欢我必须做多少次迭代，让三个 for 循环背靠背感觉是错误的。但是，由于我使用的是迭代器，因此在检查列表时无法从列表中删除任何内容，而是必须将它们添加到第三个删除列表中。

在可能的答案中，请记住，速度和内存占用对我来说比编写代码的难易程度更重要。

我的问题真的归结为这一点 - 有没有更好的方法来做到这一点，我没有想到？

我在 C++/C FWIW 中，但我认为任何解决方案都可能与语言无关。

谢谢！

4

1 回答 1

0

这是另一种可能更有效的方法：

removeList = listB

for item in listA
  if listB contains item
    remove item from removeList
  else
    add item to listB

for item in removeList
  remove item from listB

因此，它不是从无到有地构建 removeList ，而是从所有内容开始，然后从中删除项目。

您还可以通过使用 removeList 存储索引而不是实际项目来提高效率。只要在初始循环中将项目添加到 listB 的末尾，并以相反的顺序删除项目，索引应该仍然有效。

实际上，如果您将removeList替换为要保留的布尔值数组，则更简单。所以算法变成了这样：

initialise all itemsToKeep to false
savedListLength = length of listB

for item in listA
  offset = find item in listB
  if found
    mark itemsToKeep[offset] as true
  else
    add item to listB

for offset from savedListLength-1 down to 0
  if itemsToKeep[offset] is false
    remove the offset from listB

这避免了最初将任何内容复制到removeList中的需要。并且itemsToKeep数组的开销肯定不会比您用来跟踪算法中访问项目的任何内容差。

在某种程度上，最合适的算法可能取决于列表的形式（即向量或链表等），但我确实认为我的方法有可能更有效。

于 2013-07-17T18:14:03.550 回答