{"id":1599,"date":"2009-04-03T23:54:00","date_gmt":"2009-04-03T14:54:00","guid":{"rendered":"https:\/\/hdmr.org\/d\/?e=326"},"modified":"2009-04-03T23:54:00","modified_gmt":"2009-04-03T14:54:00","slug":"blogn-326","status":"publish","type":"post","link":"https:\/\/hdmr.org\/d\/?e=326","title":{"rendered":"\u30de\u30eb\u30c1\u30b9\u30ec\u30c3\u30c9\u3067\u901f\u3044\u901f\u3044\u30bd\u30fc\u30c8\u3092\u3059\u308b"},"content":{"rendered":"<p>\u3068\u3053\u308d\u3067\u6628\u65e5\u306e\u8a18\u4e8b\u3067\u6700\u5f8c\u306b\u66f8\u3044\u305f\u3001\u5b89\u5b9a\u306a\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u3067\u3059\u304c\u3001\u4f8b\u3048\u3070\u3053\u3093\u306a\u306e\u3002<\/p>\n<pre>sub mysort{<br \/>  return @_ if(@_<2);<br \/>  if(@_<=16){<br \/>    for my $i(1..$#_){<br \/>      my $c=splice(@_,$i,1);<br \/>      my $j=$i;<br \/>      for(;$j>0;$j--){<br \/>        last if $_[$j-1]<=$c;<br \/>      }<br \/>      splice(@_,$j,0,$c);<br \/>    }<br \/>    return @_;<br \/>  }else{<br \/>    my $p=$_[rand(@_)];<br \/>    my @s=([],[],[]);<br \/>    while(@_){<br \/>      my $c=shift(@_);<br \/>      push(@{$s[($c <=> $p)+1]},$c);<br \/>    }<br \/>    return (mysort(@{$s[0]}),@{$s[1]},mysort(@{$s[2]}));<br \/>  }<br \/>}<br \/>@a=mysort(@a);<\/pre>\n<p>\u9069\u5f53\u306a\u5024\u3092\u9078\u3093\u3067\u3001\u524d\u304b\u3089\u9806\u756a\u306b\u5927\u304d\u3044\u304b\u540c\u3058\u304b\u5c0f\u3055\u3044\u304b\u306b\u4ed5\u5206\u3051\u3092\u3059\u308b\u3068\u3002<br \/>($c <=> $p)+1\u3068\u3044\u3046\u306e\u306f$c\u3088\u308a$p\u304c\u5c0f\u3055\u3051\u308c\u30700\u3001\u540c\u3058\u306a\u3089\u30701\u3001\u5927\u304d\u3051\u308c\u30701\u3068\u3044\u3046\u98a8\u306b\u306a\u308b\u3088\u3046\u306b\u3057\u3066\u3042\u308b\u3068\u3002<br \/>\u3053\u308c\u3067\u4ed5\u5206\u3051\u3066\u3001\u5c0f\u3055\u3044\u30b0\u30eb\u30fc\u30d7\u30fb\u5927\u304d\u3044\u30b0\u30eb\u30fc\u30d7\u3092\u305d\u308c\u305e\u308c\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u3059\u308b\u3068\u3002<br \/>\u3053\u306e\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u306f\u5b89\u5b9a\u3067\u3059\u3088\u3002\u4e16\u306e\u4e2d\u306b\u306f\u305d\u3093\u306a\u3082\u306e\u3082\u3042\u308b\u306e\u3067\u3059\u3002<br \/>\u6848\u5916\u65e9\u3044\u306e\u3067\u3059\u304c\u3001\u304b\u304b\u308b\u6642\u9593\u306e\u3070\u3089\u3064\u304d\u304c\u3072\u3069\u3044\u306e\u3067\u3069\u3046\u3057\u305f\u3082\u306e\u304b\u306a\u3068\u601d\u3063\u3066\u3044\u308b\u3002<\/p>\n<hr \/>\n<p>\u3068\u3053\u308d\u3067\u30de\u30fc\u30b8\u30bd\u30fc\u30c8\u306f\u4e26\u5217\u51e6\u7406\u306b\u5411\u304f\u3089\u3057\u3044\u3002<br \/>\u3068\u3044\u3046\u308f\u3051\u3067\u3044\u308d\u3044\u308d\u5b9f\u9a13\u3057\u3066\u305f\u306e\u3060\u304c\u3001\u7d50\u5c40\u5b9f\u9a13\u306b\u4f7f\u3046\u3053\u3068\u306b\u3057\u305f\u306e\u306fC#\u3067\u3059\u306d\u3002<br \/>\u3068\u3044\u3046\u306e\u3082Perl\u3082Ruby\u3082\u30de\u30eb\u30c1\u30b9\u30ec\u30c3\u30c9\u306f\u7121\u7406\u3067\u306f\u306a\u3044\u304c\u3001\u305d\u3093\u306a\u306b\u6027\u80fd\u304c\u3088\u304f\u306a\u3044\u3002<br \/>\u3069\u3061\u3089\u3082\u753b\u9762\u304c\u56fa\u307e\u3063\u3066\u3057\u307e\u3046\u306e\u3092\u9632\u3050\u3088\u3046\u306a\u3001\u305d\u3046\u3044\u3046\u30de\u30eb\u30c1\u30b9\u30ec\u30c3\u30c9\u3060\u3051\u306a\u3093\u3067\u3059\u306d\u3002<br \/>\u305d\u308c\u306a\u3089\u3068\u4e45\u3005\u306bLL(\u8efd\u91cf\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u8a00\u8a9e\u306e\u3053\u3068)\u3058\u3083\u306a\u3044\u8a00\u8a9e\u3092\u4f7f\u304a\u3046\u304b\u306a\u3068\u304b\u3002<br \/>\u305d\u3046\u306a\u308a\u3083C#\u3067\u3059\u306d\u3002\u4eca\u307e\u3067C#\u3067\u3044\u308d\u3093\u306a\u3082\u306e\u3092\u4f5c\u3063\u3066\u304d\u305f\u3051\u3069\u3001.NET Framework\u306e\u6027\u80fd\u306f\u304b\u306a\u308a\u3088\u308d\u3057\u3044\u3002<br \/>\u30de\u30eb\u30c1\u30b9\u30ec\u30c3\u30c9\u3060\u3063\u3066\u30d0\u30ea\u30d0\u30ea\u306b\u4f7f\u3048\u307e\u3059\u306d\u3002<br \/>\u305d\u308c\u3067\u4e45\u3057\u3076\u308a\u306b\u66f8\u304d\u59cb\u3081\u305f\u3089foreach\u3092\u3053\u3093\u306a\u98a8\u306b\u66f8\u3044\u3066\u3057\u307e\u3063\u305f\u308a\u3057\u305f\u3002<\/p>\n<pre>foreach(my cur in foo){ }<\/pre>\n<p>my\u3058\u3083\u306a\u304f\u3066int\u3067\u3059\u306d\u3002Perl\u3067\u306f\u306a\u3093\u3067\u3082\u304b\u3093\u3067\u3082my\u3067\u3057\u305f\u304b\u3089\u306d\u3002<br \/>\u3057\u304b\u3057use strict;\u3057\u3066\u3044\u3066\u5909\u6570\u5ba3\u8a00\u3092\u3059\u308b\u7fd2\u6163\u304c\u3042\u3063\u305f\u306e\u3067\u3001\u5909\u6570\u5ba3\u8a00\u3057\u306a\u3044\u3068\u304b\u306f\u305d\u3046\u3082\u306a\u304b\u3063\u305f\u3002<br \/>\u3068\u3044\u3046\u304buse strict;\u3063\u3066\u5909\u6570\u5ba3\u8a00\u306b\u3064\u3044\u3066\u306f\u7d50\u69cb\u53b3\u3057\u3044\u3067\u3059\u304b\u3089\u306d\u3002\u305d\u306e\u70b9\u3067\u306f\u305d\u3046\u3082\u5fc3\u914d\u3044\u3089\u306a\u3044\u3068\u3002<br \/>\u3061\u306a\u307f\u306b\u4eca\u56de\u4f7f\u3063\u305f\u306e\u306fVisual C# 2008 Express\u3001\u30a2\u30ab\u30c7\u30df\u30c3\u30af\u7248\u306eVisual Studio 2005\u306f\u6301\u3063\u3066\u308b\u306e\u306b\u306d\u3002<br \/>\u3051\u3069\u306a\u3093\u3067\u3053\u308c\u306a\u306e\u304b\u3068\u3044\u3048\u3070\u3001C# 3.0\u3092\u4f7f\u3044\u305f\u304b\u3063\u305f\u304b\u3089\u3002<\/p>\n<hr \/>\n<p>\u3068\u3044\u3046\u308f\u3051\u3067\u4f5c\u3063\u3066\u307f\u305f\u30bd\u30fc\u30b9\u3092\u5f35\u308d\u3046\u304b\u306a\u3002<\/p>\n<pre>static class SortWorld {<br \/>  static void Main(string[] args) {<br \/>    float[] rnd=new float[50000000];<br \/>    System.Diagnostics.Stopwatch watch=new System.Diagnostics.Stopwatch();<br \/>    SortWorld.MultiThreadMode=1;<br \/>    for (int i=0; i<rnd.Length; i++) rnd[i]=(float)_ourrnd.NextDouble();<br \/>    Console.WriteLine(\"Begin MargeSort\"); watch.Reset(); watch.Start();<br \/>    rnd.MargeSortDestroy();<br \/>    watch.Stop(); Console.WriteLine(\"Finish MargeSort Time:{0}[ms]\", watch.ElapsedMilliseconds);<br \/>    for (int i=0; i<rnd.Length; i++) rnd[i]=(float)_ourrnd.NextDouble();<br \/>    Console.WriteLine(\"Begin Array.Sort\"); watch.Reset(); watch.Start();<br \/>    Array.Sort(rnd);<br \/>    watch.Stop(); Console.WriteLine(\"Finish Array.Sort Time:{0}[ms]\", watch.ElapsedMilliseconds);<br \/>    Console.ReadKey(true);<br \/>  }<br \/>  static private Random _ourrnd;<br \/>  static public int MultiThreadMode;<br \/>  static SortWorld() {<br \/>    _ourrnd=new Random();<br \/>    MultiThreadMode=0;<br \/>  }<br \/>  static public T[] MargeSortDestroy<t>(this T[] self, params Comparison<t>[] fs) where T : IComparable<t> {<br \/>    self._MargeSortDestroy(MultiThreadMode, fs.Length==0?null:fs[0]);<br \/>    return self;<br \/>  }<br \/>  static private void _MargeSortDestroy<t>(this T[] self, int mode, Comparison<t> f) where T : IComparable<t> {<br \/>    if (self.Length<2) return;<br \/>    if (self.Length<=10) {<br \/>      self._InsertSortDestroy(self.Length, f); return;<br \/>    }<br \/>    T[] left=new T[self.Length\/2];<br \/>    Array.Copy(self, 0, left, 0, left.Length);<br \/>    T[] right=new T[self.Length-left.Length];<br \/>    Array.Copy(self, left.Length, right, 0, right.Length);<br \/>    if (mode>0) {<br \/>      System.Threading.ThreadStart ld=() => { left._MargeSortDestroy(mode-1, f); };<br \/>      System.Threading.Thread lt=new System.Threading.Thread(ld); lt.Start();<br \/>      System.Threading.ThreadStart rd=() => { right._MargeSortDestroy(mode-1, f); };<br \/>      System.Threading.Thread rt=new System.Threading.Thread(rd); rt.Start();<br \/>      lt.Join(); rt.Join();<br \/>    } else {<br \/>      left ._MargeSortDestroy(mode, f);<br \/>      right._MargeSortDestroy(mode, f);<br \/>    }<br \/>    int lp=0, rp=0, ap=0;<br \/>    while (lp<left.Length&#038;&#038;rp<right.Length) {<br \/>      int c=(f==null?left[lp].CompareTo(right[rp]):f(left[lp], right[rp]));<br \/>      if (c>0) self[ap++]=right[rp++];<br \/>      else     self[ap++]=left[lp++];<br \/>    }<br \/>    if (lp<left.Length) Array.Copy(left, lp, self, ap, left.Length-lp);<br \/>    else Array.Copy(right, rp, self, ap, right.Length-rp);<br \/>  }<br \/>  static private void _InsertSortDestroy<t>(this T[] self, int len, Comparison<t> f) where T : IComparable<t> {<br \/>    for (int i=1; i<len; i++) {<br \/>      for (int j=i; j>0; j--) {<br \/>        if ((f==null?self[j-1].CompareTo(self[j]):f(self[j-1], self[j]))<=0) break;<br \/>        T tmp=self[j];<br \/>        self[j]=self[j-1];<br \/>        self[j-1]=tmp;<br \/>      }<br \/>    }<br \/>  }<br \/>}<\/pre>\n<p>\u306a\u305c\u304b\u9577\u3044\u3002Perl\u306e\u30bd\u30fc\u30b9\u30b3\u30fc\u30c9\u3088\u308a\u3082\u660e\u3089\u304b\u306b\u304b\u3055\u3070\u308b\u3093\u3067\u3059\u306d\u3002\u306a\u3093\u3067\u3060\u308d\u3002<br \/>\u307e\u3041\u3044\u3044\u3084\u3001\u30dd\u30a4\u30f3\u30c8\u306f_MargeSortDestroy\u30e1\u30bd\u30c3\u30c9\u3067\u3059\u306d\u3002<br \/>\u3068\u3053\u308d\u3067C# 3.0\u304b\u3089\u59cb\u307e\u3063\u305f\u3053\u3068\u3060\u3051\u3069\u3001\u7b2c\u4e00\u5f15\u6570\u306e\u3068\u3053\u308d\u306bthis\u3092\u3064\u3051\u308b\u3068\u3001\u62e1\u5f35\u30e1\u30bd\u30c3\u30c9\u3068\u3044\u3046\u30e1\u30bd\u30c3\u30c9\u306b\u3067\u304d\u308b\u3093\u3067\u3059\u306d\u3002<br \/>\u3069\u3046\u3044\u3046\u3053\u3068\u304b\u3068\u3044\u3044\u307e\u3059\u3068\u3001Foo(bar)\u3068\u3059\u308b\u3079\u304d\u3068\u3053\u308d\u3092\u3001\u62e1\u5f35\u30e1\u30bd\u30c3\u30c9\u306a\u3089\u3070bar.Foo()\u3068\u304b\u3051\u308b\u3068\u3002<br \/>\u305d\u308c\u3092\u3061\u3087\u3063\u3068\u4f7f\u3063\u3066\u3044\u307e\u3059\u3002<br \/>10\u500b\u4ee5\u4e0b\u306e\u5834\u5408\u306f\u5f8c\u308d\u306b\u66f8\u3044\u3066\u3042\u308b_InsertSortDestroy\u30e1\u30bd\u30c3\u30c9\u3067\u633f\u5165\u30bd\u30fc\u30c8\u3067\u30bd\u30fc\u30c8\u3057\u3066\u3082\u3089\u3046\u3002<br \/>\u305d\u308c\u4ee5\u5916\u306e\u5834\u5408\u306f\u5de6\u53f3\u306b\u5206\u3051\u3066\u3001\u305d\u308c\u305e\u308c\u3092\u518d\u5e30\u7684\u306b\u30de\u30fc\u30b8\u30bd\u30fc\u30c8\u3001<br \/>\u305d\u308c\u3067\u5de6\u53f3\u3092\u304f\u3063\u3064\u3051\u3066\u3044\u304f\u3068\u3002\u305d\u308c\u3067\u3067\u304d\u3042\u304c\u308a\u3068\u3002<br \/>\u3068\u3053\u308d\u3067\u3044\u308d\u3093\u306a\u30e1\u30bd\u30c3\u30c9\u306b\u3084\u305f\u3089Destroy\u3068\u3064\u3044\u3066\u308b\u3051\u3069\u3001\u7834\u58ca\u7684\u30e1\u30bd\u30c3\u30c9\u3063\u3066\u3053\u3068\u306d\u3002<br \/>\u5143\u306e\u914d\u5217\u306e\u8981\u7d20\u3092\u534a\u5206\u305a\u3064left\u3068right\u306b\u30b3\u30d4\u30fc\u3057\u3066\u3001\u3053\u308c\u3092\u305d\u308c\u305e\u308c\u30bd\u30fc\u30c8\u3001<br \/>\u305d\u3057\u3066\u305d\u306eleft\u3068right\u306e\u8981\u7d20\u3092\u53d6\u308a\u51fa\u3057\u3066\u3044\u3063\u3066\u3001\u5143\u306e\u914d\u5217\u306b\u4e0a\u66f8\u304d\u3057\u3066\u3057\u307e\u3046\u3002<br \/>\u3053\u308c\u3053\u305d\u304c\u7834\u58ca\u7684\u3067\u3042\u308b\u7406\u7531\u3002Ruby\u306a\u3089\u7834\u58ca\u7684\u30e1\u30bd\u30c3\u30c9\u306b\u306f!\u3064\u3051\u308b\u3093\u3060\u304b\u3089\u3001\u305d\u308c\u306b\u306a\u3089\u3063\u305f\u308f\u3051\u3002<br \/>\u305d\u308c\u3067\u3001\u3061\u3087\u3063\u3068\u5de5\u592b\u3057\u3066\u3042\u308b\u306e\u304c\u30de\u30eb\u30c1\u30b9\u30ec\u30c3\u30c9\u306e\u6d3b\u7528\u3067\u3059\u306d\u3002<br \/>\u305f\u3060\u4f55\u3067\u3082\u304b\u3093\u3067\u3082\u30b9\u30ec\u30c3\u30c9\u306b\u5207\u308a\u5206\u3051\u308b\u3068\u91cd\u304f\u306a\u308b\u306e\u3067\u3001left\u3068right\u3067\u4e26\u884c\u51e6\u7406\u3092\u884c\u3046\u306e\u306f\u3001\u59cb\u30811\u6bb5\u306e\u307f\u3068\u3057\u307e\u3057\u305f\u3002<br \/>\u30c7\u30e5\u30a2\u30eb\u30b3\u30a2\u306eCPU\u3060\u3068\u3053\u308c\u304c\u4e00\u756a\u52b9\u7387\u3088\u3055\u305d\u3046\u3067\u3059\u3002<br \/>\u305d\u306e\u305f\u3081\u306bmode\u3068\u3044\u3046\u5f15\u6570\u3092\u53d6\u3063\u3066\u308b\u3051\u3069\u3001\u3053\u308c\u306f1\u6bb5\u3060\u3051\u4e26\u884c\u51e6\u7406\u3059\u308b\u3068\u304d\u306f\u59cb\u3081\u306b1\u3092\u4e0e\u3048\u3066\u3001<br \/>\u4e26\u884c\u51e6\u7406\u3055\u305b\u308b\u305f\u3073\u306b1\u6e1b\u3089\u3057\u3066\u3044\u3063\u3066\u30010\u306b\u306a\u3063\u305f\u3089\u4e26\u884c\u51e6\u7406\u3057\u306a\u304f\u3059\u308b\u3068\u3044\u3046\u3053\u3068\u306d\u3002<br \/>\u305d\u306e\u4e26\u884c\u51e6\u7406\u3067\u3059\u304c\u3001System.Threading.Thread\u30af\u30e9\u30b9\u3092\u4f7f\u3063\u3066\u308b\u3002<br \/>\u30c7\u30ea\u30b2\u30fc\u30c8\u304c\u4f5c\u308a\u3084\u3059\u3044\u306e\u306fC# 3.0\u306e\u3044\u3044\u3068\u3053\u308d\u3067\u3059\u306d\u3002(x,y)=>{ x.foo(y); }\u306e\u3088\u3046\u306b\u4f5c\u308c\u307e\u3059\u304b\u3089\u306d\u3002<br \/>\u305d\u308c\u304c_MargeSortDestroy\u30e1\u30bd\u30c3\u30c9\u3001\u5b9f\u969b\u306b\u4f7f\u3046\u3068\u304d\u306fMargeSortDestro<br \/>\ny\u30e1\u30bd\u30c3\u30c9\u3092\u4f7f\u3046\u3002<br \/>\u3053\u3053\u3067\u3061\u3087\u3063\u3068\u304a\u3082\u3057\u308d\u3044\u5de5\u592b\u3092\u3057\u3066\u3042\u308b\u3002<br \/>C# 4.0\u304b\u3089\u306f\u7701\u7565\u53ef\u80fd\u306a\u5f15\u6570\u304c\u3067\u304d\u308b\u306e\u3067\u3059\u304c\u3001C# 3.0\u307e\u3067\u306f\u3042\u308a\u307e\u305b\u3093\u3001<br \/>\u3051\u3069\u6700\u5f8c\u306e\u5f15\u6570\u3092params\u3064\u3051\u3066\u53ef\u5909\u9577\u5f15\u6570\u306b\u3059\u308c\u3070\u3001\u6700\u5f8c\u306e\u5f15\u6570\u306f\u306a\u304f\u3066\u3082\u3044\u3044\u3093\u3067\u3059\u306d\u3002<br \/>\u305d\u308c\u3067\u7701\u7565\u3067\u304d\u308b\u3088\u3046\u306b\u3057\u3066\u3042\u308b\u3002\u6700\u5f8c\u306e\u5f15\u6570\u306f\u6bd4\u8f03\u7528\u30c7\u30ea\u30b2\u30fc\u30c8\u3067\u3059\u306d\u3002(x,y)=>((int)x).CompareTo((int)y)\u3068\u304b\u4e0e\u3048\u308c\u3070\u52d5\u304d\u307e\u3059\u3088\u3002<br \/>\u307e\u3041\u3053\u3093\u306a\u3068\u3053\u308d\u3067\u3059\u3002<br \/>\u305d\u308c\u3067\u5b9f\u884c\u7d50\u679c\u3067\u3059\u304c5000\u4e07\u500b\u306e\u914d\u5217\u306e\u30bd\u30fc\u30c8\u309238\u79d2\u3067\u884c\u3046\u3002\u304b\u306a\u308a\u901f\u3044\u3067\u3059\u306d\u3002<br \/>\u3053\u308c\u306f\u30de\u30eb\u30c1\u30b9\u30ec\u30c3\u30c9\u5316\u306e\u6210\u679c\u3067\u3001\u305d\u3046\u3057\u306a\u3051\u308c\u307060\u79d2\u3050\u3089\u3044\u304b\u304b\u308b\u3002<br \/>\u3061\u306a\u307f\u306b\u6a19\u6e96\u306eSystem.Array.Sort\u30e1\u30bd\u30c3\u30c9\u306f16\u79d2\u3067\u3084\u308b\u3002\u305f\u3060\u3057\u3053\u3061\u3089\u306f\u5b89\u5b9a\u3067\u306a\u3044\u30bd\u30fc\u30c8\u3002<\/p>\n<hr \/>\n<p>\u5b89\u5b9a\u306a\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u3092\u304c\u3093\u3070\u3063\u3066\u5b9f\u88c5\u3057\u3066\u307f\u305f\u306e\u3067\u3059\u304c\u3001\u3053\u308c\u304c\u7d50\u69cb\u56f0\u308b\u3002<br \/>\u3068\u3044\u3046\u306e\u3082\u914d\u5217\u30923\u3064\u306b\u4ed5\u5206\u3051\u3059\u308b\u305f\u3081\u306b\u30e1\u30e2\u30ea\u3092\u3059\u3054\u304f\u98df\u3044\u305d\u3046\u306a\u3093\u3067\u3059\u306d\u3002<br \/>\u305d\u3053\u3067\u3053\u3093\u306a\u98a8\u306b\u3057\u3066\u914d\u5217\u3092\u7bc0\u7d04\u3059\u308b\u3053\u3068\u306b\u3002<br \/>\u307e\u305a\u5143\u306e\u914d\u5217\u3068\u540c\u3058\u9577\u3055\u306e\u914d\u5217\u3092\u7528\u610f\u3059\u308b\u3002\u305d\u3057\u3066\u3053\u306e\u914d\u5217\u3092\u982d\u304b\u3089\u8aad\u307f\u53d6\u3063\u3066\u3001<br \/>\u3042\u308b\u5024\u3088\u308a\u3082\u5c0f\u3055\u3051\u308c\u3070\u5143\u306e\u914d\u5217\u306e\u8aad\u307f\u53d6\u308a\u6e08\u307f\u306e\u30b9\u30da\u30fc\u30b9\u306b\u5165\u308c\u308b\u3002<br \/>\u5927\u304d\u3051\u308c\u3070\u65b0\u3057\u304f\u7528\u610f\u3057\u305f\u914d\u5217\u306b\u524d\u304b\u3089\u5165\u308c\u308b\u3002\u7b49\u3057\u3051\u308c\u3070\u65b0\u3057\u304f\u7528\u610f\u3057\u305f\u914d\u5217\u306b\u5f8c\u308d\u304b\u3089\u5165\u308c\u308b\u3002<br \/>\u4ed5\u5206\u3051\u304c\u7d42\u308f\u3063\u305f\u3089\u3001\u7b49\u3057\u3044\u30b0\u30eb\u30fc\u30d7\u3092\u5c0f\u3055\u3044\u30b0\u30eb\u30fc\u30d7\u306e\u5f8c\u308d\u306b\u79fb\u52d5\u3059\u308b\u3002<br \/>\u305d\u3057\u3066\u3001\u5143\u306e\u914d\u5217\u306e\u5c0f\u3055\u3044\u30b0\u30eb\u30fc\u30d7\u306e\u90e8\u5206\u3060\u3051\u3068\u3001\u65b0\u3057\u304f\u7528\u610f\u3057\u305f\u914d\u5217\u306e\u5927\u304d\u3044\u30b0\u30eb\u30fc\u30d7\u306e\u90e8\u5206\u3060\u3051\u3092\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u3002<br \/>\u5b8c\u4e86\u3057\u305f\u3089\u65b0\u3057\u304f\u7528\u610f\u3057\u305f\u914d\u5217\u306e\u305d\u306e\u90e8\u5206\u3092\u5143\u306e\u914d\u5217\u306e\u5f8c\u308d\u306b\u623b\u3059\u3002<br \/>\u3068\u3044\u3046\u30e1\u30e2\u30ea\u306e\u7bc0\u7d04\u306e\u305f\u3081\u306b\u304b\u306a\u308a\u82e6\u3057\u3044\u3053\u3068\u3092\u3057\u3066\u3044\u307e\u3059\u3002\u306a\u306e\u3067\u8aad\u307f\u306b\u304f\u3044\u3063\u305f\u3089\u3042\u308a\u3083\u3057\u306a\u3044\u3002<\/p>\n<pre>  static public T[] StableQuickSortDestory<t>(this T[] self, params Comparison<t>[] fs) where T : IComparable<t> {<br \/>    self._StableQuickSortDestory(self.Length, MultiThreadMode,fs.Length==0?null:fs[0]);<br \/>    return self;<br \/>  }<br \/>  static private void _StableQuickSortDestory<t>(this T[] self, int len, int mode, Comparison<t> f) where T : IComparable<t> {<br \/>    if (len<2) return;<br \/>    if (len<=50) {<br \/>      self._InsertSortDestroy(len, f);<br \/>      return;<br \/>    }<br \/>    T[] buf=new T[len];<br \/>    T p=self[_ourrnd.Next(len)];<br \/>    int lp=0, rp=0, cp=buf.Length-1;<br \/>    for (int sp=0; sp<len; sp++) {<br \/>      int m=(f==null?p.CompareTo(self[sp]):f(p, self[sp]));<br \/>      if (m>0)       self[lp++]=self[sp];<br \/>      else if (m==0) buf[cp--]=self[sp];<br \/>      else           buf[rp++]=self[sp];<br \/>    }<br \/>    int llen=lp;<br \/>    for (int i=buf.Length-1; i>cp; i--) self[lp++]=buf[i];<br \/>    if (mode>0) {<br \/>      System.Threading.ThreadStart rd=() => {<br \/>        buf._StableQuickSortDestory(rp, mode-1, f);<br \/>        Array.Copy(buf, 0, self, lp, rp);<br \/>      };<br \/>      System.Threading.Thread rt=new System.Threading.Thread(rd); rt.Start();<br \/>      System.Threading.ThreadStart ld=() => { self._StableQuickSortDestory(llen, mode-1, f); };<br \/>      System.Threading.Thread lt=new System.Threading.Thread(ld); lt.Start();<br \/>      lt.Join(); rt.Join();<br \/>    } else {<br \/>      buf._StableQuickSortDestory(rp, mode, f);<br \/>      Array.Copy(buf, 0, self, lp, rp);<br \/>      self._StableQuickSortDestory(llen, mode, f);<br \/>    }<br \/>  }<\/pre>\n<p>\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u306f\u6570\u304c\u5c11\u306a\u3044\u3068\u672c\u5f53\u306b\u8abf\u5b50\u304c\u60aa\u3044\u306e\u306750\u500b\u4ee5\u4e0b\u3067\u633f\u5165\u30bd\u30fc\u30c8\u306b\u5207\u308a\u66ff\u3048\u3066\u3044\u307e\u3059\u3002<br \/>\u305d\u308c\u3067\u3055\u3063\u304d\u306eMain\u30e1\u30bd\u30c3\u30c9\u306eMargeSortDestroy\u3092StableQuickSortDestory\u306b\u3059\u308c\u3070\u3044\u3044\u306e\u3067\u3059\u304c\u3001<br \/>MultiThreadMode=3\u306b\u30bb\u30c3\u30c8\u3057\u3068\u3044\u305f\u65b9\u304c\u3044\u3044\u3067\u3059\u306d\u3002<br \/>\u3068\u3044\u3046\u306e\u3082\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u306f\u5de6\u53f3\u306e\u5206\u5272\u304c\u5747\u7b49\u3067\u306a\u304f\u306a\u308b\u3053\u3068\u304c\u3088\u304f\u3042\u308a\u307e\u3059\u3002<br \/>\u305d\u3046\u306a\u308b\u3068\u5de6\u306f\u3068\u3046\u306b\u51e6\u7406\u7d42\u308f\u3063\u3066\u308b\u306e\u306b\u3001\u53f3\u306f\u307e\u3060\u307e\u3060\u3068\u3044\u3046\u3053\u3068\u304c\u3042\u308a\u307e\u3059\u3002<br \/>\u306a\u306e\u3067\u30b9\u30ec\u30c3\u30c9\u6570\u3092\u591a\u3081\u306b\u7528\u610f\u3057\u3066\u304a\u3044\u3066\u3001\u624b\u304c\u7a7a\u3044\u305f\u3089\u53f3\u306e\u3092\u5206\u62c5\u3057\u3066\u304f\u308c\u3068\u3002<br \/>\u305d\u3093\u306a\u611f\u3058\u3067\u3059\u3002\u3059\u308b\u3068CPU\u306f\u305a\u3063\u3068100%\u3067\u52d5\u3044\u3066\u304f\u308c\u307e\u3059\u3002<br \/>\u3053\u308c\u306740\u79d2\u3050\u3089\u3044\u3067\u30bd\u30fc\u30c8\u3057\u307e\u3059\u3002\u5b9f\u306f\u30de\u30fc\u30b8\u30bd\u30fc\u30c8\u3068\u6027\u80fd\u306f\u305d\u3046\u3082\u5909\u308f\u3089\u306a\u3044\u3093\u3067\u3059\u306d\u3002<br \/>\u3068\u3044\u3046\u306e\u3082\u30de\u30fc\u30b8\u30bd\u30fc\u30c8\u306f\u4e26\u5217\u51e6\u7406\u306b\u3059\u308b\u3068\u672c\u5f53\u306b\u6027\u80fd\u304c\u4e0a\u304c\u308b\u3093\u3067\u3059\u3051\u3069\u3001<br \/>\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u306f\u3055\u3063\u304d\u8a00\u3063\u305f\u3088\u3046\u306a\u4e8b\u60c5\u3067\u4e26\u5217\u51e6\u7406\u304c\u306a\u304b\u306a\u304b\u3046\u307e\u304f\u3044\u304b\u306a\u3044\u3068\u3002<br \/>\u305d\u308c\u3067\u30b9\u30ec\u30c3\u30c9\u6570\u3092\u5897\u3084\u3059\u3068\u9045\u304f\u306a\u3063\u3066\u304f\u308b\u3002<br \/>\u305d\u308c\u3068\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u4e00\u822c\u306e\u554f\u984c\u3067\u3059\u304c\u3001\u3042\u308b\u5024\u306e\u9078\u3073\u65b9\u306b\u3088\u3063\u3066\u3001\u6642\u9593\u304c\u304b\u304b\u308a\u3059\u304e\u3066\u3057\u307e\u3046\u3068\u3044\u3046\u554f\u984c\u304c\u3042\u308b\u3002<br \/>\u5b89\u5b9a\u30bd\u30fc\u30c8\u306a\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u3067\u3059\u304c\u3001\u6b8b\u5ff5\u306a\u304c\u3089\u304b\u304b\u308b\u6642\u9593\u306f\u4e0d\u5b89\u5b9a\u3067\u3059\u3002<br \/>\u3068\u3044\u3046\u308f\u3051\u3067\u3055\u3063\u304d\u306e\u30de\u30fc\u30b8\u30bd\u30fc\u30c8\u306e\u65b9\u304c\u304a\u3059\u3059\u3081\u3067\u3059\u306d\u3002<\/p>\n<hr \/>\n<p>\u3044\u308d\u3044\u308d\u8a66\u3057\u3066\u3044\u305f\u3051\u3069\u3001\u3084\u3063\u3071\u308a\u30de\u30fc\u30b8\u30bd\u30fc\u30c8\u306f\u5b89\u5b9a\u3057\u3066\u3044\u3044\u3067\u3059\u306d\u3002<br \/>\u3053\u308c\u306fPerl\u304c\u30de\u30fc\u30b8\u30bd\u30fc\u30c8\u306b\u5207\u308a\u66ff\u3048\u305f\u306e\u3082\u7d0d\u5f97\u3044\u304f\u3053\u3068\u3060\u3002<br \/>\u3068\u3053\u308d\u3067\u4e45\u3057\u3076\u308a\u306bC#\u4f7f\u3063\u3066\u305f\u3089\u3001\u914d\u5217\u81ea\u4f53\u306b\u306fpush\u3082shift\u3082\u306a\u3044\u3068\u3002<br \/>\u3060\u304b\u3089\u59cb\u3081System.Collections.Generic.Queue<t>\u30af\u30e9\u30b9\u3092\u4f7f\u3063\u305f\u3093\u3067\u3059\u306d\u3002<br \/>\u3057\u304b\u3057\u3042\u307e\u308a\u306b\u9045\u3044\u3057\u3001OutOfMemoryException\u6295\u3052\u308b\u3057\u3002\u3053\u308c\u3067\u697d\u3067\u304d\u308c\u3070\u306a\u3041\u3068\u3044\u3046\u6c17\u6301\u3061\u306f\u3042\u3063\u305f\u306e\u3067\u3059\u304c\u7121\u7406\u3089\u3057\u3044\u3002<br \/>\u3068\u3044\u3046\u308f\u3051\u3067\u914d\u5217\u3092\u30ac\u30ea\u30ac\u30ea\u64cd\u4f5c\u3059\u308b\u30d7\u30ed\u30b0\u30e9\u30e0\u3092\u4e45\u3005\u306b\u66f8\u304d\u307e\u3057\u305f\u306d\u3002<br \/>\u3084\u3063\u3071\u308aPerl\u3084\u3089\u306e\u914d\u5217\u64cd\u4f5c\u95a2\u6570\u306f\u5049\u5927\u3067\u3059\u306d\u3002<br \/>\u3051\u3069\u305d\u3046\u3044\u3046\u306e\u306b\u5bfe\u5fdc\u3067\u304d\u306a\u3044.NET Framework\u306e\u914d\u5217\u306f\u52d5\u4f5c\u304c\u901f\u3044\u3067\u3059\u304b\u3089\u306d\u3002\u305d\u3046\u3044\u3046\u610f\u5473\u3067\u306f\u3042\u308a\u304c\u305f\u3044\u304b\u306a\u3068\u3002<br \/>\u9069\u6750\u9069\u6240\u3068\u3044\u3046\u3053\u3068\u3067\u3059\u304c\u3001\u3042\u307e\u308a\u306b\u5de8\u5927\u306a\u30c7\u30fc\u30bf\u3092\u6271\u3046\u3068\u304d\u306f\u3072\u305f\u3059\u3089\u914d\u5217\u3092\u4f7f\u3046\u306e\u304c\u3088\u3055\u305d\u3046\u3067\u3059\u3002<br \/>\u305d\u3046\u3058\u3083\u306a\u3051\u308c\u3070System.Collection\u306e\u4e0b\u306b\u3042\u308b\u6570\u3005\u306e\u30af\u30e9\u30b9\u3092\u9078\u3093\u3067\u4f7f\u3063\u3066\u3082\u4fbf\u5229\u304b\u306a\u3068\u601d\u3044\u307e\u3059\u3088\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u3068\u3053\u308d\u3067\u6628\u65e5\u306e\u8a18\u4e8b\u3067\u6700\u5f8c\u306b\u66f8\u3044\u305f\u3001\u5b89\u5b9a\u306a\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u3067\u3059\u304c\u3001\u4f8b\u3048\u3070\u3053\u3093\u306a\u306e\u3002 sub mysort{ return @_ if(@_<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-1599","post","type-post","status-publish","format-standard","hentry","category-computer"],"_links":{"self":[{"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=\/wp\/v2\/posts\/1599","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1599"}],"version-history":[{"count":0,"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=\/wp\/v2\/posts\/1599\/revisions"}],"wp:attachment":[{"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1599"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1599"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hdmr.org\/d\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1599"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}