有效地生成所有可能的4人团队组合，其中包含130个字符中的特定字符并计算某些值
问题描述 投票：2回答：1
我在内存中的字典中加载了大约130个字符（如在游戏角色中），每个字符包含一个字符的特定数据。
这个怎么运作？每个角色有2个聊天和22个反应。
在一个4人团队中，你会经历每一个角色，抓住他们的两个聊天，然后对其他三个角色进行反应并总结他们的反应值并重复。完成此操作后，抓住两个最高值（聊天不能重复）并将它们相加作为最终值。
试图“伪代码”：
results = []
for character in team
for chat in chats_of_character
chat_morale = 0
for remaining_character in team
if remaining_character is not character
grab from remaining_character reactions values the value of chat and sum it
to chat_morale
add (chat_morale, character, chat) to results as a tuple
sort results list by the first value of each tuple (chat_morale)
create a new list that removes duplicates based on the third item of every tuple in results
grab the two first (which would be the highest chat_morale out of them all) and sum both
chat_morale and return the result and total_morale
或者我当前使用的当前代码片段:(我省略了我按照相反的顺序按每个元组的第一个值对结果进行排序的部分，如果它们的选项值相同则删除元组，并根据第一个值获取两个最高元组如果需要，我会添加这些部分。）
def _camping(self, heroes):
results = []
for hero, data in heroes.items():
camping_data = data['camping']
for option in camping_data['options']:
morale = sum(heroes[hero_2]['camping']['reactions'][option]
for hero_2 in heroes if hero_2 != hero)
results.append( (morale, hero, option) )
一个简短的示例，说明其中一个字符值是什么样的：
"camping": {
"options": [
"comforting-cheer",
"myth"
],
"reactions": {
"advice": 8,
"belief": 0,
"bizarre-story": 1,
"comforting-cheer": 6,
...
因此，我正在尝试构建的是一个高效且快速的系统，可根据用户输入的字符为团队检索最佳X剩余成员。如果用户输入2个字符，我们将根据某些字符特定值的计算返回两个最适合的剩余字符，如果用户输入3个字符，则只返回一个成员。
在我的情况下，效率是必要的，因为我想为Discord机器人提供快速响应。
所以我提出了两种不同的尝试来解决这个问题：
尝试1：动态计算它们
all_heroes = self.game_data.get_all_heroes()
# Generate all possible combinations.
for combination in itertools.combinations(h.keys(), r=4):
# We want only combinations that contains for example the character 'Achates'.
if set(['achates']).issubset(combination):
# We grab the character data from the all heroes list to pass it to _camping.
hero_data = {hero: all_heroes[hero] for hero in combination}
self._camping(hero_data)
单独使用组合大约需要大约6秒钟（大约1300万个组合），并且根据固定字符的数量（在代码示例上面只有“Achates”），它将需要大约另外3到6秒。这通常会导致运行时间超过10秒，这是一个问题，因为我希望这个功能可以使用很多。
这个系统的缺点是我必须全部计算它们。
尝试2：预先计算所有可能的团队组合及其总体士气并将其存储在数据库中
到目前为止，这是我最接近解决此问题的方法。我生成了所有可能的团队组合（大约11-13百万），计算他们的总体士气并将他们的团队和士气总量存储在数据库中。计算所有内容并插入数据将需要一个多小时，但这不是一个问题，因为它只是一次性的事情，如果有一个新字符，那么插入的记录就会少一些。
使用索引，如果查询只包含一个字符，则只需要约50-60毫秒即可获取所有团队，按总士气排序并将其限制为50，如果团队包含2或3个字符，则时间更短。
这种尝试的问题在于如何将数据存储在列中，这对我来说是一个巨大的疏忽。虽然团队订单不会影响总体士气结果，但这是由itertools.combinations生成的。
在第一个问题上，我想要尝试的是搜索一个同时包含Cidd和Tenebria的团队，其余最好的两个成员是Watcher Schuri和Yufine，据说总共34个士气。但是，这是第二个查询证明的错误结果。有一个团队既包含Cidd和Tenebria，又有更高的总士气48，但由于Tenebria在第四列，以前的查询将无法捕捉它。
编辑1：我尝试为查询生成所有可能的条件，但仍导致查询速度慢。
尝试3 - 使用@bimsapi方法
这是我今天早些时候尝试过的，但我再次尝试逐步回答他的答案。我最终得到了这样的架构：
Table "public.campingcombinations"
Column | Type | Collation | Nullable | Default
--------------+---------+-----------+----------+-------------------------------------------------
id | bigint | | not null | nextval('campingcombinations_id_seq'::regclass)
team | text[] | | |
total_morale | integer | | |
Indexes:
"idx_team" gin (team)
表格看起来像这样：
yufinebotdev=# SELECT * FROM CampingCombinations LIMIT 5;
id | team | total_morale
--------+----------------------------------------+--------------
100001 | {achates,adlay,aither,alexa} | 26
100002 | {achates,adlay,aither,angelica} | 24
100003 | {achates,adlay,aither,aramintha} | 25
100004 | {achates,adlay,aither,arbiter-vildred} | 23
100005 | {achates,adlay,aither,armin} | 24
遗憾地给了我不同的结果。第一次查询将花费一秒钟，但这取决于字符，查询计划将是相同的。使用一个例子：Achates。
yufinebotdev=# EXPLAIN ANALYZE SELECT * FROM CampingCombinations WHERE team @> ARRAY['achates'] ORDER BY total_morale DESC LIMIT 50;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=188770.50..188776.33 rows=50 width=89) (actual time=1291.841..1302.641 rows=50 loops=1)
-> Gather Merge (cost=188770.50..221774.07 rows=282868 width=89) (actual time=1291.839..1302.633 rows=50 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Sort (cost=187770.47..188124.06 rows=141434 width=89) (actual time=1183.865..1183.868 rows=34 loops=3)
Sort Key: total_morale DESC
Sort Method: top-N heapsort Memory: 35kB
Worker 0: Sort Method: top-N heapsort Memory: 35kB
Worker 1: Sort Method: top-N heapsort Memory: 35kB
-> Parallel Bitmap Heap Scan on campingcombinations (cost=3146.68..183072.14 rows=141434 width=89) (actual time=119.376..1152.543 rows=119253 loops=3)
Recheck Cond: (team @> '{achates}'::text[])
Heap Blocks: exact=1860
-> Bitmap Index Scan on idx_team (cost=0.00..3061.82 rows=339442 width=0) (actual time=213.798..213.798 rows=357760 loops=1)
Index Cond: (team @> '{achates}'::text[])
Planning Time: 11.893 ms
Execution Time: 1302.707 ms
(16 rows)
第二个查询计划就像这个大约需要135毫秒。但是，我尝试了另一个角色'Serila'。
yufinebotdev=# EXPLAIN ANALYZE SELECT * FROM CampingCombinations WHERE team @> ARRAY['serila'] ORDER BY total_morale DESC LIMIT 50;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=188066.24..188072.07 rows=50 width=89) (actual time=30684.587..30746.121 rows=50 loops=1)
-> Gather Merge (cost=188066.24..224336.01 rows=310862 width=89) (actual time=30684.585..30746.110 rows=50 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Sort (cost=187066.22..187454.79 rows=155431 width=89) (actual time=30369.531..30369.535 rows=37 loops=3)
Sort Key: total_morale DESC
Sort Method: top-N heapsort Memory: 36kB
Worker 0: Sort Method: top-N heapsort Memory: 35kB
Worker 1: Sort Method: top-N heapsort Memory: 36kB
-> Parallel Bitmap Heap Scan on campingcombinations (cost=3455.02..181902.91 rows=155431 width=89) (actual time=519.121..30273.208 rows=119253 loops=3)
Recheck Cond: (team @> '{serila}'::text[])
Heap Blocks: exact=47394
-> Bitmap Index Scan on idx_team (cost=0.00..3361.76 rows=373035 width=0) (actual time=771.046..771.046 rows=357760 loops=1)
Index Cond: (team @> '{serila}'::text[])
Planning Time: 7.315 ms
Execution Time: 30746.199 ms
(16 rows)
30秒......但我想也许下面的查询会更快？不，大约在同一时间每个查询28到30秒。虽然我无法彻底测试它，但似乎“更进一步”的字符是查询速度越慢。
例如，用A或B“开始”的字符在第一次查询时需要1秒，而后续的字符需要90-100ms。但是我尝试使用像Serila这样的S角色，每个查询最多可以射击15秒，每个查询大约18秒开始用T开头的角色，或者以M 7秒首次查询开始的角色以及后续的查询900毫秒 - 1秒。
Attempt 4 - Same as above but with varchar[] columns
我不是只使用INSERT每个值，而是使用COPY，这大大减少了将值添加到表中所需的时间，我不太确定这是否会影响任何事情，但会提及它。另一个提到是我切换到运行在1个vCPU上的服务器和一个带有1GB内存的25GB SSD。
当前架构如下所示：
Table "public.campingcombinations"
Column | Type | Collation | Nullable | Default
--------------+---------------------+-----------+----------+-------------------------------------------------
id | bigint | | not null | nextval('campingcombinations_id_seq'::regclass)
team | character varying[] | | |
total_morale | integer | | |
Indexes:
"idx_camping_team" gin (team)
"idx_camping_team_total_morale" btree (total_morale DESC)
再次有不同的结果。一些单个字符查询在第一次被查询时最多需要大约10ms而在第一次查询时需要花费近2秒的其他查询，后续的查询取决于它们将需要的字符~10ms对2秒。
EXPLAIN ANALYZE SELECT * FROM CampingCombinations WHERE team @> ARRAY['yufine']::varchar[] ORDER BY total_morale DESC LIMIT 5;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.44..17.03 rows=5 width=89) (actual time=2.155..2.245 rows=5 loops=1)
-> Index Scan using idx_camping_team_total_morale on campingcombinations (cost=0.44..2142495.49 rows=645575 width=89) (actual time=2.153..2.242 rows=5 loops=1)
Filter: (team @> '{yufine}'::character varying[])
Rows Removed by Filter: 2468
Planning time: 2.241 ms
Execution time: 2.274 ms
(6 rows)
这是在查询之间保持一致的情况之一。但是，无论我运行多少次查询，都需要几秒钟。
EXPLAIN ANALYZE SELECT * FROM CampingCombinations WHERE team @> ARRAY['tieria']::varchar[] ORDER BY total_morale DESC LIMIT 5;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.44..17.21 rows=5 width=89) (actual time=4396.876..8626.916 rows=5 loops=1)
-> Index Scan using idx_camping_team_total_morale on campingcombinations (cost=0.44..2142495.49 rows=638566 width=89) (actual time=4396.875..8626.906 rows=5 loops=1)
Filter: (team @> '{tieria}'::character varying[])
Rows Removed by Filter: 129428
Planning time: 0.160 ms
Execution time: 8626.951 ms
(6 rows)
第二个查询将有类似的结果。计划时间为3.879ms，执行时间为6945.253ms。无论我运行多少次。出于某种原因，它似乎与该角色有关，但尚未在其他特定角色上找到此信息。如果我尝试具有该角色的2人团队，也会发生同样的情况。
EXPLAIN ANALYZE SELECT * FROM CampingCombinations WHERE team @> ARRAY['yufine', 'tieria']::varchar[] ORDER BY total_morale DESC LIMIT 5;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..874.29 rows=5 width=89) (actual time=24752.449..39808.550 rows=5 loops=1)
-> Index Scan using idx_camping_team_total_morale on campingcombinations (cost=0.43..1937501.21 rows=11086 width=89) (actual time=24752.444..39808.535 rows=5 loops=1)
Filter: (team @> '{yufine,tieria}'::character varying[])
Rows Removed by Filter: 439703
Planning time: 0.215 ms
Execution time: 39809.799 ms
(6 rows)
对这两个人团队的后续运行将花费几乎相同的时间，或多或少。现在，3人团队似乎与这个角色一起工作。 50-60ms。
我还发现一些2人团队花了将近1分钟而不管我查询了多少次，但是单独查询两个角色都有0个问题。
EXPLAIN ANALYZE SELECT * FROM CampingCombinations WHERE team @> ARRAY['purrgis', 'angelica']::varchar[] ORDER BY total_morale DESC LIMIT 5;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..821.41 rows=5 width=89) (actual time=33491.860..51059.420 rows=5 loops=1)
-> Index Scan using idx_camping_team_total_morale on campingcombinations (cost=0.43..1937501.21 rows=11800 width=89) (actual time=33491.857..51059.409 rows=5 loops=1)
Filter: (team @> '{purrgis,angelica}'::character varying[])
Rows Removed by Filter: 595184
Planning time: 0.139 ms
Execution time: 51060.318 ms
但是这两个角色分别是〜2ms。
我的问题是：在考虑性能并获得正确结果的同时，第二次尝试是否有可能的解决方案？或者，如果不可能，这个功能的更好方法是什么？
1个回答
1
投票
投票
预计算是一个很好的优化;为了更好地处理列布局，我建议使用PostgreSQL数组列来存储团队成员。
- 您可以在一列中存储合理任意数量的名称
- “包含”运算符
@>与顺序无关。即，如果输入为['foo'，'bar']为['bar'，'foo']，则会得到相同的结果 - 您可以索引列以便更快地搜索，但必须使用
gin类型 - 您可以扩展到其他团队规模，而不会显着改变架构。
在您的SQL / DDL中：
#simplified table definition:
create table campingcombinations (
id bigserial,
members text[],
morale int
);
create index idx_members on campingcombinations using gin ('members');
在你的Python中：
# on insert
for team in itertools.combinations(source_list, r=4):
team = [normalize(name) for name in team] #lower(), strip(), whatever
morale = some_function() #sum, scale, whatever
stmt.execute('insert into campingcombinations (members, morale) values (%s, %s)', (team, morale,))
# on select
stmt.execute('select * from campingcombinations where members @> %s order by morale desc', (team,))
for row in stmt.fetchall():
#do something
在大多数情况下，psycopg2驱动程序处理类型转换，但有一个问题：根据您如何定义数组，您可能需要进行转换。例如，我将列定义为members varchar[]，因此“contains”子句需要一个强制转换，如下所示：where members @> %s::varchar[]。默认情况下，输入数组将被视为text[]。如果将列定义为text[]，则应该没有问题。
最新问题
- tailwind.css 未在 Heroku 的 Rails 7 项目中生成
- 如何从 matplotlib/seaborn 图中删除或隐藏 y 轴刻度标签
- Docker 使用 glob 模式复制文件？
- Webpack4 npm start 未捕获类型错误
- nil:NilClass 的未定义方法 `each'...为什么？
- K8s FQDN EndpointSlice 无法被入口识别？
- 如何在app_commands.Choice中从数据库获取数据？
- 如何处理可变大小的 Zig 结构字符串
- 查找行值比前两行组合大 X2 的所有行的最有效方法
- 更改 Excel 中的默认“分隔符”
- MSSQL - 查找行值比前两行组合大 X2 的所有行的最有效方法
- 允许用户仅使用JS同时选择多个视频
- 分配标签：所有值均为 false
- constexpr 数据成员和单一定义规则
- 为什么 JavaScript 双边字符串文字插值不是二次的？
- 如何将二维 numpy 数组变成三维数组？
- 如何在C中识别字符串中的减法？
- 在Konsole中执行命令时显示时间
- 如何卸载ag-grid-community
- 在 Android SQLite 上执行“PRAGMAcompile_options”没有输出任何内容
© www.soinside.com 2019 - 2024. All rights reserved.