• 瀏覽: 152,663
  • 回覆: 522
  • 追帖: 4
[隱藏]
熱賣及精選

回覆 引用 TOP

好多binary tree嘅題目

汪汪呢幾日係蘋果forum到同另一個人(嘈)
基本上就係佢抱怨蘋果Swift為何只有Set和Dictionary但沒有OrderedSet同OrderedDictionary

然後佢就開始左研發自家OrderedSet之旅...不過就遇到更多問題, 例如明明寫緊Swift又死都要用Pointer去bypass個initializer
又或者明明係circular reference但又唔肯用weak reference, 到肯用weak reference時又死都要用unowned...
而明知unowned係必定在non-nil情況下才可以用...同時也有容許nil的weak implicitly unwrapped optional reference又肯唔用(根本就係同一樣)

言歸
汪汪就由一開始已經極速寫好一個
複製內容到剪貼板
代碼:
public func !=<T : Equatable>(lhs: OrderedSet<T>, rhs: OrderedSet<T>) -> Bool {
   
    if lhs.count != rhs.count {
        return true
    }
    for idx in 0..<lhs.count {
        if lhs[idx] != rhs[idx] {
            return true
        }
    }
    return false
}

public func ==<T : Equatable>(lhs: OrderedSet<T>, rhs: OrderedSet<T>) -> Bool {
   
    if lhs.count != rhs.count {
        return false
    }
    for idx in 0..<lhs.count {
        if lhs[idx] != rhs[idx] {
            return false
        }
    }
    return true
}

public struct OrderedSet<T : Comparable> : CollectionType {
   
    private var root: OrderedSetNode<T>?
   
    public init() {
        
    }
   
    public init<S : SequenceType where T == S.Generator.Element>(_ sequence: S) {
        
        for item in sequence {
            self.insert(item)
        }
    }
   
    public var startIndex: Int {
        return 0
    }
    public var endIndex: Int {
        return root?.weight ?? 0
    }
   
    public var count: Int {
        return root?.weight ?? 0
    }
   
    public func contains(member: T) -> Bool {
        return root?.contains(member) ?? false
    }
   
    public subscript (position: Int) -> T {
        return root![position]
    }
   
    public mutating func insert(member: T) {
        if isUniquelyReferencedNonObjC(&root) {
            root!.insert(member)
            root!.weightCheck()
            return
        } else if let _root = root {
            root = _root.clone
            root!.insert(member)
            root!.weightCheck()
            return
        }
        root = OrderedSetNode(member)
    }
   
    public func generate() -> GeneratorOf<T> {
        var _view = root?.view.0
        return GeneratorOf {
            if _view != nil {
                let value = _view!.value
                _view = _view!._next
                return value
            }
            return nil
        }
    }
   
    public var isEmpty: Bool {
        return root == nil
    }
}

extension OrderedSet : ArrayLiteralConvertible {
   
    public init(arrayLiteral elements: T ...) {
        for item in elements {
            self.insert(item)
        }
    }
}

extension OrderedSet : Printable, DebugPrintable {
   
    public var description: String {
        if self.count == 0 {
            return "0 members"
        }
        return "{" + ", ".join(map(self) { "\($0)" }) + "}"
    }
   
    public var debugDescription: String {
        if self.count == 0 {
            return "0 members"
        }
        return "{" + ", ".join(map(self) { "\($0)" }) + "}"
    }
}

private class OrderedSetNode<T : Comparable> {
   
    var value: T
    var node1, node2: OrderedSetNode<T>?
   
    // used for tree rotation
    var weight: Int
   
    init(_ value: T) {
        self.value = value
        self.weight = 1
    }
}

extension OrderedSetNode {
   
    var clone: OrderedSetNode<T> {
        let _clone = OrderedSetNode(value)
        _clone.node1 = self.node1
        _clone.node2 = self.node2
        _clone.weight = self.weight
        return _clone
    }
}

extension OrderedSetNode {
   
    func leftRotate() {
        
        let _tnode = node1
        node1 = OrderedSetNode(value)
        node1!.node1 = _tnode
        node1!.node2 = node2!.node1
        node1!.weightCheck()
        
        value = node2!.value
        node2 = node2!.node2
        
    }
   
