LRU Cache
class ListNode(object): def __init__(self, key, val): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.head = ListNode(-1, -1) # 新しいほう self.tail = ListNode(-2,-2) # 古いほう self.cache = dict() # nodeがval self.head.next = self.tail self.tail.prev = self.head self.capacity = capacity self.length = 0 # 先頭にnodeを追加 def add(self, node): node.prev = self.head node.next = self.head.next self.head.next = node node.next.prev = node # 削除 def remove(self, node): node.prev.next, node.next.prev = node.next, node.prev # 一回削除してから先頭に足す。増えないのでcapacityを超えることはない def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] self.remove(node) self.add(node) return node.val def put(self, key: int, value: int) -> None: # 既にキャッシュ内に存在するならgetとほぼ同じ if key in self.cache: node = self.cache[key] node.val = value self.remove(node) self.add(node) # ないならcapacityを超える場合はtailに最も近いものを削除してから追加 else: if len(self.cache) == self.capacity: tail_node = self.tail.prev del self.cache[tail_node.key] self.remove(tail_node) node = ListNode(key, value) self.cache[key] = node self.add(node)
collections.OrderedDictを使うと非常にスッキリする
class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.dic = collections.OrderedDict() def get(self, key): if key not in self.dic: return -1 val = self.dic[key] self.dic.move_to_end(key) # 後ろのものほど新しい return val def put(self, key, value): self.dic[key] = value self.dic.move_to_end(key) if len(self.dic) > self.capacity: # last=Trueなら末尾（最も新しく利用したもの）を、Falseなら先頭のkey,valueを削除 self.dic.popitem(last=False)
参考
medium.com
Go言語によるWebアプリケーション開発 5章でつまったところ
Go言語によるWebアプリケーション開発 １～３章をやった
目的
Go書きたい＆ソケット通信でなんか作ってみたかった（現職では他社システムから叩かれるAPIをつくっていて、ソケット通信に関する知識がないため）。
Goでサーバ立ててチャットアプリ作って、Googleとかを利用した認証機能を作って、アイコン画像アップ機能追加して、リファクタリングして、みたいな流れ。
ソケット通信を利用したアプリの勘所が全くなかったので、とても興味深く面白かった。
普通のWebページとかと異なり、接続が瞬間的なものではなくいつ切れるかわからないため、負荷分散やスケーラブルなシステム設計がかなり難しそうだとおもった。youtubeとかのような動画配信はどんな感じで対応してるのか気になる。
「データ指向アプリケーションデザイン」のメモ
２章
宣言的コード：SQLクエリのような、「結果をこのような形でください」というような依頼。裏側で処理をどのように行っているかは気にしなくてよく、CPU利用などのその時に適した最適化なども期待できる。一方で、既存の命令セット（という表現はよいのか？）の外のことをするのが難しいので、柔軟性の面では命令的コードに劣るか。
命令的コード：通常のプログラミングのように、「この順でこのように処理をしてね」のような依頼により、所望の結果を得る。処理を自由に組み合わせられるので、柔軟性は高いが、その分CPU最適化などが難しい。また、宣言的コードのように、結果だけください、というわけにはいかず、結果に至るまでの処理を自身で構成する必要がある。
どちらも一長一短あり、データモデルによりどちらが適してるかも変わりそう。また、どちらか一方のみしか使わない、というようなものでもなく、ミドルウェアによってはどちらも（というかこれらの中間的なもの）をつかえるか。
ドキュメント型DB：データが単体で完結していて、データ間に関係が薄いものに向く。
グラフデータベース：あらゆるもの同士に関係が存在するようなデータに向く。
RDB：データ間に関係性が強いもの
まずはデータから考えて、それらにどのような特性・関係性があるか見ていくことで、適した処理方法やミドルウェアが見えてくる。これらに絶対的な正解はなく（明らかに適さないものもあるだろうが）、たいてい何らかのトレードオフから重視したいものを選ぶ形か。
３章
06/21~06/27
唐突にやったこと記録を付け始める
今週やったこと
・カジュアル面談を受けた
・「応用技術者合格教本2020」を７割ぐらいまで読んだ
・「コンピュータシステムの理論と実装（nand2tetris）」をやり始めた
・「達人に学ぶDB設計徹底指南書」を半分ぐらい読んだ
今後やる/やりたいこと
・nand2tetris引き続きやる
・システム設計の本をぽちったので読む
・英語を聴く習慣を作りたい
・引き続き転職活動
・コードも書きたい
AtCoder Beginner Contest 129 E - Sum Equals Xor
問題ページ
愚直解
L以下の全a,bに対して、
a + b <= L
a xor b = a + b
になるか見ていって、条件にあうものを数え上げる。
計算量は O(N^2) で、最大でa,bそれぞれ 10^5 通りぐらいあるので、間に合わない
愚直解の良くない点として、例えば
L = 111100001111111、a = 11111~~, b = 00000~~
のような場合に、左から５文字目を調べた段階で、a xor b > L が決まり条件を満たさないことが確定するのに、6文字目以降も全パターン調べてしまう。
なので、左から徐々に幅を増やして（小さい問題から大きい問題へ）、条件を満たすものだけ拾っていく形に変更する。メモ化を利用した処理（DPなど）
また、xor は桁ごとに処理するので、桁DPが使えそう
xor には桁上がりがないので、 a, b で同じbitに1が立っている場合は、 a+b = a xor b が満たせない。
DP[i+1][j] : Lの左からi番目まで見たときに、条件を満たすa,bの組。j=1のとき、L未満である。
遷移
dp[i][1] -> dp[i+1][1] : a+b = a xor b となる組合わせならOK
dp[i][0] -> dp[i+1][1] : L[i] = 1 のときに、a xor b = 0 かつ a+b = a xor b になるようにとればよい
dp[i][1] -> dp[i+1][0] : L[i] = a xor b のi桁目、a xor b = 0 かつ a+b = a xor b になるようにとればよい
解答
