ToRapture's Blog

A Programmer

0%

Posted on Edited on Disqus:

460. LFU Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class LFUCache {
    struct LFUItem {
        int key;
        int value;
        int freq;
        LFUItem() {}
        LFUItem(int key, int value, int freq) : key(key), value(value), freq(freq) {}
    };

    int capacity;
    int min_freq;
    unordered_map<int, list<LFUItem>> freq_to_list;
    unordered_map<int, list<LFUItem>::iterator> key_to_iter;

   public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        this->min_freq = 1;
    }

    int get(int key) {
        if (capacity <= 0) return -1;

        auto it = key_to_iter.find(key);
        if (it == key_to_iter.end()) return -1;
        int value = it->second->value;
        put(key, value);
        return value;
    }

    void put(int key, int value) {
        if (capacity <= 0) return;

        auto it = key_to_iter.find(key);
        if (it != key_to_iter.end()) {
            auto list_node = it->second;
            freq_to_list[list_node->freq + 1].push_back(LFUItem(key, value, list_node->freq + 1));
            key_to_iter[key] = prev(freq_to_list[list_node->freq + 1].end());
            freq_to_list[list_node->freq].erase(list_node);
            if (freq_to_list[min_freq].empty()) min_freq++;
        } else {
            if (key_to_iter.size() == capacity) {
                key_to_iter.erase(freq_to_list[min_freq].begin()->key);
                freq_to_list[min_freq].pop_front();
            }
            min_freq = 1;
            freq_to_list[min_freq].push_back(LFUItem(key, value, min_freq));
            key_to_iter[key] = prev(freq_to_list[min_freq].end());
        }
    }
};

Posted on Edited on Disqus:

146. LRU Cache

Using linked list: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class LinkedNode {
   public:
    LinkedNode *prev, *next;
    int val;
    LinkedNode(int val) {
        this->val = val;
        this->prev = nullptr;
        this->next = nullptr;
    }
};

class LinkedList {
   private:
    LinkedNode *head, *tail;

   public:
    LinkedList() {
        this->head = nullptr;
        this->tail = nullptr;
    }
    void erase(LinkedNode *p) {
        if (p == tail) {
            tail = tail->prev;
        } else if (p == head) {
            head = head->next;
        }
        if (p->prev) {
            p->prev->next = p->next;
        }
        if (p->next) {
            p->next->prev = p->prev;
        }
    }
    LinkedNode *begin() { return head; }
    LinkedNode *rbegin() { return tail; }
    void push_front(int val) {
        LinkedNode *node = new LinkedNode(val);
        node->prev = nullptr;
        node->next = head;
        if (head) {
            head->prev = node;
        }
        head = node;
        if (tail == nullptr) {
            tail = head;
        }
    }
    void pop_back() { erase(tail); }
};

class LRUCache {
    LinkedList lst;
    unordered_map<int, LinkedNode *> key_to_node;
    unordered_map<int, int> key_to_value;
    int capacity;

   public:
    LRUCache(int capacity) { this->capacity = capacity; }

    int get(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) {
            return -1;
        }
        int value = key_to_value[key];
        put(key, value);
        return value;
    }

    void put(int key, int value) {
        auto it = key_to_node.find(key);
        if (it != key_to_node.end()) {
            lst.erase(it->second);
            key_to_node.erase(key);
            key_to_value.erase(key);
        }
        lst.push_front(key);
        key_to_node[key] = lst.begin();
        key_to_value[key] = value;

        if (key_to_node.size() > capacity) {
            LinkedNode *tail = lst.rbegin();
            key_to_node.erase(tail->val);
            key_to_value.erase(tail->val);
            lst.pop_back();
        }
    }
};

Using STL: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class LRUCache {
    int capacity;
    list<pair<int, int>> lst;
    unordered_map<int, list<pair<int, int>>::iterator> mp;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        lst.clear();
        mp.clear();
    }
    
    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) {
            return -1;
        }
        int value = it->second->second;
        put(key, value);
        return value;
    }
    
    void put(int key, int value) {
        auto keyToIter = mp.find(key);
        if (keyToIter != mp.end()) {
            lst.erase(keyToIter->second);
            mp.erase(keyToIter);
        }
        lst.push_front({key, value});
        mp[key] = lst.begin();
        
        if (lst.size() > capacity) {
            mp.erase(lst.rbegin()->first);
            lst.pop_back();
        }
    }
};

Posted on Edited on Disqus:

384. Shuffle an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import copy
import random


