ITエンジニアの技術メモ

神奈川在住のITエンジニアの備忘録です。おもにプログラミングやネットワーク技術について、学んだことを自分の中で整理するためにゆるゆると書いています。ちゃんと検証できていない部分もあるのでご参考程度となりますが、誰かのお役に立てれば幸いです。

LinuxサーバのDNS問い合わせのタイムアウト

LinuxサーバがDNSサーバに問い合わせを行う際のタイムアウト時間について調べた時のメモ。

resolv.conf のmanページ:

https://linuxjm.osdn.jp/html/LDP_man-pages/man5/resolv.conf.5.html

に以下の記載があるので、デフォルトでは、5秒×2回で「10秒」となるようだ。

timeout:n
「レゾルバが他のネームサーバで問い合わせをリトライする前に、 リモートネームサーバからの応答を待つ時間」を設定する。 単位は秒で、デフォルトは RES_TIMEOUT である (現状では 5 秒、<resolv.h> を参照)。 このオプションの値の上限は 30 であり、黙ってこの値まで切り詰められる。

attempts:n
「レゾルバが諦めて呼び出し元のアプリケーションにエラーを返すまでに、 ネームサーバに問い合わせを行う回数」を設定する。 デフォルトは RES_DFLRETRY 回である (現状では 2 回、<resolv.h> を参照)。 このオプションの値の上限は 5 であり、黙ってこの値まで切り詰められる。

 

 Linuxサーバで実機確認したところ、確かに10秒ほどでタイムアウトした。

leetCode:Design Twitter

leetCode の「Design Twitter」を解いてみた。この問題は、簡易版の Twiter を作成するというもの。
https://leetcode.com/problems/design-twitter

実装する上で気にしたのは以下の点。

  • ユーザやフォロワーの検索を速くするため、これらの入れ物には ArrayList ではなく HashSet や HashMap を使用している。
  • ツイートを時刻でソートして取り出す処理を高速化するため、PriorityQueue を使用している。
  • 各ツイートに持たせる時刻は、ミリ秒単位ではなく、ナノ秒単位にしている。これはミリ秒単位だと、連続ツイートの際に時刻が全く同じになってしまうことがあり、時刻でのソートがうまく効かないため。
  • 本来であれば、ユーザ登録が最初に来ると思うのだが、この問題ではユーザ登録機能はないので、新しいユーザが出てくるたびにユーザを作成し、ユーザ一覧のMapに登録している。


提出したコードは以下。

import java.util.*;

public class Twitter {
    private Map<Integer, User> userIdToUser;

    /** Initialize your data structure here. */
    public Twitter() {
        userIdToUser = new HashMap<>();
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        Tweet tweet = new Tweet(tweetId, System.nanoTime());

        User user = userIdToUser.get(userId);
        if (user == null) {
            User newUser = registerUser(userId);
            newUser.getTweets().add(tweet);
        }
        else {
            userIdToUser.get(userId).getTweets().add(tweet);
        }
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> newsFeedIds = new ArrayList<>();
        User user = userIdToUser.get(userId);
        if (user == null) {
            return newsFeedIds;
        }

        Queue<Tweet> tweetQueue = new PriorityQueue(Comparator.comparing(Tweet::getTime, Comparator.reverseOrder()));
        for (Tweet tweet : user.getTweets()) {
            tweetQueue.add(tweet);
        }
        for (User follower : user.getFollowers()) {
            if (follower.equals(user)) {
                continue;
            }
            for (Tweet tweet : follower.getTweets()) {
                tweetQueue.add(tweet);
            }
        }

        int count = 0;
        while(!tweetQueue.isEmpty() && count < 10) {
            newsFeedIds.add(tweetQueue.poll().getTweetId());
            count++;
        }
        return newsFeedIds;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        User follower = userIdToUser.get(followerId);
        if (follower == null) {
            follower = registerUser(followerId);
        }

        User  followee = userIdToUser.get(followeeId);
        if (followee == null) {
            followee = registerUser(followeeId);
        }

        follower.getFollowers().add(followee);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        User follower = userIdToUser.get(followerId);
        if (follower == null) {
            follower = registerUser(followerId);
        }

        User  followee = userIdToUser.get(followeeId);
        if (followee == null) {
            followee = registerUser(followeeId);
        }

        follower.getFollowers().remove(followee);
    }

