読者です 読者をやめる 読者になる 読者になる

LevelDBがどのようにレコードにデータを保存しているか

だいたいこのような感じだとおもう.

package main

import (
    "encoding/binary"
    "fmt"
)

const kBatchHdrLen = 8 + 4


// LevelDBはbatch単位で書き込む.(マルチスレッド対応のため?
type Batch struct {
    buf  []byte
}


func (b *Batch) grow(n int) {
    off := len(b.buf)
    if off == 0 {
        off = kBatchHdrLen  // 先頭はヘッダのために空けておく
        n += off
    }
    if cap(b.buf)-off >= n {
        return
    }
    buf := make([]byte, 2*cap(b.buf)+n)
    copy(buf, b.buf)
    b.buf = buf[:off]
}


func (b *Batch) appendRec(t byte, key, value []byte) {
    n := 1 + binary.MaxVarintLen32 + len(key)
    if t == byte(1) {
        n += binary.MaxVarintLen32 + len(value)
    }
    b.grow(n)
    off := len(b.buf)
    buf := b.buf[:off+n]
    buf[off] = t

    fmt.Println(buf)  // 論理削除フラグをセット(Put操作とDelete操作でわけてる

    off += 1
    off += binary.PutUvarint(buf[off:], uint64(len(key)))  // keyの格納にどれだけ必要になるか
    fmt.Println(buf)  // 同時にバッファにkeyの長さを書き込んでいる

    copy(buf[off:], key)  // keyをバッファに書き込む

    fmt.Println(buf)

    off += len(key)
    if t == byte(1) { // valueもおなじかんじ
        off += binary.PutUvarint(buf[off:], uint64(len(value)))
        copy(buf[off:], value)
        off += len(value)

        fmt.Println(buf)
    }

    b.buf = buf[:off]  // 足切り
    fmt.Println(b.buf)
}


func (b *Batch) Put(key, value []byte) {
    b.appendRec(byte(1), key, value)  // byte(1) = 論理削除フラグ
}


func main() {
    b := new(Batch)
    b.Put([]byte("key"), []byte("vlue"))
}

出力結果:

$ go run batch.go 
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 3 107 101 121 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 3 107 101 121 4 118 108 117 101 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 3 107 101 121 4 118 108 117 101]

あんまり調べてないけど,いくつかのKVSもにたかんじだったのでレコードの書式ってどれも似たようなものなんだろうか. bitcaskとかは全然違ってたけど.

std::comm::Chanを利用した簡易メッセージキューサーバもどき

chanをcloneすることで複数クライアントからの入力を共通のPortで待ち受けることができる.

use std::io::BufferedStream;
use std::io::net::ip::{Ipv4Addr, SocketAddr};
use std::io::net::tcp::{TcpStream, TcpListener};
use std::io::{Acceptor, Listener};
use std::comm::{Chan, Port};


fn handle_client(stream: TcpStream, ch: Chan<~str>) {
    let mut stream = BufferedStream::new(stream);
    let buf = match stream.read_line() {
        Ok(buf) => buf,
        Err(err) => fail!("{}", err.to_str())
    };

    ch.send(buf.replace("\r\n", ""));
}


fn main() {
    let addr = SocketAddr { ip: Ipv4Addr(127, 0, 0, 1), port: 8000 };

    let mut acceptor = match TcpListener::bind(addr).listen() {
        Ok(acceptor) => acceptor,
        Err(err) => fail!("{}", err.to_str())
    };

    let (port, chan): (Port<~str>, Chan<~str>) = Chan::new();

    spawn(proc() {
            let mut arr: ~[~str] = ~[];
            loop {
                let msg = port.recv();
                arr.push(msg);
                println!("{}", arr.to_str());
            }
        });

    loop {
        let mut stream = match acceptor.accept() { 
            Ok(stream) => stream,
            Err(err) => fail!("{}", err.to_str())
        };
        let ch = chan.clone();
        spawn(proc() { handle_client(stream, ch); });
    };
}

Rustで大文字/小文字変換

最近ちょっと新しいことをやるべきかと思ってRustを触っていて、ちょっとハマったところがこれ.

文字列には to_upper()/to_lower() は用意されておらず、一度 to_ascii() でASCII型に変換する必要がある.

use std::io;

fn main() {
    let name = ~"KUBO39";

    let lower_name = name.to_ascii().to_lower().into_str();
    io::println(lower_name);
}

話題のコーディング問題を、話題のD言語で解いてみる