class Solution(object):
    def __init__(self, nums):
        self.ori = copy.copy(nums)
        self.nums = nums

    def reset(self):
        return self.ori

    def shuffle(self):
        for i in range(len(self.nums)):
            pos = random.randrange(i, len(self.nums))
            self.nums[i], self.nums[pos] = self.nums[pos], self.nums[i]
        return self.nums

Posted on Edited on Disqus: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

void heap_sort(vector<int> &vec) {
    for (int i = 0; i < vec.size(); i++) {
        for (int p = i; p && vec[(p - 1) / 2] < vec[p]; p = (p - 1) / 2) {
            swap(vec[p], vec[(p - 1) / 2]);
        }
    }

    for (int i = vec.size() - 1; i >= 0; i--) {
        int top = vec[0];
        vec[0] = vec[i];

        for (int p = 0, c; (c = p * 2 + 1) < i; p = c) {
            if (c + 1 < i && vec[c] < vec[c + 1]) c++;
            if (vec[c] < vec[p]) break;
            swap(vec[c], vec[p]);
        }

        vec[i] = top;
    }
}

int main(int argc, char **argv) {
    default_random_engine rd(time(NULL));

    for (int cas = 0; cas < 100; cas++) {
        vector<int> vec;
        for (int i = 0; i < 100000; i++) {
            vec.push_back(rd());
        }
        auto stl = vec;
        heap_sort(vec);
        sort(stl.begin(), stl.end());
        assert(vec == stl);
    }

    return 0;
}

Posted on Edited on Disqus: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

void ms(int l, int r, vector<int> &vec, vector<int> &temp) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    ms(l, mid, vec, temp);
    ms(mid + 1, r, vec, temp);
    int cnt = 0;

    for (int i = l, j = mid + 1; i <= mid || j <= r;) {
        if (i > mid) {
            temp[cnt++] = vec[j++];
        } else if (j > r) {
            temp[cnt++] = vec[i++];
        } else if (vec[i] <= vec[j]) {
            temp[cnt++] = vec[i++];
        } else {
            temp[cnt++] = vec[j++];
        }
    }

    for (int i = 0, j = l; i < cnt; i++, j++) {
        vec[j] = temp[i];
    }
}

void merge_sort(vector<int> &vec) {
    vector<int> temp(vec.size());
    ms(0, vec.size() - 1, vec, temp);
}

int main(int argc, char **argv) {
    default_random_engine rd(time(NULL));

    for (int cas = 0; cas < 100; cas++) {
        vector<int> vec;
        for (int i = 0; i < 100000; i++) {
            vec.push_back(rd());
        }
        auto stl = vec;
        merge_sort(vec);
        sort(stl.begin(), stl.end());
        assert(vec == stl);
    }
    return 0;
}

Posted on Edited on Disqus: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

void bubble_sort(vector<int> &vec) {
    for (int i = 0; i < vec.size() - 1; i++) {
        for (int j = vec.size() - 1; j > i; j--) {
            if (vec[j] < vec[j - 1]) {
                swap(vec[j], vec[j - 1]);
            }
        }
    }
}

int main(int argc, char **argv) {
    default_random_engine rd(time(NULL));

    for (int cas = 0; cas < 100; cas++) {
        vector<int> vec;
        for (int i = 0; i < 1000; i++) {
            vec.push_back(rd());
        }
        auto stl = vec;
        bubble_sort(vec);
        sort(stl.begin(), stl.end());
        assert(vec == stl);
    }

    return 0;
}

Posted on Edited on Disqus:

安装 imwheel

$ sudo apt-get install imwheel

编辑imwheelrc配置

$ vim ~/.imwheelrc

1
2
3
4
5
6
7
".*"
None,      Up,   Button4, 2
None,      Down, Button5, 2
Control_L, Up,   Control_L|Button4
Control_L, Down, Control_L|Button5
Shift_L,   Up,   Shift_L|Button4
Shift_L,   Down, Shift_L|Button5

配置开机启动

$ gnome-session-properties

Posted on Edited on Disqus:

Remove Completely and Install

1
2
3
4
5
6
7
8
sudo apt-get remove --purge "mysql*"
sudo apt-get purge "mysql*"
sudo apt-get autoremove
sudo apt-get autoclean
sudo apt-get remove dbconfig-mysql
sudo apt-get dist-upgrade
sudo rm -rf /etc/mysql /var/lib/mysql
sudo apt-get update && sudo apt-get install mysql-server

Enable Remote Access

