6

所以，我需要一系列项目。我想知道哪个是最快/最好使用的（在 c# 中），我将做以下事情：

  1. 最后添加元素
  2. 在开始时删除元素
  3. 查看第一个和最后一个元素（每一帧）
  4. 偶尔清理一下
  5. 将其转换为普通数组（不是列表。我使用的是 iTween，它会询问普通数组。）我几乎每一帧都会这样做。

那么，考虑到这些事情，最好使用什么？尤其是最后一个，因为我每帧都这样做。我应该只使用一个数组，还是有其他东西可以非常快速地转换为数组并且在开始和结束时也可以轻松添加/删除元素？

4

5 回答 5

4

你可以看看LinkedList<T>。

它具有 O(1) 支持在开头或结尾检查、添加和删除项目。它需要 O(n) 才能复制到数组，但这似乎是不可避免的。ICollection<T>如果您使用的 API 接受了or ，则可以避免复制IEnumerable<T>，但如果无法更改，那么您可能会被使用ToArray.

如果您的列表每帧更改少于一次，那么您可以缓存该数组，并且仅ToArray当列表自上一帧以来发生更改时才再次调用。下面是一些方法的实现，让您了解这种潜在的优化是如何工作的：

private LinkedList<T> list = new LinkedList<T>();

private bool isDirty = true;

private T[] array;

public void Enqueue(T t)
{
    list.AddLast(t);
    isDirty = true;
}

public T[] ToArray()
{
    if (isDirty) 
    {
        array = list.ToArray();
        isDirty = false;
    }

    return array;
}
于 2012-12-16T23:14:51.393 回答
4

要求 1) 和 2) 指向 a Queue<T>，它是唯一针对这两个操作优化的标准集合。

3）你需要一些技巧来获得最后一个元素，首先是Peek()。
4) 很简单 ( .Clear())
5) 标准.ToArray()方法会做到这一点。

您不会逃避复制O(n)第 5 项的所有元素 ())

于 2012-12-16T23:17:50.757 回答
2

我假设您使用的是类（而不是结构）？（如果您使用的是结构（值类型），那么这会改变一些事情。）

该System.Collections.Generic.List课程可让您快速完成所有这些工作。使用 LinkedList 可以做得更好的唯一部分是从一开始就删除，但是单个块​​内存副本并没有太大的痛苦，它可以轻松创建数组。

我不建议使用链接列表，特别是如果您只是从开头或结尾删除。每次添加（使用标准 LinkedList 集合）都需要分配内存（它必须构建一个对象来引用您实际想要添加的内容）。

列表还有很多方便的功能，如果性能有问题，使用时需要小心。列表本质上是数组，当你添加东西时会变得更大（每次你把它们填满，它们就会变得更大，这样可以节省过多的内存操作）。清除它们不需要任何努力，并将分配的内存留作另一天使用。

根据个人经验，.NET 不适合通用链接列表，您需要专门编写代码才能在整个过程中使用它们。列表：

  • 易于使用

  • 做你想做的一切

  • 不会让你的记忆看起来像瑞士奶酪（好吧，当你每帧分配一个新数组时，你可以做的最好 - 我建议你让垃圾收集器有机会在创建一个新数组之前摆脱任何旧数组，如果通过重新使用任何数组引用并将不需要的任何数组归零，这些数组将变得很大）。

正确的选择很大程度上取决于应用程序的具体情况，但如果您问我，List 始终是一个安全的选择，而且您不必编写任何特定于结构的代码来使其工作。

如果您确实喜欢使用列表，则需要研究这些方法和属性：

  • ToArray() // 生成你想要的数组

  • Clear() // 清除数组

  • Add(item) // 在末尾添加一个项目

  • RemoveAt(index) // 第一项的索引为 0，最后一项为 .Count - 1

  • Count // 检索列表中的项目数 - 这不是免费查找，因此请尽量避免不必要的请求

对不起，如果这整个帖子是矫枉过正。

于 2012-12-16T23:36:11.633 回答
0

圆形数组怎么样？如果您保留最后一个元素和第一个元素的索引，则您给出的每个标准都可以有 O(1)。

编辑：您可以采用 C++ 向量方法来获取容量：容量满时将大小加倍。

于 2012-12-16T23:20:22.393 回答
0

常规列表将完成这项工作，它比链接列表插入更快。

  • 在末尾添加元素 -> myList.Insert(myList.Count - 1)
  • 在开始时删除元素 -> myList.RemoveAt(0)
  • 查看第一个和最后一个元素（每帧）-> myList[0] 或 myList[myList.Count - 1]
  • 偶尔清除它-> myList.Clear()
  • 将其转换为普通数组（不是列表。我使用的是 iTween，它会询问普通数组。）我几乎每一帧都会这样做。-> myList.ToArray()
于 2012-12-16T23:33:08.413 回答