基于上一个帖子 C 语言 循环下 创建动态数组 非常慢 应该如何解决？ 贴代码啦

[hhhhhh123]

首先，通过上一个帖子，确实提示很快的速度，总体来说提高了 3.5 倍左右。 非常感谢大家！！！ 我的问题是: 想在提升时间复杂度, 目前个人觉得能在提升速度的地方只有 比较那块能操作，但是已经黔驴技穷了.

void main() {

// 以下简介是通过 举例来进行说明
// 类似于多人打游戏，假设三个人(A,B,C)， 每局每个人会有一个分数， 一般来说分高则获胜(这里取最低，不影响理解)
// 最终通过 N 个迭代计算各个玩家的 Equity （ Equity = win+tie ）, win , tie 数。
// 如何计算 win: 每局只有一个人获胜, 至多一个，则+1 ，
// 如何计算 tie: 1 / n , 其中 n 为当局分数最低的人数

// 第 1 局 A:50 , b: 60 , c: 60, 故 A 获胜. win-> A = 0 + 1 
// 最终结果：win: A=1 , B = 0, C = 0    tie-> A: 0 , B : 0, C : 0
// 
// 第 2 局 A:50 , b: 50 , c: 70, 故 A, B 平. tie-> A = (1/2) , B = (1/2)
// 最终结果：win: A=1 , B = 0, C = 0    tie-> A: 0.5 , B : 0.5, C : 0
// 
// 第 3 局 A:100 , b: 100 , c: 100, 故 A, B, C 平. tie: A=1/3=0.33 , B=1/3=0.33, C=1/3=0.33 
// 最终结果：win: A=1 , B = 0, C = 0    tie-> A: 0.5+0.33=0.83, B=0.5+0.33=0.83,  C=0.33

// 假设只玩了三局, 那么本次游戏所有的胜率为: 
// 最后结果全部除以 3 ,因为本次玩了 3 局
// A: {Equity: 1.83, win: 1, tie: 0.83} ->  {Equity: 1.83/3, win: 1/3, tie: 0.83/3} ->  {Equity: 0.61, win: 0.33, tie: 0.28}
// B: {Equity: 0.83, win: 0, tie: 0.83} ->  {Equity: 0.83/3, win: 0/3, tie: 0.83/3} ->  {Equity: 0.28, win: 0, tie: 0.28}
// C: {Equity: 0.33, win: 0, tie: 0.33} ->  {Equity: 0.33/3, win: 0/3, tie: 0.33/3} ->  {Equity: 0.11, win: 0, tie: 0.11}
//
// 如何验证结果是否正确: 将所有的 Equity 相加是否约等于 1. 0.61+0.28+0.11 = 1; 故正确！

// 下面简单阐述下代码逻辑
// 使用两个数组储存结果, win 数组 和 tie 数组， 分别记录次数，两个数组的长度为本次游戏的人数
// 使用上面的例子可以演变为: 
// 第一局: win 数组 -> [1, 0, 0] tie 数组-> [0, 0, 0]
// 第二局: win 数组 -> [1, 0, 0] tie 数组-> [0.5, 0.5, 0]
// 第三局: win 数组 -> [1, 0, 0] tie 数组-> [0.83, 0.33, 0.33]
// 最后只需要用 n(n 为游戏次数) 除以这两个数组各个元素就可以了

int h_ = 1; // 为了方便 本次游戏次数 1 故忽略次数 for 循环 
int c_ = 2; // 玩家个人数

int* res_card_lst = (int*)malloc(c_ * sizeof(int));
int* min_v_index_lst = (int*)malloc(c_ * sizeof(int)); 
int* score_arr_win = (int*)calloc(c_, sizeof(int)); // win 数组
float* score_arr_tie = (float*)calloc(c_, sizeof(float)); // tie 数组

int min_v_index; int min_score;
int ii; int jj; int k; int l; int m;
int a_; int min_i; int index_;

int poker_lst[] = {
  0,
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
  11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
  21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
  31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
  41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
  51, };
int len_poker_lst = 52;
// 五层是 将 poker_lst 进行不重复组合。 
// 1.要么先组合成，在遍历,遍历的同时做逻辑处理。
// 2. 要么同时生成排列组合的时候 进行逻辑处理, 一下就是采用此方案。
for (ii = 0; ii < len_poker_lst; ii++) {
	for (jj = ii + 1; jj < len_poker_lst; jj++) {
		for (k = jj + 1; k < len_poker_lst; k++) {
			for (l = k + 1; l < len_poker_lst; l++) {
				for (m = l + 1; m < len_poker_lst; m++) {
					// 下面是主要逻辑
					min_score = 7462;
					// 用数组进行储存结果 同时获取最小值的结果
					for (int j = 0; j < c_; j++) {
						// res 其实就是通过上面的循环拿到组合,进行一些逻辑操作，最终返回一个 int 数值.
						// 可以理解为游戏分数, 
						// 可以随便写死，写死无非就是全部都是平局, 
						// 本次主要是测试时间复杂度,这个函数不能动,和这个函数也无太大关系
						//res = evaluate_7cards(poker_lst[ii], poker_lst[jj], poker_lst[k], poker_lst[0], poker_lst[1],
						//	          玩家数据 1 , 玩家数据 2);
						res = 666;  
						res_card_lst[j] = res;
						if (res < min_score) min_score = res;
					}
					// 找到最小值的玩家的下标, 同时记录最小值玩家的个数
					min_v_index = 0;
					for (a_ = 0; a_ < c_; a_++) {
						if (res_card_lst[a_] == min_score) {
							min_v_index_lst[min_v_index] = a_;
							min_v_index += 1;
						}
					}
					//  如果最小值玩家只有一个，那么就直接 win 数组 += 1
					if (min_v_index == 1) {
						score_arr_win[min_v_index_lst[0]] = score_arr_win[min_v_index_lst[0]]+ 1;
					}
					else {
						// 最小值玩家多个情况, 遍历玩家下标，在 tie 数组进行计算 (1 / n)
						for (min_i = 0; min_i < min_v_index; min_i++) {
							index_ = min_v_index_lst[min_i] + c_;
							score_arr_tie[index_] = score_arr_tie[index_] + (1.0 / min_v_index);
						}
					};

				}
			}
		}
	}
}

}

