STL trees: add presorted items one-by-one

The STL standard requires insert() and find() to be O(log N), so the tree has to remain fairly balanced at all times.

Q: When inserting sorted data one-by-one, what’s the frequency of re-balancing?

%%A: I didn’t find any definitive answer. I think it’s quite frequent. System has to assume “This could the last insertion and there will be many queries.” so re-balancing has to kick in whenever the tree becomes lopsided.

Incidentally, if you have presorted data in some temp container and you insert them /in one gulp/, then c++98 [1] standard requires the tree container to provide O(N) insertion which is better than O(N log N).

[1] not c++11. See http://www.cplusplus.com/reference/set/set/insert/

Advertisements

find every 3-subsets adding up to 9 #Ashish

Q: You have 9 poker cards, numbered 1 to 9. Given two integers SUM (for example 11) and COUNT (for example, 3), construct every combination of 3 cards, who add up to the target 11.

Within each combination, if we need to generate each permutation, it’s as simple as calling next_permutation() within an array (which is a combination).

You can only choose each card 0 or 1 time, i.e. no redraw.

I used to feel this was dynamic programming. Now I feel we have no choice but iterate over all combinations. We have an algo to generate ascending combinations. We can stored them in mini arrays, each one is ascending. We could use binary search in each mini-array.

https://github.com/tiger40490/repo1/blob/cpp1/cpp/array/sizeN-subset_TargetSum_Ashish.cpp is a very short recursive solution by my friend CSY.

//There are N distinct poker cards numbered 1 to N. Find all combinations
//of C cards such that each combo adds up to the same given Target
//
//Based on https://bintanvictor.wordpress.com/2017/11/08/generate-next_combo3-boys-out5-recursive/
//
//Note some range of the generated sequence is ascending, permitting
//binary search like lower_bound, but it's not easy to tweak the algo
//to skip ahead. There's no random access iterator here!
#include <iostream>
#include <sstream>
#include <deque>
#include <iomanip> //setw
#include <algorithm>  //sort
#include <assert.h>
//#define DEBUG
using namespace std;
size_t calls=0, combos=0;
size_t const C=3; //how many in each combination
size_t const Target=12;
deque<int> pool{1,3,4,5,8};
deque<int> prefix;

template<typename T> void dumpDeque(deque<T> const & p, string const & headline){
  cout<<"-- "<<headline<<" -- size = "<<p.size()<<endl;
  for(int i=0; i<p.size(); ++i) cout<<setw(5)<<p[i];
  cout<<endl;
}
template<typename T> int showCombo(deque<T> const * p){
  ++ combos;
  size_t sum = 0;
  stringstream ss;
  for(int i=0; i<p->size(); ++i){
        ss<<setw(5)<<(*p)[i];
        sum+= (*p)[i];
  }
  static string last;
  string combo=ss.str();
  cout<<"combo: "<<combo;
  if (sum == Target) cout<<" <- Hit!";
  cout<<endl;
  assert(last <= combo && "should be ascending");
  last = combo;
}

template<typename T> int recurs(){
  ++calls;
#ifdef DEBUG
  cout<<"-------------\nentering "; dumpDeque(prefix, "prefix"); dumpDeque(pool, "pool");
#endif
  if (prefix.size() == C) return showCombo(&prefix); //prefix alone is the combo
  if (pool.empty()) return 0;
  T poolhead = pool.front(); pool.pop_front();

  prefix.push_back(poolhead); //add poolhead to prefix

  //this 1st recursive function call starts a rather deep call stack and prints
  //all combinations that start with the given (new longer) prefix
  recurs<T>();//use the longer prefix and the shorter pool

  prefix.pop_back();//restore prefix
  recurs<T>();
  pool.push_front(poolhead); //restore pool, needed by the 2nd call in the parent stack
#ifdef DEBUG
  cout<<"^^^^^^ restored before returning "; dumpDeque(prefix, "prefix"); dumpDeque(pool, "pool");
#endif
}

int main() {
  assert(C <= pool.size());
  sort(pool.begin(), pool.end());
  recurs<int>();
  cout<<calls<<"  calls to the recursive function to generate "<<combos<<endl;
}

mv-semantic: %%Lesson #1

#9 std::move()
#8 STL containers using mv-semantic — confusing if we don’t have a firm grounding on …

#7 mv ctor and mv assignment — all the fine details would be poorly understood if we don’t have a grip on …

#5 RVR — is a non-trivial feature by itself. First, we really need to compare…

#3 rval expression vs lval expression — but the “expression” bit is confusing!

#1 lval expression vs lval variable vs objects in a program
This is fundamental concept.

RVR – exclusively used as function parameter@@

RVR – exclusively(?) used as function parameter

There could be tutorials showing other usages, like a regular variable, but i don’t see any reason. I only understand the motivation for
– move-ctor/move-assignment and
– insertions like push_back()

