Project1

标题: Array#shuffle! #shuffle #samples (优化） [打印本页]
作者: RPGzh500223    时间: 2022-1-22 17:54
标题: Array#shuffle! #shuffle #samples (优化）
本帖最后由 RPGzh500223 于 2022-2-2 21:32 编辑

RUBY 代码复制
  1. class Array
  2.   def to_int
  3.     self.object_id
  4.   end
  5.  
  6.   CallWndProc = Win32API.new('user32.dll', 'CallWindowProc', 'PLLLL', 'L')
  7.  
  8.   CodeSeed = [85,137,229,139,77,8,3,77,12,187,1,0,0,0,139,69,16,247,227,
  9.     3,69,20,137,195,193,232,16,37,255,127,0,0,226,236,137,216,201,
  10.     194,16,0].pack('C*')
  11.   @@seed = CallWndProc.call(CodeSeed, rand(41), 10, 214013, 2531011)
  12.  
  13.   CodeShuffle = [85,137,229,139,93,8,139,76,27,8,131,249,1,118,55,139,116,27,
  14.     16,73,141,60,142,139,93,12,139,69,16,247,227,3,69,20,137,195,193,232,16,
  15.     37,255,127,0,0,49,210,65,247,241,73,193,226,2,1,242,255,50,255,55,143,2,
  16.     143,7,131,239,4,226,214,137,216,201,194,16,0].pack('C*')
  17.  
  18.   def shuffle!
  19.     @@seed = CallWndProc.call(CodeShuffle, self, @@seed, 214013, 2531011)
  20.     self
  21.   end
  22.  
  23.   def shuffle
  24.     (self + []).shuffle!
  25.   end
  26.  
  27.   def sample
  28.     self[rand(self.size)]
  29.   end
  30.  
  31.   CodeSamples = [85,137,229,139,69,8,139,92,0,8,139,68,0,16,137,69,8,141,116,
  32.     152,252,139,69,12,139,76,0,8,81,139,68,0,16,141,124,136,252,184,253,67,3,
  33.     0,247,101,20,5,160,51,130,1,137,69,20,193,232,16,37,255,127,0,0,49,210,
  34.     247,243,75,193,226,2,3,85,8,255,50,255,54,143,2,143,6,137,23,131,239,4,
  35.     131,238,4,226,203,89,131,198,4,139,6,131,199,4,139,23,137,7,255,50,255,
  36.     54,143,2,143,6,226,234,139,69,20,201,194,16,0].pack('C*')
  37.  
  38.   def samples(n)
  39.     len = self.size
  40.     return self[rand(len), 1] if n < 2
  41.     n = len if n > len
  42.     return self.shuffle if n == len
  43.     result = Array.new(n)
  44.     @@seed = CallWndProc.call(CodeSamples, self, result, 0, @@seed)        
  45.     result
  46.   end
  47. end


\s又是一年……，想起也在论坛发帖问过Array#sample\s

使用 Fisher-Yates 算法(几十年前的……，也是目前网上搜索最常见的洗牌算法)
随机则是参照C语言的rand()函数写的，使用该方法的数组大小不能超过0x7FFF

Array#shuffle!  => array_obj
Array#shuffle   => array_obj
Array#sample  => array_element_obj
Array#samples => array_obj

该帖方法效率基本为RUBY的同名或类似方法的十分之一 (RMVA测试)
由于是调用win32api的CallWidnowProc实现(最简单的code测试 8.5-8.6W次/秒……)，较小运算量比不过ruby方法直接执行，运算量大的情况RMXP基本用不到……

