一意性の基準を満たす同様のアイテムの総数

Question

とpositionのタプルで構成されるrodsというリストがあります。 positionは、指定されたlengthに対して常に一意です。私は、最も頻繁なロッドの長さを見つけて、隣接するすべてのロッド（最も頻繁に含まれるもの）のユニークな（positionによる）ものの合計数を見つけたいと思います。壊れた：

• 最初に私は最も頻繁なロッド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に重複があり、lengths 13 and 12です。

ここ

Answer 1

ビット以上の圧縮場合、私は、あなたが全体的に合理的な解決策だと思います。私の主な提案はもう少しそれを分解することです。また、ここでgroupbyを使用する代わりに、可能であればCounterを使用することをお勧めします。そうでない場合はdefaultdictを使用することをお勧めします。 groupbyは、事前ソートされたマテリアルに対する遅延処理用です。それがあらかじめソートされておらず、怠け者である必要がない場合は、おそらくそれを使用すべきではありません。

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) 

：それはドロップイン置換の2行のためだ

length_freq = collections.defaultdict(int) 
for l in lengths: 
    length_freq[l] += 1 
best_length = max(length_freq, key=length_freq.get) 

はまた、私の以前のコードがエラーを持っていたことに注意してください。それは今修正されました。

Answer 2

が私にはかなり合理的なようで、かなり簡単な方法です：

>>> 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])})