When there’s a function (usually a big4) taking a RVR param, there’s usually a “traditional” overload without RVR, so compiler can choose based on the argument:
* if arg is an rval expression then choose the RVR version [1]
* otherwise, default to the traditional

[1] std::move(myVar) would cast myVar into an rval expression. This is kind of adapter between the 2 overloads.

In some cases, there exists only the RVR version, perhaps because copy is prohibited… like in a class holding a FILE pointer?

Microsoft COM – a few keywords

“COM library” vs “type library”???

I suspect most code (whether people mention COM or not) written before dotnet are probably technically COM code???

— dotnet without the dotnet context —

Client/server — A COM client is whatever code or object that gets a pointer to a COM server and uses its services. A COM server is any object that provides services to clients. In-process servers are implemented in a dynamic linked library (DLL), and out-of-process servers are implemented in an executable file (EXE). Out-of-process servers can reside either on the local computer or on a remote computer.


Registry — COM types are usually listed by GUIDs in the registry, though some COM types are RegFree

DLL — COM components are usually implemented in DLL files, and registration allows only a single version of a DLL. Dotnet classes also exist in DLL or EXE files.


MS-Office – For example COM allows Word documents to dynamically link to data in Excel spreadsheets
Bindings — COM interfaces have bindings in several languages, such as C, C++, Visual Basic

ActiveX – is part of COM


— Excel Addin —
All COM Add-ins must implement each of the five methods of this interface: OnConnection, OnStartupComplete, OnAddinsUpdate, OnBeginShutDown, and OnDisconnection.

joint prob – jargon, …

Relevance –
– I feel conditional prob is based on joint prob
– conditional expn is based on joint prob

I feel one *extensible* example would be poker cards with 2 colors, 4 shapes, 13 values (based on how many “points”).

Important – variance of X+Y. http://www.math.cornell.edu/~back/m171/var_sum.pdf is a simple proof in discrete case.

Somewhat important – X*Y

matlab cheat sheet

–to insert a column into a matrix…. create a new matrix with the new column and the existing matrix.
–format long g % to display more digits without “e”

%{
multi-line comment
%}

nan(N) % better error detection than
ones(N)
zeros(N)
–Calling another .m script (not a function) — http://stackoverflow.com/questions/5226840/call-a-matlab-script-in-a-script

