文字列系アルゴリズムのオーバーロードについて #26
Comments
|
IEquatableのオーバーヘッドが少し気になりますが、ゼロコストでできるならば嬉しいですね。型変換についてはArrayを用いれば良さそうに思えますが、どうでしょうか…? |
|
using System;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
class Program
{
static void Main(string[] args)
{
BenchmarkRunner.Run<EquatableTest>();
}
}
public class EquatableTest
{
private int N = 20000;
private int[] _data;
[GlobalSetup]
public void SetUp()
{
var random = new Random();
_data = new int[N];
for (int i = 0; i < _data.Length; i++)
{
_data[i] = random.Next();
}
}
[Benchmark]
public bool ArrayTest() => ArrayTest(_data);
private bool ArrayTest(int[] a)
{
var result = false; // 最適化によりループが消えるのを防ぐ
for (int i = 0; i < a.Length; i++)
{
for (int j = 0; j < a.Length; j++)
{
result ^= a[i] == a[j];
}
}
return result;
}
[Benchmark]
public bool ReadOnlySpanTest() => ReadOnlySpanTest<int>(_data);
private bool ReadOnlySpanTest<T>(ReadOnlySpan<T> a) where T : IEquatable<T>
{
var result = false;
for (int i = 0; i < a.Length; i++)
{
for (int j = 0; j < a.Length; j++)
{
result ^= a[i].Equals(a[j]);
}
}
return result;
}
}結果 今回試した限りは誤差の範囲のようなので、おそらく大丈夫そうですね。 |
|
[Benchmark]
public bool ReadOnlySpanEqualityComparerTest() => ReadOnlySpanEqualityComparerTest<int>(_data);
private bool ReadOnlySpanEqualityComparerTest<T>(ReadOnlySpan<T> a)
{
var result = false;
for (int i = 0; i < a.Length; i++)
{
for (int j = 0; j < a.Length; j++)
{
result ^= System.Collections.Generic.EqualityComparer<T>.Default.Equals(a[i], a[j]);
}
}
return result;
} |
|
ありがとうございます！ |
|
検証助かります…! 現状の文字列系アルゴリズムでは、 Comparer を用いた同様の比較の場合でもベンチを取ってみました。ソース 比較
等価判定
|
|
Spanのソートが追加される予定が |
|
細かく元コードの実装を追えてはいないので適当なことを言っていたら申し訳ないのですが……。 |
|
Array.Sort(Array, Array)と同等の、keyとなるSpanを指定して他のSpanをソートするメソッドがあったので使いたいなというモチベーションでしたが、言われてみればそうでした。(目的を見失ってました) |
|
今更で申し訳ないのですが、 |
public static int[] ZAlgorithm(string s) => ZAlgorithm<char>(s.AsSpan());
public static int[] ZAlgorithm(T[] s) where T : IEquatable<T> => ZAlgorithm<T>((ReadOnlySpan<T>)s);
public static int[] ZAlgorithm<T>(ReadOnlySpan<T> s) where T : IEquatable<T>ではダメなのでしょうか |
|
おっしゃる通りですね……！どうして気付かなかったのか……。 |
.NET 5が出るまで 公開する部分はあまり後からいじりたくないですし、Z-algorithm等と違って部分列に対してsuffix arrayが欲しい場面ってそうそうなさそうな気がしますし。 |
|
そうですね。 #34 の変更は |
|
Openにしっぱなしですみません……。こちらCloseとさせて頂きます。 |
文字列系アルゴリズム（
LCPArray,SuffixArray,ZAlgorithm）の引数ですが、ReadOnlySpan<T>を受け取るオーバーロードもあると良いのかなと思いました。以下のようなイメージです。
定義側
使用側
ReadOnlySpan<T>を受け付けるものさえあれば他はいらないのでは？とも思いましたが、型変換が入ると型推論が効かない（int[]をReadOnlySpan<int>と解釈してくれない）ようで、毎回型引数を明示しないといけないのが面倒そうなので諦めました……。The text was updated successfully, but these errors were encountered: