符合唯一性标准的同类物品总数
符合唯一性标准的同类物品总数
提问于 2012-04-19 14:02:24
我有一个列表，rods是由length的元组和position组成的。对于给定的position，length总是唯一的。我想找出最频繁的杆长，然后是所有唯一的(由position)相邻的杆的总发生次数(包括最频繁的)。分解：
首先，我想找出最常见的杆-- length.
- Then，我想用某种标准(本例中为+-1)包括所有其他有相邻的杆(在这个例子中是+-1)，但前提是它们有一个唯一的位置--没有考虑到(或者是原始组中的“最频繁的”棒，或者是通过满足相邻的标准而添加到这个组中的‘新棒’)。
- 和找到这个新的总频率。
通过对集合进行排序和使用集合，我可以通过以下方式完成这一任务，但也许有更好的解决方案：
import itertools
#tuples of (length, position)
rods = [(18, 21), (17, 2), (15, 3), (14, 21), (14, 5), (13, 6), (13, 7),
(13, 8), (13, 9), (13, 10), (13, 11), (13, 12), (13, 13), (13, 14),
(13, 15), (13, 16), (13, 17), (13, 18), (13, 19), (13, 20), (13, 21),
(13, 22), (13, 23), (13, 24), (13, 25), (13, 26), (12, 5), (12, 21),
(12, 2)]
lengths = [length for length, position in rods]
#gives tuples of lengths and their frequencies:
length_freq = (sorted([(k,len(list(j))) for k,j in itertools.groupby(sorted(lengths))],
key=lambda x: x[1],reverse=1))
best_length = length_freq[0][0]
#cumulative frequency of rods near best_length, with unique position:
tally = (len(set((best_length,v) for j,v in rods
if best_length - 1 <= j <=best_length + 1)))
print length_freq
#output:
#[(13, 21), (12, 3), (14, 2), (15, 1), (17, 1), (18, 1)]
print tally
#output:
#23 注23是这个测试数据的正确答案。由于带有length= 14的两根杆都定位在点上，因此也被length=15 ( 21和5位置)的杆所占据。position=21的lengths 13 and 12也有重叠。
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-04-19 14:25:59
我认为你的整体解决方案是合理的，如果有点压缩的话。我的主要建议是把它再细分一点。此外，与其在这里使用groupby，不如在可能的情况下使用Counter，如果不使用，则使用defaultdict。groupby用于对预先排序的材料进行懒惰操作；如果它不是预排序的，并且您不需要它来懒惰，那么您可能不应该使用它。
由于Nolen Royalty提供了defaultdict-based解决方案，我将在这里使用Counter，但请参阅下面的插入替换。结果是一个O(n)算法；由于您的排序，您的排序是O(n log )，所以这是一个轻微的改进。
import collections
#tuples of (length, position)
rods = [(18, 21), (17, 2), (15, 3), (14, 21), (14, 5), (13, 6), (13, 7),
(13, 8), (13, 9), (13, 10), (13, 11), (13, 12), (13, 13), (13, 14),
(13, 15), (13, 16), (13, 17), (13, 18), (13, 19), (13, 20), (13, 21),
(13, 22), (13, 23), (13, 24), (13, 25), (13, 26), (12, 5), (12, 21),
(12, 2)]
lengths = (length for length, position in rods)
length_freq = collections.Counter(lengths)
((best_length, _),) = length_freq.most_common(1)
print best_length
#cumulative frequency of rods near best_length, with unique position:
rod_filter = ((l, p) for l, p in rods if best_length - 1 <= l <= best_length + 1)
tally = len(set((best_length, p) for l, p in rod_filter))
print length_freq
print tally由于您不能使用Counter，为了完整性起见，这里有一个替代方案。这是对这两行的替换：
length_freq = collections.Counter(lengths)
((best_length, _),) = length_freq.most_common(1)只需将其替换为：
length_freq = collections.defaultdict(int)
for l in lengths:
length_freq[l] += 1
best_length = max(length_freq, key=length_freq.get)还请注意，我以前的代码有一个错误；它现在是固定的。
Stack Overflow用户
发布于 2012-04-19 14:20:37
下面是一个非常简单的方法，在我看来是相当合理的：
>>> from collections import defaultdict
>>> rods = [(18, 21), (17, 2), (15, 3), (14, 21), (14, 5), (13, 6), (13, 7),
... (13, 8), (13, 9), (13, 10), (13, 11), (13, 12), (13, 13), (13, 14),
... (13, 15), (13, 16), (13, 17), (13, 18), (13, 19), (13, 20), (13, 21),
... (13, 22), (13, 23), (13, 24), (13, 25), (13, 26), (12, 5), (12, 21),
... (12, 2)]
>>> neighbor_cutoff = 1
>>> length_to_count = defaultdict(int)
>>> neighbors_for_length = defaultdict(set)
>>> for rod in rods:
... length_to_count[rod[0]] += 1
... neighbors_for_length[rod[0]].add(rod[1])
... for i in range(1, neighbor_cutoff+1):
... neighbors_for_length[rod[0]-i].add(rod[1])
... neighbors_for_length[rod[0]+i].add(rod[1])
...
>>> sorted([(length, length_to_count[length]) for length in length_to_count], key=lambda x: x[1], reverse=True)
[(13, 21), (12, 3), (14, 2), (15, 1), (17, 1), (18, 1)]
>>> [(length, len(neighbors_for_length[length])) for length in neighbors_for_length]
[(11, 3), (12, 23), (13, 23), (14, 23), (15, 3), (16, 2), (17, 2), (18, 2), (19, 1)]
>>> sorted(_, key=lambda x: x[1], reverse=True)
[(12, 23), (13, 23), (14, 23), (11, 3), (15, 3), (16, 2), (17, 2), (18, 2), (19, 1)]
>>> neighbors_for_length
defaultdict(<type 'set'>, {11: set([2, 5, 21]), 12: set([2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]),
13: set([2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]),
14: set([3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]),
15: set([3, 21, 5]), 16: set([2, 3]), 17: set([2, 21]), 18: set([2, 21]), 19: set([21])})页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/10229751
复制相关文章
相似问题
腾讯云开发者
