はてなキーワード: ソートとは
まず、もしテーブルが小さいならそれこそJOINなんてそもそも無駄。
usersが1万件くらいのサイズなら、最初に全件引いて辞書にしておけば、処理時は全部O(1)。
一方JOINはどうなる？SQL構文パース、オプティマイザ、プランの生成と実行、インデックス参照、場合によってはソート・一時テーブル、何重にもコストがかかる。JOIN使うのは、全力で自己放尿してるのと同じ。
「今後も巨大にはならない」
これ、現実逃避の典型な。開発初期で小さくても、プロダクトってのは使われてナンボ。使われればデータは自然に増える。
さらに「本当に巨大なら辞書は無理」って言ってるけど、じゃあJOINならいけると？
脳ミソの冷却ちゃんと回ってるか？
JOINってのは重いんだよ。リレーショナル演算のコスト、現場でまともに見積もったことあるか？
JOINするたびに何十万、何百万件ってレコード舐めて、インデックス使って、それでもI/Oボトルネック起きる。
そういうの避けるためにRedisとか列指向DBとかプリマテリアライズするんだろ。JOINは最適解じゃない、最後の逃げだよ。
結局、JOINを正当化する理由が「JOIN以外知らない」ってだけじゃねえの？
設計手段を学ばず、「それしか知らない」ことを自信に変えるな。
知識の不足を理屈で補うのは無理がある。JOINを使うなとは言わん。でも、JOINが最適って言うなら、それ相応の読み、キャッシュ設計、オプティマイザとの対話が必要だ。
農林水産大臣が更迭された。失言ひとつで更迭というのも極端な気もするがコメ不足というのはそれだけ切羽詰まった問題なのだろう。前にスーパーでコメを買ったのはいつだったか。田舎の方に住んでいるため、コメが店頭から消えるということはなかったように思う。
更迭を「更送」と書いている人がいた。確かに字の形はそっくりである。しんにょうの中身は失うか朕のつくりか。大抵の機器には漢字変換が搭載されるようになったが、読み方を知らなければ漢字変換を利用することもできない。読み方を調べるにも一工夫が必要だ。(iPhoneなら選択して調べるという簡単なコマンドがある)
私の学生時代はタッチパネルに漢字を書ける電子辞書というものがあった。いまでもスマホが利用できない学生は使っているかもしれない。それより前は漢字辞典を開いたのだろうか。部首でソートされた事典ははじめ非常に使いにくかったが、今になってありがたみを感じる。
我々は漢字辞典の使い方から初等教育を受けているのだから、読めない漢字があることは恥ずかしいことではないが、知ろうとしないことはやはり恥である。
ところで、果たして私もこの円マークに足がついた漢字の読み方を知らなかった。しかし手元に電子辞書も漢字辞典もない。部首も見当がつかない。「天」という部首は存在するだろうか。そう思ってGoogleで「天にちょんちょん」と検索した。これで見つかるのだから大変便利な時代になったものである。せっかくなので読み方は皆さんそれぞれで確認していただきたい。
最後に、「斜に構える」とはなんと読むだろうか。私はかつてよりずっと「はすにかまえる」と読み、発音していたが「しゃにかまえる」が正解らしい。私一人かとも思ったのだが小学校から大学まで一緒だった友人が「はすにかまえる」と発音したのを聞いた。一種の方言なのか、単なる誤用なのか。その友人とは久しぶりに顔を合わせたのだが奇妙な縁を感じ帰路についた。
bookliveとかの検索結果って理論的にはページ送りするたびに結果が再生成されるだろ。
漫画全部知りたいみたいな動機で漫画全部引っかかるような検索条件で結果出すと、全部探している間にどんどん検索順位が変わるわけで、ページ送りしているうちに、まだ見てないページにある漫画が、順位の更新で今まで見たページに移動することが十分な可能性あるわけだけし、しかもそれが何周しようと起こる。何周してもそのbookliveとかに登録されている漫画を全て確認しようとしても漏れが出る可能性はなくせないってことなんだよな。
これは人気順のようなアルゴリズム不明なソートならいうまでもなく最新順でも起こりうること(掘り下げてまた後日このへん書くかもしれない)。
なんとか、ページ送りのさせた方でもなんでもいいけど、こういう結果生成の方法をとっている物に対して漏れなくその検索条件でヒットする項目を抽出できるようなアルゴリズムって考えられないものなのかねえ？
https://anond.hatelabo.jp/20250421203939
まず大事な原則として、味や食感が違うものが混じっているとうまい。
チョコレートがくっついたクッキー（きのこ・たけのこもこの流派だ）がうまいのもこの原理が大きく作用している。
さて、リンドールは冷やして食べてもそのポテンシャルは引き出せない。公式サイトには
＞上質なチョコレートでできたシェルを破ると、この上なくなめらかなフィリングがお口の中で甘美にとけ始めます
とあるが、断言する、これは嘘だ。
適切な室温で馴染ませ、フィリングを融かして完全に液体にしてから食べるのが正しい。
外側のシェル、内側の溶けたフィリングがそれぞれ口の中で混じり合い、リンドールという一つの体験を生む。
それはせいぜい数秒間の至福に過ぎず、コスパという観点では決して優れたものではないことは確かだが、
きのこ・たけのこといったクッキーや均質な材料でできた板チョコには到達しえない世界であり、
リンドールが（行きつけの店の品揃え的に、あるいは経済力的に）お手軽に買える人間は幸いである。
問題は温度管理が難しいことで、包み紙を引っ張ってほどく際に柔らかくなったシェルが潰れてしまう、
あるいは完全に融解してべちょべちょの塊になってしまうといった事故も発生しがち。
丁寧に扱えば応えてくれるのがリンドールというチョコレートだ。
ちなみに
JSで０インデックスがヘダーのストリングのアレイのアレイからなるテーブルのカラムを別アレイのカラムインフォオブジェクトのディスプレイナンバーに合わせて並び替えて名前をnameからdisplayNameの値に入れ替えるコード
だと
想定される入力
['id', 'name', 'age'], // ヘッダー
['1', 'Alice', '30'],
['2', 'Bob', '25'],
];
const columnInfo = [
{ name: 'name', displayName: '名前', displayNumber: 0 },
{ name: 'age', displayName: '年齢', displayNumber: 1 },
{ name: 'id', displayName: 'ID', displayNumber: 2 }
];
[
['Alice', '30', '1'],
['Bob', '25', '2']
]
function reorderAndRenameTable(table, columnInfo) {
const nameToIndex = header.reduce((acc, name, idx) => {
return acc;
}, {});
const sortedColumns = [...columnInfo].sort((a, b) => a.displayNumber - b.displayNumber);
// 新しいヘッダーを displayName に置き換え
const newHeader = sortedColumns.map(col => col.displayName);
// 各行の値も同じ順で並び替える
const newBody = body.map(row => {
return sortedColumns.map(col => row[nameToIndex[col.name]]);
});
return [newHeader, ...newBody];
}
ここまで数秒なのでまあこれくらいだと書くよりは早い
以下の問題を徹底的に抽象数学を用いて定式化しなさい。また、具体的実装についても定式化しなさい。ただし、文献はarxiv等の信頼できる情報源のみを利用しなさい。
本報告では、ユーザー集合Uとアイテム集合Iからなる推薦システムを、圏論と行列代数の統合的枠組みで再構築する。特にarXiv論文[2][7]で提案されたSheaf4Recアーキテクチャと、古典的マトリックス分解手法[3][8]を統合した新しい定式化を提案する。実装戦略としてApache Spark[4]を活用した分散処理を採用し、理論的保証と計算効率の両立を実現する。
圏RecSysを次のように定義する：
各ユーザーu∈Uの行動履歴f(u)⊆Iは、圏論的データモデル[7]において層(sheaf)構造で表現される。具体的には：
各スコア関数g_j:2^I×I→ℝ^mは、層の断面(section)として定式化される：
g_j = \bigoplus_{i=1}^m \mathcal{F}_i \otimes \mathcal{G}_j
ここで$\mathcal{F}_i$はアイテムiの特徴層、$\mathcal{G}_j$はスコアタイプjの重み層[2]。
任意のS⊆T⊆Iに対して、層的接続写像δ:F(S)→F(T)が存在し、次を満たす：
\forall j, \|g_j(S) - δ(g_j(T))\| ≤ L_j \cdot d_H(S,T)
ユーザー-アイテム行列R∈ℝ^{|U|×m}を以下のように分解[3]：
R ≈ UΣV^T \quad (U∈ℝ^{|U|×r}, Σ∈ℝ^{r×r}, V∈ℝ^{m×r})
Apache Spark[4]を活用した分散計算フレームワーク：
from pyspark.mllib.recommendation import ALS model = ALS.trainImplicit( ratings=interactions, rank=100, iterations=10, lambda_=0.01, blocks=200 # 分散処理用ブロック数 )
g_1(u,i) = U_u \cdot V_i^T
g_2(u,i) = \text{SheafConv}(F(u), F(i); \Theta)
g_3(u,i) = \sum_{t∈T_{ui}} e^{-λ(t-t_0)}
h(Y)_i = \bigoplus_{j=1}^n w_{ij} \otimes y_{ij}
ここで⊕はmax-pooling、⊗はアダマール積[2]。重み行列W=(w_{ij})は以下の最適化問題で決定：
\min_W \sum_{u∈U} \|R(u) - h(G(u))\|_F^2 + λ\|W\|_*
val interactions = spark.read.parquet("hdfs://interactions") val model = new ALS() .setRank(100) .setBlocks(200) .run(interactions) val scores = model.userFeatures .join(itemFeatures) .map { case (u, (v_u, v_i)) => (u, dotProduct(v_u, v_i)) }
| 手法 | 時間計算量 | 空間計算量 |
| 集中処理[3] | O(m^3) | O(m^2) |
| 分散処理[4] | O(m^2/p) | O(m√p) |
| Sheaf4Rec[7] | O(m log m) | O(m) |
ここでpは並列度、mはアイテム数[4][7]。
ブロックSVDアルゴリズム[3]は、任意のε>0に対してO(log(1/ε))反復でε近似解を達成する。
証明の概略：
\|R - U^{(k)}Σ^{(k)}V^{(k)T}\|_F^2 ≤ (1 - 1/\text{cond}(R))^k \|R\|_F^2
\|h(Y) - h(Y')\| ≤ \sum_{j=1}^n L_j \|W_j\| \cdot \|y_j - y_j'\|
本論文では、圏論的構造と分散行列分解を統合した新しい推薦システムフレームワークを提案した。Sheaf4Rec[7]の層構造とSpark[4]の分散処理を組み合わせることで、精度と効率の両立を実現。今後の課題として、動的層構造の適応的更新や量子化による計算効率改善が挙げられる。
Citations:
[1] https://arxiv.org/html/2407.13699v1
[2] https://arxiv.org/html/2304.09097v3
[3] https://www.cs.toronto.edu/~mvolkovs/sigir2015_svd.pdf
[4] https://ics.uci.edu/~cs237/projects2020/4_reports.pdf
[5] https://arxiv.org/abs/2502.10050
[6] https://arxiv.org/pdf/2109.08794.pdf
[7] https://arxiv.org/abs/2304.09097
[8] https://dspace.mit.edu/bitstream/handle/1721.1/99785/927438195-MIT.pdf?sequence=1
ポモドーロ は、ハーバード大学が提供する、David J. Malan 教授が教える人気のコースです。このコースは、コンピュータ サイエンスとプログラミングの幅広い入門を提供するように設計されており、幅広いトピックをカバーしています。
: C、Python、JavaScript、SQL、HTML/CSS を使用したプログラミングを学習します。
配列、リンク リスト、スタック、キュー、ハッシュ テーブルなどのデータ構造を理解します。
ポインタ、メモリ割り当て、その他の低レベルのメモリ管理の概念を学習します。
フロントエンドとバックエンドのプログラミングを含む、Web 開発の入門を学習します。
ChatGPT: 「ホテルアムステルダムハウステンボス」をアイウエオ順にソートすると、以下のようになります。
アウオステスダテンハホテルマムボ
私: アイウエオ順とは「アイウエオカキクケコ…」と続く五十音順のことです。この通りにソートしてください。
ChatGPT: 「ホテルアムステルダムハウステンボス」の文字を五十音順（アイウエオ順）に並べ替えると、以下のようになります。
私: アイウエオ順を全て指定します。 アイウエオカキクケコサシスセソタチツテトナニヌネノハヒフヘホマミムメモヤユヨラリルレロワヲン
この順でソートし直してください。
ChatGPT: ご指定の五十音順で「ホテルアムステルダムハウステンボス」を並べ替えると、
となります。
なんか新種の蝶の名前が誕生した。そもそもマはどこから来たんだ。
誰かうまくいくまであとは頼む
30代後半の男。
身長体重は普通。見た目もまあ普通と思う。高校時代には同級生と付き合ってた。
で、上京して、女遊びをしたくなった。まずモテるためにとにかく清潔感は気をつけた。小まめな散髪、眉毛カット、常にコンタクト、ファストファッションでもいいからサイズの合う新品、人と会う前はシャワー、直前や中座してブレスケア。
会話面では高圧的にならないようにとか、下ネタを言わない、あと何より相手の意見を肯定するとかの基本を抑えた。
1年目は東京や学生生活に馴れるのに精一杯だったが、2年目からは成果が見え始めた。2年の夏休みから女と寝なかった月はまったくないと思う。
20代まではそのまま常に女には困らない程度にはモテた。ナンパとかはやってない。
大学時代はイケメンや面白いやつには負けるけど、「相談しやすい人」という枠でサークルやバイトの後輩の誰かとはいい雰囲気になってた。
意識的に3番手を狙った節もある。競争率低い、というか競争するほどではない手軽さ、それでいて他の男よりは身綺麗にしてるちょうどよさみたいなのを意識した。
大学生の男なんて(とくに20年近く前のZ世代など影も形もなかった時代は)みんな大体清潔感なくて、女にもだいたい偉そうですぐ下ネタを言った。なので逆をやってるだけで、平均よりかは相対的に上になったんだよ。
良い行いではないとわかっているが、大学とバイト先とで常にセフレが三人くらい同時並行いた。
色んな女の子と遊びたいから彼女になりたがってるなーと思ったらリリースしてた。まあ裏では実は評判悪かったかもしれない。
卒業してからはマッチングアプリをやると学生時代よりから面倒になったが誰かとは常に男女の関係になって、もう一人くらいはキープできてた。あと趣味のサークルとかね。これも女の子多いとこを狙ってた。
基本は2歳差くらいが一番相性よかったけど、20代後半は10歳近く年下とも結構関係持ってた。いわゆる周りの男がガキに見える女の子みたいなタイプ。これもまあ褒められたことではないと分かってるので、友達とかにもあんま話したことはない。
逆に年上とも年下ほどは多くないがちょくちょくあった。
就職してからは仕事の人と男女関係になったことはないので、そこらへんのコンプラに関しては心配していない。
同意形成も意識して、酔わせた勢いでみたいなこともない。酔いすぎてたらなにもせず帰した。
一般的な痴話喧嘩以上になったことはない。大学以降は誰か特定の相手と付き合ってなかったし、そこを誤解させることはしなかった。
なんにせよ、ナンパ師ほど数を自慢できるわけではないが、とにかく女に飢えたことがない。風俗とか行く気がしれなかった。特殊なプレイをしたいならわからんが。
そんな感じで、女遊びをしようと思った18歳から20年弱、ピークは28歳だっただろうか。セフレが5人いるみたいなのがデフォルトだった。自分がテクニックも上がったのか、大学生の頃より明らかに色々手軽になった。
このまま自分は上手く女の子と遊んで、イケおじポジションに落ちつけるのだと思い込んでいた。なにせ年々成果は上がってるのだから。
が、甘かった。というか勘違いだった。30歳を越えたあたりで怪しくなり、半ばを越えて確信した。モテなくなっていってるのだ。
とにかく同じことをやっていても、女の子といい雰囲気にならない。同世代は清潔感があるだけじゃ足りないし、結婚も視野に入れるか、そうでなくとも20代みたいなズルズルした関係を望む子は絶対的に少なくなった。
30代にもなってそういうことやってるのはみっともないという見方が強まった。後半になればなるほど強まる。
この年になるとむしろ遊び好きは不倫してる人たちの方が多い印象すらある。結婚してなくとも、決まった恋人がいる人が多い。
いや20代でも社会人になれば一般的にそうかもしれないが、風当たりの強さがぜんぜん違う。その風は年々強くなる。
そして、そういうルーズな男女関係を望むタイプの20代半ばまでの若い子は、29歳はギリ「周囲のガキな男とは違う話のわかるお兄さん」と見てくれていたが、30代になると一気におじさん扱い。もう本当にぜんぜん違う。35歳になると物の数にも入らない。
「19歳や20歳から見たら28歳はおじさん」も正論とは思うし、勘違い男を増やさないためにも、それを世の中的な正論とすべきと思う。
だが自分の見てきた現実ではそれくらいならお兄さん扱いしてくれる子も結構いる。相当いる。少なくとも30歳のおじさん扱いとは雲泥の差。この2、3歳は天と地ほど差がある。これは世の中的に正しい正しくないではなく、俺の実感ベース。
もう本当に年齢言った瞬間に態度がぜんぜん違う。
マッチングアプリなんかは年齢でソートできるからマッチ数が露骨だし。
40代以降も女遊びしたいなら相応の収入と地位が必要になるのでそこをがんばるのは当然として、女遊びは卒業してどこかに落ちつくか、それとも一発勝負のナンパ師、パパ活なんかすらも見えてくる。
そういうのが嫌なら本当に落ちつくべきなんだろうなと思って最近は遊ぶのをやめて、真面目に一人の女性と交際している。結婚するかはわからん。結婚するかもしれない。不倫のチャンスがあったら我慢できるだろうか。
大体のものは日本語でアルゴリズムやデーター構造の解説があります。
でも、時々、こういうのがあります。
https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes.pdf
Rebalancing
Rebalancing produces a balanced version of the argument rope. The original
is unaffected.
(中略)
Many variations of this approach are possible. Our balance condition was expressed
in terms of length, and our algorithm tends to move long ¯at ropes close to the
root. One could also rebalance purely in terms of node count.
Ropeがくそ遅いのでリーフノードをリンクドリストでつなごうとしたら、訳が分からなくなりました。
適当にやってはいけないと思い、ググったら、Ropeのリバランスのやり方を解説した奴は英語の奴しかありませんでした。
あと、リンク先を読めばわかるけど、数学でおなじみの記号がいたるところに出てきます。
数３Ｃまで取ったほうがいいです。
大学に行けば体系的にアルゴリズムやデーター構造、最先端の技術を教えてくれますが、情報系の大学は数３Ｃが必須です。
そして、ネットに転がってるデーター構造の解説書は数３Ｃを勉強していることを前提に書かれていることが多いです。
微分積分が出た時代の数１Ａと数２しかとってないので、この手の本はマジで訳が分かりません。
だから、おじさんは高校生向けの優しい、アルゴリズムやデーター構造の本で勉強しました。
なぜかというとライブラリーしか触れず、リンクドリストやＡＶＬ木、クイックソートや基数ソートをかじったぐらいのプログラマーは腐るほどいるからです。
だから、君たちはおじさんのようにはなるな。
匿名で承認欲求満たそうとしてボコボコにされたら「承認欲求激しすぎｗ中二病かｗ」って中学生未満やん
実際に、
どのようなコンテンツを
どのようなクエリで（RESTなのかRPCなのかGraphQLかそれ以外か）
どのようにマッチして
返すAPIを君は作ったの？
承認欲求満たそうよ