0

我是相当新的程序员。因此，我正在查看来自文件的数据，并且我必须以占用最少处理时间和内存的方式对数据进行排序。我正在考虑的一种方法是实现一个平衡的二进制文件以有序的方式存储数据，以便我可以以非常有效的方式检索相同的数据。为了测试，我以这种方式生成我的日志文件。

import time
import random

JITTER = 275 
TICKS = 1000
LINES_PER_TICK = 1000

def log_line(now):
    timestamp = now - (random.random() * JITTER)
    return "%f   City %d" % (timestamp, random.randint(0,10000))

start = time.time()

for tick in xrange(TICKS):
    now = start + tick
    for num_line in xrange(LINES_PER_TICK):
    print(log_line(now))

平衡二叉树是实现此类程序的最佳方法。有没有更好的方法来做同样的事情？谢谢。

4

1 回答 1

0

我假设您想要做的主要事情是：

  1. 在末尾添加一个新的日志行。
  2. 在非常接近结尾处添加一个新的日志行（如果您的程序是多线程的或其他异步的）。
  3. 搜索最接近给定时间戳的行。
  4. 搜索给定时间范围内的所有行。

对于所有这些，二叉搜索树是 O(log N)。跳过列表或 B 树或许多其他数据结构也是如此。

那么，您如何在它们之间进行选择呢？

好吧，除非您真的需要自己构建它，否则您可能更关心接口而不是确切的性能特征，只要它们都“足够快”，它们可能是。例如，blist.sorteddict是一个精心设计的类，它几乎可以替代dict任何排序的东西。bintrees.RBTree具有一些很酷的功能，例如您可能根本没想过要寻找的密钥切片，但一旦找到它们就可能会一直使用它们。sqlite3可以简单地备份到磁盘，并且可以通过您系统上已有的好工具进行搜索。其中一个对您来说可能比 B+Tree、红黑树和具有 B-tree 索引的数组之间的差异更重要。

如果挤出最后一点性能确实很重要，您可能希望在特征系统上使用真实数据集进行测试，而不是尝试猜测。有一些很好的经验法则：如果你有足够的数据可以交换到内存，那么 B 树是好的；跳过列表适用于细粒度锁定；跳过列表有利于阅读大范围；二叉树适合通过位置而不是键快速逼近；等等。但无论如何你还是想测试你的猜测，所以不要在猜测上投入太多精力。

于 2013-07-03T22:56:31.337 回答