草庐IT

Python:一个不会被重新定位的列表

coder 2023-08-25 原文

我正在尝试优化 Python 中的算法纯粹是为了好玩/好奇。我有一个列表，我不断地从中添加项目和删除项目。我知道 Python 列表的实现方式，Python 会根据列表的大小为您在内存中重新定位列表。例如，如果您有一个包含 10 个成员的列表，这 10 个指针将连续存储在内存中，但可能没有空间容纳 100 个连续的指针，因为另一个程序可能占用了挡路的内存块。因此，当您向列表中添加更多成员时，有时 Python 会将整个列表重新定位到内存中的不同位置，以便为列表扩展提供更多空间。

我很想知道 Python 中是否有一个自定义数据结构，其行为类似于列表，但允许我避免执行重定位的性能成本。我期待这个数据类型会事先询问我，我预计它会有多少成员，然后它会在内存中分配一个大的连续空间，这样它就不需要重新定位列表，因为它会慢慢增长到我的成员数量指定。

(注意:我尝试使用 Numpy 数组，但我不得不保留一个单独的“针”变量来保持列表的大小，恐怕在 Python 中维护该针的开销比收获。)

最佳答案

出于好奇，我实现了简单的基准测试来测试这里提到的各种方法。正如人们预测的那样，差异非常小。也就是说，对于较大的数据集，预先分配列表并跟踪大小会更快，但这当然只是在最后添加/删除项目时的情况。

基准

import time
from collections import deque

def normal(size):
    res = []
    for x in xrange(size):
        res.append(x)

def prealloc(size):
    res = [0] * size
    len = 0 # Separate length tracking
    for x in xrange(size):
        res[len] = x
        len += 1

def deq(size):
    res = deque()
    for x in xrange(size):
        res.append(x)

FUNCS = [
    ['list', normal],
    ['pre-allocate', prealloc],
    ['deque', deq]
]

size = 10
while size <= 10000000:
    print 'size: {0}'.format(size)
    for n, f in FUNCS:
        start = time.clock()
        for i in xrange(30):
            f(size)
        t = time.clock() - start
        print '{}: {}'.format(n, (t / 30))
    size *= 100
    print ''

结果

size: 10
list: 2.13049681786e-06
pre-allocate: 2.03719038788e-06
deque: 2.00608824456e-06

size: 1000
list: 0.000104425446219
pre-allocate: 8.72415120307e-05
deque: 0.000106369330176

size: 100000
list: 0.00984092031242
pre-allocate: 0.00825001457913
deque: 0.0101434508606

size: 10000000
list: 1.23171166758
pre-allocate: 0.876017370547
deque: 1.05051393959

测试是在 Windows 8 上使用 Python 2.7.10 运行的。

关于Python:一个不会被重新定位的列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37072953/

Python一个sizestrongsectionarrayslistoptimization

有关Python:一个不会被重新定位的列表的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

  3. ruby-on-rails - Rails - 一个 View 中的多个模型 - 2

    我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何

  4. ruby-on-rails - 渲染另一个 Controller 的 View - 2

    我想要做的是有2个不同的Controller，client和test_client。客户端Controller已经构建，我想创建一个test_clientController，我可以使用它来玩弄客户端的UI并根据需要进行调整。我主要是想绕过我在客户端中内置的验证及其对加载数据的管理Controller的依赖。所以我希望test_clientController加载示例数据集，然后呈现客户端Controller的索引View，以便我可以调整客户端UI。就是这样。我在test_clients索引方法中试过这个:classTestClientdefindexrender:template=>

  5. ruby - Highline 询问方法不会使用同一行 - 2

    设置:狂欢ruby1.9.2高线(1.6.13)描述:我已经相当习惯在其他一些项目中使用highline，但已经有几个月没有使用它了。现在，在Ruby1.9.2上全新安装时，它似乎不允许在同一行回答提示。所以以前我会看到类似的东西:require"highline/import"ask"Whatisyourfavoritecolor?"并得到:Whatisyourfavoritecolor?|现在我看到类似的东西:Whatisyourfavoritecolor?|竖线(|)符号是我的终端光标。知道为什么会发生这种变化吗？ 最佳答案

  6. ruby - 如何在续集中重新加载表模式？ - 2

    鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende

  7. ruby - RVM 使用列表[0] - 2

    是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。 最佳答案 这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论

  8. ruby-on-rails - active_admin 目录中的常量警告重新声明 - 2

    我正在使用active_admin，我在Rails3应用程序的应用程序中有一个目录管理，其中包含模型和页面的声明。时不时地我也有一个类，当那个类有一个常量时，就像这样:classFooBAR="bar"end然后，我在每个必须在我的Rails应用程序中重新加载一些代码的请求中收到此警告:/Users/pupeno/helloworld/app/admin/billing.rb:12:warning:alreadyinitializedconstantBAR知道发生了什么以及如何避免这些警告吗？ 最佳答案 在纯Ruby中:classA

  9. ruby-on-rails - 项目升级后 Pow 不会更改 ruby​​ 版本 - 2

    我在我的Rails项目中使用Pow和powifygem。现在我尝试升级我的ruby​​版本(从1.9.3到2.0.0，我使用RVM)当我切换ruby​​版本、安装所有gem依赖项时，我通过运行railss并访问localhost:3000确保该应用程序正常运行以前，我通过使用pow访问http://my_app.dev来浏览我的应用程序。升级后，由于错误Bundler::RubyVersionMismatch:YourRubyversionis1.9.3,butyourGemfilespecified2.0.0，此url不起作用我尝试过的:重新创建pow应用程序重启pow服务器更新战俘

  10. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

随机推荐