9

情况如下：
我列出了哪些存储字符串实际上是数字并且可以变得非常大（数亿个项目）。
我将数字存储为字符串，因为可以选择显示一些附加信息，即文本。

因为这需要大量内存来存储，所以我决定最多只存储 500 万个项目。（这只需要大约 250-300mb）。

该列表由计算的输出填充。如果找到一个数字，它将被添加到列表中，这个数字总是大于现有项目。

当列表达到 5 百万时，我想删除第一个项目并将新项目添加到列表中。

像：

    // Why is this so freaking slow???
    if (_result.Count == 5000000)
        _result.RemoveAt(0);
    _result.Add(result);

正如您在评论中看到的那样，这非常、非常、非常慢。它只是将我的性能降低了 15 倍。以前需要 2 分钟，现在大约需要 30 分钟。

我尝试了一些类似 linq 的方法，.Skip(1).ToList但这会重新创建列表，因此速度会更慢。

该列表必须保持正确的顺序，因此不能选择按索引覆盖（除非您可以解释一个很好的解决方法）。

我的问题：
有什么体面的方法可以做到这一点吗？

我真的需要这里的性能，因为它可能需要检查大约 10000000000 个数字。这可能需要一天的时间，但一个月有点太多了:(。

需要更多信息，请随时询问，我很乐意提供。

解决方案：
这执行 O(1)

    // Set the _result
    Queue<object> _result = new Queue<object>(5000000);

    /// Inside the method
    // If the count has reach it's max, dequeue the first item
    if (_result.Count == 5000000)
        _result.Dequeue();
    _result.Enqueue(result);
4

5 回答 5

4

你有没有重新订购物品？如果你不这样做，循环队列会很好用。

System.Collections.Generic.Queue 是一个，我只是仔细检查了一遍。

为了扩展队列的好处，这是RemoveAt实现（大致）：

for (int i = 1; i < count; i++)
    items[i-1] = items[i];
count--;

因为list[0]始终是第一项，所以您必须移动所有内容才能删除第一项。

相反，队列单独跟踪第一项。这将上面的代码更改为：

head++
于 2012-09-20T17:46:32.790 回答
1

我会建议你更好地实现一个循环队列。然后将每个 int 推到队列的末尾，当空间不足（由固定大小确定）时，每个操作都需要弹出第一个并推到底部。O(1).

与数组相比，优势在于您不会在需要之前预先分配空间。但是，最后，考虑将整数存储为整数。无论您将执行什么操作，您都应该始终将数字存储为数字。

于 2012-09-20T17:44:55.080 回答
0

为什么不预先分配数组，并且有两个整数，表示数组的开始和结束。显然，它们开始时都等于 0。一旦你用完了空间，你就开始环绕。

一个示例伪助手类：

class CircularArray
{
  const int maxSize = 5000000;
  private int[] arr = new int[maxSize];
  private int start = 0;
  private int end = 0;

  public void Add(int value)
  {
    int newEnd = (end + 1) % maxSize;
    if (newEnd == start)
      start = (start + 1) % maxSize;
    end = newEnd;
    arr[end] = value;
  }

  public int Get(int index)
  {
    int newIndex = (start + index) % maxSize;
    return arr[newIndex];
  }
}
于 2012-09-20T17:45:01.803 回答
0

当您删除 ArrayList 中的第一项时，所有其他项都会下移。循环队列将允许您保持原始顺序并消除在删除列表头部时发生的耗时移位。

于 2012-09-20T17:48:18.133 回答
0

可能对你有LinkedList<T> Class帮助吗？在两端删除和添加是O（1）操作，但迭代将是O（n），或者如果您需要O（1）访问您可以使用Dictionary或SortedDictionary 另一个自定义实现是QueueDictionary，我在需要时使用它O (1) 在结束或开始（队列/出队）以及访问值时添加和删除操作。QueueDictionary 在这里：我将如何实现一个 QueueDictionary，它是 C# 中队列和字典的组合？

于 2012-09-20T18:20:37.417 回答