https://paiza.jp/poh/ec-campaign/

ちゃんと検算してないので間違ってるかもしれない。 もっときれいな書き方があるよ!とかこうしたほうが速いよ!とかあったらこっそり教えてください。

import std.algorithm, std.array, std.conv, std.stdio, std.string;

void main() {
  string[] arr = stdin.readln().strip().split(" ");
  int num = arr[0].to!int;
  int days = arr[1].to!int;

  int[] prices;

  foreach (string line; lines(stdin)) {
    if (line == "\n") break;
    prices ~= line.strip().to!int();
  }

  int[] items = prices[0 .. num];

  int[] perms;
  for (int i; i < num-1; ++i)
    for (int j = i+1; j < num; ++j)
      perms ~= items[i] + items[j];

  perms = perms.sort!("a < b").array;

  foreach (goal; prices[num .. num+days]) {
    if (goal < perms[0]) {
      writeln("0");
      continue;
    }

    foreach_reverse (perm; perms) {
      if (perm <= goal) {
        writeln(perm);
        break;
      }
    }
  }
}

実行結果も貼る。

(^ν^) :~/tmp/paiza $ rdmd problem1.d 
4 3
8000
4000
9000
6000
3000
14000
10000

0
14000
10000

ハッシュテーブルってやつ

教科書とかでみるハッシュテーブルの実装はcollisionやrehashを考慮してないケースばかりなので、参考用に書いた。 といってもこのコードもpointer使ってないし削除やら同じキーがセットされた場合を考慮してないので、実用に使えるものではないので注意。

import std.container;


class Hashtable {

private:

  struct HashValue {
    byte[] key;
    byte[] value;
  }

  uint size;
  uint counter;
  DList!(HashValue)[] buckets;

  this(uint _size) {
    size = _size;
    buckets.length = _size;
    for (int i; i < size; ++i)
      buckets[i] = make!(DList!(HashValue));
  }

  @property
  uint getSize() {
    return size;
  }

  void set(byte[] key, byte[] value) {
    buckets[getIndex(key)].insertBack(HashValue(key, value));
    counter++;

    // ckeck rehash
    if (counter / buckets.length > 5)
      rehash();
  }

  byte[] get(byte[] key) {
    auto l = buckets[getIndex(key)];

    foreach(hvalue; l)
      if (hvalue.key == key)
        return hvalue.value;

    assert(0);
  }

private:

  // ported from Tokyo Cabinet
  uint getIndex(byte[] key) {
    uint hash = 19780211;
    foreach(octet; key)
      hash = hash * 37 + octet;
    return hash % size;
  }

  void rehash() {
    size *= 2;  // resize bucket size * 2
    DList!(HashValue)[] newBuckets;
    newBuckets.length = size;
    for (int i; i < size; ++i)
      newBuckets[i] = make!(DList!(HashValue));

    foreach(bucket; buckets) {
      foreach(hvalue; bucket) {
        uint newIndex = getIndex(hvalue.key);
        newBuckets[newIndex].insertBack(hvalue);
      }
    }
    buckets = newBuckets;
  }

}


unittest {
  import std.stdio;
  auto ht = new Hashtable(100);

  byte[] k = ['a', 'b', 'c'];
  byte[] v = ['1', '2', '3'];

  ht.set(k, v);
  auto tmp = ht.get(k);
  writeln(tmp);
  assert(tmp == v);
}


version(unittest) void main() {}

ここでrehashはsize*=2として2倍のbucketsを用意して、新たにハッシュ値を計算しなおしてから詰め直している。(sizeの値そのものを変更してるのでgetIndexの計算も変わることに注意)

これはわりかしnaiveながら一般的なやつだと思っているのだが、Redisなんかは遅延rehashというなかなかおもしろい仕組みを持っている。(興味がある人はsrc/dict.cあたりを読むとよい)

ハッシュテーブルは基本的なデータ構造ながらなかなかおもしろいので今後いろいろ遊んでみたい。

追記: このコードはD言語で書きました。まだまだ勉強中ですが、CやJavaよりも書きやすくRubyより実効速度がだいぶはやいので最近は重宝してます。

Ubuntu12.04でemacsで日本語入力変換ができなくなったとき

sudo rm -r ~/.anthy

むかしは.Anthyだったけどいつのまにか小文字はじまりになっていた。 どうりでタブ補完ででてこなかったわけだ・・ いや普通すぐきづくんだろうけど。

ラブライブ!のアニメが終わってしまった

辛い

あと風邪引いたっぽい