    func rightRotate() {
        
        let _tnode = node2
        node2 = OrderedSetNode(value)
        node2!.node2 = _tnode
        node2!.node1 = node1!.node2
        node2!.weightCheck()
        
        value = node1!.value
        node1 = node1!.node1
        
    }
   
    func weightCheck() {
        
        if node1 == nil && node2 != nil && node2!.weight > 1 {
            leftRotate()
        } else if node2 == nil && node1 != nil && node1!.weight > 1 {
            rightRotate()
        } else if node1 != nil && node2 != nil {
            if node1!.weight > node2!.weight * 2 {
                rightRotate()
            } else if node1!.weight * 2 < node2!.weight {
                leftRotate()
            }
        }
        
        let _w1 = node1?.weight ?? 0
        let _w2 = node2?.weight ?? 0
        self.weight = _w1 + _w2 + 1
    }
   
    func contains(member: T) -> Bool {
        if member < value {
            return node1?.contains(member) ?? false
        }
        if value < member {
            return node2?.contains(member) ?? false
        }
        return true
    }
   
    subscript (position: Int) -> T! {
        let _w1 = node1?.weight ?? 0
        if position < _w1 {
            return node1?[position]
        }
        if position == _w1 {
            return value
        }
        return node2?[position - _w1 - 1]
    }
   
    func insert(newValue: T) {
        if newValue < value {
            if isUniquelyReferencedNonObjC(&node1) {
                node1!.insert(newValue)
            } else if let _node1 = node1 {
                node1 = _node1.clone
                node1!.insert(newValue)
            } else {
                node1 = OrderedSetNode(newValue)
            }
            node1!.weightCheck()
            return
        }
        if value < newValue {
            if isUniquelyReferencedNonObjC(&node2) {
                node2!.insert(newValue)
            } else if let _node2 = node2 {
                node2 = _node2.clone
                node2!.insert(newValue)
            } else {
                node2 = OrderedSetNode(newValue)
            }
            node2!.weightCheck()
            return
        }
        value = newValue
    }
}

extension OrderedSetNode {
   
    var view: (OrderedSetView<T>, last: OrderedSetView<T>) {
        let _v = OrderedSetView(value)
        let _v1 = node1?.view
        let _v2 = node2?.view
        if _v1 != nil && _v2 != nil {
            _v1!.last._next = _v
            _v._next = _v2!.0
            return (_v1!.0, _v2!.last)
        }
        if _v1 == nil && _v2 != nil {
            _v._next = _v2!.0
            return (_v, _v2!.last)
        }
        if _v1 != nil && _v2 == nil {
            _v1!.last._next = _v
            return (_v1!.0, _v)
        }
        return (_v, _v)
    }
}

private class OrderedSetView<T> {
   
    var value: T
    var _next: OrderedSetView<T>?
   
    init(_ value: T) {
        self.value = value
    }
}



回覆 引用 TOP

Interesting Swift code.
睇住你既code突然諗起persistent data structure,一種functional language寫,可以access所有historical state既data structure。有興趣可以去研究一下。



回覆 引用 TOP

[隱藏]
引用:
原帖由 darigold 於 2015-4-3 02:29 PM 發表

Interesting Swift code.
睇住你既code突然諗起persistent data structure,一種functional language寫,可以access所有historical state既data structure。有興趣可以去研究一下。
汪汪都唔知呢個...只係寫寫下諗到呢個做法

因為要保持Swift嘅特色, 所有container外在行為必需要同value type一樣(也所以要用struct定義)
第二點係Swift屬lazy evaluation, 所以所有container都係copy-on-write

基於以上原因...汪汪自己寫嘅都保留呢個特性



回覆 引用 TOP

複製內容到剪貼板
代碼:
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class persistent_tree
{
public:
    persistent_tree();
    ~persistent_tree();
    void insert(int x);
    void dump(unsigned int time_stamp);
private:
    class persistent_tree_node
    {
    public:
        persistent_tree_node(int data, persistent_tree_node* left, persistent_tree_node* right, int count);
        ~persistent_tree_node();
        
        void add_ref();
        void release();

        // Ideally these should be encapsulated - skipped for illustration
        persistent_tree_node* left;
        persistent_tree_node* right;
        unsigned int count;
        int data;
        int ref_count;
    };

    vector<persistent_tree_node*> roots;

    persistent_tree_node* recursive_insert(persistent_tree_node* current, int new_data);
    void recursive_dump(persistent_tree_node* current);
};