优化：
①参数的改变，看起来更直接( 使用obj；原来obj.object_id。参数实质没变，效率我是感觉没差）
②优化了Array#samples，原先并没有用好result的内存……


关于效率测试，具体次数与电脑性能相关（my_**方法为该帖的方法）

RUBY 代码复制
  1. # 非代码
  2. =begin
  3. rmva测试
  4. 【(0...10).to_a】
  5.   Array#suffle! :                         148031次/秒
  6.   Array#suffle :                          121141次/秒
  7.   Array#my_suffle! :                       68741次/秒
  8.   Array#my_suffle :                        60609次/秒
  9.   Array#sample(5) :                       131731次/秒
  10.   Array#my_samples(5) :                    55161次/秒
  11.   Array#sample(100) :                     126950次/秒
  12.   Array#my_samples(100) :                  56554次/秒
  13.   Array#sample(200) :                     126669次/秒
  14.   Array#my_samples(200) :                  56390次/秒
  15.  
  16. 【(0...100).to_a】
  17.   Array#suffle! :                          70314次/秒
  18.   Array#suffle :                           60290次/秒
  19.   Array#my_suffle! :                       59772次/秒
  20.   Array#my_suffle :                        51764次/秒
  21.   Array#sample(5) :                       131434次/秒
  22.   Array#my_samples(5) :                    55044次/秒
  23.   Array#sample(100) :                      67510次/秒
  24.   Array#my_samples(100) :                  49509次/秒
  25.   Array#sample(200) :                      66997次/秒
  26.   Array#my_samples(200) :                  49541次/秒
  27.  
  28. 【(0...500).to_a】
  29.   Array#suffle! :                          20981次/秒
  30.   Array#suffle :                           19097次/秒
  31.   Array#my_suffle! :                       38931次/秒
  32.   Array#my_suffle :                        32487次/秒
  33.   Array#sample(5) :                       131307次/秒
  34.   Array#my_samples(5) :                    54454次/秒
  35.   Array#sample(100) :                      57960次/秒
  36.   Array#my_samples(100) :                  45561次/秒
  37.   Array#sample(200) :                      41348次/秒
  38.   Array#my_samples(200) :                  38972次/秒
  39.  
  40. 【(0...1000).to_a】
  41.   Array#suffle! :                          11331次/秒
  42.   Array#suffle :                           10317次/秒
  43.   Array#my_suffle! :                       27282次/秒
  44.   Array#my_suffle :                        22167次/秒
  45.   Array#sample(5) :                       130697次/秒
  46.   Array#my_samples(5) :                    55175次/秒
  47.   Array#sample(100) :                      49234次/秒
  48.   Array#my_samples(100) :                  45636次/秒
  49.   Array#sample(200) :                      36858次/秒
  50.   Array#my_samples(200) :                  39417次/秒
  51.  
  52. =end



作者: 哇哇哇啊叭叭    时间: 2022-1-23 08:36
本帖最后由 哇哇哇啊叭叭 于 2022-1-24 09:16 编辑

  
  突然有个想法：以单元功能为单位，展开一场关于编程的教程。

  比如：
  单元功能 = 让标题画面有循环播放的背景
  知识点    = 循环
  教程设计重点：把除“循环”代码外的所有工作都打包做完。多找几个同样用到循环的其他功能一并打包进教程。

  这个思路是以功能为线索，以问题为驱动，以基本知识点为抓手，统筹协调，构建一体多翼式教程体系的设计。
  如果能做到“一个知识点对应一个常问功能”，就能提增讨论区的质效，同时避免知识点抽象、学习时间长的问题。
  功能与知识点最好能有关键词层面的重复。这样用户想要完成循环有关功能时，会搜到循环的知识点。
  无关知识点和功能的封装，能让用户重点关注核心问题，避免在游戏制作中分散精力。我常有因为完成一个小设计，却不得不做大量其他工作的情况。等回头再审核设计思路，却又想删改它了。总之事前对设计背后的工作量估计不足，事后又会因罕有复习导致知识点易忘易错。
  归类。用户完成功能后，应当有课后练习。应当提供类似功能、相同知识点的工程供用户使用，以加深印象。这样可能会涉及知识点、功能编订id，避免重复或互异性不高的类似知识点和功能。也利于触类旁通。

  这样，正反馈更及时，同时可持续的元初知识点也更能普及，出工效率也更高。一并解决了：耐心不足x用户粘性小、版本迭代快熵耗知识点巨多、工程完成度低社区没产品的问题。甚至连沃G的教育事业都能受惠，就算大家不玩了也能学会一门编程手艺，还锻炼数学。
  我觉得管理员应当把我的想法置顶。



[line]6[/line]
  瓦特矮酉淘坑额爆特？


作者: 音狼MW    时间: 2022-1-23 11:58
呐，这什么啊......
竟然一行注释也没有，太恐怖了吧......
作者: guoxiaomi    时间: 2022-1-23 22:40
效率是10倍还是十分之一可得说清楚了……
作者: guoxiaomi    时间: 2022-1-24 15:46
本帖最后由 guoxiaomi 于 2022-1-24 18:33 编辑

我也用C写了个shuffle： 20220124-rubyshuffle.zip (36.07 KB, 下载次数: 17) ，测试比Array#shuffle!快了~12%，可能是省去了类型检查吧。

但是代码要怎么变成CallWndProc能调用的内容呢？@RPGzh500223 你的那一串数字是咋生成的……

  1. #include <ruby.h>
  2. #include <stdlib.h>
  3. #include "extconf.h"

  5. VALUE test_shuffle(VALUE module, VALUE array)
  6. {
  7.     VALUE *ptr = RARRAY_PTR(array);
  8.     long len = RARRAY_LEN(array);
  9.     long a;
  10.     long b;
  11.     for (a = len - 1; a != 0; --a)
  12.     {
  13.         b = rand() % (a + 1);
  14.         *(ptr + b) = *(ptr + b) ^ *(ptr + a);
  15.         *(ptr + a) = *(ptr + b) ^ *(ptr + a);
  16.         *(ptr + b) = *(ptr + b) ^ *(ptr + a);
  17.     }
  18.     return Qnil;
  19. }

  21. VALUE test_seed(VALUE module, VALUE seed)
  22. {
  23.     srand(FIX2UINT(seed));
  24.     return Qnil;
  25. }

  27. void Init_shuffle()
  28. {
  29.     VALUE mtest = rb_define_module("Test");
  30.     rb_define_module_function(mtest, "shuffle!", test_shuffle, 1);
  31.     rb_define_module_function(mtest, "seed", test_seed, 1);
  32. }
复制代码
benchmark


有时候真的会感慨自己这些年编程水平的进步，17年的时候我写的代码还是这样的：https://rpg.blue/thread-403593-1-1.html，那时候还研究了好多天，头都想破了，而现在半小时就能写好。希望自己能再接再厉吧。



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1