3

我有一个列表，rods它由 和 的元组length组成position。 position对于给定的length. position我想找到最常见的杆长度，然后是所有唯一（按）相邻杆（包括最频繁）的出现总数。分解：

  • 首先我想找到最频繁的杆length。
  • 然后我想包括所有其他length按某些标准相邻的杆（在本例中为 +-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在for也有重叠lengths 13 and 12。

4

2 回答 2

2

我认为你的整体是一个合理的解决方案，如果有点过度压缩。我的主要建议是将其分解得更多。此外，如果可能，groupby最好使用 a或如果没有，而不是在这里使用。用于对预分类材料的惰性操作；如果它没有预先排序并且你不需要它是懒惰的，你可能不应该使用它。Counterdefaultdictgroupby

由于Nolen Royalty提供了defaultdict基于 - 的解决方案，因此我将Counter在此处使用，但请参阅下面的直接替换。结果是一个 O(n) 算法；因为你的排序，你的是 O(n log n)，所以这是一个轻微的改进。

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)

另请注意，我之前的代码有错误；现在已经修好了。

于 2012-04-19T14:25:59.240 回答
1

这是一个非常简单的方法，对我来说似乎很合理：

>>> 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])})
于 2012-04-19T14:20:37.660 回答