洗牌算法,以随机打乱数组中元素的位置
测试数据创建
int[] _data;
Random rng = new Random();
protected override void CreateData()
{_data = new int[_size];for (int i = 0; i < _data.Length; i++){_data[i] = i;}
}
普通打乱数组元素位置
protected override void OrdinaryMethod(){int n = (int)_size;while (n-- > 1){int k = rng.Next(n + 1);int value = _data[k];_data[k] = _data[n];_data[n] = value;}}
simd打乱
readonly int[] mask = { 30, 39, 45, 54, 57, 75, 78, 99, 108, 114, 120, 135, 141, 147, 156, 177, 180, 198, 201, 210, 216, 225, 228 };
protected override void SimdMethod()
{int n = (int)_size;int vsize = Vector128<int>.Count;int m = n - (n & (vsize - 1));fixed (int* ptr = _data, maskPtr = mask){int j = 0;int i = 0;for (j = 0; j < m; j += vsize){Vector128<int> v = *(Vector128<int>*)(ptr + j);// 打乱var t = Sse2.Shuffle(v, (byte)*(maskPtr + rng.Next(mask.Length)));// 拷贝Sse2.Store(ptr + j, t);j += vsize;}for (; j < n; j++){int* t = ptr + rng.Next(n);int* val = ptr + j;*val = (*t ^= *val ^= *t) ^ *val;}}
}
指令说明
Shuffle指令:用于根据提供的控制值(control)重新排列 Vector128<int> 类型向量中的元素。(比如洗牌算法打乱数组中元素的位置)。
Store指令:将向量的数据存储到内存地址。
补充,上面Simd打乱数组位置为局部打乱,下面是全局打乱
protected void SimdMethod2(){int n = (int)_size;int vsize = Vector128<int>.Count;int m = n - (n & (vsize - 1));Vector128<int>[] vectors = new Vector128<int>[m / vsize];fixed (int* ptr = _data, maskPtr = mask){fixed (Vector128<int>* vptr = vectors){int j = 0;int i = 0;for (j = 0; j < m; j += vsize){*(vptr + i++) = *(Vector128<int>*)(ptr + j);}j = 0;for (i = 0; i < vectors.Length; i++){Sse2.Store(ptr + j, Sse2.Shuffle(*(vptr + i), (byte)*(maskPtr + rng.Next(mask.Length))));j += vsize;}for (; j < n; j++){int* t = ptr + rng.Next(n);int* val = ptr + j;int temp = *t;*t = *val;*val = temp;}}}}