「クイックソート」が商標登録されていた 53
ストーリー by nagazou
どんな機械にこの名前がつくのだろうか 部門より
どんな機械にこの名前がつくのだろうか 部門より
特許情報プラットフォームによれば、「クイックソート」が商標として登録されているようだ（特許情報プラットフォーム）。
呼称に関してはクイックソートもしくはソートが登録されている。権利者は大阪にある椿本チエインで、主に産業用機械を手がけている企業。単語的にはコンピュータ分野のクイックソートとは同じものだが、用途的には以下の通り産業用機器向けとなっていることから、コンピュータ関連の製品とぶつかって揉めることはなさそうではある。
金属加工機械器具,土木機械器具,荷役機械器具,化学機械器具,動力機械器具（陸上の乗物用のものを除く。）,廃棄物圧縮装置,廃棄物破砕装置,機械要素（陸上の乗物用のものを除く。）,起動器,交流電動機及び直流電動機（陸上の乗物用の交流電動機及び直流電動機（その部品を除く。）を除く。）
選別機の事「ソーター」って言うやん (スコア:1)
コンベアメーカーがそれ関連の商標持っていて何の不思議が？
Re:選別機の事「ソーター」って言うやん (スコア:2, 参考になる)
これが実物ですね。
https://www.tsubakimoto.jp/materials-handling/distribution/products/qu... [tsubakimoto.jp]
考えてみると、種を分類・分別することがsortなのであって、こちらの方が原義に近いものなのでは。
分類を繰り返していけば確かに順番には並んできますが、順序という意味はもともとなかったような。
Re: (スコア:0)
これを晴れと言われた気がした
https://www.youtube.com/watch?v=RrQO9qse3h8 [youtube.com]
他にもあると言われた気がした
Re: (スコア:0)
球形ローラー使って自由度が高いんだな。
平行から交差なんてのも簡単に出来るし、シュートの融通も利く。
うん、良さげなシステムだわ。
Re: (スコア:0)
https://www.tsubakimoto.jp/power-transmission/top-chain/block/ [tsubakimoto.jp]
Re: (スコア:0)
最初に「ぶろっく ちぇーん」でイメージするのって、
だいたいこういう奴だと思う。
https://twitter.com/yamada_theta/status/1234058849503473670 [twitter.com]
Re: (スコア:0)
こっちかと思った→ https://electrictoolboy.com/media/12242/ [electrictoolboy.com]
語順が反対だった
Re: (スコア:0)
よくわからんけど、回転寿司のコンベヤの従姉妹？
Re: (スコア:0)
レゴみたいにハメ込みだけで構成できるコンベア用チェーン。
特許情報プラットフォーム (スコア:1)
ようやくURL直リンクできないアホな設計が見直されたのか。まあこれは素直に褒めておこう。すばらしい
ダメっ娘部下がいた時代。。。 (スコア:1)
「16:00に納品だから、14:00までにソートしておいてくれ。」と頼んだら、13:00を過ぎても何の連絡もない。
どうしたのか聞いたら「14:00までそおっとしとけと言われたのでそのままにしていました。」とのこと。
慌てて引き取って、当時のマシンで処理し、何とか納品に間に合わせたのも今では楽しい思い出。
今のパソコンなら秒で終わる処理だと思う。
コンピュータ関連の製品は (スコア:0)
普通名称に引っかかって通らないのではなかろうか。（担当者が知っていれば）
appleよりはマシかな (スコア:0)
Windowsもsがなければもっとやばかったかと
Re: (スコア:0)
Windowsもsがなければもっとやばかったかと
wINDOw
インド人も怒るかもしれんな
Re: (スコア:0)
wINDOw
インド人も怒るかもしれんな
どちらかというと草生やしてるように見える。
Re:appleよりはマシかな (スコア:1)
OpenOffice「代わりにオレがCalc使うわ」
Re: (スコア:0)
そういや、MultiplanがどうしてExcelになったんだろう？
Re: (スコア:0)
セリオにちなんだ名前に改名したから。
Re: (スコア:0)
HMX-13?
Re: (スコア:0)
当時は女性が使うことも多く、まるチンぷらん。のように聞こえて恥ずかしかったから。
ウソばっか (スコア:1)
汎用ソートアルゴリズムで、クイックソートを時代遅れにするほど
早い奴って、具体的にはどれの話？
＞あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
知ったかぶりしても、こういう所でウソがバレる。
クイックソートでは再帰呼び出しは使わない。
再帰呼び出しを使っても書けるだけ。必用なんてとんでもない。
Re:ウソばっか (スコア:1)
具体的なソート名が欲しいですね
ただ、今のソートって内部はイントロソートのようにクイックソートだけでなく組み合わせたソートになっているケースはあるかも
素朴なクイックソートだと最悪計算量にさせることもできてしまうので
とはいえ概ね多くのケースではクイックソートを時代遅れと表現するような差は生まれないですね
Re:ウソばっか (スコア:1)
「2要素間の比較で並べ替えるソート」としては、理論的に最速でも O(n log n) が限界であることは証明されていて、
クイックソートやマージソート、ヒープソートなどの「速いソート」はどれも O(n log n) なので、
所詮、同じ計算量オーダーの中でのオーバーヘッドの優越にすぎず、
「時代遅れにするほど速い奴」なんてのはありえないでしょうね。
バケットソートやラディックスソートが使える場面なら、そっちの方が桁違いに速いですが、そもそも使える場面が限られるし。
Re:ウソばっか (スコア:1)
彼は量子コンピュータの進歩で、すべてのn!の並べ替えが重ね合わさった状態から正しくソートされた状態に波束を収束させることが可能になった未来から来たんだよ。そこではこの量子ボゴソート(?)がすべてのソートアルゴリズムを過去の遺物にしたんだ。
Re: (スコア:0)
クイックソートは最悪値のO(N^2)が比較的容易に発生するし、メジャーな処理系のsortにはまず採用されてない
Re:ウソばっか (スコア:1)
そんなことない。よくある並べ替えるリストの要素数に応じてソートアルゴリズムを使い分けるケースでクイックソートを使ってるケースもある。
例えば、.net 5 の Array.Sort メソッドでは、
このメソッドでは、次のように introspective sort (introsort) アルゴリズムが使用されます。
- パーティションサイズが16要素以下の場合は、 挿入並べ替え アルゴリズムが使用されます。
- パーティションの数が 2 * Log Nを超えている場合 ( n は入力配列の範囲)、 heapsort アルゴリズムが使用されます。
- それ以外の場合は、 クイックソート アルゴリズムを使用します。
https://docs.microsoft.com/ja-jp/dotnet/api/system.array.sort?view=net-5.0 [microsoft.com]
Re:ウソばっか (スコア:1)
Re: (スコア:0)
O(N^2)になるのは、データが逆順に並んでいるときですね。作為的にやらない限りは容易に発生しないと思いますが。
Re: (スコア:0)
というか、実作業で一番クリティカルなのはワーストなんだよなあ。
うちの上司も困ったことに、「普段の速度稼ぐのは簡単だろ？」と言ってワーストが悪化する案を持ち込んで来るんで騒ぎになるんだが。
「これなら最速1割早い」「ワーストが1割以上遅くなる」ってよくケンカしている。
システムの要件が余裕が有るのなら反対しないが、ギリギリで破綻する様な状態でそれ言われても。
Re: (スコア:0)
そういや、「最悪でもO(n log n)時間」で「安定(入れ替えなくて良い所は元の順序が保たれる)」で「内部(必要な追加のメモリがO(log n))」な、ある種の究極ソートアルゴリズムは見つかっていないようですが、存在しないことが証明されてるような話なんでしょうか? あるいは有るかどうかもまだ分かっていない未解決問題なんでしょうか?
Re: (スコア:0)
元の論文は読んで無いけど、解説によると実用上速くないらしい。
https://stackoverflow.com/questions/22390951/how-does-the-franceschini... [stackoverflow.com]
Re: (スコア:0)
「読んで無い」
Re: (スコア:0)
「内部」である、なんて用語は聞いたことないけど一般的なのか？
括弧の位置がおかしいだけ？
Re: (スコア:0)
in-placeなソートアルゴリズムを日本語に訳すと内部ソート。
内部ソートとしての性質を満たすような、をどう短く形容詞に落とし込めば良いのかは良く知らない。
Re: (スコア:0)
煽るタイプの教えてクンにあまり給餌しないでくれないかな
Re: (スコア:0)
同意。
ソートアルゴリズムは研究され尽くしたと言ってもよいくらい歴史がありますが、大規模データのソートなどで門外不出のアルゴリズムがあっても不思議はないかも。ソートアルゴリズムが熱心に研究されていた時代とはデータ量が桁違いなので。
Re:ウソばっか (スコア:1)
データのソートではないけど、変わったやり方してるのはいくつかあるね。
ブロックソートはデータ圧縮以外にもバイオインフォマティクス方面で色々応用されてるぽいし、
ウェーブレット木（ウェーブレット変換とはあまり関係ない）で
大量データに対する何種類かの処理を超高速にこなす方法があったり、
大量データとは無関係だけど秘密計算とか用法だけだと意味不明な奴とかもある。
# 門外不出というより使用シーンがマイナーな奴は目立たんというだけな気もする。
# ブロックチェーンを使った演算系の奴をそういう方面で興味津々に見に行ったら絶望した。
Re: (スコア:0)
ブラウザがJavaScriptでどうやってソートしてるのか調べてみたけど、ざっと見た感じ、Firefoxはマージソートで、Webkit系はstd::sortを呼んでるぽいから、おそらくイントロソートってことになるね。
Re:ウソばっか (スコア:1)
C++のstd::sort()だとイントロソートか何か。
今時の規格では「最悪時間計算量がO(n log n)の内部ソート」と定められているので少なくともクイックソートでは無理。
std::stable_sort()は「最悪時関計算量がO(n log n)の安定そーと」と規格で定められてるので、これもクイックソートは該当しない。
JavaのSort()は安定ソートと規格で定められていて、同じく。
マニュアルを見ると、それじゃなきゃダメって訳ではないけど、と前置きしてマージソートが例として挙げられてる。
PythonやRubyやJavascriptも最近では利便性のため安定ソートと明言されたり、
明言される前から利便性のため、こそっと実装がそうなってたりする。
マニュアルを見るとPythonは今はTimソートとやららしい。
実用されてるとしたら、使える既存のライブラリが存在しないようなマイナーな環境で、
他から移植するにも実装にかけられる時間が足りないか、極端にメモリが小さいかで、
しょうがなく…とかそういう? そんな例あるのかな。
Re: (スコア:0)
イントロソートはクイックソートの亜種でしょ。
Re: (スコア:0)
ソートアルゴリズムを性質で分類したら、全く別の枠に収まるぐらいに改良された亜種だけどね。
その亜種もC++みたいなスピード狂向けの言語でしか標準ライブラリに採用されない程度に人気が無い。
なんでこんなに不安定なソートが不人気なのか知らないけど。
あとまあ、でかいデータを扱うソフトウェアほどスピード狂が実装する傾向にあるだろうし、
その極北のデータベースなんかでは使われてるのかも知れないけど。
そうなると、世界で最も大量のデータをソートしてるアルゴリズムは? の答えはその手の亜種かも知れない。
Re: (スコア:0)
> なんでこんなに不安定なソートが不人気なのか知らないけど。
？？？
Re: (スコア:0)
不安定なソートを標準ライブラリに持っているプログラミング言語が少ない。
不安定・安定の違いは、安定なソートは必要の無いところを入れ替えない。不安定はそういう保証が無い。
例えば名前順に並んでいる成績表を成績順にソートしたときに、100点のやつが複数人居たとする。安定なソートアルゴリズムだと、100点のやつだけ抜き出すと、そこは名前の順のままになっている。不安定なソートアルゴリズムでソートすると、同点の連中の並び順が揃わない。そういう成績表をそのまま張り出すと不格好な結果になる。
不格好で済めば良いけど、オークションなんかで、入札金額
Re: (スコア:0)
条件を満たすまでは普通にクイックソートするアルゴリズムがクイックソートとは全く別の枠？
しまいにゃスピード狂とか全く関係ないこと口走ってるし。
そこは言語規格側でアルゴリズムまで明示してるかどうか程度の話だよ……
革新的進歩してると思ってたら案外して無かったってのが恥ずかしいのはわからんでもないが……
Re: (スコア:0)
クイックソートは「最悪計算量がO(n^2)」の枠。
イントロソートに改良すると「最悪時関計算量がO(n log n)」の枠。
アルゴリズムのアイデアの系譜で分類しても実用的な意味はない。
最終的に出来上がるアルゴリズムの性質が別物という話。
同じく、言語の規格ではアルゴリズムが明示されてはいない。
そんなところを規格化したら、より良いアルゴリズムが見つかったら困るだろうに
その関数やメソッドが満たす性質(安定か不安定か、最悪時関計算量がO(n log n)であるなど)が示されているだけ。
その条件を満たすアルゴリズムがあれば、実装は何でも良い。
一般に、不安定なソートの方
Re: (スコア:0)
適当に放言してるその文体、元コメの人ですね？
Re:ウソばっか (スコア:1)
クイックソートは、マルチスレッド化したときにキャッシュが効きやすいように領域を分割するので、メインメモリに収まるようなデータ列のソートについては、むしろ、時代にマッチしているように思います
Re: (スコア:0)
そりゃダムソートだよ。ダムん早いよ。
Re: (スコア:0)
もしかして：コムソート
Re: (スコア:0)
また髪の話してる...