Array#shuffle! #shuffle #samples (优化）

RPGzh500223

[pre lang="ruby"]class Array
  def to_int
    self.object_id
  end
  
  CallWndProc = Win32API.new('user32.dll', 'CallWindowProc', 'PLLLL', 'L')
  
  CodeSeed = [85,137,229,139,77,8,3,77,12,187,1,0,0,0,139,69,16,247,227,
    3,69,20,137,195,193,232,16,37,255,127,0,0,226,236,137,216,201,
    194,16,0].pack('C*')
  @@seed = CallWndProc.call(CodeSeed, rand(41), 10, 214013, 2531011)
  
  CodeShuffle = [85,137,229,139,93,8,139,76,27,8,131,249,1,118,55,139,116,27,
    16,73,141,60,142,139,93,12,139,69,16,247,227,3,69,20,137,195,193,232,16,
    37,255,127,0,0,49,210,65,247,241,73,193,226,2,1,242,255,50,255,55,143,2,
    143,7,131,239,4,226,214,137,216,201,194,16,0].pack('C*')
   
  def shuffle!
    @@seed = CallWndProc.call(CodeShuffle, self, @@seed, 214013, 2531011)
    self
  end
  
  def shuffle
    (self + []).shuffle!
  end
  
  def sample
    self[rand(self.size)]
  end
  
  CodeSamples = [85,137,229,139,69,8,139,92,0,8,139,68,0,16,137,69,8,141,116,
    152,252,139,69,12,139,76,0,8,81,139,68,0,16,141,124,136,252,184,253,67,3,
    0,247,101,20,5,160,51,130,1,137,69,20,193,232,16,37,255,127,0,0,49,210,
    247,243,75,193,226,2,3,85,8,255,50,255,54,143,2,143,6,137,23,131,239,4,
    131,238,4,226,203,89,131,198,4,139,6,131,199,4,139,23,137,7,255,50,255,
    54,143,2,143,6,226,234,139,69,20,201,194,16,0].pack('C*')
   
  def samples(n)
    len = self.size
    return self[rand(len), 1] if n < 2
    n = len if n > len
    return self.shuffle if n == len
    result = Array.new(n)
    @@seed = CallWndProc.call(CodeSamples, self, result, 0, @@seed)        
    result
  end
end[/pre]

\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_**方法为该帖的方法）

[pre lang="ruby"]# 非代码
=begin
rmva测试
【(0...10).to_a】
  Array#suffle! :                         148031次/秒
  Array#suffle :                          121141次/秒
  Array#my_suffle! :                       68741次/秒
  Array#my_suffle :                        60609次/秒
  Array#sample(5) :                       131731次/秒
  Array#my_samples(5) :                    55161次/秒
  Array#sample(100) :                     126950次/秒
  Array#my_samples(100) :                  56554次/秒
  Array#sample(200) :                     126669次/秒
  Array#my_samples(200) :                  56390次/秒

【(0...100).to_a】
  Array#suffle! :                          70314次/秒
  Array#suffle :                           60290次/秒
  Array#my_suffle! :                       59772次/秒
  Array#my_suffle :                        51764次/秒
  Array#sample(5) :                       131434次/秒
  Array#my_samples(5) :                    55044次/秒
  Array#sample(100) :                      67510次/秒
  Array#my_samples(100) :                  49509次/秒
  Array#sample(200) :                      66997次/秒
  Array#my_samples(200) :                  49541次/秒

【(0...500).to_a】
  Array#suffle! :                          20981次/秒
  Array#suffle :                           19097次/秒
  Array#my_suffle! :                       38931次/秒
  Array#my_suffle :                        32487次/秒
  Array#sample(5) :                       131307次/秒
  Array#my_samples(5) :                    54454次/秒
  Array#sample(100) :                      57960次/秒
  Array#my_samples(100) :                  45561次/秒
  Array#sample(200) :                      41348次/秒
  Array#my_samples(200) :                  38972次/秒

【(0...1000).to_a】
  Array#suffle! :                          11331次/秒
  Array#suffle :                           10317次/秒
  Array#my_suffle! :                       27282次/秒
  Array#my_suffle :                        22167次/秒
  Array#sample(5) :                       130697次/秒
  Array#my_samples(5) :                    55175次/秒
  Array#sample(100) :                      49234次/秒
  Array#my_samples(100) :                  45636次/秒
  Array#sample(200) :                      36858次/秒
  Array#my_samples(200) :                  39417次/秒

=end[/pre]

哇哇哇啊叭叭

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

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

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

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

---

  瓦特矮酉淘坑额爆特？

音狼MW

呐，这什么啊......
竟然一行注释也没有，太恐怖了吧......

guoxiaomi

效率是10倍还是十分之一可得说清楚了……

guoxiaomi

我也用C写了个shuffle： 20220124-rubyshuffle.zip (36.07 KB, 下载次数: 17)

2022-1-24 15:57 上传

点击文件名下载附件

，测试比Array#shuffle!快了~12%，可能是省去了类型检查吧。

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

1. #include <ruby.h>
   
2. #include <stdlib.h>
   
3. #include "extconf.h"
   
4. 
   
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. }
    
20. 
    
21. VALUE test_seed(VALUE module, VALUE seed)
    
22. {
    
23.     srand(FIX2UINT(seed));
    
24.     return Qnil;
    
25. }
    
26. 
    
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. }
    

复制代码

[fold=benchmark]Rehearsal --------------------------------------------------
Array#shuffle!   2.328000   0.000000   2.328000 (  2.323382)
Test#shuffle     1.922000   0.000000   1.922000 (  1.924539)
----------------------------------------- total: 4.250000sec

                     user     system      total        real
Array#shuffle!   2.313000   0.000000   2.313000 (  2.326262)
Test#shuffle     1.907000   0.000000   1.907000 (  1.914808)
Rehearsal --------------------------------------------------
Array#shuffle!   1.718000   0.000000   1.718000 (  1.717608)
Test#shuffle     1.360000   0.000000   1.360000 (  1.361850)
----------------------------------------- total: 3.078000sec

                     user     system      total        real
Array#shuffle!   1.719000   0.000000   1.719000 (  1.716432)
Test#shuffle     1.359000   0.000000   1.359000 (  1.356099)
Rehearsal --------------------------------------------------
Array#shuffle!   1.594000   0.000000   1.594000 (  1.593563)
Test#shuffle     1.312000   0.000000   1.312000 (  1.308345)
----------------------------------------- total: 2.906000sec

                     user     system      total        real
Array#shuffle!   1.594000   0.000000   1.594000 (  1.597845)
Test#shuffle     1.375000   0.000000   1.375000 (  1.361285)[/fold]

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