LeetCodeその１：ContainDuplicate

NeetCodeなるものの存在を知ってLeetCodeを始めました。
解説動画がわかりやすくてとても良いです。
英語なので大変ですが。。。

neetcode.io

自分の解答

何も考えずに2重ループで重複チェック。

タイムオーバーでした。

   //配列に重複する数値があるかを調べるプログラム
    // これだとタイムオーバー
    public boolean containsDuplicate(int[] nums) {
        
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

模範解答

class Solution {

    public boolean containsDuplicate(int[] nums) {
        Set<Integer> uniques = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (uniques.contains(nums[i])) {
                return true;
            }
            uniques.add(nums[i]); //←ここでaddしているのがグッド
        }
        return false;
    }
}

・引用元
github.com

学び

HashSetを使う。

HashSetは順序なし、重複なし。

ランダムアクセスができない。

HashSetは検索の計算量がO(1)。

• ランダムアクセス：まずアクセスする場所を特定して、そこに一発でアクセスするやり方
• シーケンシャルアクセス：端から順番に見ていきながらアクセスする場所を探すやり方

学び２

addする位置を工夫するだけで少しコードがきれいになる。

模範解答のコードは自分だったらこう書いてしまう。

   public boolean containsDuplicate3(int[] nums) {
        Set<Integer> uniques = new HashSet<>();
        for (int i = 0; i < nums.length - 1; i++) {//その３．さらに要素数オーバーしないように-1が必要になる
            
            uniques.add(nums[i]);  //←その１．ifでチェック直前にaddしたくなる
            if (uniques.contains(nums[i + 1])) { //その２．そうするとここで+1する必要が出てくる 
                return true;
            }
        }
        return false;
    }

Javaのコレクション一覧と計算量

各コレクションの特徴

・参考
コレクションクラスの比較 - Javaちょこっとリファレンス

xxxxxxxxxxx	ArrayList	LinkedList	HashMap	LinkedHashMap	TreeMap	HashSet	TreeSet
ｲﾝﾀﾌｪｰｽ	List	List	Map	Map	Map	Set	Set
重複	○	○	×	×	×	×	×
null可否	○	○	○	○	×	○	×
自動ソート	×	×	×	×	○	×	○
備考				格納した順番が保持される

List

List構造は要素を順番付けして管理するデータ構造。

要素が番号順に並んでいるので、要素番号を指定して取得する。O(1)
list.get(1);

要素番号がわからない時は要素の値で検索。O(n)
list.indexOf("ねこ"));

Map

Map構造はキーと値をセットにした要素を持つデータ構造。

キーの重複は不可。
キーを指定して要素を取得する。O(1)
map.getKey("a");

HashMapは検索時のアドレス特定方法が面白い↓
HashMapについてのメモ - okinawa

Set

Set構造は要素を順番付けせずに管理するデータ構造。

キーや要素番号がない。
そのため要素を1個指定して取得することができない。
要素取得にはIteratorや拡張for文を使う。

コレクションの計算量

クラス	追加	検索	挿入/削除	ランダムアクセス	メモリ使用量
ArrayList	O(n)	O(n)	O(n)	O(1)	少ない
LinkedList	O(1)	O(n)	O(1)	O(n)	中
HashSet	O(1)	O(1)	O(1)	不可能	多い
TreeSet	O(log n)	O(log n)	O(log n)	不可能	不明

↑色々みたけど微妙に書いてることが違って正解がわからず。この表は当てになりません。
後で修正したい。

※ランダムアクセスの補足

• ランダムアクセス：アクセスする場所を特定して、そこに一発でアクセスするやり方
• シーケンシャルアクセス：端から順番に見ていきながらアクセスする場所を探すやり方

・参考
JavaでよくつかうCollection実装クラスの仕組みと特性 - Qiita
Collectionインターフェイスの計算量 - 数学/競プロメモ

計算量の目安

計算量の例	意味
O(1)	データ数によらず一定時間で処理が完了する	小
O(log N)	データ数の対数に比例して処理時間が増える	↑
O(N)	データ数に比例して処理時間が増える	↓
O(N2)	データ数の2乗に比例して処理時間が増える	大

計算量の例	意味
O(1)	ハッシュテーブルのアクセス（衝突なし）
O(log N)	二分探索
O(N)	ループ、線形探索
O(N log N)	標準APIが提供するソートアルゴリズム ※
O(N2)	二重ループ

・参考
計算量に注目してプログラムを高速化する - Qiita

バッファプールとログバッファ

バッファプールとログバッファ

バッファプール：ストレージ（HDD)にあるRDBのデータの一部を保持している。高速化のため。

ログバッファ：更新処理のときに更新情報をログバッファ上にためて、コミット時にまとめて行う。
なんと更新処理が終わったという通知はログバッファに更新情報を書き溜めたよという通知であって、実際にストレージの更新が終わったという通知ではないらしい。
ストレージの更新は遅いからログバッファ上での終了を更新終了として通知しているんだって。
なので、ストレージの更新が終わる前に障害で落ちるとデータ整合性が取れなくなる。

SQLServerでのバッファプールの確認方法

SELECT [name], [value], [value_in_use]
FROM sys.configurations
WHERE [name] = 'max server memory (MB)' OR [name] = 'min server memory (MB)';

SSMSでDBを右クリック→プロパティ→メモリ　でもOK

メモリ

・参考
サーバー メモリの構成オプション - SQL Server | Microsoft Learn