1
2
3
4
5
6
su root
mysql -uroot -e " \
    ALTER USER 'root'@'localhost' IDENTIFIED WITH caching_sha2_password BY 'yourpasswd'; \
    CREATE USER 'root'@'%' IDENTIFIED BY 'yourpasswd'; \
    GRANT ALL PRIVILEGES ON *.* TO 'root'@'%'; \
    FLUSH PRIVILEGES;"

In /etc/mysql/mysql.conf.d/mysqld.cnf:

  • replace bind-address = 127.0.0.1 with bind-address = 0.0.0.0

Then restart mysql by sudo service mysql restart.

Posted on Edited on Disqus:

Installation

https://github.com/protocolbuffers/protobuf/blob/master/src/README.md

Proto

pb/entities.proto: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
syntax = "proto3";

package entities;
option go_package = "pb/entities";

enum Gender {
    UNKNOWN = 0;
    MALE = 1;
    FEMALE = 2;
}

message Person {
    Gender gender = 1;
    string name = 2;
    repeated string tags = 3;
    double height = 4;
    int32 age = 5;
    oneof important {
        string task = 6;
        int32 problem = 7;
        double point = 8;
    }
    map<string, string> extra = 10;
}

Golang

https://developers.google.com/protocol-buffers/docs/gotutorial

$ protoc --proto_path=./ --go_out=./ pb/entities.proto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main

import (
    "io/ioutil"
    "os"

    "./pb/entities"
    "github.com/golang/protobuf/proto"
    logger "github.com/sirupsen/logrus"
    prefixed "github.com/x-cray/logrus-prefixed-formatter"
)

func init() {
    logger.SetFormatter(&prefixed.TextFormatter{
        TimestampFormat: "2006-01-02 15:04:05",
        FullTimestamp:   true,
        ForceFormatting: true,
        DisableColors:   true,
    })
    logger.SetOutput(os.Stdout)
    logger.SetLevel(logger.DebugLevel)
}

func main() {
    p := &entities.Person{
        Gender:    entities.Gender_FEMALE,
        Name:      "ToRapture",
        Tags:      []string{"Hello", "World"},
        Height:    114,
        Age:       32,
        Important: &entities.Person_Task{Task: "OneOfExample"},
        Extra: map[string]string{
            "who":   "are you",
            "where": "to go",
        },
    }

    logger.Infof("p: %v", p)
    bt, err := proto.Marshal(p)
    if err != nil {
        logger.Errorf("proto marshal error: %v", err)
        return
    }

    b := new(entities.Person)
    if err = proto.Unmarshal(bt, b); err != nil {
        logger.Errorf("proto unmarshal error: %v", err)
        return
    }

    logger.Infof("b: %v, b == p: %v", b, proto.Equal(b, p))
    switch oneOf := b.GetImportant().(type) {
    case *entities.Person_Task:
        logger.Infof("oneOf is task, value: %v", oneOf.Task)
    case *entities.Person_Point:
        logger.Infof("oneOf is point value: %v", oneOf.Point)
    case *entities.Person_Problem:
        logger.Infof("oneOf is problem value: %v", oneOf.Problem)
    }

    if err := ioutil.WriteFile("person.data", bt, 0666); err != nil {
        logger.Errorf("write to file error: %v", err)
        return
    }
}

Python

https://developers.google.com/protocol-buffers/docs/pythontutorial

$ protoc --proto_path=./ --python_out=../python pb/entities.proto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# coding: utf-8

from pb import entities_pb2


def main():
    data = b""
    with open("../go/person.data", "rb") as f:
        data = f.read()
    person = entities_pb2.Person()
    person.name = "ToRapture"
    print("person: %s" % person)
    print("serialized: %s" % person.SerializeToString())

    person.ParseFromString(data)
    print("parsed: %s" % person)

    which = person.WhichOneof('important')
    print('which: %s' % which)
    if which:
        print('oneof value: %s' % getattr(person, which))


if __name__ == '__main__':
    main()

Posted on Edited on Disqus:

IDL and Code Generation

easy.thrift: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
namespace go easy
namespace py easy
namespace cpp easy


service Easy {
    void ping();
    string say_hello(1: list<string> words);
    i32 add(1: i32 x, 2: i32 y);
}

service Hard {
    void ping();
    string say_hello(1: list<string> words);
    i32 add(1: i32 x, 2: i32 y);
}

$ thrift -r --gen go ./easy.thrift

Golang

goland: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package main