— print variable with tag
disp([‘x is equal to ‘,num2str(x),’.’])
fprintf(‘TS: row # %in’, foundInHeet);

–“die”

    error(‘Every time stamp must match between EWJ/JPP time series’)

— execute a multi-line selection of code
select -> right-click -> evaluate selection
–locate nan’s in a large vector
find(isnan(yourarray))
–code folding
preferences -> editor/debugger

IKM c++ misc points

——–
Q: is increment operator synthesized by the compiler?
——–
Portable file paths? Relative path OK. For absolute paths, use boost::filesystem
——–
terminate(void)
——–
default args must follow non-default args.
——–
(obscure syntax) int *(*p)[5] = new int *[5][5];
——–
(obscure syntax) redefinition error:
const int Mon = 1, Tue =2;
——–
Pointer to private field? legal
Pointer to ctor? Illegal
——–
Templatize operator<< then specialize it? legal
——–
Causing ambiguity error —
class base{};
class der: public base{};
void SomeFunc(base& b){ };
void SomeFunc(base b){ };
void SomeFunc(der& b){ };
void SomeFunc(der b){ };

python script to descend n edit files in-place

import re
import os
import sys
from os import walk
import xml.dom.minidom as md

pretty_print = lambda f: ‘n’.join([line for line in md.parse(open(f)).toprettyxml(indent=’ ‘*2).split(‘n’) if line.strip()])

dirName, baseName = os.path.split(sys.argv[1])
print sys.argv
print dirName
print baseName

for (path, dirs, files) in walk(sys.argv[1]) :
        for oFileName in files :
                print oFileName; #raw_input(“…”)
                if not re.search(“vol.*.xml$”,oFileName): continue
                fullpath = path+”\”+oFileName;
                try:
                        write_file=open(fullpath+”_normalized.txt”,’w’)
                except Exception as e:
                        print e; raw_input(“…”)                      

                totalsubs = 0
                for line in open (fullpath): #path+”\tmp.txt”) :
                        # $2 not supported!
                        # \b same as in perl
                        newStr, subsMade = re.subn(‘\b(Tenor=”.*?”)s+(Date=”.*?”)’ , “\2 \1”, line)
                        if (subsMade > 0):
                                print newStr, # comma to suppress n
                                totalsubs += subsMade
                        write_file.write(newStr)
                write_file.close()
                print str(totalsubs) + ” total substitutions made — ” + fullpath

   
raw_input(“…”)
”’
                tmpFile=open(path+”\tmp.txt”, ‘w’)
                tmpFile.write(pretty_print (fullpath))
                tmpFile.close
”’

##c++(GTD+)learning-aids to upgrade 6→7

Which yardstick? First must be IV. 2nd would be common (not the obscure) GTD skills
For IV, need to analyze how I was beaten in past interviews. For GTD zbs, a few major home projects has significantly increased my proficiency.
  • see recoll -> c++Q&A.txt
  • [ZZ] try out debug tools in the gdb book? LG
  • [ZZ] experiment with sample code in [[fin instrument pricing using c++]]
  • [ZZ] proj: valgrind (linux) – get hands-on experience. Might take too much time to get it working
  • problem – test if a linked list has cycles
  • problem: all permutations of 0 or more of abcde
  • problem: write skeleton c++ code for ref counted string or auto_ptr
  • problem: test if a given container is in ascending order
  • [ZZ means … see https://bintanvictor.wordpress.com/2017/02/14/low-leverage-ctopics/]

c# delegates – 2 fundamental categories

Update: java 8 lambda. [[mastering lambds]] P 5 mentions AA BB DD as use cases for Command pattern

AA — is the main topic of the book
BB — https://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html
DD — http://www.oracle.com/technetwork/articles/java/lambda-1984522.html and http://www.drdobbs.com/jvm/jdk-getting-a-head-start-with-lambdas/240008174

Today I finally feel ready to summarize the 2 usage categories of c# delegates. If you are new like me, it’s better to treat them as 2 unrelated constructs. Between them, the underlying technical similarities are relevant only during initial deep dive, and become less important as you see them in various patterns (or “designs”).

In java, these features are probably achieved using interface + other constructs. Dotnet supports interfaces too, but in some contexts offers more “specialized” constructs in the form of delegates. As shown below, in such a context interfaces are usable but less than delegates.

Most tutorials would start with unicast delegate, without the inv list.

Coming from a java or c++ background, you will want to find a counterpart or close equivalent to delegates. Almost hopeless for BB. For AA there are quite a few, which adds to the confusion.

AA) lambda as function AAArgument
* I believe compiler converts such a lambda into a STATIC method (there’s really no host object) then bind it to a delegate Instance
* often returns something
* Usually _stateless_, usually without captured variables.
* predominantly unicast
* Action, Func and Predicate are often used in this context, but you can also use these 3 constructs as closures, which is a 3rd category beyond AA and BB
* Domain? Linq; functor argument as per Rajesh of OC
* Before java 8, often implemented as an interface or an anonymous inner class

BB) event field Backed by a multicast delegate instance (See other posts on “newsletter”)
* Usually NON-STATIC methods, esp. in GUI context
* Usually returns void
* A callback method is usually _stateful_, because the callback method often does its job with “self-owned” i.e. this.someField objects, beyond the argument objects passed in
* event is a pseudo _f i e l d_ in a class. Static field or non-static field are both common.
* Domain? GUI + asynchronous WCF
* we must register the callback method with the event source.
** can lead to memory leak
* in java, implemented by several callback Objects supporting a common interface (cf swing)


Some of the other categories —
CC) CCClosure — stateful, seldom passed in as a func arg
DD) thread start
EE) Passing in a delegate instance as a function input is the lambda usage (AA). How about returning from a function? P83 [[c#precisely]] shows examples to return an anon delegate instance. This is an advanced and non-trivial unicast use case. The underlying anon method is usually static and stateless

In a source code with AA, we see lots of custom delegate Types created on the fly.

In a source code with BB, delegate Instances take center stage, since each instance is assigned to a … pseudo field. The delegate type is less complicated.

op-new : no DCBC rule

B’s op-new is bypassed by D’s op-new [1]
B’s ctor is always used (never bypassed) by D’s ctor.

This is a interesting difference.

Similarly, an umbrella class’s op-new [1] would not call a member object’s op-new. See [[more effC++]]

These issues are real concerns if you want to use op-new to prohibit heap instantiation of your class.

See http://bigblog.tanbin.com/2012/01/dcbc-dtor-execution-order.html

[1] provided these two classes each define an op-new()

By the way, op-new is a static member operator, but is still inherited.

mv-semantics: MSDN article

http://blogs.msdn.com/b/vcblog/archive/2009/02/03/rvalue-references-c-0x-features-in-vc10-part-2.aspx is one of the best articles to shed lights on this confusing topic, written by someone in the Visual c++ core team.

One comment says “…this is mainly a feature for use in library-code. It’s mostly transparent to client-code which will just silently benefit from it”. How true!

I always believed move-semantic is a non-trivial topic. Many authors try to dumb it down and make it accessible to the mere mortals, but I feel a correct understanding takes effort.

Scott Meyers articles are also in-depth but seem to skip the basics.

As I mentioned earlier, [[c++ primer]] has the best deep-intro on this confusing topic. Again, the author is another legend in the c++ community.