    private User registerUser(int userId) {
        User newUser = new User();
        userIdToUser.put(userId, newUser);
        return newUser;
    }

    private static class User {
        List<Tweet> tweets = new ArrayList<>();
        Set<User> followers = new HashSet<>();

        private List<Tweet> getTweets() {
            return tweets;
        }

        private Set<User> getFollowers() {
            return followers;
        }
    }

    private static class Tweet {
        private int tweetId;
        private long time;

        private Tweet(int tweetId, long time) {
            this.tweetId = tweetId;
            this.time = time;
        }

        private int getTweetId() {
            return tweetId;
        }

        private long getTime() {
            return time;
        }
    }
}


上記を提出したら、

Runtime: 29 ms, faster than 49.75% of Java online submissions for Design Twitter.
Memory Usage: 46.9 MB, less than 100.00% of Java online submissions for Design Twitter.

となった。提出者の中では真ん中くらいのスピード。メモリの使用量はかなり少なく済んでいる。

上述のコードのうち getNewsFeed メソッドについては、まだまだ高速化の余地はあると思うので、時間のある時にさらなる高速化を試みたい。

powershellでクラスを定義する。

powershellの勉強の一環で、クラスを自分で定義して使ってみた。
例として、Personクラスを定義して、そのクラスから生成したオブジェクトに、Name、Age、Addressをセットして、Age でソートして表示させてみた。

今回、Personオブジェクトにセットする値は、以下のファイルから読み込むものとする。

入力ファイル

Taro	30	東京
Jiro	29	大阪
Saburo	28	京都


powershellスクリプト

# 入力ファイル
$inputFile = $Args[0]

$persons = @();
foreach ($line in Get-Content -Encoding UTF8 $inputFile) { # 入力ファイルが UTF-8 でエンコードされていたとする。
    $items = $line.split("`t") # タブで分割
    $person = New-Object Person($items[0], $items[1], $items[2]); # person オブジェクトを生成
    $persons += $person
}
$persons = $persons | Sort-Object -Property Age # person オブジェクトを年齢でソート(昇順)
foreach ($person in $persons) {
    Write-Output $person.Name
}

# Personクラスの定義
class Person {
    [string] $Name
    [int] $Age
    [string] $Address
    
    # コンストラクタ
    Person ([string] $name, [int] $age, [string] $address) {
        $this.Name = $name
        $this.Age = $age
        $this.Address = $address
    }
}


上記を実行すると、

Saburo
Jiro
Taro

と出力される。(意図通り、Ageで昇順にソートされている。)

powershell では、上記のようにクラスを簡単に定義して使えるので、言語がデフォルトで持っているデータ構造で合う用途のものがなければ、積極的に独自クラスを使っていきたい。

JavaのIntegerオブジェクトの比較

先日、Listのリストから取得した異なるIntegerオブジェクト同士 (中身のint値は同じ) を「==」で比較するという定番の間違いをしてしまったのだが、なぜか「等しい」と判定された。Javaでは、異なるオブジェクト同士を「==」で比較したら、「等しくない」と判定されるという認識だったので、あれ?何で・・?と思ってちょっと調べてみたところ、以下の記事を見つけた。
http://javatechnology.net/java/integer-equal/

どうやら、Javaでは、-128から127の数値は、Java内部で同一オブジェクトが使われるらしい。つまり、オブジェクト同士の比較を行っても、同一オブジェクトなので「等しい」と判定されるようだ。
以下は、上記を検証した時のサンプル。

        List<Integer> numList = new ArrayList<>();
        numList.add(1);
        numList.add(1);
        numList.add(128);
        numList.add(128);

        if (numList.get(0) == numList.get(1)) { // 良くない比較の方法
            System.out.println("Equal"); // 予想に反して、「等しい」と判定される。
        }
        else {
            System.out.println("Not equal");
        }

        if (numList.get(2) == numList.get(3)) { // 良くない比較の方法
            System.out.println("Equal");
        }
        else {
            System.out.println("Not equal"); // 予想通り、「等しくない」と判定される。
        }

        if (numList.get(2).equals(numList.get(3))) { // 正しい比較の方法
            System.out.println("Equal"); // 「等しい」と判定される。
        }
        else {
            System.out.println("Not equal");
        }
    }