import (
    "context"
    "errors"
    "math/rand"
    "os"
    "strings"
    "time"

    "go-learn/gen-go/easy"

    "github.com/apache/thrift/lib/go/thrift"
    logger "github.com/sirupsen/logrus"
    "github.com/x-cray/logrus-prefixed-formatter"
)

func init() {
    logger.SetFormatter(&prefixed.TextFormatter{
        TimestampFormat: "2006-01-02 15:04:05",
        FullTimestamp:   true,
        ForceFormatting: true,
        DisableColors:   true,
    })
    logger.SetOutput(os.Stdout)
    logger.SetLevel(logger.DebugLevel)
}

type EasyHandler struct{}

func (h *EasyHandler) Ping(ctx context.Context) error {
    logger.Infof("ping")
    if rand.Int()%2 == 0 {
        logger.Infof("return error")
        return errors.New("a random error")
    }
    return nil
}

func (h *EasyHandler) SayHello(ctx context.Context, words []string) (string, error) {
    return strings.Join(words, ", "), nil
}

func (h *EasyHandler) Add(ctx context.Context, x int32, y int32) (int32, error) {
    return x + y, nil
}

func runEasy() error {
    processor := easy.NewEasyProcessor(&EasyHandler{})
    transport, err := thrift.NewTServerSocket(":27024")
    if err != nil {
        return err
    }
    transportFactory := thrift.NewTTransportFactory()
    protocolFactory := thrift.NewTBinaryProtocolFactoryDefault()

    server := thrift.NewTSimpleServer4(processor, transport, transportFactory, protocolFactory)
    return server.Serve()
}

func runClient() error {
    var transport thrift.TTransport
    transport, err := thrift.NewTSocket(":27024")
    if err != nil {
        return err
    }
    transportFactory := thrift.NewTTransportFactory()
    protocolFactory := thrift.NewTBinaryProtocolFactoryDefault()
    transport, err = transportFactory.GetTransport(transport)
    if err != nil {
        return err
    }

    defer transport.Close()
    if err := transport.Open(); err != nil {
        return err
    }

    iprot := protocolFactory.GetProtocol(transport)
    oprot := protocolFactory.GetProtocol(transport)
    client := easy.NewEasyClient(thrift.NewTStandardClient(iprot, oprot))

    if err := client.Ping(context.Background()); err != nil {
        logger.Errorf("ping error: %v", err)
    }
    if sum, err := client.Add(context.Background(), 1, 2); err != nil {
        logger.Errorf("add error: %v", err)
    } else {
        logger.Infof("result of add: %v", sum)
    }
    if ret, err := client.SayHello(context.Background(), []string{"hello", "world"}); err != nil {
        logger.Errorf("say hello error: %v", err)
    } else {
        logger.Infof("result of say hello: %v", ret)
    }

    return nil
}

func main() {
    go func() {
        err := runEasy()
        if err != nil {
            logger.Errorf("run server error: %v", err)
        }
    }()
    time.Sleep(time.Second * 2)
    go func() {
        err := runClient()
        if err != nil {
            logger.Errorf("run client error: %v", err)
        }
    }()
    time.Sleep(time.Second * 2)
}

Python

python-server: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# coding: utf-8

from easy.easy import Easy


from thrift.transport import TSocket
from thrift.transport import TTransport
from thrift.protocol import TBinaryProtocol
from thrift.server import TServer


class EasyHandler:
    def __init__(self):
        pass

    @staticmethod
    def ping():
        print("ping")

    @staticmethod
    def say_hello(words):
        return ", ".join(words)

    @staticmethod
    def add(x, y):
        return x + y


if __name__ == '__main__':
    handler = EasyHandler()
    processor = Easy.Processor(handler)
    transport = TSocket.TServerSocket(host='127.0.0.1', port=9090)
    tfactory = TTransport.TBufferedTransportFactory()
    pfactory = TBinaryProtocol.TBinaryProtocolFactory()

    server = TServer.TSimpleServer(processor, transport, tfactory, pfactory)
    server.serve()

python-client: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# coding: utf-8

from thrift.protocol import TBinaryProtocol
from thrift.transport import TSocket
from thrift.transport import TTransport

from easy.easy import Easy


def main():
    transport = TSocket.TSocket('localhost', 9090)
    transport = TTransport.TBufferedTransport(transport)
    protocol = TBinaryProtocol.TBinaryProtocol(transport)

    client = Easy.Client(protocol)

    transport.open()
    print(client.ping())
    print(client.add(1, 2))
    print(client.say_hello(["hello", "world"]))
    transport.close()


if __name__ == '__main__':
    main()