问:
Persistence Strategies - Filling a cache strategy
Let's say I have an interface IDataAccessObject<TSource> with CRUD methods to access a data source.

I have an implementation StrategyDataAccessObject<TSource>, which uses an strategy pattern in order to fetch and update data.

All persistence strategies should implement IPersistenceStrategy<TSource>, so for instance, I may have:

CachePersistenceStrategy<TSource>

FileSystemPersistenceStrategy<TSource>

SQLServerPersistenceStrategy<TSource>

...

StrategyDataAccessObject<TSource> is injected a list of these strategies.

The workflow is somewhat like this:

When the user queries the data source (i.e., does not change the inner data model), the DAO iterates over all strategies, and if any of them return a non empty result, breaks out of the loop and returns it to the user

When the user requests a change to the data model (i.e., insertion, update, deletion), then the DAO applies the change to all the strategies.

So if we have the following list of strategies: [cache, fileSystem, sqlServer] and the user queries for the user with ID = 1, then we will inspect the cache, if it is not there, move on to inspect the file system. if it is there, we don't go to the SQL Server database, we return what we found on the file system.

A cache strategy is initialized empty, so I have to fill in the data somehow.

Providing the DAO does not know anything about the strategies implementation (it just sees an interface) and knowing that each strategy is unaware of the existence of the other, how can I fill my cache strategy with data from the next strategies?

答:
I'm far from a design patterns wizard, but this doesn't sound to me like a natural implementation of the strategy pattern given this kind of synchronization that's going on between each entity as opposed to simply choosing one appropriate strategy based on runtime input.

Instead it sounds strikingly similar to the memory hierarchy used by our hardware ranging from disk to DRAM to CPU cache to register.

Provided that you can find a common, abstract interface for all these data sources, one thing that might be worth trying is to instead aggregate them using an intrusive doubly-linked list representation, like so (note that the list pointers/references can and probably should be stored in concrete objects):

A singly-linked representation would also do just fine here, though the doubly-linked representation may simplify implementation quite a bit at a most trivial cost given the coarseness of these nodes.

This will allow you to do the dependency injection at the data source level which can become useful for automating the synchronization/caching that occurs between these data sources in a very symmetrical fashion and making the process of caching no longer an external concern of the DAO, but instead an internal concern of the data storage type.

We can then link together the data sources like so:

The DAO can then be injected with an IDataSource-compliant node, preferably your fastest one (the memory cache) since it's typically going to be the first node we check for the availability of data prior to checking the bigger but more expensive nodes linked to it.

This allows quite a bit of flexibility with how you choose to cache data, since you can skip the caching by simply injecting the DAO directly with the SQL Server data source if caching is undesirable. It's also easy to do things like take the disk cache out of the picture by simply connecting the memory cache to the server and injecting the DAO with the memory cache.

Read Propagation

A cache strategy is initialized empty, so I have to fill in the data somehow.

If you apply this kind of memory hierarchy design, then the process of reading can fill these intermediary data storage caches implicitly/automatically in the process of the DAO simply requesting to perform operations from its injected data source.

We begin with the DAO requesting to read from its injected data source, the memory cache. The memory cache then checks in its load implementation if the data is available. If not, it recursively requests a read operation from the bigger, linked data source, the disk cache, and this repeats.

Here's the twist: if a smaller data source does not find the requested data and thus propagates a read request to a bigger data source, the returned data is then stored (cached) in the smaller, faster data source prior to returning it back to the caller. This logic is symmetrical across data sources and can be provided as part of an abstract base class. The pseudocode would be as follows:

```<code>DataSource::read(key):                 // implemented once in a base class
   data = load(key)                    // abstract
   if data != null:
       return data
   if bigger_node != null:
       data = bigger_node.read(key)
       store(key, data)                // abstract: cache data prior to returning
       return data
   return null
</code>```

Eviction

