V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hhhhhh123
V2EX  ›  C

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

  •  
  •   hhhhhh123 · 36 天前 · 1043 次点击
    这是一个创建于 36 天前的主题,其中的信息可能已经有所发展或是发生改变。

    首先,通过上一个帖子,确实提示很快的速度,总体来说提高了 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);
    						}
    					};
    
    				}
    			}
    		}
    	}
    }
    

    }

    19 条回复    2022-07-07 09:09:36 +08:00
    hhhhhh123
        1
    hhhhhh123  
    OP
       36 天前
    新手代码, 现学现用的。勿喷
    hhhhhh123
        2
    hhhhhh123  
    OP
       36 天前
    @hhhhhh123 目前 一轮需要 58ms, 还是比较慢的,应该还是有很大的提升空间。。
    hhhhhh123
        3
    hhhhhh123  
    OP
       36 天前
    @hhhhhh123 index_ = min_v_index_lst[min_i] + c_; 这里是不需要 + C_的 粘贴错了
    cdxjcl123
        4
    cdxjcl123  
       36 天前
    第一局,A 的 tie 不应该是 1/1=1 吗?
    hhhhhh123
        5
    hhhhhh123  
    OP
       36 天前
    @cdxjcl123 第一局最低分是 50 ,其他两个人是 60 ,只能算第一个人获胜, 其他人就是输 ,如果获胜的人数大于 1 ,那么这些获胜的人只能平分。
    hhhhhh123
        6
    hhhhhh123  
    OP
       36 天前
    @cdxjcl123 因为这是我公司的业务逻辑是这样, 和生活中打牌,打游戏什么的还是有一点出入
    bloodspasm
        7
    bloodspasm  
       36 天前
    `for (int j = 0; j < c_; j++)`
    hhhhhh123
        8
    hhhhhh123  
    OP
       36 天前
    @bloodspasm 怎么说?
    bloodspasm
        9
    bloodspasm  
       36 天前
    大概理解是 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
        10
    bloodspasm  
       36 天前
    不应该 return
    应该是 continue
    hhhhhh123
        11
    hhhhhh123  
    OP
       36 天前
    @bloodspasm 是这样的,poker_lst 总共是要执行 C ( m, 5 ) 但是玩家分数不是完全基于这五个来进行计算的, 还有就是每个玩家自带的两个参数,也就是说有 7 个参数,会传入到 evaluate_7cards() 函数 ,然后返回一个分数。
    hhhhhh123
        12
    hhhhhh123  
    OP
       36 天前
    @bloodspasm 也可以这么理解, 五个参数 其实就是 温度 湿度 大气压等参数, 另外两个参数就是自己 的 触觉,嗅觉等,然后进行计算,在同温度 湿度 大气压 下, 每个人的分数是多少 。因为每个人的自带的参数 如嗅觉的灵敏性不同,所以结果不同
    bloodspasm
        13
    bloodspasm  
       36 天前
    @hhhhhh123 嗯.我是提供一个思路不算是解决方法,推荐可以在一些情况下减少循环次数.具体就是你的业务功能了,因为我觉得正常 C (m,5) 循环已经没法再少了.现在是否可以在这里优化一下,不用全部执行完.
    hhhhhh123
        14
    hhhhhh123  
    OP
       36 天前
    @bloodspasm 我个人认为 那个 计算 win tie 次数的地方 应该可以合在一起 ,,但是一直没有思路
    bloodspasm
        15
    bloodspasm  
       36 天前
    @hhhhhh123
    可以的,你的找最小值玩家换成 min_user_list 数组而且不是 min_v_index 下标
    如果 min_user_list 的 length == 1 做 win 操作 , 否则直接对数组做 tie 操作就行
    hhhhhh123
        16
    hhhhhh123  
    OP
       36 天前
    @bloodspasm min_v_index_lst 这个数组 里面存的就是最小值玩家的下标。min_v_index 只是统计最小值玩家有几个, 也就是等于 min_v_index_lst 的长度.
    bloodspasm
        17
    bloodspasm  
       36 天前
    @hhhhhh123
    的确 是我看漏了.
    我觉得你的优化应该在 C (m,5) 这里 ,因为这个才是耗时的地方
    hsfzxjy
        18
    hsfzxjy  
       36 天前
    如果对于每个参数组 (ii, jj, k, l, m) 而言运算是独立的,也就是参数是 (ii1, jj1, k1, l1, m1) 时的运算不依赖于参数是 (ii2, jj2, k2, l2, m2) ,那我觉得你可以尝试并行化这 C(m,5)组运算,再把它们的结果合起来
    hhhhhh123
        19
    hhhhhh123  
    OP
       35 天前
    @bloodspasm
    @hsfzxjy 这个 C(m, 5) 我个人觉得是很难优化, 首先确定一点 这个组合数是固定的,也就是说上面是 52 个数据就是 C(52,5) ,这个循环次数是少不了的, 无非就是首先 用递归跑出所有结果,然后将所有结果存到一个数组里面, 然后在遍历。 要么就是 生成 C(52, 5) 的同时,同时去进行逻辑操作。 难道还有其他的思路吗?
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1584 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 42ms · UTC 17:32 · PVG 01:32 · LAX 10:32 · JFK 13:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.