気に入った記事をブックマーク
- 気に入った記事を保存できます
保存した記事の一覧は、はてなブックマークで確認・編集ができます
- 記事を読んだ感想やメモを書き残せます
- 非公開でブックマークすることもできます
tech.mobilefactory.jpエントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント16件
- 注目コメント
- 新着コメント
オーナーコメントを固定しています
mcq
基準点(0,0)/現在地(-1,0)/駅A(2.5,0)/駅B(-4,0)っていう例を考えると、Aの距離3.5、Bの距離3.0で最寄り駅はBなのに、赤円の半径3.0内に存在するAを間違って出力しそう＼11/22に修正されたけど、←の例でAは赤円内だけど青円外になる
shunkeen
事前計算のO(N)のとこ、ソート処理入れたらO(N log N)じゃない？まあ、移動したところで 、ほとんど整列済みだからリストを再利用して、挿入ソートすれば瞬殺かもだが。あとはpartial sortで誤魔化しても問題ない気もする。
fashi
「ChatGPT に聞くと KD-Tree という初めて聞くデータ構造で時間計算量を落とす方法を紹介されました」「コードレビューもメンテナンスも大変です」理論が確立されてて実装例も多くある方式の方がメンテしやすい気がするな
tohima
事前計算をブロック式にして現在地を(0,0)として(-1,-1)から(1,1)の範囲の駅を事前計算して、毎秒を(0,0)にいるか判定したほうが効率良さそうな気がするけど、実際と感覚って結構違うから違うんだろなw
オーナーコメントを固定しています
fashi
「ChatGPT に聞くと KD-Tree という初めて聞くデータ構造で時間計算量を落とす方法を紹介されました」「コードレビューもメンテナンスも大変です」理論が確立されてて実装例も多くある方式の方がメンテしやすい気がするな
shunkeen
事前計算のO(N)のとこ、ソート処理入れたらO(N log N)じゃない？まあ、移動したところで 、ほとんど整列済みだからリストを再利用して、挿入ソートすれば瞬殺かもだが。あとはpartial sortで誤魔化しても問題ない気もする。
mcq
基準点(0,0)/現在地(-1,0)/駅A(2.5,0)/駅B(-4,0)っていう例を考えると、Aの距離3.5、Bの距離3.0で最寄り駅はBなのに、赤円の半径3.0内に存在するAを間違って出力しそう＼11/22に修正されたけど、←の例でAは赤円内だけど青円外になる
tohima
事前計算をブロック式にして現在地を(0,0)として(-1,-1)から(1,1)の範囲の駅を事前計算して、毎秒を(0,0)にいるか判定したほうが効率良さそうな気がするけど、実際と感覚って結構違うから違うんだろなw
sumijk
どちらもO(N)だが動的に探索範囲を更新して平均(最悪)計算量を抑えるという話だと思うが移動速度が電車程度だとするとベースラインをN_max〜全国の駅数とするのはフェアなのか？上位1割くらいしか更新されないよね
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
いまの話題をアプリでチェック！
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
毎秒現在地を使った最近傍探索をしたい - Mobile Factory Tech Blog
こんにちは。駅メモエンジニアの id:dorapon2000 です。 約半年前の 6 月 1 日にステーションメモリーズ... こんにちは。駅メモエンジニアの id:dorapon2000 です。 約半年前の 6 月 1 日にステーションメモリーズ！（駅メモ！）10 周年を記念してタイムラインと地図の切替機能をリリースしました。大変好評を頂いておりとても嬉しいです。 今回は、その機能の中で毎秒最寄り駅を計算するロジックをどのように実現しているのかについてお話します。様々なスペックの端末で遊ばれているため、可能な限りリソースを節約するような工夫をしました。堅い言い方をすれば、過去の計算情報を使った最近傍探索アルゴリズムを実装しました。 記事中のサンプルコードは TypeScript で記述しています。 2024/11/22 追記： はてなブックマークでのご指摘ありがとうございます。 ご指摘をいただいた「事前計算の時間計算量」と「基準点と現在地の距離が近すぎるとき」の説明部分を修正しております。 誤：事前計算を O(N
ブックマークしたユーザー
すべてのユーザーの
詳細を表示します
詳細を表示します
tech.mobilefactory.jp
tech.mobilefactory.jp
tech.mobilefactory.jp
tech.mobilefactory.jp
news.tv-asahi.co.jp
fromdusktildawn.hatenablog.com
www.jcp.or.jp
www.sponichi.co.jp
anond.hatelabo.jp
techblog.lycorp.co.jp
speakerdeck.com/spindle
www.socym.co.jp
www.itmedia.co.jp
www.techno-edge.net
support.inkling.com
www.lib.ibaraki.ac.jp
x.com
mona-news.com
2024/11/21 リンク