These intermediary storage caches may end up reaching some state of being "full". If so, an eviction strategy is necessary. A simple and effective one is to simply evict LRU (least recently-used) data whenever a cache is full. In that case, we need some kind of time stamp to update when data is accessed in the intermediary cache storage (not for the SQL server, since it's modeling nonvolatile storage), like so:

```<code>Memory::load(key):                     // overridden by each data storage type
   if data[key] != null:
       update_timestamp(data[key])
   return data[key]

Memory::store(key, new_data):          // overridden by each data storage type
    if not key_exists(key) and full():
        evict_lru_data()               // evict(remove) least-recently used data
    data[key] = new_data
    update_timestamp(data[key])
</code>```

Create, Update, Delete

For these kinds of mutating operations, an easy strategy is as you described: simply mirror the operations to all the data sources.

```<code>create(key, data):
    store(key, data)
    if bigger_node != null:
       bigger_node.create(key, data)
</code>```

... and so forth. The update operation can be similar to read propagation by copying the data into all three storage types, with create, as implemented above, likewise filling all three data storage types.

A more complex strategy is to only perform these operations in the faster data storage types and then propagate modifications to the bigger ones later in a deferred fashion (ex: during eviction, at periodic intervals, on shutdown). However, that might screw with atomicity and make transaction-safety more difficult in addition to exacerbating synchronization issues with the latest data available on the server.

Going Beyond

There are potentially some more complex issues here like the fact that an intermediary cache may not necessarily be up-to-date with what's on the server if there are other DAO clients in the mix. There's also transaction-safety to consider and, of course, thread-safety. However, these concerns apply regardless of how you choose to design this as they're conceptually attached to the notion of intermediary caches between your database server.

In any case, I hope this kind of design might help a bit and potentially offer some solutions to these problems, or at least offer a new kind of perspective to this problem whether or not this kind of design is used.

Body:
I'm far from a design patterns wizard, but this doesn't sound to me like a natural implementation of the strategy pattern given this kind of synchronization that's going on between each entity as opposed to simply choosing one appropriate strategy based on runtime input.

Instead it sounds strikingly similar to the memory hierarchy used by our hardware ranging from disk to DRAM to CPU cache to register.

Provided that you can find a common, abstract interface for all these data sources, one thing that might be worth trying is to instead aggregate them using an intrusive doubly-linked list representation, like so (note that the list pointers/references can and probably should be stored in concrete objects):

A singly-linked representation would also do just fine here, though the doubly-linked representation may simplify implementation quite a bit at a most trivial cost given the coarseness of these nodes.

This will allow you to do the dependency injection at the data source level which can become useful for automating the synchronization/caching that occurs between these data sources in a very symmetrical fashion and making the process of caching no longer an external concern of the DAO, but instead an internal concern of the data storage type.

We can then link together the data sources like so:

The DAO can then be injected with an IDataSource-compliant node, preferably your fastest one (the memory cache) since it's typically going to be the first node we check for the availability of data prior to checking the bigger but more expensive nodes linked to it.

This allows quite a bit of flexibility with how you choose to cache data, since you can skip the caching by simply injecting the DAO directly with the SQL Server data source if caching is undesirable. It's also easy to do things like take the disk cache out of the picture by simply connecting the memory cache to the server and injecting the DAO with the memory cache.

Read Propagation

A cache strategy is initialized empty, so I have to fill in the data somehow.

If you apply this kind of memory hierarchy design, then the process of reading can fill these intermediary data storage caches implicitly/automatically in the process of the DAO simply requesting to perform operations from its injected data source.

We begin with the DAO requesting to read from its injected data source, the memory cache. The memory cache then checks in its load implementation if the data is available. If not, it recursively requests a read operation from the bigger, linked data source, the disk cache, and this repeats.

Here's the twist: if a smaller data source does not find the requested data and thus propagates a read request to a bigger data source, the returned data is then stored (cached) in the smaller, faster data source prior to returning it back to the caller. This logic is symmetrical across data sources and can be provided as part of an abstract base class. The pseudocode would be as follows:

DataSource::read(key):                 // implemented once in a base class
   data = load(key)                    // abstract
   if data != null:
       return data
   if bigger_node != null:
       data = bigger_node.read(key)
       store(key, data)                // abstract: cache data prior to returning
       return data
   return null

Eviction

These intermediary storage caches may end up reaching some state of being "full". If so, an eviction strategy is necessary. A simple and effective one is to simply evict LRU (least recently-used) data whenever a cache is full. In that case, we need some kind of time stamp to update when data is accessed in the intermediary cache storage (not for the SQL server, since it's modeling nonvolatile storage), like so:

Memory::load(key):                     // overridden by each data storage type
   if data[key] != null:
       update_timestamp(data[key])
   return data[key]

Memory::store(key, new_data):          // overridden by each data storage type
    if not key_exists(key) and full():
        evict_lru_data()               // evict(remove) least-recently used data
    data[key] = new_data
    update_timestamp(data[key])

Create, Update, Delete

For these kinds of mutating operations, an easy strategy is as you described: simply mirror the operations to all the data sources.

create(key, data):
    store(key, data)
    if bigger_node != null:
       bigger_node.create(key, data)

... and so forth. The update operation can be similar to read propagation by copying the data into all three storage types, with create, as implemented above, likewise filling all three data storage types.

A more complex strategy is to only perform these operations in the faster data storage types and then propagate modifications to the bigger ones later in a deferred fashion (ex: during eviction, at periodic intervals, on shutdown). However, that might screw with atomicity and make transaction-safety more difficult in addition to exacerbating synchronization issues with the latest data available on the server.

Going Beyond

There are potentially some more complex issues here like the fact that an intermediary cache may not necessarily be up-to-date with what's on the server if there are other DAO clients in the mix. There's also transaction-safety to consider and, of course, thread-safety. However, these concerns apply regardless of how you choose to design this as they're conceptually attached to the notion of intermediary caches between your database server.

In any case, I hope this kind of design might help a bit and potentially offer some solutions to these problems, or at least offer a new kind of perspective to this problem whether or not this kind of design is used.


问:
Approach to Web Services Exposure By Version
What's a good approach to exposing web services of different versions on the same URL? I don't want to have different URLs for different versions so I can change which version consumers are using from the server side. If version is in the URL, it's not optional and I can't provide a sensible default.

Offhand I can think of:

Putting a version parameter in the query string

Putting a version parameter in the post body

Are either of these good choices, or is there a different approach I should be taking?

Let me also add another question. How would a framework/program execute different versions if they reside in different JAR or EAR versions of the code?

答:
It's not an altogether uncommon practice to use headers for version specification on web services these days. Query string is also one I've seen used; both of these rely on the concept of a "sensible default" which is typically the latest version when the header or query string are not provided.

Another approach can be to have versions tied to consumers so if you require some authentication token on all requests, along with using it to identify who the consumer is, it can be used to identify what version of the API they have selected to use. This approach has good and bad sides to it as depending on how consumers use it, they may wish to use multiple versions at the same time (perhaps one call they want to use a later service version, while all the other calls they're still on an older one).

I would strongly discourage using a parameter in the post body because this would require you to make every single request a post, which is bad form for REST. If you're using SOAP however, then actually the SOAP headers would be the perfect place to put this as you can't rely on HTTP headers since SOAP can be transmitted via non-HTTPtransports (e-mail, TCP, MQ, etc).

tl;dr

If it's REST, use HTTP headers or query string; whichever's easier for you. For SOAP use the SOAP headers. If none of these are viable choices, I'd say you'll have to fall back on the classic of using different URLs for different versions.

ContentLicense: CC BY-SA 3.0


问:
How to determine when to open a new branch or a new repository when using Git?
Currently I am working on a project to make a product for company X. The team I am working with is selling similar service to many company with similar product, where 40% of the code is reused and 60% customized feature made to particular company. Previously there were no version control until I suggest using git recently. We are happy that we don't need to copy and paste each other's work repeatedly after introducing Git, but now we are a bit confused that should the new project be open as a new branch of previous product's repository (i.e. one repository for all products to different company) or as a new stand alone repository (i.e. one repository for different products)

Normally we are not merging the products of different companies, but sometimes when we find some good and commonly-wanted features, we would like to add those features to all the products of different company as a gift(once or twice per year). In this case, will it be better to open a new repository or just start a new branch?

答:
40% of the code is reused and 60% customized feature made to particular company

This might take a little time to actually get to the point that you can do this, but I think it should be a goal to extract that 40% out and make it its own repository. This is your main library/framework from which to work.

Then, that other 60% can be in dedicated repositories on a per-client basis.

It sounds like your code base qualifies as "legacy," so I highly recommend picking up Working Effectively With Legacy Code by Michael Feathers for yourself and your team. It provides techniques for bringing code under test, which can also be used for creating a plan to extract your code out into a library.

How would you go about doing this starting now? Here's what I'd do:

Make every client its own repository (or, if you're using something like Github or Gitlab to manage the git repositories, and you have several repositories for a client, you can create an organization per client, but we'll assume 1 repository per client).

Take a class that I reuse a lot and extract it out (assuming an object-oriented approach, though a functional one should have similar principles). We'll use this to start the library repository (this makes it useful from day 1). If you don't have full classes yet, then that's where Feathers' book comes in, as it shows you how to make classes out of non-classed code. While we're at it, we can add some basic testing to ensure it still does what we expect it to do.

Commit this extraction as its own thing, and you can use it as the template to replicate the change across all repositories.

As I come across shared parts, I extract them out and add them to this library repository.

As the library grows, and I find things that are used by some clients, but not others, I can work toward a modular approach, where larger features are extracted out into their own repositories and included as "modules" or "plugins" to the main system. Alternatively, if there are themes for particular groups of items (such as a bunch that deal with authentication or payment processing), I can extract those out to their own repositories. How you go, exactly, in this stage depends on the nature of your code and the direction you want to go with it.

The advantage of this system is that all you need to do is add that shared item into the library and wire up any hooks necessary to make it work, and it's available to all of the clients, no copy-pasta needed!

Why this instead of branches? While technologically, branches aren't much different from standalone repositories, convention differentiates between them. A repository is a complete project (with references of some sort, either via submodules or scripts, to dependencies), while a branch is generally a given state of the project. You branch when you want to add a feature, fix a bug, or make another kind of change, but the system itself is considered the same. You make a new repository when the project is considered a different one (in this case, for a different client, with its own customizations and whatnot).

A good example of this is Oracle OpenOffice vs LibreOffice. LibreOffice is a fork of OpenOffice, and is even maintained by the same people. However, LibreOffice, even when it was technologically identical to OpenOffice (when it was first forked), it was considered a different product. The team then stripped the Oracle branding from it and started LibreOffice's own development path, which is now distinct from OpenOffice. While the changes that have been made to LibreOffice could have gone into a branch in OpenOffice, since LibreOffice is considered a different project, it needed its own repository, instead.


问:
Do special-cases with fallbacks violate the Liskov Substitution Principle?
Let's say I have an interface FooInterface that has the following signature:

```<code>interface FooInterface {
    public function doSomething(SomethingInterface something);
}
</code>```

And a concrete class ConcreteFoo that implements that interface:

```<code>class ConcreteFoo implements FooInterface {

    public function doSomething(SomethingInterface something) {
    }

}
</code>```

I'd like to ConcreteFoo::doSomething() to do something unique if it's passed a special type of SomethingInterface object (let's say it's called SpecialSomething).

It's definitely a LSP violation if I strengthen the preconditions of the method or throw a new exception, but would it still be an LSP violation if I special-cased SpecialSomething objects while providing a fallback for generic SomethingInterface objects? Something like:

```<code>class ConcreteFoo implements FooInterface {

    public function doSomething(SomethingInterface something) {
        if (something instanceof SpecialSomething) {
            // Do SpecialSomething magic
        }
        else {
            // Do generic SomethingInterface magic
        }
    }

}
</code>```

答:
No, taking advantage of the fact that a given argument doesn't just provide the interface A, but also A2, does not violate the LSP.

Just make sure that the special path does not have any stronger pre-conditions (aside from those tested in deciding to take it), nor any weaker post-conditions.

C++ templates often do so to provide better performance, for example by requiring InputIterators, but giving additional guarantees if called with RandomAccessIterators.

If you have to decide at runtime instead (for example using dynamic casting), beware of the decision which path to take consuming all your potential gains or even more.

Taking advantage of the special case often goes against DRY (don't repeat yourself), as you might have to duplicate code, and against KISS (Keep it Simple), as it's more complex.


答:
There is a trade-off between the principle of "don't do type checks" and "segregate your interfaces".  If many classes provide a workable but possibly-inefficient means of performing some tasks, and a few of those can also offer a better means, and there is a need for code which can accept any of the broader category of items that can perform the task (perhaps inefficiently) but then perform the task as efficiently as possible, it will be necessary to either have all objects implement an interface that includes a member to say whether the more efficient method is supported and another to use it if it is, or else have the code which receives the object check whether it supports an extended interface and cast it if so.

Personally, I favor the former approach, though I wish object-oriented frameworks like .NET would allow interfaces to specify default methods (making larger interfaces less painful to work with).  If the common interface includes optional methods, then a single wrapper class can handle objects with many different combinations of abilities while promising for consumers only those abilities present in the original wrapped object.  If many functions are split into different interfaces, then a different wrapper object will be needed for every different combination of interfaces that wrapped objects might need to support.

Title: Do special-cases with fallbacks violate the Liskov Substitution Principle?

Body:
Let's say I have an interface FooInterface that has the following signature:

```<code>interface FooInterface {
    public function doSomething(SomethingInterface something);
}
</code>```

And a concrete class ConcreteFoo that implements that interface:

```<code>class ConcreteFoo implements FooInterface {

    public function doSomething(SomethingInterface something) {
    }

}
</code>```

I'd like to ConcreteFoo::doSomething() to do something unique if it's passed a special type of SomethingInterface object (let's say it's called SpecialSomething).

It's definitely a LSP violation if I strengthen the preconditions of the method or throw a new exception, but would it still be an LSP violation if I special-cased SpecialSomething objects while providing a fallback for generic SomethingInterface objects? Something like:

```<code>class ConcreteFoo implements FooInterface {

    public function doSomething(SomethingInterface something) {
        if (something instanceof SpecialSomething) {
            // Do SpecialSomething magic
        }
        else {
            // Do generic SomethingInterface magic
        }
    }

}
</code>```


问:
How confusing is `new SomeCollection(values...)::contains` as a Predicate?
Traditionally, a function that want to skip certain items during processing will accept a Collection or var-args argument, but in the Java 8 world I think I should switch to Predicates.

Now, since the code I am working on is mainly for testing, most of the exclusion will be ad-hoc "literals", so I am suggesting users use the form

```<code>Arrays.of(a, b, ...)::contains
</code>```

I am just wondering how acceptable this is?

(I see little value in wrapping the above form in an overload because it will be one more signature to learn and prevents the simple optimisation of extrating this "literal" to a variable.)

Edit:

Old function will be like

```<code>public void processUnlessNameIn(String... names)
</code>```

I want the new one to be

```<code>public void processUnlessName(Predicate<String> pred)
</code>```

答:
To directly answer your question: "somewhat confusing", since the code example you gave just doesn't sit right, for me anyway.

TBH, if your collection always contains strings, then I think adding predicates/lambdas is overkill in this situation. What does it really get you? If you have a collection of a richer object type, and want the user to be able to operate on that, then supplying a lambda instead of many overrides for every possible filtering choice would be sensible.

(Also, I'd rename processUnlessName(...) to processExcept(...), which seems clearer, but that's purely my opinion.)


问:
Is it the same to say "instantiate a class" and "instantiate an object"? "Instantiate a class" does not mean creating a new class?
I have seen the phrases "instantiate an object", "instantiate a Square object", or "a Cat object is instantiated." (p.17, p.22, and p.26 of The Object-Oriented Thought Process, 4th Edition, Addison-Wesley).

And then when reading Design Patterns (the Gof book), I keep on reading "instantiate a class", as in "it must instantiate a Glyph subclass" or "A class creational pattern uses inheritance to vary the class that's instantiated" (p.48 and p.81, Design Patterns, Erich Gamma et al, Addison-Wesley).

But then, in the same book, it says, "A dashed arrowhead line indicates a class that instantiates objects of another class" (p.15) to mean "CreationTool creates LineShape objects" (p.364).

Do they mean the same thing?  And if they do, which way of saying it is more correct or accurate?  Is it true that in normal circumstances, we don't use running code to "create" a new class?  (That is, "instantiate a class" doesn't mean create a new class).

I bring this up because while reading the Design Patterns book by GoF, I read "instantiate an object" and I thought, "ok, an object is created", then in the factory method chapter, I read "instantiate a class", and I thought "hmmm... a class is created?" and it kind of made me dizzy...

答:
Is it more accurate to say "instantiate a class" or "instantiate an
  object"?

Here's an answer by analogy:

If a tailor has a pattern for a shirt that is an Oxford style shirt, would you say, "he makes a pattern," or, "he makes a shirt," or "he makes an Oxford?" "He makes a pattern" seems a bit off, because he's not actually making a pattern from which he can then make other shirts. It would be most precise to say that "He makes an Oxford," especially if, by the context, you understand that he's making a shirt.

Similarly, it's a bit off to say, "instantiate a class." It is an object that is instantiated. You are instantiating an object from the class as it is defined. It will then be an object of that type, say an Oxford, to continue with the analogy. However, from context, we do understand what is meant, and internally expand, "instantiate a class," to, "instantiate an object of class Oxford." The intent is clear from the context.

It's accurate to say "instantiate an object" because that's what is instantiated, an object. But you may as well say "instantiate a thing", it would be just as descriptive, it's just that "thing" has little to no usage in the context of programming, so this is a bit imprecise. So this is more accurate than saying "instantiate a class".

It's both accurate and precise to say "instantiate an Oxford" which would be a specific type of object. It's also more descriptive and informative - assuming you know that an Oxford is an object (in this case, a shirt).

If the intent is clarity of communication, I would aim to be both accurate and precise.


答: Both are correct and both mean the exact same thing. Objects are instances of classes. Whether you "instantiate class X [to create an object of class X]" or "instantiate an object [of class X]" is just semantic nitpicking. </p>

Title: Is it the same to say "instantiate a class" and "instantiate an object"? "Instantiate a class" does not mean creating a new class?

Body:
I have seen the phrases "instantiate an object", "instantiate a Square object", or "a Cat object is instantiated." (p.17, p.22, and p.26 of The Object-Oriented Thought Process, 4th Edition, Addison-Wesley).

And then when reading Design Patterns (the Gof book), I keep on reading "instantiate a class", as in "it must instantiate a Glyph subclass" or "A class creational pattern uses inheritance to vary the class that's instantiated" (p.48 and p.81, Design Patterns, Erich Gamma et al, Addison-Wesley).

But then, in the same book, it says, "A dashed arrowhead line indicates a class that instantiates objects of another class" (p.15) to mean "CreationTool creates LineShape objects" (p.364).

Do they mean the same thing?  And if they do, which way of saying it is more correct or accurate?  Is it true that in normal circumstances, we don't use running code to "create" a new class?  (That is, "instantiate a class" doesn't mean create a new class).

I bring this up because while reading the Design Patterns book by GoF, I read "instantiate an object" and I thought, "ok, an object is created", then in the factory method chapter, I read "instantiate a class", and I thought "hmmm... a class is created?" and it kind of made me dizzy...


答:
To instantiate something means to provide a real instance of an abstract concept. The class is the abstract concept. An object is an instance of a class. When you create a new object, you're instantiating the class.

If you see "instantiate a Square object", that's usually shorthand for "create a new object by instantiating the Square class". It's not 100% correct but it conveys the same meaning.

"Instantiate" and "create" don't have the same meaning, so "creating a class" has a different meaning to "instantiating a class".


答:
There are two separate issues in your question:

Start the new product in the same repository or open a new one for it?

This is a matter of taste. Some keep all products in a single, giant repo, some open a new repo for each separate unit (even if it contains only a single file). Some find a healthy balance between the two extremes.

For now I'd say put your common libraries in one repo and each, unrelated end-product in its own repo.

Open a new branch or open a new repo?

This never should be the question. You may decide to put the new product in the same repo. In that case, you do open a new (feature) branch, start developing the product there and, when it's stable, you merge it back to the main branch and delete the feature-branch.

Most of the time you can think of git branches as long commits. Eventually they will be merged back to the main branch and you delete them.

On the other hand there are persistent, maintenance branches. But you won't do any feature development on them.

So my answer is: you may decide to add the new product to the same repo (with new product also living on the main branch) or create a new repo for it. But don't abuse the branching mechanism to develop a separate product in the same repo.

I recommend you to check out Atlassian's Git Tutorials

Title: How to determine when to open a new branch or a new repository when using Git?

Body:
Currently I am working on a project to make a product for company X. The team I am working with is selling similar service to many company with similar product, where 40% of the code is reused and 60% customized feature made to particular company. Previously there were no version control until I suggest using git recently. We are happy that we don't need to copy and paste each other's work repeatedly after introducing Git, but now we are a bit confused that should the new project be open as a new branch of previous product's repository (i.e. one repository for all products to different company) or as a new stand alone repository (i.e. one repository for different products)

Normally we are not merging the products of different companies, but sometimes when we find some good and commonly-wanted features, we would like to add those features to all the products of different company as a gift(once or twice per year). In this case, will it be better to open a new repository or just start a new branch?


答:
Is it more accurate to say "instantiate a class" or "instantiate an object"?

Webster defines instantiate:

to represent (an abstraction) by a concrete instance

From this definition, we could use either "instantiate a class" or "instantiate an object." We could also simply say, "instantiate" since "class," (the abstraction) and, "object," (the concrete instance) are both now made redundant by the definition of instantiate.

If we wanted to be more precise, we could specify the object we're instantiating, for example: "instantiate a Foo."

Background information:

This chart demonstrates that the word "instantiate" did not come into common use until starting in the 1950s, and peaking very recently. Source.

Further, this ngram demonstrates that "instantiate an object" is much more common than "instantiate a class".


问:
Web interface with FastCGI or with direct HTTP?
Let's assume I want (for fun at start) to play with some new DSL (domain specific language) idea. And I really want its user[s] (probably only me at first) to interact thru a web interface. I'll probably implement it in C++ (probably using LLVM).

Should I use an HTTP server library (like libonion or microhttpd) to talk directly HTTP or should I use FastCGI? I could also use libraries doing both like cppcms or wt...

In particular, I am noticing that several recent web frameworks (Opa, Ocsigen, ...) do not have any FastCGI interface but only HTTP one....
(but Ur/Web seems to have both)

So my feeling is that FastCGI is really out of fashion....

Any opinions on that? Do you know recently started project using FastCGI ?
(and what about SCGI?)

答:
I've considered many implementations, with different types of connection methods, and this is how I view the choice.

From a developer perspective FastCGI IS out of style, in the same way they would consider C.  from a developer perspective accomplishing the task can be done through simpler ways.

From an implementation perspective, HTTP isn't a perfect replacement, however there is enough overlap so that they could be used to solve the same goals. BUT really this question is about implementation and architecture, and not a developer focused question, so I'll answer it from systems engineering side.

Despite what I've unfortunately read in developer blogs, FastCGI CAN be a better choice when utilized in the proper circumstances.  It separates a large complicated concern, that otherwise must be implemented higher up the stack.

For example, It allows you to avoid creating a robust web server inside your framework/language.  A huge task if you actually care about quality, but very doable if you slap it together like most.   So it's ironically easier to roll it all up in a spaghetti ball, then cleanly separate that part. This is why so many avoid FastCGI, because they could only implement it by almost wrapping HTTP anyway, due to their bad architectural choices.

Since you didn’t get more detailed about how ambitious your plan, I can't really give you great recommendations. Let me suggest a few things to investigate, that are not the common slap together python node style.

Read about the implementation details of ,
php-fpm

If you want to do a more appserver model, do it right, read about
uwsgi


问:
How can we be certain that the lower components of computer programming like compilers, assemblers, machine instructions, etc. are flawless?
Since we are becoming more and more reliant on computing, including very critical tasks of day-to-day life, I was just wondering how those vital components are tested.

More technically, how are the compilers and assemblers tested? (I suppose this relates to the halting problem!!)

答:
This is a "dangerous" question for new developers in that they'll start blaming their tools instead of their code (been there, done that, seen too many do it). Although there are bugs in compilers, runtime environments, OS, etc., developers should be realistic and remember that, until there is evidence and unit tests demonstrating otherwise, the bug is in your code.

In 25+ years of programming in mostly C, C++, and Java I have found:

two bugs due to a compiler bug (gcc and SunOS C)

about once every year or two a bug due to a Java JVM problem (usually related to memory consumption/garbage collection)

about once every month or two a bug in a library, which frequently is fixed by using the latest version or reverting to the prior version of the library

All of the other bugs are directly related to a bug or, more frequently, a lack of understanding of how a library works. Sometimes what seems to be a bug is due to an incompatibility, for instance how the Java class structure changed that broke some AOP libraries.


问:
Efficient algorithm to merge n successive sorted arrays in place
I am developing an in-place sorting algorithm that leaves the array into a state where it is basically a succession of sorted subsequences of any size (most are bigger than log2(size(array))); then it merges the said subsequences in place. Once the described state has been reached, the algorithm in its current form simply merges the first two subsequences, then merges the result with the following subsequence, etc... Note that at the time of merging, we know where the sorted subsequences begin, we don't have to find them again.

While it works fine, I guess that this merging scheme is suboptimal and I believe that it should be possible to use a smarter merging scheme. The best algorithm I could think of would be an algorithm that looks for the smallest successive sorted subsequences and merges them, then repeats until everything has been merged. The idea is that merging smaller sequences first is cheaper, so we should merge the biggest ones only in the end.

Is there a more efficient algorithm to merge n successive subsequences in place?

As requested, let's imagine that we want to sort the following array:

```<code>10 11 12 13 14 9 8 7 6 5 0 1 2 3 4
</code>```

My algorithm will do things that are totally irrelevant for the question, but leave the array in the following state:

```<code>10 11 12 13 14 0 5 6 7 8 9 1 2 3 4
^              ^           ^
</code>```

The carets show where big enough sorted subsequences in the array begin; in the actual code, they correspond to iterators, or indices depending on the abstraction you use. The next step is to merge these subsequences together to sort the array (note that all of them are bigger than log2(size(array)) if that matters, but they might have different sizes). To merge the different parts of this array, the smartest move is apparently to merge the last subsequence with the middle one in place, leaving the array in the following state:

```<code>10 11 12 13 14 0 1 2 3 4 5 6 7 8 9
^              ^
</code>```

...then two merge the two remaining subsequences in place so that the array is actually sorted. As I said, there can be up to log2(size(array)) such subsequences before the in-place merge step.

My current solution for the merging step involves a bit of indirection: iterators pointed by carets are stored in a list, then I create a min heap where every element is one of the list iterators and the comparison function associates to every iterator the distance between its neighbours. When two subsequences are merged, I pop a value from the heap and remove the corresponding iterators from the list. Here is basically what my C++ algorithm does:

```<code>template<typename Iterator, typename Compare=std::less<>>
auto sort(Iterator first, Iterator last, Compare compare={})
    -> void
{
    // Code irrelevant to the question here
    // ...
    //

    // Multi-way merge starts here

    std::list<Iterator> separators = { first, /* beginning of ordered subsequences */, last };
    std::vector<typename std::list<Iterator>::iterator> heap;
    for (auto it = std::next(separators.begin()) ; it != std::prev(separators.end()) ; ++it)
    {
        heap.push_back(it);
    }
    auto cmp = [&](auto a, auto b) { return std::distance(*std::prev(a), *std::next(a)) < std::distance(*std::prev(b), *std::next(b)); };
    std::make_heap(heap.begin(), heap.end(), cmp);

    while (not heap.empty())
    {
        std::pop_heap(heap.begin(), heap.end(), cmp);
        typename std::list<Iterator>::iterator it = heap.back();
        std::inplace_merge(*std::prev(it), *it, *std::next(it), compare);
        separators.erase(it);
        heap.pop_back();
    }
}
</code>```

I wrote the algorithm in C++ because I find it easier to reason about iterators, but a general algorithmic answer is welcome.

答: I would just do an in place quick sort and write a generic wrapper for your arrays so they can be viewed as one big array.  </p>


问:
Mobile app architecture to improve speed and reduce data transfer

Business Context of the Problem

Our iphone app allows users to pay merchants and earn rewards.

Users can also do things like:

View transaction history

View their points and available rewards, or claim rewards.

Earn money by referring friends, view a history of converted and unconverted referrals.

View running deals at some merchants (happy hour specials, etc)

View information about merchants (location, hours, etc)

Since things like available deals or rewards, transaction history, and referrals can change at any time, we have a classic cache invalidation problem on the user's device.

Current, Unsatisfactory Solution

Our current architecture is fairly standard, and consists of API endoints like "/merchants", "/rewards", "/transactions", "/deals", and so on.

We currently solve the stale cache problem by:

Polling the server frequently while the app is open (as often as every minute for some API calls), as well as whenever the app regains focus.

Indicating possibly stale data with text like Last updated 3 mins ago

We use etags to avoid resending unchanged data whole hog (eg, the entire merchant list), but there is still a lot of wasted bandwidth with our current approach.  For example, if a single merchant changes, all merchants are resent.  If a single new transaction is added, all transactions are resent.

In practice, from the user's perspective, this usually isn't a big deal, as we're talking about sizes of 1-200K at the very most, and typically less.  However, it can be a problem in areas with poor cell reception, a situation that comes up often enough that we hear complaints.

And on the server side, all this polling creates a lot of unnecessary load, especially because processing and database queries occur even when etags are unchanged,

Better Solutions?

We are re-architecting the app and the server code, and thinking about alternative strategies.  Since this is a fairly common problem, I'd like to know how others are solving it.

Some ideas I have so far:

For minimizing data transfer: Keep track, on the server, of the data each user actually has.  Send JSON patches of only changed data, rather than fresh copies of all the data.  Copies of each user's data could be stored in redis, and expire after a few days or a week.  This would keep "active session" fast, while user's without a stored server cache could just be sent a fresh copy of all their data when logging in after a dormant period (same as now).  While in theory this could work, keeping server and client copies in sync, by patching both, seems like a rich source of potential bugs, even if I'm using vetted JSON patch libraries.

For minimizing server load: Establish web socket connections with each client, instead of polling.  Let events that change the client's state (eg, a purchase, a referral converting, a deal ending, etc) push down websocket messages, which in turn trigger the client to refresh.  This could be used in conjunction with idea 1, or with the current method of sending fresh copies of all changed data.  Even with the current method, this would still be a huge improvement, since data would only be requested and sent when it needed to be.

Right now, I am leaning toward 2 without 1, as 1 seems too potentially fraught with problems.  I have some concerns about relying on websockets on mobile, but after doing research here, on SO, and other places, it seems that this concern isn't valid.

I would love to hear other, perhaps radically different, suggestions for solving these problems.

答:
Since it's a native app you can sidestep HTTP entirely if you want to.

You could use HTTP/2.0 which allows streams.  Streams are a partial solution to head of line (HOL) blocking allowing multiple requests to share a single TCP connection and be delivered incrementally and concurretly.  It also allows for some server-initiated communication.  It's still TCP so it isn't a complete solution to HOL blocking.

You could use WebRTC which uses DTLS to avoid HOL blocking entirely and enables server or peer to peer events efficiently.

I'm inclined to avoid HTTP for this kind of use case because it places artificial and unsympathetic constraints on your application data request flows.  It's a necessity in the browser, but not in an app.  HTTP does have the advantage of providing a single service interface for all broswer based, desktop, and mobile app clients though so take this with a grain of salt.

You could use AMQP over TLS (with something like RabbitMQ) on port 443 and do event-based communications via its message queues.  Backend services would push updates into the queues or an intermediary updater service would call the REST services and update them.  This would still suffer from HOL blocking at the TCP level.

Another option is ZeroMQ with CurveZMQ.  It's also a message-oriented solution, but one in which you don't need a separate central broker like AMQP.   Your app could talk directly to your server via messaging.  Your server could do the REST polling and state management and push updates to the client as frequently or infrequently as you want.  This allows for graceful degradation in failure situations. This is the most flexible and arguably the leanest option, but is also over TCP so doesn't fully avoid HOL blocking.

For what it's worth HOL blocking is unlikely anywhere near your immediate problem and solving it requires significant compromises.


问:
How wrong is it to talk about C++ "methods" (versus "member functions")?
I understand that according to the C++ spec there is no such thing as a "method", and some (many? most?) C++ programmers consider "method" to be a Java-ism.  On the other hand, even on a C++ forum people seem to talk about methods without twitching.  I am looking for known conventions or common practices regarding this terminology.

I am documenting an API that has both C++ and Java versions.  The developers actually kept the class and method/member-function names the same between the two, presumably for expedience in porting and testing.  Because of this, some of what needs to be documented about these APIs sits "above" the choice of language; I need to be able to talk in general about Foos and Bars, with their baz() and mumble()...methods?

If I talk about methods Java programmers will consider it natural and, it appears, C++ programmers will probably understand but some will consider it to be incorrect.  My question is: how heinous is this in practice?  How are C++ member functions conventionally talked about in "general OOP" contexts, as opposed to C++-specific ones?  Is there a better way to talk about member functions in a way that's not incorrect for either language?  ("Member functions" is a little verbose.)

This isn't an opinion survey; I'm trying to determine if there are actual conventions or common practices to address this problem.

I am aware of this question, but it's about OOP in general and doesn't ask about specific languages.

答:
Well, you're not going to get executed for it.

The complaint in the C++ world is not one of pedantic correctness: it's one of ambiguity. There are so many different kinds of "methods" out there in the wilderness depending on what domain you're talking about, that a bunch of us prefer to stick to standard terminology to avoid misunderstandings later. That means, roughly, "static/[non-static] [pure] virtual/[non-virtual] member/[free] function".

If you write "method" in your documentation instead, some C++ programmers may complain that it's not really clear what you're talking about, or worry that if you're not familiar with this C++ convention, what others are you missing?

But I'm sure there are millions of professional C++ programmers who themselves have no idea that this is even a thing. It's a big ol' world.

You're not going to get executed for it.


问:
Does it make sense to use the term "Space Leak" with regard to Java?
I stumbled across some posts on the main stackoverflow community about whether you can have a 'memory leak' in Java and it (maybe unsurprisingly) creates a lot of contentious debate.  At some point I had decided that Java applications don't have memory leaks (or have them all the time depending on how you look at it) but rather have 'space leaks'.

I can't recall where I got this term from did a quick search to make sure I hadn't dreamed it up or something and it seems to be used with regard to Haskell and lazy evaluation.  Here, I found a concise definition that appears to be authoritative.

A space leak occurs when a computer program uses more memory than
  necessary. In contrast to memory leaks, where the leaked memory is
  never released, the memory consumed by a space leak is released, but
  later than expected.

The concept of a 'memory leak' as I was taught back in the previous century was caused by losing track of memory without deallocating it.  It's something you can detect without understanding the program which is why it's the exact condition that a GC uses to know what is garbage.  What people refer to as 'memory leaks' in Java seem to me to be more closely aligned with the term 'space leak' because the application is still referencing the offending memory when it really doesn't need to.

I feel like this distinction would help bring some clarity to discussions about managed memory languages but I'm not sure if it's too much of a stretch?  Maybe it's too late but I think it would be best to keep the term 'memory leak' specific and not overload it to also apply to something that produces similar results but has different causes.

To clarify, I am not suggesting that leaks don't happen in a managed application.  I'm simply pondering about how we talk about them.  There are some highly upvoted discussions about memory leaks and Java that contain flame wars with 'fanboy' slurs and such that center around this exact question.  Actually given that even my question is misunderstood tells me that this is an issue of terminology.

答:
No.

Pretty much all modern programs use more space than is necessary. If your Java program is keeping objects alive when the programmer thinks it should be eligible for collection, it is a memory leak. It is a common, well known term. Yes, it will vary a bit by context, but the underlying concept is close enough that the mental jump is very short.

Pedantry provides no benefit here.


答: Eiffel calls them Routines or Features, C++ calls them Member Functions, and (almost) every single other OO language ever created in the entire history of computing, both before and after C++ calls them Methods, so that latter term should generally be understood even by C++ (and Eiffel) programmers, unless they really have never heard of Simula, Smalltalk, Self, Objective-C, Newspeak, Java, C#, VB.NET, PHP, Python, Ruby, ECMAScript/JavaScript, Scala, CoffeeScript, …

Title: How wrong is it to talk about C++ "methods" (versus "member functions")?

Body:
I understand that according to the C++ spec there is no such thing as a "method", and some (many? most?) C++ programmers consider "method" to be a Java-ism.  On the other hand, even on a C++ forum people seem to talk about methods without twitching.  I am looking for known conventions or common practices regarding this terminology.

I am documenting an API that has both C++ and Java versions.  The developers actually kept the class and method/member-function names the same between the two, presumably for expedience in porting and testing.  Because of this, some of what needs to be documented about these APIs sits "above" the choice of language; I need to be able to talk in general about Foos and Bars, with their baz() and mumble()...methods?

If I talk about methods Java programmers will consider it natural and, it appears, C++ programmers will probably understand but some will consider it to be incorrect.  My question is: how heinous is this in practice?  How are C++ member functions conventionally talked about in "general OOP" contexts, as opposed to C++-specific ones?  Is there a better way to talk about member functions in a way that's not incorrect for either language?  ("Member functions" is a little verbose.)

This isn't an opinion survey; I'm trying to determine if there are actual conventions or common practices to address this problem.

I am aware of this question, but it's about OOP in general and doesn't ask about specific languages.


答:
The main difference is in terms of time.  A space leak as described in your linked article occurs before the user is finished with the result, while a memory leak occurs after.  As soon as the user is done with the result in a space leak situation, it is garbage collected, it just temporarily used more memory than necessary.

A memory leak never lets go of the memory, it just continues to grow until eventually the program crashes, even after the user is done with the given results.  This sort of problem is indeed possible in garbage collected languages.  Technically, you're still referencing the memory somewhere, but not intentionally in a user-visible way.

Title: Does it make sense to use the term "Space Leak" with regard to Java?

Body:
I stumbled across some posts on the main stackoverflow community about whether you can have a 'memory leak' in Java and it (maybe unsurprisingly) creates a lot of contentious debate.  At some point I had decided that Java applications don't have memory leaks (or have them all the time depending on how you look at it) but rather have 'space leaks'.

I can't recall where I got this term from did a quick search to make sure I hadn't dreamed it up or something and it seems to be used with regard to Haskell and lazy evaluation.  Here, I found a concise definition that appears to be authoritative.

A space leak occurs when a computer program uses more memory than
  necessary. In contrast to memory leaks, where the leaked memory is
  never released, the memory consumed by a space leak is released, but
  later than expected.

The concept of a 'memory leak' as I was taught back in the previous century was caused by losing track of memory without deallocating it.  It's something you can detect without understanding the program which is why it's the exact condition that a GC uses to know what is garbage.  What people refer to as 'memory leaks' in Java seem to me to be more closely aligned with the term 'space leak' because the application is still referencing the offending memory when it really doesn't need to.

I feel like this distinction would help bring some clarity to discussions about managed memory languages but I'm not sure if it's too much of a stretch?  Maybe it's too late but I think it would be best to keep the term 'memory leak' specific and not overload it to also apply to something that produces similar results but has different causes.

To clarify, I am not suggesting that leaks don't happen in a managed application.  I'm simply pondering about how we talk about them.  There are some highly upvoted discussions about memory leaks and Java that contain flame wars with 'fanboy' slurs and such that center around this exact question.  Actually given that even my question is misunderstood tells me that this is an issue of terminology.


问:
audio file processing in C++
I thought of the following project that I want to pursue:

I want to create a C++ program, that can play audiofiles and visualize the amplitudes of individual frequency bands in real time (e.g. with bars).

I did some search on google, and I found that SDL provides libraries that might do the trick. First I read about the format in which an audio file is saved (more specific uncompressed .wav files, as they seem to be the easiest to read). However, even though I now know how I can get the data of the file, I don't know what it tells me. I mean, how many bytes do I have to read to get one sample, how is the sample saved (I think it's not a direct representation of the frequency space), and so I really have no idea how to work with it. As a direct consequence, I neither know how to play the files.
Then I found SDL, and figured it should be able to extract the information that I need. Looking through the SDL wiki I was not able to find out how I have to proceed, though.

I have done some basic C++ programming in the past, I think I'm on a high enough level to do this on the programming side. I have, however, now worked with binary files so far. Also I have a strong maths background, the maths involved are no problem at all.

The ultimate goal would probably be to do the frequency analysis of all audio output or input, but I read that this depends heavily on the operating system used. Also, applying filters in real time would be a nice thing to do, but this should be rather advanced. Hence just playing an audio file and visualizing would be the first goal.

So to sum up, I think my question is the following:

What does the data in an audio file tell me? How can I get it to a state such that I can do a frequency analysis? How can this be done in real time, while playing the audio file? Is SDL a good choice for this, or is there a better way without taking away all the work (I wouldn't like to just use a program that does everything as I need it, I want to do something of my own!)?

Any ideas and inputs are much appreciated!

PS: I'm not sure I'm on the right stackexchange here, but I really couldn't find out where else this would fit.

答:
Here's a good library for opening and reading a sound file. It supports most open codecs, and it is not nearly as complex as ffmpeg. However it does not support any closed codecs like mp3. It is written in pure C.

http://www.mega-nerd.com/libsndfile/

For analyzing the audio you could use fftw3 to do a dft to analyze the audio.

Most of the audio libraries, I have found are almost pure C.

Beyond that you can use whatever you want for handling the gui.

Title: audio file processing in C++


问:
Object oriented vs vector based programming
I am torn between object oriented and vector based design. I love the abilities, structure and safety that objects give to the whole architecture. But at the same time, speed is very important to me, and having simple float variables in an array really helps in vector based languages/ libraries like Matlab or numpy in Python.

Here is a piece of code I wrote to illustrate my point

Problem: Adding Tow volatility numbers. If x and y are two volatility numbers, the sum of the volatility is (x^2 + y^2)^0.5 (assuming certain mathematical condition but that's not important here).

I want to perform this operation very fast, and at the same time I need to ensure that people don't just add the volatility in the wrong way (x+y). Both of these are important.

The OO based design would be something like this:

```<code>from datetime import datetime
from pandas import *

class Volatility:
    def __init__(self,value):
       self.value = value

    def __str__(self):
       return "Volatility: "+ str(self.value)

    def __add__(self,other):
        return Volatility(pow(self.value*self.value + other.value*other.value, 0.5))
</code>```

(Aside: For those who are new to Python, __add__ is just a function that overrides the + operator)

Let's say I add tow lists of volatility values

```<code>n = 1000000
vs1 = Series(map(lambda x: Volatility(2*x-1.0), range(0,n)))
vs2 = Series(map(lambda x: Volatility(2*x+1.0), range(0,n)))
</code>```

(Aside: Again, a Series in Python is sort of a list with an index)
Now I want to add the two:

```<code>t1 = datetime.now()
vs3 = vs1 + vs2
t2 = datetime.now()
print t2-t1
</code>```

Just the addition runs in 3.8 seconds on my machine, the results I have given doesn't include the object initializaion time at all, its only the addition code that has been timed. If I run the same thing using numpy arrays:

```<code>nv1 = Series(map(lambda x: 2.0*x-1.0, range(0,n)))
nv2 = Series(map(lambda x: 2.0*x+1.0, range(0,n)))

t3 = datetime.now()
nv3 = numpy.sqrt((nv1*nv1+nv2*nv2))
t4 = datetime.now()
print t4-t3
</code>```

It runs in 0.03 seconds. That's more than 100 times faster!

As you can see, the OOP way gives me a lot of security that people won't be adding Volatility the wrong way, but the vector method is just so crazy fast! Is there a design in which I can get both? I am sure a lot of you have run into similar design choices, how did you work it out?

The choice of language here is immaterial. I know a lot of you would advise that use C++ or Java, and the code may run faster than vector based languages anyway. But that's not the point. I need to use Python, because I have a host of libraries not available in other languages. That's my constraint. I need to optimize within it.

And I know, that a lot of people would suggest parallelization, gpgpu etc. But I want to maximize single core performance first, and then I can parallelize both the versions of code.

Thanks in advance!

答:
As you can see, the OOP way gives me a lot of security that people
  won't be adding Volatility the wrong way, but the vector method is
  just so crazy fast! Is there a design in which I can get both? I am
  sure a lot of you have run into similar design choices, how did you
  work it out?

Design bigger objects. A Pixel object has no breathing room for a parallelized loop or GPU image transformations or anything like that. An Image does provided it doesn't have to go through the barrier of a teeny Pixel object to get at the data.


问:
Why do we have the "running" state in behavior trees?
I'm following the paper: Towards a Unified Behavior Trees Framework for Robot Control and attempting to implement my own behavior tree.  I believe that I have the correct logic working for the main nodes: Sequence, Selector, Condition, and Action, but I'm only allowing nodes to return Success or Failure for now.  Additionally, I'm not sure I understand why you need a Running state.

My distillation of the two main branch nodes, Selector and Sequence, is as such:

Sequence

Iterate all children

Stop if child fails or is running

Return failure or running if depending on child

Return success if all children succeeded

Selector

Iterate all children

Stop if child succeeds or is running

Return success or running depending on child

Return false if no children were successful or running

To me, Running is just synonymous to Success or Failure depending on if it is used in a Selector or Sequence respectively.  When does Running actually matter?

答:
Here is an example tree:

```<code>Selector
    Sequence
         Roll Forward 1 foot
         Beep
    Panic
</code>```

The idea here is that the robot should roll forward and then beep. If something goes wrong, it should panic.

While the robot is rolling forward, what does the roll forward node return?

The correct way is to have it return RUNNING, because its still rolling forward. Then three looks like:

```<code>Selector [RUNNING]
    Sequence [RUNNING]
         Roll Forward 1 foot [RUNNING]
         Beep
    Panic
</code>```

In this state, everything is running, and the Beep and Panic don't happen.

Alternatively, could we use SUCCESS instead of RUNNING? In that case, the tree would be:

```<code>Selector [SUCCESS]
    Sequence [SUCCESS]
         Roll Forward 1 foot [SUCCESS]
         Beep [SUCCESS]
    Panic
</code>```

But this is bad, because it isn't supposed to beep until after rolling forward.

Perhaps we should have used FAILURE?

```<code>Selector [SUCCESS]
    Sequence [FAILURE]
         Roll Forward 1 foot [FAILURE]
         Beep
    Panic [SUCCESS]
</code>```

But this is bad again, because we panicked, when we should have waited to see if rolling forward worked.

Thus, we need RUNNING in order to indicate when a task is not yet finished.

Body:
Here is an example tree:

Selector
    Sequence
         Roll Forward 1 foot
         Beep
    Panic

The idea here is that the robot should roll forward and then beep. If something goes wrong, it should panic.

While the robot is rolling forward, what does the roll forward node return?

The correct way is to have it return RUNNING, because its still rolling forward. Then three looks like:

Selector [RUNNING]
    Sequence [RUNNING]
         Roll Forward 1 foot [RUNNING]
         Beep
    Panic

In this state, everything is running, and the Beep and Panic don't happen.

Alternatively, could we use SUCCESS instead of RUNNING? In that case, the tree would be:

Selector [SUCCESS]
    Sequence [SUCCESS]
         Roll Forward 1 foot [SUCCESS]
         Beep [SUCCESS]
    Panic

But this is bad, because it isn't supposed to beep until after rolling forward.

Perhaps we should have used FAILURE?

Selector [SUCCESS]
    Sequence [FAILURE]
         Roll Forward 1 foot [FAILURE]
         Beep
    Panic [SUCCESS]

But this is bad again, because we panicked, when we should have waited to see if rolling forward worked.

Thus, we need RUNNING in order to indicate when a task is not yet finished.


答:
If you repeatedly merge the 2 first sequences you will get a runtime that is much worse than merge sort as you compare the first elements far too many times (n log(n)^2???) if you merge the 2 (or more) smallest (adjacent) sequences each time you should approach merge sorts efficiency.

Finding the smallest adjacent sequences might be done by building a tree with roughly half the sequence in each branch recursively and then merging the lowest branches first.

---- Edit

First version:

Essential a mergesort where the separators are the implicit partition of the mergesort algorithm.

```<code>Order separators according to their index in the array

MergeIt(first, last) {
    if (only one or zero separator)
       return first;

    split = separator containing the middle separator (first, last)

    return inplace_merge(MergeIt(first, split), MergeIt(split, end));
}
</code>```

This ensures that you only do the minimum number of merges, but not the minimum number of compares as larger sequences might be merge with the current minimum sequence.

Version two:

Still basically a mergesort where we now take into consideration the length of the sequences.

```<code>Order separators according to their index in the array

MergeIt(first, last) {
    if (only one or zero separator)
       return first;

    split = separator containing the middle element of array(first, last) // not the middle separator

    return inplace_merge(MergeIt(first, split), MergeIt(split, end));
}
</code>```

The split insures that the smaller sequences merge first as the larger stop higher up in the call tree. This still does not insure the least number of compares as there still is the chance that larger sequences are merge with the current minimum length, though this is still better than version one as the large sequences here are smaller.

Version three:

Merge the adjacent sequences which span the least number of elements

```<code>Make heap of pairs of adjacent sequences, sort after minimum length of the pairs, for each sequence only add the shortest of its prev and next.
// each sequence will appear max twice except the first and last.

while (heap.size() > 1) {
    min = heap.pop

    remove the possible other occurrence of min.first and min.second

    sequence = inplace_merge(min.first, min.second)

    insert the minimum of pair(prev(sequence), sequence) and pair(sequence, next(sequence)) in heap.
}
</code>```

The overhead might make this slower than the second version but the compares in made by inplace_merge should now be the minimum.

Title: Efficient algorithm to merge n successive sorted arrays in place

Body:
I am developing an in-place sorting algorithm that leaves the array into a state where it is basically a succession of sorted subsequences of any size (most are bigger than log2(size(array))); then it merges the said subsequences in place. Once the described state has been reached, the algorithm in its current form simply merges the first two subsequences, then merges the result with the following subsequence, etc... Note that at the time of merging, we know where the sorted subsequences begin, we don't have to find them again.

While it works fine, I guess that this merging scheme is suboptimal and I believe that it should be possible to use a smarter merging scheme. The best algorithm I could think of would be an algorithm that looks for the smallest successive sorted subsequences and merges them, then repeats until everything has been merged. The idea is that merging smaller sequences first is cheaper, so we should merge the biggest ones only in the end.

Is there a more efficient algorithm to merge n successive subsequences in place?

As requested, let's imagine that we want to sort the following array:

```<code>10 11 12 13 14 9 8 7 6 5 0 1 2 3 4
</code>```

My algorithm will do things that are totally irrelevant for the question, but leave the array in the following state:

```<code>10 11 12 13 14 0 5 6 7 8 9 1 2 3 4
^              ^           ^
</code>```

The carets show where big enough sorted subsequences in the array begin; in the actual code, they correspond to iterators, or indices depending on the abstraction you use. The next step is to merge these subsequences together to sort the array (note that all of them are bigger than log2(size(array)) if that matters, but they might have different sizes). To merge the different parts of this array, the smartest move is apparently to merge the last subsequence with the middle one in place, leaving the array in the following state:

```<code>10 11 12 13 14 0 1 2 3 4 5 6 7 8 9
^              ^
</code>```

...then two merge the two remaining subsequences in place so that the array is actually sorted. As I said, there can be up to log2(size(array)) such subsequences before the in-place merge step.

My current solution for the merging step involves a bit of indirection: iterators pointed by carets are stored in a list, then I create a min heap where every element is one of the list iterators and the comparison function associates to every iterator the distance between its neighbours. When two subsequences are merged, I pop a value from the heap and remove the corresponding iterators from the list. Here is basically what my C++ algorithm does:

```<code>template<typename Iterator, typename Compare=std::less<>>
auto sort(Iterator first, Iterator last, Compare compare={})
    -> void
{
    // Code irrelevant to the question here
    // ...
    //

    // Multi-way merge starts here

    std::list<Iterator> separators = { first, /* beginning of ordered subsequences */, last };
    std::vector<typename std::list<Iterator>::iterator> heap;
    for (auto it = std::next(separators.begin()) ; it != std::prev(separators.end()) ; ++it)
    {
        heap.push_back(it);
    }
    auto cmp = [&](auto a, auto b) { return std::distance(*std::prev(a), *std::next(a)) < std::distance(*std::prev(b), *std::next(b)); };
    std::make_heap(heap.begin(), heap.end(), cmp);

    while (not heap.empty())
    {
        std::pop_heap(heap.begin(), heap.end(), cmp);
        typename std::list<Iterator>::iterator it = heap.back();
        std::inplace_merge(*std::prev(it), *it, *std::next(it), compare);
        separators.erase(it);
        heap.pop_back();
    }
}
</code>```

I wrote the algorithm in C++ because I find it easier to reason about iterators, but a general algorithmic answer is welcome.

Body:
If you repeatedly merge the 2 first sequences you will get a runtime that is much worse than merge sort as you compare the first elements far too many times (n log(n)^2???) if you merge the 2 (or more) smallest (adjacent) sequences each time you should approach merge sorts efficiency.

Finding the smallest adjacent sequences might be done by building a tree with roughly half the sequence in each branch recursively and then merging the lowest branches first.

---- Edit

First version:

Essential a mergesort where the separators are the implicit partition of the mergesort algorithm.

Order separators according to their index in the array

MergeIt(first, last) {
    if (only one or zero separator)
       return first;

    split = separator containing the middle separator (first, last)

    return inplace_merge(MergeIt(first, split), MergeIt(split, end));
}

This ensures that you only do the minimum number of merges, but not the minimum number of compares as larger sequences might be merge with the current minimum sequence.

Version two:

Still basically a mergesort where we now take into consideration the length of the sequences.

Order separators according to their index in the array

MergeIt(first, last) {
    if (only one or zero separator)
       return first;

    split = separator containing the middle element of array(first, last) // not the middle separator

    return inplace_merge(MergeIt(first, split), MergeIt(split, end));
}

The split insures that the smaller sequences merge first as the larger stop higher up in the call tree. This still does not insure the least number of compares as there still is the chance that larger sequences are merge with the current minimum length, though this is still better than version one as the large sequences here are smaller.

Version three:

Merge the adjacent sequences which span the least number of elements

Make heap of pairs of adjacent sequences, sort after minimum length of the pairs, for each sequence only add the shortest of its prev and next.
// each sequence will appear max twice except the first and last.

while (heap.size() > 1) {
    min = heap.pop

    remove the possible other occurrence of min.first and min.second

    sequence = inplace_merge(min.first, min.second)

    insert the minimum of pair(prev(sequence), sequence) and pair(sequence, next(sequence)) in heap.
}

The overhead might make this slower than the second version but the compares in made by inplace_merge should now be the minimum.


答:
Perhaps the difference here can be described as physical vs. logical leaks. GC protects excellently against the former.

Yet just talking about "memory leaks" in general, I'd suggest that GC doesn't really offer very strong protection and might even make it harder to avoid them. This is kind of controversial so I'll try to explain it carefully (and also the safety negatives associated when GC is lacking which definitely exist).

To me the greatest benefit GC provides is not protecting against leaks but in providing safety in cases where leaks aren't the biggest deal.

Take an example of a video game. Probably people have tried some games out there written by aspiring game developers in languages that provide garbage collection which leak resources like crazy. Within a half hour of playing the game, the memory usage of a simple 2D game has risen to gigabytes, and the game is increasingly getting slower and slower with prolonged usage until it is restarted. 1 year of development and 16 updates later, the game is still leaky as ever.

These types of leaky games almost always tend to be written against garbage collectors, yet they're among the leakiest applications out there. How could that be if GC is considered by some to be a silver bullet against memory leaks?

The comparison may not be fair since these games are often developed by not-so-experienced developers. Yet I would suggest these game devs might write less leaky (but more crashy) software if they didn't use garbage collection.

Resource Mismanagement

The reason these leaks occur is because of rooted resources. More generally speaking, they're the result of resource mismanagement which is a problem that can occur with or without GC. A game might allocate sprites repeatedly during gameplay, but multiple areas of the codebase may reference those sprites. Failure to manually release the reference in any one of these places then leads to that dreaded logical leak with rooted resources that aren't freed at the time they are no longer needed, and not freed at all until the application is shut down.

Safety

Yet the game continues to run without crashing. It might unnecessarily loop over sprites that are no longer needed or being drawn, getting slower and slower and using up more and more memory with the accumulation of unneeded sprites. Nevertheless, it's worth noting how stable (crash-free) even these amateurish indy games are, and that's where I see GC offering a great benefit.

Dangling Pointers vs. Unfreed Resources

In a similar scenario given a native codebase that doesn't use GC, the resource would be freed by an explicit request to free the resource through any one of its references (pointers). That then causes the other references (pointers) to become invalidated (become dangling pointers). Subsequent access of those dangling pointers in some part of the game then leads to very deadly undefined behavior, typically a hard crash resulting from a segfault/access violation.

A segfault here would be a very showstopping-bug, introducing a crash: a jarring, very frustrating interruption to the gameplay. Nevertheless, it would be blatantly obvious and easy to detect and correct. That's why I think the edge in ultimately avoiding memory leaks actually goes to languages that don't use garbage collection (albeit some patches later). The easiest bugs to correct are the easiest to notice/reproduce. Instead these languages without GC pay for it with more dangerous code and undefined behavior resulting from resource mismanagement at a lower memory management level. GC languages can pay for resource mismanagement in the form of safe but deceptive and subtle leaky behavior which can fly under the radar of testing.

This can be especially annoying in extensible plugin architectures where loading a third party plugin then causes that plugin to acquire a reference to a resource in your system, say some gigantic image that spans 300 megabytes. When that plugin code (which isn't even under your control) fails to manually release the reference, the mere presence of that plugin causes the codebase to mysteriously leak 300 megabyte resources here and there at no fault of your own, only the mere presence of this third-party plugin.

Silver Bullets

Anyway, I would suggest not trying to distinguish various types of leaks so much. They're all equally annoying (actually, logical leaks tend to be the most annoying). Instead I'd try to focus on the fact that garbage collection is not a silver bullet against memory leaks. To buy into this kind of illusion is often inviting very leaky software. It pays to give special attention to concepts like soft/weak/phantom references in languages with GC upfront if there's a strong motivation to avoid memory leaks. Resource management doesn't necessarily get much easier with GC and may even get harder in some cases, it's just that mismanagement tends to lead to less deadly behavior (which can actually be both good and bad depending on the context).

It's also worth noting that the physical leaks which GC definitely avoids outright are some of the easiest to avoid, with leak detection tools like valgrind immediately showing which line of code allocated memory that wasn't freed even after application shutdown. The logical leaks are typically far more difficult, and the ones that GC and other tools can't so effectively protect us against, only a careful design and implementation when complex resource management is involved.


答:
Maybe. A "memory leak" in the presence of GC can mean one of two things:

A flaw in the garbage collector or language runtime where memory escapes the notice of the garbage collector without actually being freed at the OS level. Nobody knows it exists anymore, so it will never be freed (at least not until the process exits).

A flaw in user code where objects continue to be referenced (maybe indefinitely) after they're no longer useful, for example through circular references or lexical closure. The GC sees that the objects are still referenced, so it won't free them. The article you reference calls this a "space leak", but I think that most reasonable people would consider it a straightforward example of a memory leak.

However, there are a couple of other cases where neither of these things happened, and where the loss isn't quite so permanent:

An object is properly managed by the GC, and has been properly unreferenced, but hasn't actually been collected yet, probably because whatever condition triggers the GC hasn't happened yet, or because some condition is temporarily preventing GC. The memory is theoretically available in the future, but it isn't right now, and the low-level memory usage of the program exceeds its actual working set by a possibly large amount.

The program allocated a lot of memory, then finished with it, and the GC properly freed it, but it hasn't been returned to the OS yet, either because the condition for doing that hasn't been satisfied yet, because it simply isn't possible on a given OS, or because the runtime hasn't been written to make it possible. The memory is available for future allocations by the same program, but it isn't available for other programs — from the outside, the program's memory usage goes up but not down.

These cases are usually much less problematic than proper memory leaks, because they tend to sort themselves out eventually — until one day you find yourself with a program that crashes with out-of-memory errors because it triggers one of these conditions by allocating in a tight loop or doing large transient allocations or whatever happens to be the magic combination for a given language/runtime/OS. Then you have a problem that you have to deal with.

In short: memory leaks aren't banished by GC, they're still a concern. They're just harder to create. But there's a whole other class of problems that you might also run into someday (although hopefully not). I think that "space leak" would actually be a reasonable name for them, but that's in conflict with the article you linked, so perhaps something else.


问:
How can I create extensible reader and writer wrappers around a shared opaque resource class?
In C++,
Say I have a Buffer class (cannot be inherited) which is given and can support the following operation:

```<code>class Buffer {
public:
    void write_buffer(Data);
    Data read_next_data();
};
</code>```

Now I want something like BufferWriter and BufferReader.

There are some requirements:

BufferWriter should only write but not read the buffer, while
BufferReader should only read the buffer.

BufferWriter and BufferReader should be extendable (can be inherited)

A Buffer can be shared by multiple BufferReaders and BufferWriters

I do not want others to use the Buffer directly (which the read/write logic has not been separated)

How should I organize the class structure in this case? Or is the requirement contradictory to what is given?

答:
I understand your design goal.
You can attempt to use Combination model.

Like this as follow:

```<code>class Buffer {
   public:
      WriterBuffer wb
      ReaderBuffer rb;
 };

 class WriterBuffer{

 };

 class ReaderBuffer{

 };
</code>```

Body:
I understand your design goal.
You can attempt to use Combination model.

Like this as follow:

class Buffer {
   public:
      WriterBuffer wb
      ReaderBuffer rb;
 };

 class WriterBuffer{

 };

 class ReaderBuffer{

 };


答:
Does it make sense to use the term “Space Leak” with regard to Java?

Frankly, no.

While the term is well-founded, and it is (or may be) understood by the Haskell community, the distinction between "space leak" and "memory leak" is NOT widely understood by Java developers or the wider software engineering community1.

Therefore, making a distinction between "space leak" and "memory leak" is likely to cause confusion rather than illumination.

As to the question of whether this term "brings clarity" ... IMO, not necessarily:

You can be equally clear without using this "new" terminology.  Possibly even more so ... if you set out fully what you are talking about.

Using terminology that people don't understand does not bring clarity.

1 - For instance, I've been programming for 40+ years, and in Java for 15+ years, and I can't ever recall seeing "space leak" used in this way ... until now.


答:
I don't know about the "best" way given these tight constraints, but provided that Buffer has separate read/write pointers and works sufficiently on its own through its public interface, you can do like so:

```<code>class BufferReader
{
public:
    explicit BufferReader(Buffer& ibuf): buf(&ibuf) {}
    virtual ~BufferReader() {}

    virtual int read_int() = 0;
    ...

protected:
    Buffer* buf;
};

class TextBufferReader: public BufferReader
{
public:
    explicit TextBufferReader(Buffer& buf): BufferReader(buf) {}

    int read_int() override
    {
        // return an integer from 'buf' as a text entry
        // using lexical conversion to an integer.
    }
    ...
};

class BinaryBufferReader: public BufferReader
{
public:
    explicit BinaryBufferReader(Buffer& buf): BufferReader(buf) {}

    int read_int() override
    {
        // return an integer from 'buf' in binary.
    }
    ...
};
</code>```

... similar idea for BufferWriter (with BufferWriter calling write_buffer and BufferReader calling read_next_data).

In this case, both BufferReader and BufferWriter aren't merely extensible (capable of being  inherited). They need to be inherited, as this design makes them into abstract base classes. Yet that's probably the most flexible way to go (and also safest since it's not prone to object slicing).

You could also loosen the coupling by making buf private and exposing protected methods to read and write from a buffer, e.g. as opposed to a protected data member.

DIP

It's worth noting that this design inevitably violates the dependency inversion principle, as we have abstractions depending upon concrete details (Buffer) through dependency injection. Yet there are always exceptions to the rule. If your buffer is always some kind of raw buffer of bits and bytes, e.g., and doesn't benefit in the slightest from being abstracted, then it's probably okay to violate DIP in this case as the alternative might make things harder to maintain rather than easier.

Smart Pointers

For a safer design, you can use shared_ptr<Buffer> instead of a raw pointer, e.g. I'm kind of biased against this in the context of handles that don't need to own memory since I work in a performance-critical field and would prefer to reserve the ability to simply allocate Buffer on the stack (especially if you have critical loops that allocate teeny buffers left and right), making it the client's responsibility to ensure that Buffer is not destroyed while BufferReader and BufferWriter are using it. But if performance isn't a pressing goal or if you're willing to tackle efficiency at the memory pool level (possible PITA), then it's definitely a lot safer to use shared_ptr<Buffer> here.

In either case, whether through the safer shared_ptr which manages the buffer for you or a client-level responsibility to manage Buffer manually while using raw pointers, you get the ability to share a single buffer across multiple readers/writers that way.

I do not want others to use the Buffer directly (which the read/write
  logic has not been separated)

If you want to enforce this with an iron fist, one way is to make Buffer opaque like so:

```<code>// In some public header:
class Buffer;

// Returns a newly-created buffer for use with BufferReader/BufferWriter subtypes.
std::shared_ptr<Buffer> create_buffer(...);
</code>```

That's all your clients will end up seeing, making it impossible to access the buffer functionality from the outside. In this case, it'd generally be silly not to use shared_ptr, since the opacity here of this forward-declared type will require a heap (free store) allocation regardless with a custom allocator being the only way to speed things up.

Then BufferReader and BufferWriter implementations can include a private header which makes the definition of Buffer only visible to them. In this case, shared_ptr<Buffer> then turns into an opaque handle which can only be passed into a BufferReader or BufferWriter. Clients cannot do anything with Buffer except pass a handle to it along to readers and writers to use.

Title: How can I create extensible reader and writer wrappers around a shared opaque resource class?

Body:
In C++,
Say I have a Buffer class (cannot be inherited) which is given and can support the following operation:

```<code>class Buffer {
public:
    void write_buffer(Data);
    Data read_next_data();
};
</code>```

Now I want something like BufferWriter and BufferReader.

There are some requirements:

BufferWriter should only write but not read the buffer, while
BufferReader should only read the buffer.

BufferWriter and BufferReader should be extendable (can be inherited)

A Buffer can be shared by multiple BufferReaders and BufferWriters

I do not want others to use the Buffer directly (which the read/write logic has not been separated)

How should I organize the class structure in this case? Or is the requirement contradictory to what is given?

Body:
I don't know about the "best" way given these tight constraints, but provided that Buffer has separate read/write pointers and works sufficiently on its own through its public interface, you can do like so:

class BufferReader
{
public:
    explicit BufferReader(Buffer& ibuf): buf(&ibuf) {}
    virtual ~BufferReader() {}

    virtual int read_int() = 0;
    ...

protected:
    Buffer* buf;
};

class TextBufferReader: public BufferReader
{
public:
    explicit TextBufferReader(Buffer& buf): BufferReader(buf) {}

    int read_int() override
    {
        // return an integer from 'buf' as a text entry
        // using lexical conversion to an integer.
    }
    ...
};

class BinaryBufferReader: public BufferReader
{
public:
    explicit BinaryBufferReader(Buffer& buf): BufferReader(buf) {}

    int read_int() override
    {
        // return an integer from 'buf' in binary.
    }
    ...
};

... similar idea for BufferWriter (with BufferWriter calling write_buffer and BufferReader calling read_next_data).

In this case, both BufferReader and BufferWriter aren't merely extensible (capable of being  inherited). They need to be inherited, as this design makes them into abstract base classes. Yet that's probably the most flexible way to go (and also safest since it's not prone to object slicing).

You could also loosen the coupling by making buf private and exposing protected methods to read and write from a buffer, e.g. as opposed to a protected data member.

DIP

It's worth noting that this design inevitably violates the dependency inversion principle, as we have abstractions depending upon concrete details (Buffer) through dependency injection. Yet there are always exceptions to the rule. If your buffer is always some kind of raw buffer of bits and bytes, e.g., and doesn't benefit in the slightest from being abstracted, then it's probably okay to violate DIP in this case as the alternative might make things harder to maintain rather than easier.

Smart Pointers

For a safer design, you can use shared_ptr<Buffer> instead of a raw pointer, e.g. I'm kind of biased against this in the context of handles that don't need to own memory since I work in a performance-critical field and would prefer to reserve the ability to simply allocate Buffer on the stack (especially if you have critical loops that allocate teeny buffers left and right), making it the client's responsibility to ensure that Buffer is not destroyed while BufferReader and BufferWriter are using it. But if performance isn't a pressing goal or if you're willing to tackle efficiency at the memory pool level (possible PITA), then it's definitely a lot safer to use shared_ptr<Buffer> here.

In either case, whether through the safer shared_ptr which manages the buffer for you or a client-level responsibility to manage Buffer manually while using raw pointers, you get the ability to share a single buffer across multiple readers/writers that way.

I do not want others to use the Buffer directly (which the read/write
  logic has not been separated)

If you want to enforce this with an iron fist, one way is to make Buffer opaque like so:

// In some public header:
class Buffer;

// Returns a newly-created buffer for use with BufferReader/BufferWriter subtypes.
std::shared_ptr<Buffer> create_buffer(...);

That's all your clients will end up seeing, making it impossible to access the buffer functionality from the outside. In this case, it'd generally be silly not to use shared_ptr, since the opacity here of this forward-declared type will require a heap (free store) allocation regardless with a custom allocator being the only way to speed things up.

Then BufferReader and BufferWriter implementations can include a private header which makes the definition of Buffer only visible to them. In this case, shared_ptr<Buffer> then turns into an opaque handle which can only be passed into a BufferReader or BufferWriter. Clients cannot do anything with Buffer except pass a handle to it along to readers and writers to use.


答: Why don't you include an explanation (very much like you did in your question) in the introductory part of the documentation, e.g. a Conventions section?  Then you could explain that the term "method", as used in your documentation, is meant in the generic sense of method (Java), member function (C++), ... since the documentation applies to all implementations.


问:
Member functions vs. Non-member functions for math operators
I'm writing a linear algebra library (long story short, it's a school assignment) that involves matrices, vectors, etc.  In the process of creating this library, I'm going to be creating functions that perform mathematical operations on objects.  For example, transpose matrix, invert matrix, normalize vector, etc.

I was curious as to what is the "best practice" for this sort of function...  That is, should I make the function a member function, or non-member?  (For clarity/library use sake)

Example:

```<code>//Member function way:
B = A.transpose();
C = A.inverse();

//Non-member function way:
B = linalg::transpose(A); //Non-member transpose function in linear algebra namespace
C = linalg::inverse(A);
</code>```

Is there some standard regarding these sorts of operations?  Or, at least, is there a common way people do this?  I'm leaning towards the first option, but I'd like to know if this is recommended.

答:
Avoid membership fees: Where possible, prefer making functions
  nonmember nonfriends.

Nonmember nonfriend functions improve encapsulation by minimizing
  dependencies: The body of the function cannot come to depend on the
  nonpublic members of the class (see Item 11). They also break apart
  monolithic classes to liberate separable functionality, further
  reducing coupling (see Item 33). They improve genericity, because it's
  hard to write templates that don't know whether or not an operation is
  a member for a given type [...]

Herb Sutter