Matsushita's Blog

オーダー計算量と実際の処理時間と使用容量を比較する

結果

僕の環境では以下の値となった。言語はJava

  • 空間計算量O(N)とすると実際の使用容量はN byte程度
  • 時間計算量O(10x) とすると、10-1*(9-x) 秒程度

※オーダーの値が小さいと誤差は出る

Javaのメモリーサイズ

Javaのメモリーサイズはメソッドによって取得することができる。

Runtime (Java Platform SE 6)

maxMemoryとは、使用メモリーがtotalMemoryに近づいた時に、更にメモリーの使用を試みる値となる。

maxMemoryは大体2GBであることが分る。

空間計算量

Int型の整数1つのバイト数は1バイトとなる。つまりO(106)だと106バイトとなり、1MBとなる。 109個の場合は、1GBとなり、out of memory errorが発生する。

107の場合、10MBとなる。

実際に図ってみても使用メモリーは40MBと妥当な値を出している。

まとめると、空間計算量O(N)とすると実際の使用容量はN byte程になった。

時間計算量

処理時間はSystem.nanoTime()によってナノセカンドを得る事ができる。

O(107)だと13msで10^-2秒程となる。

  • O(109) : 1703ms → 2秒弱
  • O(108) : 127ms → 0.1秒 (10^-1秒)
  • O(107) : 13ms → 0.01秒 (10^-2秒)
  • O(106) : 6ms → (10^-3秒)

まとめると 時間計算量O(10x) の場合、10-1*(9-x) 秒かかる。

Design TinyURL in LeetCode

Problem

TinyUrl is a URL that a original URL is compressed. This problem is how should we design TinyURL services.

https://leetcode.com/problems/design-tinyurl/#/solutionsDesign TinyURL - LeetCode

How to code

First, I prepare two HashMap to store short URL and original url. One is for storing short url as a key and original url as a value. Another is for the reverse. Next, how I create tiny url from original url. In my case, I create tiny url by random characters, such as 0-9, a-z, A-Z. And the size of tiny url is 10. If tiny url which I create is duplicate, I create it until the url is not duplicate.

Source Code

How to design

In this problem of leet code, some additional questions is prepared. I pick up some questions of them.

How many unique identifiers possible?

In my case, I set that the size of tiny url is 10. And the number of characters is 26 + 26 + 10 = 62 because the letters of tiny url are alphabet (both uppercase and lowercase) and numbers. So the number of unique tiny urls is 62101018. One billion is 109 and the population of the world is about 7 billion.

Estimate the maximum number of URLs a single machine can store.

The capacity depends on memory and disk size of the machine. I think about the capacity to store the urls. I assume the each number blow.

  • The number of urls I have to store is one million (10^6)
  • The size of each url is 100 (10^2)

In this case, since the size of one character is about one byte, the size of url is about 100 byte. And there are one million urls, so the size is 108 byte = 100MB.

Java has 2GB memory so that there are enough capacity to store one million urls.

Estimate the maximum number of queries per second (QPS) for decoding a shortened URL in a single machine.

When we decode a shorted URL, split method and containsKey are executed. If the size of url is 100, this process takes O(102) time. In my java environment, O(102) process takes 102 nano time. Therefore one decode process takes 0.1 ms. So in a second, QPS is 107. (System.nanoTime())

How would you scale the service?

There are some solutions how to scale. When we use some machine to store data, we have to consider how would we distribute the data. If this service is used in all over the world, it’s effective to distribute each data by user location.

If you can enable caching, what would you cache and what’s the expiry time?

  • Least Recently Used
  • Least Frequently Used

2分探索木からノードを削除する Delete Node in a BST in LeetCode

問題

2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。

leetcode.com

解法

以下のステップで解く

  1. 2分探索でkeyを見つける
  2. 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。
  3. 右側のサブツリーから最小値のノードを削除する
  4. (削除するノードのleft, rightのどちらかがnullの場合はnullではない方のサブツリーを削除するノードと置き換える)

f:id:atiek1121:20170613091118p:plain

ソースコード

Perfect SquareかをO(logN)で判定する LeetCode

問題

leetcode.com

解法

単純にfor文を用いた解法だとO(√N)となり間に合わない。 2文探索を用いることでO(logN)で解くことができる。

ソースコード

【グラフ理論とネットワーク理論】Extended Complete Graph

Connectivity and Damage Index

Connectivity

Connectivity express the reliability of the graph

  • Node Connectivity Cv(G) : Minimum number of nodes to be removed to make a graph unconnected.
  • Branch Connectivity Ce(G) : Minimum number of branches to be removed to make a graph unconnected.
  • Node connectivity = d → d - 1 node failures OK
  • Branch connectivity = d → d - 1 branch failures OK

Theorem1

Cv(G) ≦ Ce(G) ≦ δ(G) : δ = degree (the number of branches of one node)

Damage index

Damage index is an index of the increase of hops to connect in case of failure.

α-Node(Branch) Damage Index Iα(G) (Jα(G)) is defined as blow

Maximum diameter of a graph without α nodes(branches) - Diameter of the original graph G

Design Method of Extended Complete Graph

f:id:atiek1121:20170530094111p:plain

Extended Complete Graph : Complete graph Gd → Line conversion, m times → Extended complete graph.

Lm(Gd) = L(L(…(L(G))…)) (m times)

Ex. 1 f:id:atiek1121:20170530095406p:plain

Number of nodes Number of branched
Gd d+1 (d+1)d
L(Gd) (d+1)d (d+1)d2
L2(Gd) (d+1)d2 (d+1)d3

Comparison

Complete graph Extended Complete Graph
正則性 Regularity d-Regular d-Regular
Number of nodes V d + 1 (d + 1)dm
Number of branches E (d + 1)d (d+1)dm+1
直径 Diameter k(G) 1 m+1
Node connectivity Cv(G) d d
Branch connectivity Ce(G) d d
次数 Degree δ(G) d d
節点罹障度 Node damage index Iα(G) 0 ≦ m
枝罹障度 Branch damage index Jα(G) 1 ≦ m+1

Throughput ratio in case of failure

k(G)/(Jα(G) + k(G)) → 0.5 for both Gd and Lm(Gd)

サイズNの配列からM個の要素をランダムに取り出す

問題

サイズNの配列からM個の要素を取り出し新たな配列を返すメソッドを実装する。各要素が選ばれる確率は全て等確率になるようにする。

解き方

はじめに元々の配列の先頭からM個取り出して配列を作る。後は、インデックスがm以上の要素と以下の要素を交換するチャンスを等しく与えてあげることで、等確率をつくることができる。

ソースコード

Least Recently Used (LRU) cache を実装する

問題

LRUキャッシュとはキーとバリューをマッピングするデータ構造で、キャパティを超えたら最後に使われたキャッシュが削除されるという挙動をする。

leetcode.com

解法

HashMapと双方向連結リストを利用することで実装することができる。 リストを用いることで、使われた順番を管理することができる。

ソースコード