我有一个如下所示的列表推导式:
cart = [ ((p,pp),(q,qq)) for ((p,pp),(q,qq))\
in itertools.product(C.items(), repeat=2)\
if p[1:] == q[:-1] ]
C 是一个字典，其键是任意整数的元组。所有元组的长度都相同。最坏的情况是所有组合都应该包含在新列表中。这种情况经常发生。
举个例子，我有一个这样的字典:
C = { (0,1):'b',
(2,0):'c',
(0,0):'d' }
我希望结果是:
cart = [ (((2, 0), 'c'), ((0, 1), 'b'))
(((2, 0), 'c'), ((0, 0), 'd'))
(((0, 0), 'd'), ((0, 1), 'b'))
(((0, 0), 'd'), ((0, 0), 'd')) ]
因此，通过重叠，我指的是元组 (1,2,3,4) 和 (2,3,4,5) 有重叠部分 (2,3,4)。重叠部分必须位于元组的“边缘”。我只想要长度比元组长度短一个的重叠。因此 (1,2,3,4) 不与 (3,4,5,6) 重叠。另请注意，当删除元组的第一个或最后一个元素时，我们可能会得到非不同的元组，所有这些元组都必须与所有其他元素进行比较。 最后一点在我的第一个例子中没有强调。
我的代码执行时间的大部分时间花在了这个列表理解上。我总是需要 cart 的所有元素，因此在使用生成器时似乎没有加速。
我的问题是:是否有更快的方法？
我的一个想法是我可以尝试创建两个这样的新词典:
aa = defaultdict(list)
bb = defaultdict(list)
[aa[p[1:]].append(p) for p in C.keys()]
[bb[p[:-1]].append(p) for p in C.keys()]
并以某种方式将 aa[i] 中列表元素的所有组合与 bb[i] 中的列表元素合并为所有 i , 但我似乎也无法理解这个想法。
更新
tobias_k 和 shx2 添加的解决方案都比我的原始代码(据我所知)具有更好的复杂性。我的代码是 O(n^2) 而其他两个解决方案是 O(n)。然而，对于我的问题大小和组成，所有三个解决方案似乎或多或少同时运行。我想这与函数调用相关的开销以及我正在处理的数据的性质有关。特别是不同键的数量，以及键的实际组成，似乎有很大的影响。我知道后者是因为对于完全随机的 key ，代码运行速度要慢得多。我接受了 tobias_k 的回答，因为他的代码最容易理解。但是，我仍然非常欢迎有关如何执行此任务的其他建议。
最佳答案
您实际上是在正确的轨道上，使用字典来存储键的所有前缀。但是，请记住(据我了解这个问题)如果重叠小于 len-1，两个键也可以重叠，例如键 (1,2,3,4) 和 (3,4,5,6) 也会重叠。因此，我们必须创建一个包含所有键前缀的映射。 (如果我对此有误，只需删除两个内部 for 循环。)一旦我们有了这个映射，我们就可以再次遍历所有键，并检查它们是否有任何后缀是 prefixes 映射中的匹配键。 (更新:因为键可以重叠 w.r.t. 不止一个前缀/后缀，我们将重叠对存储在一个集合中。)
def get_overlap(keys):
# create map: prefix -> set(keys with that prefix)
prefixes = defaultdict(set)
for key in keys:
for prefix in [key[:i] for i in range(len(key))]:
prefixes[prefix].add(key)
# get keys with matching prefixes for all suffixes
overlap = set()
for key in keys:
for suffix in [key[i:] for i in range(len(key))]:
overlap.update([(key, other) for other in prefixes[suffix]
if other != key])
return overlap
(请注意，为简单起见，我只关心字典中的键，而不关心值。扩展它以返回值，或者将其作为后处理步骤执行，应该是微不足道的。)
整体运行时间应该只有 2*n*k，n 是键的数量，k 是键的长度。空间复杂度(prefixes映射的大小)应该在n*k和n^2*k之间，如果key非常多具有相同的前缀。
注意:以上答案适用于重叠区域可以有任意长度的更一般情况。对于您认为仅重叠一个比原始元组短的更简单的情况，以下应该足够并产生示例中描述的结果:
def get_overlap_simple(keys):
prefixes = defaultdict(list)
for key in keys:
prefixes[key[:-1]].append(key)
return [(key, other) for key in keys for other in prefixes[key[1:]]]
关于python - 获取字典中与同一字典中其他键重叠的所有键，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15292570/
我试图在一个项目中使用rake，如果我把所有东西都放到Rakefile中，它会很大并且很难读取/找到东西，所以我试着将每个命名空间放在lib/rake中它自己的文件中，我添加了这个到我的rake文件的顶部:Dir['#{File.dirname(__FILE__)}/lib/rake/*.rake'].map{|f|requiref}它加载文件没问题，但没有任务。我现在只有一个.rake文件作为测试，名为“servers.rake”，它看起来像这样:namespace:serverdotask:testdoputs"test"endend所以当我运行rakeserver:testid时
关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。
我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚
我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123
设置:狂欢ruby1.9.2高线(1.6.13)描述:我已经相当习惯在其他一些项目中使用highline，但已经有几个月没有使用它了。现在，在Ruby1.9.2上全新安装时，它似乎不允许在同一行回答提示。所以以前我会看到类似的东西:require"highline/import"ask"Whatisyourfavoritecolor?"并得到:Whatisyourfavoritecolor?|现在我看到类似的东西:Whatisyourfavoritecolor?|竖线(|)符号是我的终端光标。知道为什么会发生这种变化吗？ 最佳答案
当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested
我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？ 最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog
有没有办法在这个简单的get方法中添加超时选项？我正在使用法拉第3.3。Faraday.get(url)四处寻找，我只能先发起连接后应用超时选项，然后应用超时选项。或者有什么简单的方法？这就是我现在正在做的:conn=Faraday.newresponse=conn.getdo|req|req.urlurlreq.options.timeout=2#2secondsend 最佳答案 试试这个:conn=Faraday.newdo|conn|conn.options.timeout=20endresponse=conn.get(url
我有一个存储主机名的Ruby数组server_names。如果我打印出来，它看起来像这样:["hostname.abc.com","hostname2.abc.com","hostname3.abc.com"]相当标准。我想要做的是获取这些服务器的IP(可能将它们存储在另一个变量中)。看起来IPSocket类可以做到这一点，但我不确定如何使用IPSocket类遍历它。如果它只是尝试像这样打印出IP:server_names.eachdo|name|IPSocket::getaddress(name)pnameend它提示我没有提供服务器名称。这是语法问题还是我没有正确使用类？输出:ge
我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？ 最佳答案 为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c