草庐IT

python - 用于在已排序数据中快速插入和随机访问的数据结构

coder 2023-08-21 原文 

p = random_point(a,b)
#random_point() returns a tuple/named-tuple (x,y)
#0<x<a 0<y<b
if centers.validates(p):
    centers.insert(p)
#centers is the data structure to store points

在 centers 数据结构中，所有的 x 和 y 坐标都存储在两个单独的排序(升序)列表中，一个用于 x 和其他 y。 x 中的每个节点都指向对应的y，反之亦然，这样它们可以单独排序并仍然保持对属性:centers.get_x_of(y ) 和 centers.get_y_of(x)

我在数据结构中需要的属性:

  1. 快速插入，在已经排序的数据中(最好是 log n)
  2. 随机访问
  3. 分别对 x 和 y 排序，不丢失对属性

最初我想到使用简单的Lists，并使用Binary search 来获取用于插入任何新元素的索引。但我发现，可以使用像 AVL 或 B 树这样的自平衡树来改进它。我可以为 x 和 y 分别创建两棵树，每个节点都有一个额外的指针，可以从 x 树节点指向 y 树节点。

但我不知道如何在这些树中构建随机访问功能。函数 centers.validate() 尝试插入 x & y，并对相邻元素运行一些检查，这需要随机访问:

def validate(p):
    indices = get_index(p)
    #returns a named tuple of indices to insert x and y, Eg: (3,7)
    condition1 =  func(x_list[indices.x-1], p.x) and func(x_list[indices.x+1], p.x)
    condition2 =  func(y_list[indices.y-1], p.y) and func(y_list[indices.y+1], p.y)
    #func is some mathematical condition on neighboring elements of x and y
    return condition1 and condition2

在上面的函数中，我需要访问 x & y 的相邻元素 数据结构。我认为在树中实现它会使它复杂化。是否有任何数据结构组合可以实现这一目标？我正在用 Python 写这个(如果有帮助的话)

最佳答案

用 2 个字典保存值，键是另一个字典的键，该字典包含与此字典中的值相关的值。它需要为当前顺序维护每个字典的列表，以便在调用它时调用该字典的元素(您当前排序的字典值)。您将需要二进制或其他有效的排序来对每个字典进行操作以进行插入，尽管它实际上是使用该字典的顺序列表来查找每个中点键，然后检查该键的值。

关于python - 用于在已排序数据中快速插入和随机访问的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50721813/

python数据codesectioncenterspython-3.xlistdata-structurestree

有关python - 用于在已排序数据中快速插入和随机访问的数据结构的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

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

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

  3. ruby-on-rails - Rails 常用字符串(用于通知和错误信息等) - 2

    大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje

  4. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  5. ruby-on-rails - 在混合/模块中覆盖模型的属性访问器 - 2

    我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？ 最佳答案 您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah

  6. ruby - 续集在添加关联时访问many_to_many连接表 - 2

    我正在使用Sequel构建一个愿望list系统。我有一个wishlists和itemstable和一个items_wishlists连接表(该名称是续集选择的名称)。items_wishlists表还有一个用于facebookid的额外列(因此我可以存储opengraph操作)，这是一个NOTNULL列。我还有Wishlist和Item具有续集many_to_many关联的模型已建立。Wishlist类也有:selectmany_to_many关联的选项设置为select:[:items.*,:items_wishlists__facebook_action_id].有没有一种方法可以

  7. Ruby Sinatra 配置用于生产和开发 - 2

    我已经在Sinatra上创建了应用程序，它代表了一个简单的API。我想在生产和开发上进行部署。我想在部署时选择，是开发还是生产，一些方法的逻辑应该改变，这取决于部署类型。是否有任何想法，如何完成以及解决此问题的一些示例。例子:我有代码get'/api/test'doreturn"Itisdev"end但是在部署到生产环境之后我想在运行/api/test之后看到ItisPROD如何实现？ 最佳答案 根据SinatraDocumentation:EnvironmentscanbesetthroughtheRACK_ENVenvironm

  8. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  9. ruby - inverse_of 是否适用于 has_many？ - 2

    当我使用has_one时，它​​工作得很好，但在has_many上却不行。在这里您可以看到object_id不同，因为它运行了另一个SQL来再次获取它。ruby-1.9.2-p290:001>e=Employee.create(name:'rafael',active:false)ruby-1.9.2-p290:002>b=Badge.create(number:1,employee:e)ruby-1.9.2-p290:003>a=Address.create(street:"123MarketSt",city:"SanDiego",employee:e)ruby-1.9.2-p290

  10. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

随机推荐