Javaで、-128から127の数値について内部で同一オブジェクトが使われるのは、おそらく、省メモリのためではないかと考えている。よく使われるであろう先の範囲の数値のオブジェクトについては同一のものを使用することで、Integerオブジェクトがたくさん生成されてもJava全体のメモリがあまり増えないようにしているのではないか、と推測している。

powershell で grep する。

powershell の勉強として、指定したフォルダ配下の指定した名前のファイル(正規表現)を、指定した文字列で grep するスクリプトを作成した。

grep.ps1

$targetDir = $Args[0]
$targetFile = $Args[1]
$grepStr = $Args[2]

# -Filter はデフォルトで正規表現が有効。
$fullNames = @(Get-ChildItem $targetDir -Recurse -Filter $targetFile | Select-Object FullName)
Write-Output "----- Result -----`r`n" | Set-Content result.txt -Encoding Default
foreach ($fullName in $fullNames) {
    # Select-String はデフォルトで正規表現が有効。
    # 正規表現を使いたくない場合は「-SimpleMatch」を付ければ良いらしい。
    $foundStrings = @(Select-String $grepStr $fullName.fullName)
    foreach ($foundString in $foundStrings) {
        Write-Output $foundString | Add-Content result.txt -Encoding Default
    }
}


使い方は、

grep.ps1 "grep対象フォルダ" "grep対象ファイル名(正規表現)" "grep対象文字列"

となる。grep 結果は、カレントディレクトリに result.txt として出力される。

powershell は、こうした処理がコマンドレットで簡単に書けるところが良いと思う。

powershell でハッシュを扱う。

powershell でハッシュ (連想配列、辞書とも言われる) を扱う場合のコードの例を以下に記す。

# ハッシュの宣言
$hash = @{}

# ハッシュに追加するデータの準備
$key1 = "key1"
$value1 = "value1"
$key2 = "key2"
$value2 = "value2"
$key3 = "key3"
$value3 = "value3"

# ハッシュに準備したデータを追加する。
$hash[$key1] = $value1
$hash[$key2] = $value2
$hash[$key3] = $value3

# ハッシュのキーから値を取得する。
Write-Output $hash[$key1]          # 「value1」と出力される。
# ハッシュに指定したキーが含まれているか確認する。
Write-Output $hash.Contains($key2) # 「True」と出力される。

powershell では、ハッシュについても、その他のスクリプト言語と同じ感じで扱えるようだ。

powershell でファイルを一行ずつ読み込む

最近、powershell の勉強をしている。勉強した内容をここに少しずつメモしていく。
今回は、powershell でファイルを一行ずつ読み込む方法について書く。調べたところ、幾つか書き方があるようだが、以下のように Get-Content コマンドレットを使う方法が自分的にはしっくり来た。

$inputFile = $Args[0]

# 入力ファイルが UTF-8 でエンコードされているとする。この場合、以下のように「-Encoding UTF8」を付ける。
foreach ($line in Get-Content -Encoding UTF8 $inputFile) { 
    $items = $line.split("`t") # タブで分割
    $item0 = $items[0] # タブで分割した一つ目を取得
    $item1 = $items[1] # タブで分割した一つ目を取得
    Write-Output "First item: $item0,  second item $item1"
}

ただファイルを一行ずつ読み込んでいくだけでは面白くないので、例として、上記のように読み込んだ行をタブで分割してみた。

幾つかネット上でサンプルコードを読んでみたところ、powershell は、これまでにやってきた perl などのスクリプト言語と書き方が似ているので、使いこなせるようになるまでそんなに苦労しないと思っている (思いたい・・)。


2020/02/23 追記
読み込んだファイルに、分割文字のタブが複数あった場合、

    $items = $line.split("`t+")

で行けるかと思ったが、これでは意図通り分割されなかった。
意図通りというのは、
aaa[tab][tab]bbb
が「aaa」と「bbb」に分割されること。

いろいろ調べたところ、

    $items = $line -split "`t+"

で意図通りに分割できた。なぜ、最初の方ではダメなのかは分かっていない。。