persistent_tree::persistent_tree()
{
}

persistent_tree::~persistent_tree()
{
    for (unsigned int i = 0; i < this->roots.size(); i++)
    {
        this->roots[i]->release();
    }
}

persistent_tree::persistent_tree_node::persistent_tree_node(int data, persistent_tree_node* left, persistent_tree_node* right, int count)
{
    this->left = left;
    this->right = right;
    this->data = data;
    this->count = 1;

    if (this->left != nullptr)
    {
        this->left->add_ref();
    }
    if (this->right != nullptr)
    {
        this->right->add_ref();
    }
}

void persistent_tree::persistent_tree_node::add_ref()
{
    this->ref_count++;
}

void persistent_tree::persistent_tree_node::release()
{
    if (--this->ref_count == 0)
    {
        delete this;
    }
}

persistent_tree::persistent_tree_node::~persistent_tree_node()
{
    if (this->left != nullptr)
    {
        this->left->release();
    }
    if (this->right != nullptr)
    {
        this->right->release();
    }
}

void persistent_tree::insert(int new_data)
{
    // Insert always work on the last time stamp
    persistent_tree_node* root = nullptr;
    if (this->roots.size() != 0)
    {
        root = this->roots[this->roots.size() - 1];
    }

    persistent_tree_node* new_root = this->recursive_insert(root, new_data);
    new_root->add_ref();
    this->roots.push_back(new_root);
}

persistent_tree::persistent_tree_node* persistent_tree::recursive_insert(persistent_tree::persistent_tree_node* current, int new_data)
{
    if (current == nullptr)
    {
        return new persistent_tree::persistent_tree_node(new_data, nullptr, nullptr, 1);
    }
    else if (current->data == new_data)
    {
        return new persistent_tree::persistent_tree_node(new_data, current->left, current->right, current->count + 1);
    }
    else if (current->data > new_data)
    {
        persistent_tree::persistent_tree_node* new_left_node = this->recursive_insert(current->left, new_data);
        return new persistent_tree::persistent_tree_node(current->data, new_left_node, current->right, current->count);
    }
    else if (current->data < new_data)
    {
        persistent_tree::persistent_tree_node* new_right_node = this->recursive_insert(current->right, new_data);
        return new persistent_tree::persistent_tree_node(current->data, current->left, new_right_node, current->count);
    }
    else
    {
        assert(false);
        return nullptr;
    }
}

void persistent_tree::dump(unsigned int time_stamp)
{
    if (time_stamp < this->roots.size())
    {
        persistent_tree::persistent_tree_node* root = this->roots[time_stamp];
        this->recursive_dump(root);
        cout << endl;
    }
    else
    {
        assert(false);
    }
}

void persistent_tree::recursive_dump(persistent_tree::persistent_tree_node* current)
{
    if (current == nullptr)
    {
        return;
    }
    else
    {
        this->recursive_dump(current->left);
        for (unsigned int i = 0; i < current->count; i++)
        {
            // Extra comma at the end, don't care
            cout << current->data << ", ";
        }
        this->recursive_dump(current->right);
    }
}

int main(int argc, char** argv)
{
    persistent_tree tree;
    tree.insert(3);
    tree.insert(0);
    tree.insert(6);
    tree.insert(2);
    tree.insert(4);
    tree.dump(0);
    tree.dump(1);
    tree.dump(2);
    tree.dump(3);
    tree.dump(4);
    return 0;
}



回覆 引用 TOP

For simplicity - I implemented only the insert method for a binary tree, and didn't bother to balance it.

1.) This tree is based on immutable nodes, with more careful handling of ref_count (using interlocked increment) and root list (using a lock free queue maybe), we can run this data structure in parallel with no locks.

2) this tree can give caller back all its histories. This can be useful if we want them. For example, when a transaction need to be rollback, or maybe just because we wanted to debug. By releasing the root list selectively, we can choose what time-stamp we wish to get rid of. Of course, we could have achieve the same thing by cloning the whole tree all the time, but that's too expensive. The maintain log(n) time for the insertion (assuming the tree balancing will be there)



