- new benchmark for my read/write algorithm... - 4 Updates
- binary tree: how did you learn it? - 16 Updates
- binary tree: how did you learn it? - 2 Updates
- [win][gcc] problem with compiling 64 bit dll on 32 bit windows (via tdm-gcc) - 3 Updates
| "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com>: Mar 10 08:37PM -0700 On 3/10/2019 1:17 AM, Bonita Montero wrote: > more than (2 ^ 16) - 1 threads might have locked the mutex exclusively > or more than (2 ^ 15) - 1 threads might have locked the mutex shared > or shared recursively. I know what your issue is, and how CAS can solve the problem _before_ it can occur. However, you should make an explicit _rule_ that no more than 0xFFFF, wrt writers, can access your work for exclusive access at any one time. If your CAS loop detects an error, it is sort of acting like a proverbial the cork on the fork. Btw, there are ways to fix XADD accounting errors, but they are sometimes not pretty. Wrt robust mutex, I am writing about what happens if a process dies while waiting on a kernel primitive, (semaphore, auto-reset event)... |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 11 09:13AM +0100 > However, you should make an explicit _rule_ that no more than > 0xFFFF, wrt writers, can access your work for exclusive access > at any one time. The best way is to trap the threads in the way I told: simply check the counter before incrementing. Sometimes you simply can't predict how many threads will lock the mutex, especially with resoursive read-locking. |
| "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com>: Mar 09 06:21PM -0800 On 3/7/2019 12:47 AM, Bonita Montero wrote: > Then you would have to end the process. Rolling back the XADD > woudln't be possible because another thread would rely on the > state asynchronously. Just tell the users to not break the rules. Simple. Like, never unlock a mutex, unless it has been locked already. Or, always be sure to unlock a mutex that was previously locked. This was never meant to try and emulate a robust mutex... Why put corks on the forks? |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 10 10:17AM +0100 > Just tell the users to not break the rules. Simple. > Like, never unlock a mutex, unless it has been locked already. That's not the issue I'm talking about. The problem here is that more than (2 ^ 16) - 1 threads might have locked the mutex exclusively or more than (2 ^ 15) - 1 threads might have locked the mutex shared or shared recursively. |
| Cholo Lennon <chololennon@hotmail.com>: Mar 11 01:35AM -0300 On 3/10/19 4:31 AM, Alf P. Steinbach wrote: > But I think that shows how far in front and yet at the same time how far > out on the impractical fringes Wirth was. Really remarkable. Sorry, I > couldn't resist mentioning it. Wow we learned from the same book :-) Interesting story about Dr. Wirth, I didn't know it. Certainly Wirth is a great computer scientist, but I never understood why he created 3 programming languages instead of evolve Pascal :-O (well Oberon descends from Modula-2 and this from Modula and Pascal, so in some sense there is an evolution here, but fragmented). -- Cholo Lennon Bs.As. ARG |
| Jeremy Murphy <jeremy.william.murphy@gmail.com>: Mar 10 10:01PM -0700 On Monday, 11 March 2019 08:57:56 UTC+11, Ben Bacarisse wrote: > mean binary /search/ trees and for that, even in Lisp, you need to > decide how to represent a node. A plain tree of cons cells with atoms > at the leaves is not efficiently searchable. I didn't make a huge distinction in my original post, but when I say "binary tree" I do simply mean, for example, what Knuth defines in Volume 1. A binary _search_ tree is the same structure with extra requirements and constraints, and it's an important case because it's what a lot of people associate with a binary tree. Jeremy |
| Ben Bacarisse <ben.usenet@bsb.me.uk>: Mar 11 11:10AM > I didn't make a huge distinction in my original post, but when I say > "binary tree" I do simply mean, for example, what Knuth defines in > Volume 1. I went back to your original post and you were clear that you were talking about binary trees in general. It might have been a tad clearer had you not specified binary because that can lead people to consider specific uses. Knuth, of course, talks about trees in general with binary trees as a particular case. Anyway, I see my comment to Stefan Ram is wrong. It's not that he's being overly literal but just too narrow. The trees in Knuth have data at the nodes whether the nodes are leaf nodes or internal nodes. You can model these in Lisp, but Lisp's plain S-expression built with CONS, CAR and CDR are not binary trees in Knuth's more abstract sense. Knuth's trees correspond more closely to this Haskell type: Tree a = Node a [Tree a] with the consequence that they can't be empty -- every tree has a root node. -- Ben. |
| "Öö Tiib" <ootiib@hot.ee>: Mar 11 04:25AM -0700 On Sunday, 10 March 2019 05:13:11 UTC+2, Jeremy Murphy wrote: > Dear readers, > I'm doing some informal research for a talk I'll be giving, and what I'm interested in is firstly: how did you learn to program a binary tree in C++? About binary trees I read first from some Russian algorithm textbook (possibly translation) for either Fortran or PL/I in eighties. First binary tree that I wrote in C++ was AVL tree at start of nineties in process of self-educating C++. > Also, was it a general binary tree, or a binary _search_ tree, that was taught? > A small code snippet would be helpful but no need for complete implementations. > And if you were never taught it, I'd still be interested to hear that! I have never used binary trees that were not binary search trees. When there has been need for a tree that is not search tree then it was not binary tree that was needed. Also for searching the hash table is often worth considering as alternative to binary search tree. > Secondly, if you use a (general) binary tree occasionally now, which implementation do you use? In C++ I have lately only used the trees from Boost.Intrusive. These work fine in tests and are easy to switch between (for comparing performance) and allow enough flexibility for whatever usage of a raw binary tree. > Although I'm really interested in C++, I'd still be interested to hear if you learned it in C or maybe even Java since those languages can make similar trade offs and are not as distant in memory semantics as say Python or Haskell. Use your own discretion though, I don't want to upset anyone with a lot of non-C++ code flying around. :) I don't think my career was anyhow typical. |
| James Kuyper <jameskuyper@alumni.caltech.edu>: Mar 11 08:27AM -0400 On 3/9/19 22:13, Jeremy Murphy wrote: > Dear readers, > I'm doing some informal research for a talk I'll be giving, and what I'm interested in is firstly: how did you learn to program a binary tree in C++? > And if you were never taught it, I'd still be interested to hear that! I never did. I learned how to implement binary trees in C, and at a later time I learned how write C++, and what I learned about C should have continued to work in C++ - but I never put that assumption to the test. That's because, in any context where I would want to use a binary tree if I were working in C, I would normally use one of the standard associative containers if I'm working in C++. |
| Bonita Montero <Bonita.Montero@gmail.com>: Mar 11 04:31PM +0100 >> I learned how to implement binary trees in C, > Since they say that every C program is a C++ program, > I hope C is not too off-topic here. Arrrrgh, Stefan, you're such a mega-idiot. Since he only told how he did learn this and he not posted a non-c++ -conforming implementation of any type of binary tree this statement absolutely isn't off-topic. You're just trying to elevate your authority about his because you have a low self-esteem. > Ten years ago I was hired by a university to teach C > to a scientist, and one of the things on the wishlist > were binary trees. I wish I will never get tought anything from a compulsive person like you. |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Mar 10 08:31AM +0100 On 10.03.2019 06:01, Cholo Lennon wrote: > was so young!), using Pascal and the classic book "Algorithms + Data > Structures = Programs" by Niklaus Wirth, so if you want my first > possible implementation just get that book ;-) For me that was early 1980's, but same book and language. Worth noting that the free version of the book uses the Oberon language, successor to Modula-2 which was a successor to Pascal, all by Niklaus Wirth. Well, except to the degree that Kathleen Jensen was involved with Pascal. I never got that history, but she co-wrote the user manual. When or if C++ finally gets modules the circle will be ~completed. :) --- Sillyfact about Wirth and Oberon: Wirth was visiting Xerox PARC (the place where they invented the Ethernet, bitmapped displays, bitblt, workstations, object orientation, all nice things, but later on also RFID tags, cross-cutting concerns, and other more evil stuff), and was impressed by the What You See Is What You Get approach; bitmapped fonts! So he went back to Switzerland to build /hardware to support a programming language/. Namely the Lilith machine, to support Modula 2. Of course some decades later hardware support for Java emerged. But I think that shows how far in front and yet at the same time how far out on the impractical fringes Wirth was. Really remarkable. Sorry, I couldn't resist mentioning it. Cheers!, - Alf |
| Paavo Helde <myfirstname@osa.pri.ee>: Mar 10 10:49AM +0200 On 10.03.2019 5:13, Jeremy Murphy wrote: > Also, was it a general binary tree, or a binary _search_ tree, that was taught? > A small code snippet would be helpful but no need for complete implementations. > And if you were never taught it, I'd still be interested to hear that! I was never taught binary trees (instead I was taught things like path integrals and Grassmann algebras). I have some vague memory of reading something about red and black trees in some brochures, but I have never had a need or interest to implement such a thing. I have implemented several non-binary tree data structures though. > Secondly, if you use a (general) binary tree occasionally now, which implementation do you use? I guess std::map and std::set would qualify. |
| Melzzzzz <Melzzzzz@zzzzz.com>: Mar 10 11:03AM > In C++ I've never needed anything that the standard containers > couldn't give me, e.g. the features of a search tree exposed by > std::map, or the std::make_heap stuff if that counts. Standard containers does not provide btree which is much more efficent on modern CPUs then red black tree. -- press any key to continue or any other to quit... |
| scott@slp53.sl.home (Scott Lurndal): Mar 10 04:42PM >Dear readers, >I'm doing some informal research for a talk I'll be giving, and what I'm in= >terested in is firstly: how did you learn to program a binary tree in C++? From "Fundamentals of Data Structures" by Horowitz and Sahni long before C++. |
| Tim Rentsch <tr.17687@z991.linuxsc.com>: Mar 10 12:00PM -0700 > Specifically, what implementation were you taught? > Also, was it a general binary tree, or a binary _search_ tree, > that was taught? I first learned about binary trees, binary search trees, and balancing binary trees, from Knuth volume 1, before the C programming language existed. (In those days "Knuth" always meant "The Art of Computer Programming".) I have at various times implemented AVL trees, B trees, Red-Black trees, 2-3 trees, and 2-3-4 trees. (If I remember right the B trees were actually a slight variation, with a B tree structure in the upper levels, but the bottom level was done with hash tables.) All of these supported searching. > Secondly, if you use a (general) binary tree occasionally now, > which implementation do you use? Depends on the context. In most cases if one were readily available I would use that without caring which variation it is. Also other factors sometimes make a big difference in choosing one kind or another. For example, an imperative tree that is updated in place might favor a different representation than a functional tree that always makes a "new tree", where the new tree isn't all new but reuses large parts of the existing tree (ie, before the addition has been done). Scale also makes a big difference - an in-memory structure of up to thousands or perhaps tens of thousands of items is probably better done as a hash table (for searching), whereas a longer-lived or much larger structure (so it needs to be stored on disk) is more likely to use something like a B tree. > semantics as say Python or Haskell. Use your own discretion though, > I don't want to upset anyone with a lot of non-C++ code flying > around. :) Knuth describes algorithms in what might be called an English pseudo-code (and the Mix assembly language, which IMO is worse than useless). So in my case the learning was pretty much language agnostic. Since learning from Knuth I have programmed different sorts of trees in C, C++, and functional languages of the ML variety. |
| Jorgen Grahn <grahn+nntp@snipabacken.se>: Mar 10 07:25PM On Sun, 2019-03-10, Melzzzzz wrote: >> std::map, or the std::make_heap stuff if that counts. > Standard containers does not provide btree which is much more efficent > on modern CPUs then red black tree. Fair enough: standard containers don't expose red-black trees either. /Jorgen -- // Jorgen Grahn <grahn@ Oo o. . . \X/ snipabacken.se> O o . |
| Vir Campestris <vir.campestris@invalid.invalid>: Mar 10 09:39PM On 10/03/2019 08:17, Jorgen Grahn wrote: > In C++ I've never needed anything that the standard containers > couldn't give me, e.g. the features of a search tree exposed by > std::map, or the std::make_heap stuff if that counts. Much like me - I've never needed to write a tree that needed to grow. I've done binary searches on a fixed dictionary. ISTR doing one in Assembler as one of my first professional tasks - would have been around 1980. I wrote a hashmap about 5 years back for something where there were no runtime libraries available. And cursed that lack. But red-back trees and the like? On the rare occasions I've needed one there's been a run time library to do it for me. Andy |
| Cholo Lennon <chololennon@hotmail.com>: Mar 10 02:01AM -0300 On 3/10/19 12:13 AM, Jeremy Murphy wrote: > Secondly, if you use a (general) binary tree occasionally now, which implementation do you use? > Although I'm really interested in C++, I'd still be interested to hear if you learned it in C or maybe even Java since those languages can make similar trade offs and are not as distant in memory semantics as say Python or Haskell. Use your own discretion though, I don't want to upset anyone with a lot of non-C++ code flying around. :) > Thanks, and I'll post a link to the presentation after it happens. I learned about binary trees many years ago, in the early '90s (ohhh I was so young!), using Pascal and the classic book "Algorithms + Data Structures = Programs" by Niklaus Wirth, so if you want my first possible implementation just get that book ;-) Regards -- Cholo Lennon Bs.As. ARG |
| Melzzzzz <Melzzzzz@zzzzz.com>: Mar 10 06:53AM > tree in C++? Specifically, what implementation were you taught? > Also, was it a general binary tree, or a binary _search_ tree, that > was taught? Binary search tree. I can't remember but I think I used wikipedia. > A small code snippet would be helpful but no need for complete > implementations. Well, There is insert and delete operation. For search tree insert is done by going left right until node found. Then you insert node. for delete left right until node found. then find next which is at bottom, swap then delete last node. Here is my implementation of treap: #ifndef TREAP_H #define TREAP_H #include <functional> #include <cstddef> #include <utility> #include <cassert> #include <ctime> #include <string> #include <vector> #include <sstream> #include <iostream> #include <cstdlib> template <class K,class V, class Compare = std::less<K> > class Treap{ public: Treap(unsigned seed = time(0)) : root_(0),size_(0),counter_(0), seed_(seed) { } ~Treap() { delete root_; } size_t size()const{ return size_; } std::pair<K,V>& insert(const std::pair<K,V>& arg) { return insert_priv(arg); } V& operator[](const K& k) { return insert(std::pair<K,V>(k,V())).second; } V* find(const K& k)const; size_t depth()const { size_t fd,ld; first(root_,fd); last(root_,ld); if(fd>ld)return fd; else return ld; } void erase(const K& key) { remove(key); } std::string toString()const { std::string tmp; if(root_ == 0)tmp.append("Tree has no nodes"); else { tmp = toString(root_,"",true); } return tmp; } bool validate()const { return validate(root_); } size_t counter()const { return counter_; } void reset_counter() { counter_=0; } void clear() { delete root_; size_ = 0; root_ = 0; } template <class F> void for_each(F f) { for_each(root_,f); } void weight(size_t& left,size_t& right) { if(!root_) { left=right=0; return; } left = weight(root_->left_); right = weight(root_->right_); } private: struct Node{ Node(const std::pair<K,V>& data, Treap& trp) : parent_(0),left_(0),right_(0),priority_(trp.prn()),data_(data) { } ~Node() { delete left_; delete right_; } Node* rotate_left() { Node* n = left_; //std::cout<<"rotate left\n"<<toString(this,"",true)<<"\n"; if(n == 0) { return 0; } left_ = n->right_; if(left_)left_->parent_ = this; n->right_ = this; if(parent_) { if(parent_->left_ == this) { parent_->left_ = n; n->parent_ = parent_; } else { if(parent_->right_ != this) { std::cout<<"rotate left failed\nchild\n"<<toString(this,"",true)<<"\nparent\n"<<toString(parent_,"",true)<<"\n"; abort(); } parent_->right_ = n; n->parent_ = parent_; } } else { n->parent_ = 0; } parent_ = n; return n; } Node* rotate_right() { Node* n = right_; //std::cout<<"rotate right\n"<<toString(this,"",true)<<"\n"; if(n == 0) { return 0; } right_ = n->left_; if(right_)right_->parent_ = this; n->left_ = this; if(parent_) { if(parent_->left_ == this) { parent_->left_ = n; n->parent_ = parent_; } else { if(parent_->right_ != this) { std::cout<<"rotate right failed\nchild\n"<<toString(this,"",true)<<"\nparent\n"<<toString(parent_,"",true)<<"\n"; abort(); } parent_->right_ = n; n->parent_ = parent_; } } else { n->parent_ = 0; } parent_ = n; return n; } Node *parent_,*left_,*right_; unsigned priority_; std::pair<K,V> data_; }; size_t weight(Node* n) { if(!n)return 0; return weight(n->left_)+weight(n->right_)+1; } template <class F> void for_each(Node* n, F f) { if(!n)return; for_each(n->left_,f); f(n->data_); for_each(n->right_,f); } unsigned prn() { return rand_r(&seed_); } Node* first(Node* n,size_t& depth)const { Node *rc = 0; depth = 0; while(n) { ++depth; rc = n; n = n->left_; } return rc; } Node* last(Node* n,size_t& depth)const { Node* rc = 0; depth = 0; while(n) { ++depth; rc = n; n = n->right_; } return rc; } std::pair<K,V>& insert_priv(const std::pair<K,V>& ins_value,Node* node = 0) { if(root_ == 0) { if(!node) root_ = new Node(ins_value,*this); else { root_ = node; node->parent_ = node->left_ = node->right_ = 0; } ++size_; return root_->data_; } Compare cmp; Node* n = root_; Node *rc = 0, *prev = 0; bool ret; while(n) { prev = n; ret = cmp(ins_value.first,n->data_.first); if(ret) { n=n->left_; } else { rc = n; n = n->right_; } } if(rc && !cmp(rc->data_.first,ins_value.first)) { return rc->data_; } if(ret) { if(!node) { rc = prev->left_ = new Node(ins_value,*this); } else { rc = prev->left_ = node; rc->parent_ = rc->left_ = rc->right_ = 0; } prev->left_->parent_ = prev; } else { if(!node) { rc = prev->right_ = new Node(ins_value,*this); } else { rc = prev->right_ = node; rc->parent_ = rc->left_ = rc->right_ = 0; } prev->right_->parent_ = prev; } n = rc; rebalance_up(n); ++size_; return rc->data_; } void remove(const K& rem_value) { Compare cmp; Node* rc = 0,*n = root_; while(n) { bool ret = cmp(rem_value,n->data_.first); if(ret) { n = n->left_; } else { rc = n; n = n->right_; } } if(!rc || cmp(rc->data_.first,rem_value))return; Node* reb = 0; while(rc->left_ && rc->right_) { Node* n = rc->rotate_right(); if(root_ == rc)root_ = n; if(!reb && n->left_ && n->left_->priority_ < n->priority_)reb = n; } Node** parent_node = 0; if(rc->parent_) parent_node = ((rc->parent_->left_ == rc)?&rc->parent_->left_:&rc->parent_->right_); if(rc->left_ == 0 && rc->right_ == 0) { if(parent_node)*parent_node = 0; else root_ = 0; } else if(rc->left_ == 0) { if(parent_node) { *parent_node = rc->right_; rc->right_->parent_ = rc->parent_; } else { root_ = rc->right_; rc->right_->parent_ = 0; } rc->right_ = 0; } else if(rc->right_ == 0) { if(parent_node) { *parent_node = rc->left_; rc->left_->parent_ = rc->parent_; } else { root_ = rc->left_; rc->left_->parent_ = 0; } rc->left_ = 0; } delete rc; --size_; rebalance_left(reb); } bool validate(const Node* node)const { if(!node)return true; Compare cmp; if(node->left_ && !cmp(node->left_->data_.first,node->data_.first)) { return false; } if(node->right_ && !cmp(node->data_.first,node->right_->data_.first)) { return false; } if(node->left_ && node->left_->parent_ != node) { return false; } if(node->right_ && node->right_->parent_ != node) { return false; } if(node->left_ && node->priority_ > node->left_->priority_) { return false; } if(node->right_ && node->priority_ > node->right_->priority_) { return false; } bool rc1 = validate(node->left_); bool rc2 = validate(node->right_); return rc1 && rc2; } void rebalance_left(Node* node) { if(!node)return; rebalance_left(node->left_); while(node->left_ && node->left_->priority_ < node->priority_) { Node* n = node->rotate_left(); if(node == root_)root_ = n; } } void rebalance_right(Node* node) { if(!node)return; rebalance_right(node->right_); while(node->right_ && node->right_->priority_ < node->priority_) { Node* n = node->rotate_right(); if(node == root_)root_ = n; } } void rebalance_up(Node* n) { while(n->parent_ && n->priority_ < n->parent_->priority_) { if(n->parent_->left_ == n) n = n->parent_->rotate_left(); else n = n->parent_->rotate_right(); if(n->parent_ == 0)root_ = n; } } static std::string toString(const Node* node, const std::string& prefix, bool isTail) { std::string tmp; tmp.append(prefix).append(isTail ? "└── " : "├── "); if(!node) { tmp.append(" null"); return tmp; } std::ostringstream oss; const std::pair<K,V>& v = node->data_; oss<<"p:"<<node->priority_<<" ("<<v.first<<","<<v.second<<")"; tmp.append(oss.str()); oss.str(""); tmp.append("\n"); tmp.append(toString(node->left_,prefix + (isTail?" ":"│ "),false)); tmp.append("\n"); tmp.append(toString(node->right_,prefix + (isTail ? " " : "│ "),true)); return tmp; } public: class iterator{ public: iterator(Node* n):node_(n){} std::pair<K,V>& operator*()const{ return node_->data_; } std::pair<K,V>* operator->()const{ return &node_->data_; } bool operator==(const iterator& other)const { return node_ == other.node_; } bool operator!=(const iterator& other)const { return !(*this == other); } iterator& operator++() { if(node_->right_ != 0) { node_ = node_->right_; while(node_->left_ != 0) { node_ = node_->left_; } } else { Node* tmp = node_->parent_; while(tmp && node_ == tmp->right_) { node_ = tmp; tmp = tmp->parent_; } node_ = tmp; } return *this; } private: Node* node_; }; iterator begin() { size_t depth = 0; return iterator(root_,first(depth)); } iterator end()const { return iterator(0); } private: Node* root_; size_t size_,counter_; unsigned seed_; }; template <class K,class V, class Compare> V* Treap<K,V,Compare>::find(const K& k)const { Compare cmp; Node* n = root_,*tmp = 0; V* rc = 0; while(n) { bool ret = cmp(k,n->data_.first); if(ret) { n = n->left_; } else { tmp = n; n = n->right_; } } if(tmp && !cmp(tmp->data_.first,k)) { rc = &tmp->data_.second; } return rc; } 
Subscribe to:
Post Comments (Atom)
|
No comments:
Post a Comment