[hhhhhh123]

新手代码， 现学现用的。勿喷

[hhhhhh123]

@hhhhhh123 目前 一轮需要 58ms, 还是比较慢的,应该还是有很大的提升空间。。

[hhhhhh123]

@hhhhhh123 index_ = min_v_index_lst[min_i] + c_; 这里是不需要 + C_的 粘贴错了

[cdxjcl123]

第一局,A 的 tie 不应该是 1/1=1 吗？

[hhhhhh123]

@cdxjcl123 第一局最低分是 50 ，其他两个人是 60 ，只能算第一个人获胜， 其他人就是输 ，如果获胜的人数大于 1 ，那么这些获胜的人只能平分。

[hhhhhh123]

@cdxjcl123 因为这是我公司的业务逻辑是这样， 和生活中打牌，打游戏什么的还是有一点出入

[bloodspasm]

`for (int j = 0; j < c_; j++)`

[hhhhhh123]

@bloodspasm 怎么说？

[bloodspasm]

大概理解是 C (m,5) 取出所有情况
1. 有胜负(有最低分)情况直接判断胜负 算 win
2. 平局情况计算 tie

我想到的是拿其实可以先对 list 进行一次排序得到排序后的 poker_lst 发现
取的是 0, 1, 2, 3, 4 必输 => 0, 1, 2, 3 + 小于 29 必输
取的是 47, 48, 49, 50, 51 必胜 => 48, 49, 50, 51 + 大于 27 必胜
...
其实是可以在预处理找到的 你的循环就可以 return 了

[bloodspasm]

不应该 return
应该是 continue

[hhhhhh123]

@bloodspasm 是这样的，poker_lst 总共是要执行 C （ m, 5 ） 但是玩家分数不是完全基于这五个来进行计算的， 还有就是每个玩家自带的两个参数，也就是说有 7 个参数，会传入到 evaluate_7cards() 函数 ，然后返回一个分数。

[hhhhhh123]

@bloodspasm 也可以这么理解， 五个参数 其实就是 温度 湿度 大气压等参数， 另外两个参数就是自己 的 触觉，嗅觉等，然后进行计算，在同温度 湿度 大气压 下， 每个人的分数是多少 。因为每个人的自带的参数 如嗅觉的灵敏性不同，所以结果不同

[bloodspasm]

@hhhhhh123 嗯.我是提供一个思路不算是解决方法,推荐可以在一些情况下减少循环次数.具体就是你的业务功能了,因为我觉得正常 C (m,5) 循环已经没法再少了.现在是否可以在这里优化一下,不用全部执行完.

[hhhhhh123]

@bloodspasm 我个人认为 那个 计算 win tie 次数的地方 应该可以合在一起 ，，但是一直没有思路

[bloodspasm]

@hhhhhh123
可以的,你的找最小值玩家换成 min_user_list 数组而且不是 min_v_index 下标
如果 min_user_list 的 length == 1 做 win 操作 , 否则直接对数组做 tie 操作就行

[hhhhhh123]

@bloodspasm min_v_index_lst 这个数组 里面存的就是最小值玩家的下标。min_v_index 只是统计最小值玩家有几个， 也就是等于 min_v_index_lst 的长度.

[bloodspasm]

@hhhhhh123
的确 是我看漏了.
我觉得你的优化应该在 C (m,5) 这里 ,因为这个才是耗时的地方

[hsfzxjy]

如果对于每个参数组 (ii, jj, k, l, m) 而言运算是独立的，也就是参数是 (ii1, jj1, k1, l1, m1) 时的运算不依赖于参数是 (ii2, jj2, k2, l2, m2) ，那我觉得你可以尝试并行化这 C(m,5)组运算，再把它们的结果合起来

[hhhhhh123]

@bloodspasm
@hsfzxjy 这个 C(m, 5) 我个人觉得是很难优化， 首先确定一点 这个组合数是固定的，也就是说上面是 52 个数据就是 C(52,5) ，这个循环次数是少不了的， 无非就是首先 用递归跑出所有结果，然后将所有结果存到一个数组里面， 然后在遍历。 要么就是 生成 C(52, 5) 的同时，同时去进行逻辑操作。 难道还有其他的思路吗？