回覆 引用 TOP

回覆 引用 TOP

while we are on the topic of persistent trees, I'd like to show you my immutable 2-3 tree (or B-tree) implementation.

https://github.com/stupidsing/su ... utable/I23Tree.java

This tree implementation is immutable, auto-balanced and supports removal.  Comments are welcome.



回覆 引用 TOP

[隱藏]
引用:
原帖由 stupidsing 於 2015-4-10 06:40 PM 發表

while we are on the topic of persistent trees, I'd like to show you my immutable 2-3 tree (or B-tree) implementation.
Nice suite of source code!
I am particularly interested in the c/asm folder. You seems to have some good stuff there - garbage collector, jit code demo, bootloader, ...



回覆 引用 TOP

引用:
原帖由 darigold 於 2015-4-4 01:09 AM 發表

Code is pushed to https://github.com/cshung/MiscLab/blob/master/PersistentTreeDemo/Main.cpp
點解你地鐘意用傳統的格式? 而唔直接在個 class 內 detailed 埋 D code? 唔覺得亂及麻煩嗎?

                                    
persistent_tree::~persistent_tree()
{
    for (unsigned int i = 0; i < this->roots.size(); i++)
    {
        this->roots->release();
    }
}


class persistent_tree{
~persistent_tree()
{
    for (unsigned int i = 0; i < this->roots.size(); i++)
    {
        this->roots->release();
    }

}
};



回覆 引用 TOP

引用:
原帖由 stupidsing 於 2015-4-10 06:40 PM 發表

while we are on the topic of persistent trees, I'd like to show you my immutable 2-3 tree (or B-tree) implementation.

https://github.com/stupidsing/suite/blob/master/src/main/java/suite/immutable/I ...
之前只係簡單試過寫唔影響balance同保持最大COW的情況下嘅remove
不過有部份情況下出錯...

但之後搞緊新apps上架同更新舊app
而且除非寫database
現實多數情況下用Hash table都係最佳, 而且只有少數情況需要iterate ordinal data
針對呢D少數情況做sorting比較長期insert/remove都保持O(log n)嘅OrderedSet有過之而無不及
所以OrderedSet冇咩實質作用就一直冇理到



回覆 引用 TOP

C# Dictionary 我用得最多。
老C++沒有default HashMap, 用Map就多。Map係Red Black Tree。
我段code既keypoint係persistence。唔係save落disk既persistent,係任何時候可以搵番次前n個time step既data。

HashMap據我理解做唔到。
之前學過HashTrie,可以做到,我得閒試試:p



回覆 引用 TOP

Harder ones!
LeetCode OJ - Binary Tree Preorder Traversal (Trivial recursive walk)
LeetCode OJ - Binary Tree Inorder Traversal (Trivial recursive walk)
LeetCode OJ - Climbing Stairs (Trivial dynamic programming)
LeetCode OJ - Populating Next Right Pointers in Each Node (Non trivial traversal order - simple though)
LeetCode OJ - Repeated DNA Sequences (Compact packing)
LeetCode OJ - Valid Parentheses (Pushdown Automata)
LeetCode OJ - Unique Binary Search Trees (Catalan numbers!)
LeetCode OJ - Linked List Cycle (Floyd Cycle detection)
LeetCode OJ - Single Number II (Finite field modulo 3)

[ 本帖最後由 darigold 於 2015-7-18 05:03 AM 編輯 ]



回覆 引用 TOP

[隱藏]
引用:
原帖由 煙民母親生賤種 於 2015-4-11 01:26 AM 發表

點解你地鐘意用傳統的格式? 而唔直接在個 class 內 detailed 埋 D code? 唔覺得亂及麻煩嗎?
第一,習慣,冇乜好解釋,同你習慣用右手(我猜)寫字一樣。
第二,抽象,讀我header files既人唔需要理解我的implementation。
第三,separate compilation,儘量做細header file會minimize chances to re-compile more than I need

其實咁細段code(小於1k line),2, 3都係多餘,main point係第一。



回覆 引用 TOP

提示:支持鍵盤翻頁左 右
[按此隱藏 Google 建議的相符內容]