携帯基地局や公共施設の配置最適化の問題っぽい話ですね。
(一瞬、水着画像を水玉コラに加工するのの自動化? と思いましたがそれだと逆ですか)
ここでは便宜的に、Aの要素を携帯電話、Bの要素を基地局候補値と呼ぶことにします。
実用的な速度で実現するヒントとしては
・地図全体を5キロ区切りのマス目に区切り、携帯電話を該当するマス目に所属させます。
・基地局候補値から5キロ以内という判定対象は、周囲9マスの所属携帯電話だけに限定できます。
このアイディアをプログラムにするとこんな感じですかね。
python
1from random import random
2
3r = 5.0
4ew = 5000.0
5ns = 5000.0
6phone_count = 1000000
7site_count = 1000
8
9
10def test_data():
11 # 電話機の座標を 1000000個
12 phones = {(random() * ew, random() * ns) for _ in range(phone_count)}
13
14 # 基地局候補値の座標を 1000個
15 sites = {(random() * ew, random() * ns) for _ in range(site_count)}
16
17 return phones, sites
18
19
20def map_phones(phones):
21 """
22 5キロ区切りのマス目に電話機を割り振る
23 """
24 phones_map = {}
25 for phone in phones:
26 x, y = phone
27 bucket = (int(x / r), int(y / r))
28 if bucket in phones_map:
29 phones_map[bucket].add(phone)
30 else:
31 phones_map[bucket] = {phone}
32 return phones_map
33
34
35def covering_phones(phones_map, site):
36 """
37 候補地がカバーする電話機
38 """
39 x, y = site
40 site_bucket = (int(x / r), int(y / r))
41
42 for dx in range(-1, 2):
43 for dy in range(-1, 2):
44 bucket = (site_bucket[0] + dx, site_bucket[1] + dy)
45 for phone in phones_map.get(bucket, set()):
46 phone_x, phone_y = phone
47 if (x - phone_x)**2 + (y - phone_y)**2 <= r**2:
48 yield phone
49
50
51def remove_phones(phones_map, phones):
52 """
53 マス目マップから携帯電話を一括削除
54 """
55 for bucket, content in phones_map.items():
56 content.difference_update(phones)
57
58
59def enumerate_covering_site(phones, sites):
60 """
61 カバーできる電話機の数が多い順に基地局候補値と収容される電話機を返していきます
62 """
63
64 phones_map = map_phones(phones)
65
66 while phones or sites:
67 greatest_site = None
68 max_covered_phones = set()
69
70 for site in sites:
71 covered_phones = set(covering_phones(phones_map, site))
72 if len(covered_phones) >= len(max_covered_phones):
73 greatest_site = site
74 max_covered_phones = covered_phones
75
76 yield greatest_site, max_covered_phones
77
78 sites.remove(greatest_site)
79 remove_phones(phones_map, max_covered_phones)
80 phones.difference_update(max_covered_phones)
81
82
83def main():
84 phones, sites = test_data()
85 for site, covered_phones in enumerate_covering_site(phones, sites):
86 print(site)
87 print(covered_phones)
88
89
90main()