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より実効速度がだいぶはやいので最近は重宝してます。
ラブライブ！のアニメが終わってしまった
辛い
あと風邪引いたっぽい
