703. Kth Largest Element in a Stream #53
Conversation
| end | ||
| ``` | ||
|
|
||
| なぜか間に合った。テストケースに厳しいものが少なかったのかも。 |
There was a problem hiding this comment.
コメントありがとうございます。
Array#insertはRuby VMからC関数にすぐに制御が渡って結果を返すが、Rubyで書いたループはVMからCの制御を何回も行き来するためオーバーヘッドが大きくなるということですね。
このあたり意識できていませんでした。
試しにinsertのような処理をRubyレベルで実行して比較したところArray#insertに比べて300倍近くの差がありましたね。
require "benchmark"
def native_insert(ary, num)
ary.insert(50, num)
end
def ruby_insert(ary, num)
ary << 0
(ary.size - 1).downto(50) do |i|
ary[i + 1] = ary[i]
end
ary[50] = num
end
BASE = Array.new(10_000, 0)
N = 10 ** 3
Benchmark.bmbm(10) do |x|
x.report("insert (native Array#insert)") do
arr = BASE.dup
N.times do
native_insert(arr, 99)
end
end
x.report("ruby_array_inset") do
arr = BASE.dup
N.times do
ruby_insert(arr, 99)
end
end
endRehearsal ----------------------------------------------------------------
insert (native Array#insert) 0.001143 0.000012 0.001155 ( 0.001167)
ruby_array_inset 0.354955 0.001944 0.356899 ( 0.357692)
------------------------------------------------------- total: 0.358054sec
user system total real
insert (native Array#insert) 0.001125 0.000012 0.001137 ( 0.001135)
ruby_array_inset 0.351911 0.001223 0.353134 ( 0.353635)
| left = left_child_index(parent) | ||
| right = right_child_index(parent) | ||
| smallest = parent | ||
| smallest = left if left < @heap.size && @heap[smallest] > @heap[left] | ||
| smallest = right if right < @heap.size && @heap[smallest] > @heap[right] |
There was a problem hiding this comment.
微かにトリッキーさを感じました。
left_child_index が呼ばれたときには、まだ left child があるかどうかまだ分からないことが理由でしょうか。
left, right のスコープが広く見えるとかですかね。まあ、でもベターな案はないです。
smallest = parent
left = left_child_index(parent)
smallest = left if left < @heap.size && @heap[smallest] > @heap[left]
right = right_child_index(parent)
smallest = right if right < @heap.size && @heap[smallest] > @heap[right]There was a problem hiding this comment.
確かに、smallestを更新する直前にleft/rightをそれぞれ変数に入れる方が少しわかりやすいかもしれないです。
ちょっと冗長かもしれませんがhas_left_child?メソッドを作るとかですかね。
if has_left_child?(smallest)
left = left_child_index(smallest)
smallest = left if @heap[left] < @heap[smallest]
endThere was a problem hiding this comment.
https://discord.com/channels/1084280443945353267/1192736784354918470/1194613857046503444
私が昔書いた実装です。これはホワイトボードの前で何も見ずに書いたものです。
There was a problem hiding this comment.
ありがとうございます。
smaller_childをメソッド化してparentの値と比較する方が書く方も読む方も認知負荷が低くて良いですね。
class MinHeap
def initialize
@heap = []
end
def peek
@heap.first
end
def push(val)
@heap << val
sift_up(@heap.size - 1)
end
def pop
return nil if @heap.empty?
swap(0, @heap.size - 1)
min = @heap.pop
sift_down(0)
min
end
def size
@heap.size
end
private
def parent_index(index)
(index - 1) / 2
end
def left_child_index(index)
2 * index + 1
end
def right_child_index(index)
2 * index + 2
end
def has_left_child?(index)
left_child_index(index) < @heap.size
end
def has_right_child?(index)
right_child_index(index) < @heap.size
end
def has_child?(index)
has_left_child?(index)
end
def smaller_child_index(index)
smaller_child_index = left_child_index(index)
if has_right_child?(index) && @heap[left_child_index(index)] > @heap[right_child_index(index)]
smaller_child_index = right_child_index(index)
end
smaller_child_index
end
def sift_up(child)
parent = parent_index(child)
return if parent < 0 || @heap[parent] <= @heap[child]
swap(child, parent)
sift_up(parent)
end
def sift_down(parent)
return unless has_child?(parent)
smaller_child = smaller_child_index(parent)
return if @heap[parent] <= @heap[smaller_child]
swap(parent, smaller_child)
sift_down(smaller_child)
end
def swap(index1, index2)
@heap[index1], @heap[index2] = @heap[index2], @heap[index1]
end
end| なのでnumsの長さをN, addが呼ばれる回数をMとすると、 | ||
| 最初にnumを入れるのにO(N*logN)でaddのクエリは合計で(M * log(k))になる。 | ||
| なのでO(NlogN) | ||
| 空間計算量はO(M + N) |
There was a problem hiding this comment.
| なのでnumsの長さをN, addが呼ばれる回数をMとすると、 | |
| 最初にnumを入れるのにO(N*logN)でaddのクエリは合計で(M * log(k))になる。 | |
| なのでO(NlogN) | |
| 空間計算量はO(M + N) | |
| なのでnumsの長さをN, addが呼ばれる回数をMとすると、 | |
| addは1回O(log k)なので、初期化O(N logk)、クエリの処理O(M logk)。 | |
| よって時間計算量はO(N logk + M logk)=O((N+M)logk)。 | |
| 空間計算量はO(k)。 |
There was a problem hiding this comment.
コメントありがとうございます。
最初のheapのビルドでO(N * logK)かかっていて、その後のaddのクエリでO(M * logK)かかるので合計でO((M + N) * logk)ですね。
あとヒープの中は常に要素がkなので空間計算量はO(k)でしたね。
| raise ArgumentError, "k must be positive integer" if k <= 0 | ||
| raise ArgumentError, "Initial array size is too small to determine the top #{k}" if k > nums.size + 1 |
There was a problem hiding this comment.
確かにエラーメッセージには実際の値を埋め込むと、デバッグ時に原因を特定しやすくなると思います。
たとえば以下のようにすると、より親切だと思います。
| raise ArgumentError, "k must be positive integer" if k <= 0 | |
| raise ArgumentError, "Initial array size is too small to determine the top #{k}" if k > nums.size + 1 | |
| raise ArgumentError, "k '#{k}' must be positive integer" if k <= 0 | |
| raise ArgumentError, "Initial array size '#{nums.size}' is too small to determine the top k '#{k}'" if k > nums.size |
また、2個目のエラーは不要だと思いました。
初期配列がkより小さくてもaddメソッドがガードして正常に機能するためです。
There was a problem hiding this comment.
初期配列がkより小さくてもaddメソッドがガードして正常に機能するためです。
機能はしますが、以下のようにtop 3が欲しいのにそうではない結果を返すことが良いかは要件次第かなと思います。
個人的には上から3番目を教えて欲しい時に要素が2個しかないから二番目を返してもらうと困ると思いました。
k = KthLargest.new(3, [])
k.add(3) #=> 3を返す| def pop | ||
| swap(0, @heap.size - 1) | ||
| min_val = @heap.pop | ||
| sift_down(0) | ||
| min_val |
There was a problem hiding this comment.
step2 -> step3でreturn nil if @heap.empty?を削ったと思うですが、賛成です。
addメソッドでチェックがあるので、低レベルにもチェックがあると冗長になりますね。
もしpopメソッドでチェックを含める設計にする場合は、設計の一貫性からpeekメソッドなどにもチェックを含めて欲しくなりますね。
There was a problem hiding this comment.
個人的にはMinHeapを実装するのであればKthLargestなど他のクラスに依存せずMinHeap単体でも使えるようになっていてほしいので、emptyチェックがあるほうが安心ではあるなと思いました。
（この問題を解くだけなら確かに冗長なのですが。）
もしpopメソッドでチェックを含める設計にする場合は、設計の一貫性からpeekメソッドなどにもチェックを含めて欲しくなりますね。
こちらに関しては賛成です。
There was a problem hiding this comment.
個人的にはMinHeapを実装するのであればKthLargestなど他のクラスに依存せずMinHeap単体でも使えるようになっていてほしい
自分もこの意見ですね。step3では単純にempty?のチェックが漏れていました。
| swap(0, @heap.size - 1) | ||
| min_val = @heap.pop |
There was a problem hiding this comment.
「先頭の要素を末尾に持っていき、それをpopすると同時にmin_valとして格納する」
ということなのですが個人的にはややトリッキーに感じました。
ヒープというデータ構造が先頭が最小(or最大)という性質しか保証していないので、先頭以外から取ってくるのが違和感があるかもしれません。
一行長くなっても
- 先頭の値をmin_valに格納する
- 先頭と末尾をswap
- 末尾をpop
となっているほうが個人的には違和感がない形かなと思います。
There was a problem hiding this comment.
確かに、そっちの方がわかりやすいですね。
コメントありがとうございます！
| def pop | ||
| swap(0, @heap.size - 1) | ||
| min_val = @heap.pop | ||
| sift_down(0) | ||
| min_val |
There was a problem hiding this comment.
個人的にはMinHeapを実装するのであればKthLargestなど他のクラスに依存せずMinHeap単体でも使えるようになっていてほしいので、emptyチェックがあるほうが安心ではあるなと思いました。
（この問題を解くだけなら確かに冗長なのですが。）
もしpopメソッドでチェックを含める設計にする場合は、設計の一貫性からpeekメソッドなどにもチェックを含めて欲しくなりますね。
こちらに関しては賛成です。
|
|
||
| https://github.com/fhiyo/leetcode/pull/10/files/0ee4b594d9657627d07ef9810b8f695611e366ac#r1605950261 | ||
|
|
||
| メソッド単位でmutexを取る前提だと、topで値を返さないと |
There was a problem hiding this comment.
マルチスレッド前提だとこのような問題が起こる可能性があるのですね。勉強になりました。
There was a problem hiding this comment.
スレッドセーフではない外部ライブラリを使う時などは、呼び出し側がmutexをとって競合が起きないようにする、という方法もあり得ると思います。
| else | ||
| @sorted_nums.insert(index, val) | ||
| end | ||
| @sorted_nums[@k - 1] |
There was a problem hiding this comment.
この問題では入力の制約上無いですが、仮にこの時点で配列サイズがkより小さい場合範囲外参照になりnilが返りますかね。
解いた問題
703. Kth Largest Element in a Stream
使用言語
Ruby
次に解く問題
347. Top K Frequent Elements