SQL実践入門 ──高速でわかりやすいクエリの書き方 WEB+DB PRESS plus

統計情報とは

統計情報とは

実行計画を練るためのネタ元。

• 各テーブルのレコード数
• 各テーブルの列数と列のサイズ
• 列値のカーディナリティ(値の個数)
• 列値のデータ分布(どの値がいくつあるかのヒストグラム)
• 列内のNULLの数
• インデックス情報

カーディナリティの補足

カーディナリティは例えば、下記は値が３種類あるので３。

店鋪コード
10
20
30

ヒスグラムの補足

ヒストグラムは例えば、下記は01が３。02が2。03が1。というように同じ値の個数。

店鋪コード
10
10
10
20
20
30

例：列値のデータ分布(どの値がいくつあるかのヒストグラム)
店舗コード 0001がTableAに1万個
店舗コード 0002がTableAに5千個
みたいに統計情報に登録できる。

この統計情報をもとに実行計画を作ってくれる。
店舗コード 0001が1万個かあじゃあWhere句で「店舗コード ＝　0001」が指定されたら気合い入れて検索せんとなあ。
じゃあCPUを並列で複数実行したろ！
みたいな。
実行計画を見るとparallel~というのが並列実行。

SSMSだとインデックスフォルダの中に統計情報が入っている。

参考書籍

SQL実践入門 ──高速でわかりやすいクエリの書き方 WEB+DB PRESS plus

SQLチューニングの一覧

早い段階で取得するデータ量を減らす

Where条件が複数ある場合、抽出する件数が少なくなる条件から先に行う。 JOINも同じ。

サブクエリを含むクエリの場合も最後にwhereで絞るのではなく、各サブクエリ内でレコード数を減らしていく。

インデックスが使われなくなる時

インデックス列を加工する

columnAにインデックスが貼ってある場合。

select * from tableA
where
columnA + 1 = columnB

select * from tableA
where
TRIM(columnA) = columnB

select * from tableA
where
columnA = columnB -1 // これならOK

否定形とOR

• IS NULL
• <>
• NOT IN
• OR

否定はINDEXが効かなくなる。
ただし、否定条件に当てはまるものが多い場合はINDEX検索よりフルスキャンの方が早くなることもあり。

・参考
SQLのチューニング方法【否定形(is not nullなど)】 | SE日記

暗黙の型変換

select * from tableA
where
columnA = 10
and columnA = '10'

複合インデックスは列の順番に注意

columnA, columnB, columnCにインデックスが張られている場合。

○ select * from tableA where columnA = 10 and columnB = 10 and columnC = 10
○ select * from tableA where columnA = 10 and columnB = 10 
✕ select * from tableA where columnA = 10 and columnC = 10
✕ select * from tableA where columnB = 10 and columnC = 10
✕ select * from tableA where columnB = 10 and columnA = 10

サブクエリを減らす

サブクエリはメモリを消費する。

select * from (
    select columnA, MAX(columnB) from tableA
    group by columnA) AS AA
where
AA.columnA > 10;

select columnA from tableA
group by clomunA
having MAX(columnB) > 10;

参考書籍

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ

HAVING句をマスターすると集合志向が理解できるらしい

WHEREとHAVINGで対比するとわかりやすい

• WHERE：1行の特徴を調べる
• HAVING：集合の特徴を調べる

例：下記テーブルから算数80点以上＆国語80点以上の生徒を調べたい
答えはstudentId 100 200。

元テーブル

WHERE

・WHERE句で何も考えずに条件を指定する

SELECT * FROM testscore
where
subject = '算数'
and subject = '国語'
and score >= 80;

算数＆国語の両方を持つ行はもちろん存在しないので結果はなし。
whereだと各行に対して検索をかける。

HAVING

・HAVING句で特性関数を使って抽出

select studentid from testscore
group by studentid
having sum(case when subject = '算数' and score >= 80 then 1
            when subject = '国語' and score >= 80 then 1
            else 0
        end)
        = 2

実行結果

studentid 100 200 300は算数国語を持っている。
havingは集合に対して検索をかけるイメージ。
今回の場合はstudentidという部分集合に対して検索をかけている。

或る行ではなく、或る集合を抽出したいときに使うイメージかな。

参考書籍

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ

【SQL】テーブル同士の比較

テーブル同士の比較

テーブル同士が等しいか異なるかを集合演算子で華麗に比較する方法。

もしテーブルAとテーブルBが完全に等しければ、UNIONの結果とINTERSECTの結果も等しい。

もしテーブルAとテーブルBが異なれば、UNIONの方がINTERSECTより必ず大きくなる。

↑真ん中が完全に等しいとき。

　　 元テーブル（classb classd classe)

・classBとclassDで比較

select
case when count(*) = 0
     then '等しい'
     else '異なる'
end result
 from((
SELECT * FROM classb
union 
SELECT * FROM classd
)
except
(
select * from classb
intersect
SELECT * FROM classd
)) as inte

結果：異なる

・classBとclassEで比較

select
case when count(*) = 0
     then '等しい'
     else '異なる'
end result
 from((
SELECT * FROM classb
union 
SELECT * FROM classe
)
except
(
select * from classb
intersect
SELECT * FROM classe
)) as inte

結果：等しい

テーブルの中身を一切知らなくても比較できるSQL。
集合指向っぽくてとても良き。

参考書籍

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ（ミック）｜翔泳社の本