问:
Difference between a heap and a priority queue
I always thought that heaps and priority queues were synonyms - an abstract data structure that supports the insert, findMin and deleteMin operations.

Some literature seems to agree with me - Chris Okasaki's Purely Functional Data Structures (chapter 3), for instance.

On the other hand, Wikipedia's heap page defines it as a tree-based data structure, and states that heaps are a concrete implementation of priority queues.

I'm having a hard reconciling this with the fact that I can think of more than one heap implementation - leftist heaps, binomial heaps, splay heaps...

Does the simple fact that a heap can be implemented with different data structures not mean, by definition, that it is an abstract data structure? And if that's the case, is there an actual difference with priority queues?

答:
I think that what you wrote about concrete vs abstract is correct. Where you say that splay heaps, binomial heaps are different implementations of heaps though, I think it is more correct to say they are different types of heaps. Heap I think of as a category of implementation that generally guarantees not only the same interface, but also same access times. </p>

<p>You see this with associative maps, and hash tables and binary search trees as well. Bsts and hash tables are both concrete data structures that provide the associative map abstract interface. Red black trees and and avl trees are both balanced bsts, with same big O guarantees and same additional interface (in order traversal). They are different types of trees I would say more than different implementations of trees. They are different but closely related implementations of associative maps. </p>

Body:
I think that what you wrote about concrete vs abstract is correct. Where you say that splay heaps, binomial heaps are different implementations of heaps though, I think it is more correct to say they are different types of heaps. Heap I think of as a category of implementation that generally guarantees not only the same interface, but also same access times.

You see this with associative maps, and hash tables and binary search trees as well. Bsts and hash tables are both concrete data structures that provide the associative map abstract interface. Red black trees and and avl trees are both balanced bsts, with same big O guarantees and same additional interface (in order traversal). They are different types of trees I would say more than different implementations of trees. They are different but closely related implementations of associative maps.


答:
A priority queue can have any implementation, like a array that you search linearly when you pop. All it means is that when you pop you get the value with either the minimum or the maximum depending.

A classic heap as it is typically referred to is usually a min heap. An implementation that has good time complexity (O(log n) on push and pop) and no memory overhead.

ContentLicense: CC BY-SA 3.0

Title: Difference between a heap and a priority queue

Body:
I always thought that heaps and priority queues were synonyms - an abstract data structure that supports the insert, findMin and deleteMin operations.

Some literature seems to agree with me - Chris Okasaki's Purely Functional Data Structures (chapter 3), for instance.

On the other hand, Wikipedia's heap page defines it as a tree-based data structure, and states that heaps are a concrete implementation of priority queues.

I'm having a hard reconciling this with the fact that I can think of more than one heap implementation - leftist heaps, binomial heaps, splay heaps...

Does the simple fact that a heap can be implemented with different data structures not mean, by definition, that it is an abstract data structure? And if that's the case, is there an actual difference with priority queues?


问:
Using Mockito.reset
I've just read a lot of arguments against using Mockito.reset and can't make much sense of it. Put differently, I agree in general, but there's always a case which looks like using reset is useful or even necessary.

Grossly simplified, my class under test is an encapsulated map like

```<code>class Handler {
    private final Map<String, String> map;

    public void handle(RequestResponse rr) {
        if (rr.isPut()) {
            map.put(rr.key(), rr.value());
            rr.response("OK");
        } else {
            rr.response(map.get(rr.key());
        }
    }
}
</code>```

To test it, I mock RequestResponse and do something like

```<code>when(rr.isPut()).thenReturn(true);
when(rr.key()).thenReturn("key");
when(rr.value()).thenReturn("value");
handler.handle(rr);
verify(rr).response("OK");

reset(rr);

when(rr.isPut()).thenReturn(false);
when(rr.key()).thenReturn("key");
handler.handle(rr);
verify(rr).response("value");

reset(rr);

when(rr.isPut()).thenReturn(false);
when(rr.key()).thenReturn("anotherKey");
handler.handle(rr);
verify(rr).response(null);
</code>```

I can see, I'm testing three things at once:

proper response after "put"

proper value returned from get with the same key

null returned from get with another key

I can imagine reasons to separate the two last tests. However, they both need the first one and I still need a reset in between? Or don't I?

Update

In the meantime the class under test has got a bit more complicated and the need for reset bigger. It's sort of a state machine and the test looks like

repeat the following accross different paths

try an illegal step and expect an exception

try another illegal step and expect an exception

do a legal step and verify output

I actually only need two methods, one verifying the exception for an illegal step and the other verifying correct output for a legal step. Executing an illegal step mustn't change the state, so it's safe to mix it in.

Consider this example: If the only valid input sequence was A, B, C (three steps) and the corresponding outputs were a, b, c, then a test looks like

```<code>checkException("B")
checkException("C")

checkOutput("A", "a")
checkException("A")
checkException("C")

checkOutput("B", "b")
checkException("A")
checkException("B")

checkOutput("C", "c")
checkException("A")
checkException("B")
checkException("C")
</code>```

walks through the whole path and verifies everything. It would take many "normal" single-condition-verifying tests to achieve the same, right?

答:
The reason that you are using reset is because you are processing three different RequestResponses through your handler. But reset is actually for when you need to change the responses that an object is making. I think the conceptually correct thing for you to do is create three different RequestResponse objects. That way you don't need to reset anything.

But your test is still awkward. I think its awkward because the interface is awkward. RequestResponse fills in the role of both parameters and return value. One approach would be to write an adapter into a more typical approach, something like:

```<code>class Handler {
    private final Map<String, String> map;

    public String handle(boolean isPut, String key, String value) {
        if (isPut) {
            map.put(key, value);
            return "OK";
        } else {
            return map.get(key);
        }
    }
}

class HandlerAdapter {
    final Handler handle;

    public HandlerAdapter(Handler handler) {
         this.handler = handler;
    }

    public void handle(RequestResponse rr) {
       rr.response(handler.handle(rr.isPut(), rr.key(), rr.value()));
    }
}
</code>```

Your test then becomes:

```<code>assertEquals("OK", handler.handle(true, "key", "value"));
assertEquals("value", handler.handle(false, "key"));
assertEquals(null, handler.handle(false, "anotherkey"));
</code>```

I'd probably split that into two tests, checking for successful return and mismatched key in seperate tests. Of course you'll also want to right tests for HandlerAdapter, but that should be really straightforward since it only passes data into Handler.

Title: Using Mockito.reset

Body:
The reason that you are using reset is because you are processing three different RequestResponses through your handler. But reset is actually for when you need to change the responses that an object is making. I think the conceptually correct thing for you to do is create three different RequestResponse objects. That way you don't need to reset anything.

But your test is still awkward. I think its awkward because the interface is awkward. RequestResponse fills in the role of both parameters and return value. One approach would be to write an adapter into a more typical approach, something like:

class Handler {
    private final Map<String, String> map;

    public String handle(boolean isPut, String key, String value) {
        if (isPut) {
            map.put(key, value);
            return "OK";
        } else {
            return map.get(key);
        }
    }
}

class HandlerAdapter {
    final Handler handle;

    public HandlerAdapter(Handler handler) {
         this.handler = handler;
    }

    public void handle(RequestResponse rr) {
       rr.response(handler.handle(rr.isPut(), rr.key(), rr.value()));
    }
}

Your test then becomes:

assertEquals("OK", handler.handle(true, "key", "value"));
assertEquals("value", handler.handle(false, "key"));
assertEquals(null, handler.handle(false, "anotherkey"));

I'd probably split that into two tests, checking for successful return and mismatched key in seperate tests. Of course you'll also want to right tests for HandlerAdapter, but that should be really straightforward since it only passes data into Handler.


问:
Is there a benefit in compiling your code as you go along?
I recently had a job interview in which they gave me an hour to write some real code.  It wasn't a huge amount, probably less than 100 lines.  After about 45 minutes, I compiled, ran it, and got it to work.  I may have spent 5-10 minutes working out compile errors and a couple minor bugs, but overall it was very smooth.  (Incidentally, I did get an offer from them.)

However, what puzzled me was that after I handed over the completed code, the interviewer told me that the only thing I did wrong was "not compiling as I go along".  I asked him what the difference is, and he said "what would you have done if you finished the code and it didn't compile in time".

In my understanding that's an invalid argument, because "getting code to compile" for a given length of code generally involves fixing a constant number of compile errors and takes a fairly constant amount of time, which should be the same whether you do it after you finish writing the code, or if you interleave it with your coding time.  If anything, interrupting your coding to search for missing semicolons would probably be detrimental to your efficiency.  Except in extreme circumstances when I'm experimenting with obscurities around edge-cases on things like virtual functions in derived classes, etc. it seems reasonable to expect that code written by a an experienced developer will compile, minus the occasional typing error, and even if it doesn't, it's not as if I would have to rewrite a portion of the code in order to fix the compile error.

In another similar incident, I was given an incomplete codebase in an interview, and asked to finish it and make necessary modifications to get it running.  I started by reading through the existing code, and then after a few minutes (even before I had finished looking at the code), the interviewer told me that's enough.  When I asked him what he would have done (i.e. "what did I do wrong"), he told me that he would have started by immediately getting the code to compile.

Why is that even relevant?  In my opinion and in my experience, whether or not a piece of code compiles is essentially random, involving things like whether or not semicolons are missing, and has little to do with the correctness of the underlying program.  (To me, focusing on compiling is like running an article through a spell-check without proofreading to check the grammar.)

If you give me a piece of incomplete code, the first thing I do will be to read it.  I won't even try to compile it until I know what the code is doing and I know the algorithm is correct.

Anyway, these have been just a couple recent incidents, but in general I've heard many developers talk about compiling their code as they go along, and yet nobody has been able to tell me the benefit of doing so.  I understand the benefits of testing your code as you go along, but why compiling?

So my question is this: Is there something I missed?  Is there actually a benefit to compiling as you go along?  Or is this some sort of myth propagated by the software community that you must compile your code frequently?

答:
The other answers here mount a good defense for compiling frequently on the job, but since your question is centered around interviews, I'd like to tackle that angle of it.

In my interviews, I do the exact opposite: candidates can't use a compiler. They write short programs on the white board and then we discuss them. I have found that too many developers use the compiler (or interpreter) as a crutch, and that is a far bigger waste of time than compiling too infrequently. If I'm offering you a lot of money and you can't even write FizzBuzz correctly without a compiler, then you're never going to cut it on a long term basis, working on problems that are 100x more difficult than the toy exercises in the interview. And yet these simple exercises weed out more candidates than any other part of the interview.

The goal of an interview is to evaluate the mutual fit of the candidate and the business. A good interview question should state the objectives of the question and how the interviewee will be assessed. Springing a trick question on the interviewee and then penalizing them for not knowing the hidden answer doesn't help the interviewer or interviewee. Unfortunately, most programmers — even senior ones — aren't trained to interview other programmers, so they just rely on clichés and ask the same types of questions they were asked when they interviewed, without much though about whether these are effective techniques for evaluating candidates or not.

I'm not claiming that my approach is the "one true way", but it has served me very well. Like so many software methodologies that start with a capital letter, there are an equal number of "mandates" for interviewing. They're all bunk. You need to do what works for you and your business.


问:
2D linked list vs. multidimensional array/vector
I hope that programmers is the correct stack exchange for this, as it is quite a concept based question.

I'm working on a data structure in C++ that is a represents data in 3D space. The x-y plane is large (say 0 - 10 000) while the z-axis has a very small range (0 - 10). All the data is located on integer (x,y,z) points. However there can be more than one than one data point on an (x,y,z) coordinate.

I have thought of three ways of approaching this subject, and don't have the necessary experience to choose between them.

Using a 2D linked list inside vectors (dynamic arrays) vector<vector<structureA*>> Data where the first list item for that (x,y) point can be accessed using Data[x][y]. structureA contains an its z value, its actual data, as well as a pointer to the next structure in the list (that may, or may not have a different z coordinate, but is located  on the same line defined by x and y). Accessing elements at the middle and end of this list is slow.

Using a three dimensional array/vector: vector<vector<vector<structureB>>> Data. In this case the first two vectors define the x and y coordinates (as before) and the third vector gives us an array of all of the elements on that line defined by x and y. We can quickly determine how many elements are on this line (by querying the third vector) and can iterate from the back and the front. structureB contains, the point's z value and its data. This seems like a fairly good and safe (regarding memory allocation) solution to me.

Using a three dimensional array/vector and a linked list. In this case the data could be accessed as such: Data[x][y][z] and would point to the first element of a linked list of data that resides at this coordinate. The structure pointed to would not contain its z value here as this is already dealt with in its address in the array. However, many (x,y,z) points have no data, whereas most of those that do have data have 10+ data structures. (All lines defined by a specific (x,y) contain at least one structure). This seems the worst solution to me as in many cases I would have to iterate through empty z coordinates, before hitting a linked list to iterate through.

The emphasis in this program is speed, my data set is less than 100MB on a modern computer, so even an inefficient method of storing it in RAM is fine. Option 2 seems the best to me, although in the past I've normally seen people more inclined to go with option 1. I'm interested to hear your opinions on the best way to handle this along with your reasoning.
Many Thanks.

Update

Thanks for the responses, I stand to learn quite a lot from your comments as I am a hobby programmer, having taken only one short course on the fundamentals of C a few years back.

@MorphingDragon The array is not jagged, all z "slices" have the same range of x and y. The values also don't seem sparse enough for a hash table (which IIRC slow down significantly on hash collision - which is guaranteed as multiple elements have the same (x,y,z)). The dimensions of the set are known on file load (they are included in the file header along with an md5 hash of the file for error checking and a few bit relevant to the analysis).

@J Trana / Florian F The data set is pre-built and is infrequently modified by the program - a piece of data may need to be moved or deleted. For adjusting data particularly just adjusting its z-value (or removing it), which are the most frequent operations. The linked list will be faster as these operations are O(1) as opposed to O(n) in a vector. However, I believe these changes are infrequent enough that having O(n) for changes may be worthwhile if the lookup speed is even marginally faster (as this is the more frequent operation).

The majority of the time the data will be accessed iteratively, taking an n*p slice  from the x-y plane. Pseudocode example:

```<code>for each y between startY and (startY + p)
  for each x between startX and (startX + n)
    read all nodes in Data[x][y] //gets nodes for each z on an (x,y) line
    analyse(&nodes) //possibly modify the nodes, possibly just compute something based on their values
</code>```

Data access is always related to the (x,y) line an element is on, but we  don't always need all the nodes on that line (dependant on their z). So we either have a structure that doesn't require us to retrieve all of them (just the ones we want) or we perform a secondary sort. The data on file represents a sorted list in ascending z for each (x,y).

I will also look into those other data structures. I've never met them, as with very little training, my method is to use STL vectors or lists for everything. I'd like to spend the time to do this properly this time though.

I spent a fair amount of time thinking about this last night after posting the question and seeing the first responses. I realised that "if one piece of data from a point (x,y,z) is required, then all elements from that point are required at the same time." This has led me to think that option 3, my least preferred when I started this yesterday afternoon, is actually the best of the options I've enumerated. If I use a three-dimensional dynamic array of pointers to linked list, I don't exactly lose much speed or heap space setting a pointer to NULL rather than attaching a struct. This also allows full access to any 3d, which while not currently required may reduce some operations from O(n) to O(1).

Having had a brief look over octaves/r-trees, I feel safe saying that my data set is not complex enough to require such an engineering heavy solution. When it comes down to it, i am fairly sure that any of the three options I outlined would work, even if not the fastest, but I would like to learn a good and relatively efficient method, rather than just relying on the awesome power of modern computers to brute force a problem like I normally do.
Thanks for the replies and suggestions so far. :)

答:
I don't fully follow what's going from your answer, but a couple of comments:
 1. You should use contiguous memory. At the very least, at the outer level (for the x-y coordinates) you should have a single vector, not a vector of vectors. A vector is basically a pointer to a contiguous block of memory. A vector of vectors is a contiguous block of pointers, to contiguous blocks of memory, i.e. the data itself is not contiguous. Contiguity is incredibly important to speed due to factors like cache missing and pre-fetching.
 2. Linked lists are slow. The working of modern processors tends to give vectors a very large practical advantage. Linked lists are especially terrible for small types, for several reasons. First off, if the types are small the extra space costs of the pointers is huge. Second, when the types are small and in contiguous storage, the processor can read them very efficiently because processors generally read from memory an entire cache line at a time, which is 64 bytes. If your data type is just a double, that means that 8 doubles are read simultaneously by the processor. When you use linked lists you give this up.

The bottom line: you want a loop over your data to read the data precisely sequentially from memory in one contiguous chunk. This is the model that will give the best performance.

Edit: Ok, I reread your requirements more carefully. Here's what I think is best, however let me preface this: Alexandrescu has a great article on performance where he notes that we have made our processors better and more intelligent, and the cost of a simple mental model of how it works. So it's very hard nowadays to predict the speed of code compared to before. So profiling is more important than ever. So if you really care about speed, profile! (btw, link is https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920).

Given that your x and y locations will never change, only z, you can create a struct as you suggested that stores x, y, z and misc data. Take all the initial data points, and put them in a single std::vector of these structs, call this variable DataPoints. Sort them by x, then y, the z sorting is optional. If you are doing more operations that change z, maintaining sort order will be expensive and its easier just to loop through all z's and do an if check. If you usually just scan the data, then keep sort order by z, and you will have to pay O(N) to keep it sorted when modifying the z coordinate, where N is the number of points with the same x and y coords.

Now, we are going to build a lookup table. We create another array, a single contiguous piece of memory, that you do lookups on given an x and y coordinate. This table will return a pair of integers, telling you the first and last index in DataPoints that have that exact x and y. Now, there's just one more clever bit. Since we have this lookup table, we don't actually need the x and y coordinates stored in DataPoints at all. So we create a new DataPointsReduced; it's the same data in the same order, but with the x data stripped. We could strip the y data too, but that may or may not pay off as you'll see.

We're now basically done. When you do the loop over x and y, you can extract all the indices you need from the lookup table. Sadly because you do a range of x and range of y, the resulting data of interest can't be fully contiguous. But the scan should be contiguous over a fixed value of x. The outer loop is x, for that fixed x, since the secondary sorting is y, the range of y's of interest all contain data that is contiguous in memory. So there are only two loops, not three. The inner loop goes over a block of memory containing all z's for a range of y's, for a fixed x. Inside this inner loop you do whatever operations you want. Note that if we strip y too and we need it, we will need to return to three loops, or do some kind of lookup to determine y at each stage, which can be slower. If you don't need y at all once the range of y's is specified, then strip y from your data as well.

That's basically it. If your range of x's and y's gets very large, this lookup table will eventually use a huge amount of space (but note: no more space than your solution, this lookup table could probably store 2 32 bit unsigned integers for every x-y pair, whereas your table would store at least one 64 bit pointer for every x-y pair). You can avoid the lookup table at small cost. Since we've sorted by x and y, you can have a small prestep where you do some clever binary searching to quickly find the indices you need, and then proceed as before. The cost of this prestep is less than linear in the total amount of data being scanned, so asymptotically it doesn't affect running time. However in this case you obviously can't strip the x or y data. This shouldn't make a huge difference though, if the number of points in the contiguous y range is reasonable prefetching should nullify this difference.

This setup (with no lookup table) is pretty damn good if the ranges of x and y are huge, and your data is progressively more sparse. Note that this solution does not have any space requirement proportional to the ranges of x and y. Whereas even dynamically allocated arrays or linked lists at every x-y pair implies at least one pointer per x-y pair, which is space proportional to the ranges of x and y.

Final thought. This setup has potentially more if branching, because I basically recommend just looping through a contiguous block of memory and doing whatever checks you need to on z, instead of looping over the exact known range of z. It depends exactly what your code is doing, but for very simple if operations (e.g. 1-2 lines of code, no side effects) often the cost of branching is virtually nil: the processor can compute the if condition and both branches simultaneously
on 3 different pipelines, and then move the appropriate result back.

Final final thought: profile! What I wrote here is based on moderate experience, but honestly it is fully possible that my answer will not work out the way I think it will for any number of reasons.

Good luck.


问:
Is this a good design in C++?
Is it a good idea to replace getters and setters with a single function returning a reference?
For example, instead of this,

```<code>class Person {
  std::string name;
public:
  std::string GetName() { return this->name; }
  void SetName(std::string& toSet) { this->name = toSet; }
};
</code>```

Is this a good idea,

```<code>class Person {
  std::string name;
public:
  std::string& Name() { return this->name; }
};
...
...
Person p;
p.Name() = "Joe"; // Write.
std::string local = p.Name(); // Read.
</code>```

Does the second code have some problem?

But in C#, methods return object by reference. For example,

```<code>class Person
{
    string name;
    public Person(string _name) { this.name = _name;  }
    public string GetName()
    {
        return this.name;
    }
    public void SetName(string _name)
    {
        this.name = _name;
    }
};

class Company
{
    Person manager;
    public Company()
    {
        this.manager = new Person("Mr. K");
    }

    // The Person object is returned by reference.
    // This is equivalent to "Person& GetManager()" in C++.
    public Person GetManager()
    {
        return this.manager;
    }
};
...
...
Company comp = new Company();

// Equivalent to,
// Person& p = comp.GetManager();
Person p = comp.GetManager(); // p is a reference to comp.manager
p.SetName("Mr. L");  // This statement changes comp.manager.name

Console.WriteLine(comp.GetManager().GetName()); // Prints "Mr. L"
</code>```

In the above code, comp.manager.name wouldn't have changed if the method GetManager() returned Person by value. So, this code isn't dependent on return value optimization.
Isn't this code a violation of encapsulation?

答:
Rather than debating over the details of how to give the outside world access to the person's name, you should (IMO) be thinking about how to design the class so the outside world doesn't need access to something internal to the class.

If you want to support printing out the person's name, consider overloading operator<< for the class, and provide some manipulators to control what's printed out and in what format.

If you want to support something like sorting on name, then provide a comparison operator that handles that directly.

The better design isn't the one that gives access to the class' internals the most cleanly. It's the one that renders such access redundant.

Title: Is this a good design in C++?


问:
How to set more accurate "deadlines"?
Context:

My work is to build financial reports using mostly Excel spreadsheets. This consists mostly of formulas and a good deal of VBA. Each person is built by a single person. We service many sub-departments under the finance / accounting department and we often have many projects lined-up. I have had a rough time in the last few months because of projects taking longer than expected, then projects overlapping and getting very close to critical deadlines.

Question:

Obviously, we try our best to plan our projects so that we have a little bit of room to breathe but I always feel helpless when I have to estimate how long a given project will take me to complete. Are there techniques that can be used to better estimate how long a project can take to complete ?

Analysis:

I am thinking that one way to get a better idea of the length of the project would be to look into our process for getting requirements which could be infinitely better. It would help to get a clearer picture but it would still not give us a measurement. Then I thought that maybe isolating and measuring the average development time of different tasks that need to be done for most reports (e.g. build the queries, write the functions, construct the report, automate the process) would be one way to achieve this but it does not take into account the variability in complexity of those tasks. Some reports have very simple queries while others are extremely complex. Obviously the more complex the query the longer it would take.

Note:

Most of the time we have to deal with legacy code / inefficient reports which can cloud the waters even more.

答:
This looks like a "critical path" problem. That is, you have a major task that subsumes a bunch of subtasks.

The first thing to do is to get a handle on the subtasks. You need to start by estimating the time periods for each subtask, then "add them up" (end-to-end). Hopefully the sum will be less than the deadline date for the total task.

Keep in mind that some subtasks can be done in "parallel." That is to say, there are some subtasks that aren't as critical as others, because there is some "slack" between there completion time, and the overall completion time of some other, more critical task. If some subtask's "slack time" becomes zero (or less), it becomes the new "critical" task.

Hopefully, there will be some "slack" between the end-to-end sum of the subtasks, and the main task. This will give you some spare "emergency" time in case anything goes wrong. If there is no slack, you're on the critical path and must get everything done on "schedule" or else.

Maybe there is a way to "crash" some critical subtask. Like working evenings and/or weekends.

Title: How to set more accurate "deadlines"?


问:
Why is cleverness considered harmful in programming by some people?
I've noticed a lot of questions lately relating to different abstraction techniques, and answers saying basically that the techniques in question are "too clever." I would think that part of our jobs as programmers is to determine the best solutions to the problems we are given to solve, and cleverness is helpful in doing that.

So my question is: are the people who think certain abstraction techniques are too clever opposed to cleverness per se, or is there some other reason for the objection?

EDIT: This parser combinator is an example of what I would consider to be clever code. I downloaded this and looked it over for about half an hour. Then I stepped through the macro expansion on paper and saw the light. Now that I understand it, it seems much more elegant than the Haskell parser combinator.

答:
I'm reminded of a quote I've seen attributed to many different people, as the good quotes often are.

To paraphrase:

Any intelligent person can make the
  simple complex, it takes a genius to
  make the complex simple.

Taking a complex idea and simplifying it so it's understandable shows the cleverness of the constructor but taking a simple idea and making it complex shows the constructor wants to be seen as clever.

ContentLicense: CC BY-SA 2.5

OwnerDisplayName: Pickle Pumper


问:
What does it mean when some technology is a "standard"?
I started learning Java EE 7 and I am frequently coming across this term "standard", and I don't understand what it means.

So, for example, here is a quotation from this book:

Contrary to SOAP and the WS-* stack, which rely on W3C standards, REST
  has no standard and is just a style of  architecture with design
  principles. REST applications rely heavily on many other standards:
  HTTP, URI, URL...

I have some idea of what that might mean, but I'm not sure.

The best explanation that I have come across is the definition from here.

答:
The term "standards" in programming often refers to a technology/document that is governed by a group or community. The members of that group often share common invested goals, are active users of that technology and want to ensure the technology continues.

There are many "things" in programming that have a community that governs them. These members can range from programmers to corporate representation (i.e. Apple, Microsoft, IBM, etc. etc.)

W3C is a very large group that work together to define many standards.

Here is a list of members.

http://www.w3.org/Consortium/Member/List

REST is an example of a technology, by way of it's popularity is used by many people, but there is no group or community governing it. Therefore, there is no one place to point a finger and say "that's how the standards say it should be done".

Companies like IBM, Microsoft and others have published documentation of how to implement REST. One could say there is a "common way" of implementing REST. You can pick an authoritative source that describes an implementation of REST, and claim to follow that reference. The use of authoritative sources is one way we've been dealing with the problems of compatibility in web browsers.


问:
Client / Server dependencies with Continuous Integration
I'm starting to use continuous integration for one of my projects and had some questions about structure and architecture.

It's basically a multi-device webservice that is split into one server repository and multiple device-specific client repositories.

My question is the following:

Since clients are dependant on the server to run their tests, does it make sense to split them into another repository ?

I did some builds with Travis CI as examples and it worked great but now that I want to add tests, it's raises the issue of being dependent on the server project.

Server that itself also has it's own build and tests.

From a project architecture side it makes sense to split server and client repositories but I have troubles looking at the big picture and the CI server integration.

答:
CI server are only co-ordinators, they schedule and run builds, they schedule and run tests, and some schedule and run deployments. Its the latter you are worrying about and that's ultimately a task for whatever tool you use to deploy your build project onto whatever hardware or VM is going to be used for testing.

I have a project that consists of a client and server, each time I schedule a major build that will be released to test, it builds everything regardless of whether it needs rebuilding or not. then the guaranteed re-built-with-latest code and stamped with latest version number gets deployed.


问:
I have an unordered list of rectangles and their neighbors on four sides with no origin. How can I efficiently convert this into a grid?
I am writing a GtkGrid-like container for my GUI library for Go, and I'm trying to write the actual layout part of the code.

Basically, I have an unordered list of controls. Each control is a rectangle, and each list entry contains a pointer to the control to its north, south, east, and west. What I don't know is how to convert this back into a grid efficiently.

At first I thought I could use "the top-left control" to mark (0, 0) on the grid. But what's the top-left of

```<code>[ ][ ][X]
[ ][X][X]
[X][X][X]
</code>```

Any other solution I can think of runs in at least O(n^k) time, since I need to traverse the list multiple times to figure out what each row is, etc.

So what other approach can I use? Thanks.

The algorithm will need to be able to start from any control in the list. (Go programmers: the reason for this is that the list is a map.)

I can say that there will be no freestanding controls (all controls must be attached to another control, but can be attached on any side at any time). (Except, of course, if there is only one control at all, but I imagine this scenario falling out of the solution.)

(I hope this is in the right subdomain...)

答:
Are you guaranteed to get to any rectangle from any other? (are there any gaps?) I'm presuming so, otherwise you can't determine what the relative coordinates are for the map.

In that case, pick one arbitrarily and make that 0,0. Then it becomes a simple matter of walking the graph and assigning coordinates. If you require no negatives, then you'll need a second pass to shift everything +x/+y, but it should be O(n) at worst.


答:
TL;DR: It depends, but not because of continuous integration.  You can version everything together which will simplify dependency management, or you can split the code and make dependency management explicit between the different code bases.

This isn't really a question about continuous integration. The driving concern when splitting code bases is if you want to version and manage different parts of the codebase separately.  For example if the server code didn't change often, but the client code did then it would make sense to split the repository. You wouldn't want to do a server deploy and release when the only thing changing is the client code.

Update

Once the code has been split you must make sure you have captured explicit dependency and represented it appropriately. For example if you were creating RPMs then each package should be dependent on both the package and version that the build system is validating.

Deciding when to update the dependencies in the build system can either be a case of updating all dependents to:

the latest commit

the latest successful build

the latest release candidate

etc

This can often be handled by the build system, or some shell scripts that get triggered as pre/post build operations with each build.

Title: Client / Server dependencies with Continuous Integration

Body:
I'm starting to use continuous integration for one of my projects and had some questions about structure and architecture.

It's basically a multi-device webservice that is split into one server repository and multiple device-specific client repositories.

My question is the following:

Since clients are dependant on the server to run their tests, does it make sense to split them into another repository ?

I did some builds with Travis CI as examples and it worked great but now that I want to add tests, it's raises the issue of being dependent on the server project.

Server that itself also has it's own build and tests.

From a project architecture side it makes sense to split server and client repositories but I have troubles looking at the big picture and the CI server integration.


问:
How can a new programmer impress the software engineer (boss)?
I'm working at my first programming job. My boss is a very smart software engineer, and I feel
like I have very little to offer compared to him. Problem is, he is always busy, and needs someone to help him out. I feel like I'm not good enough, but I still want to succeed. I want to be a great programmer.

What can I do to impress him?

Thank you.

答:
What seems like forever ago I took an amazing job working with room full of amazing and accomplished programmers. Everyone was a rockstar, a few people from the original Macintosh team, almost half the people there had published books, it was a great place to be.

So I spent my first year there trying to impress everyone. I felt like I had to do somethign amazing and it drove me to learn more than I ever thought possible in a very short amount of time. In my second year I calmed down, I was a lot more confident in what I was doing, a little more vocal about my opinions, and as I looked around I grew more and more pessimistic about the actual product we were building.

That was the last year that project was fully funded. Those amazing engineers, who I still look up to today, spent 5 years and millions of dollars building framework after framework, an application platform for building on top of an application that hadn't really shipped and finally, a UI and workflow that nobody could understand, even the people that built it.

Smart is overrated. Being a "rockstar" is overrated. It's a really easy excuse to increase your threshold for complexity. It makes you think that it's more important to re-write a working system to be "cleaner" instead of implementing the next thing a customer asked for.

Jacob Kaplan Moss once said something to me about a programmer I won't name, he said "He's too smart. He writes these really smart complicated libraries that I can't use because I'm not smart enough. Stupid people should write libraries so that stupid people can use them".

The programmers that "accomplished" engineers tend to snub their nose at, people that write Ruby and JavaScript and other "toy" languages, those people make PRODUCTS and they SHIP THEM. The code might be ugly, the architecture might not be as pure and clean as you would like, but they ship god dammit and in this industry that's what really matters.

If I were you I'd give up on trying to be this rockstar and focus on shipping and building product. You shouldn't judge your contribution by how clever your code is, you should judge it by how many people run it everyday and are happy.


问:
How Much Logic in Getters
My coworkers tell me there should be as little logic as possible in getters and setters.

Yet, I am convinced that a lot of stuff can be hidden in getters and setters to shield users/programmers from implementation details.

An example of what I do:

```<code>public List<Stuff> getStuff()
{
   if (stuff == null || cacheInvalid())
   {
       stuff = getStuffFromDatabase();
   }
   return stuff;
}
</code>```

An example of how work tells me to do things (they quote 'Clean Code' from Uncle Bob):

```<code>public List<Stuff> getStuff()
{
    return stuff;
}

public void loadStuff()
{
    stuff = getStuffFromDatabase();
}
</code>```

How much logic is appropriate in a setter/getter? What's the use of empty getters and setters except a violation of data hiding?

答:
A getter which invokes other properties and methods in order to compute its own value also implies a dependency. Eg, if your property has to be able to compute itself, and doing so requires another member to be set, then you have to worry about accidental null-references if your property is accessed in initialization code where all members are not necessarily set.

That doesn't mean 'never access another member that isn't the properties backing field within the getter' it just means pay attention to what you are implying about what the required state of the object is, and if that matches the context you expect this property to be accessed in.

However, in the two concrete examples you gave, the reason I would choose one over the other is entirely different. Your getter is initialized on first access, eg, Lazy Initialization. The second example is assumed to be initialized at some prior point, eg, Explicit Initialization.

When exactly initialization occurs may or may not be important.

For example it could be very very slow, and needs to be done during a load step where the user is expecting a delay, rather than performance unexpectedly hiccuping when the user first triggers access (ie, user right clicks, , context menu appears, user has already right clicked again).

Also, sometimes there is an obvious point in execution where everything that can affect/dirty the cached property value occurs. You may even be verifying that none of the dependencies change and throwing exceptions later on. In this situation it makes sense to also cache the value at that point, even if it isn't particularly expensive to compute, just to avoid making the code-execution more complex and harder to follow mentally.

That said, Lazy Initialization makes a lot of sense in a lot of other situations. So, as often happens in programming its hard to boil down to a rule, it comes down to the concrete code.

Title: How Much Logic in Getters


问:
What optimizations can be done for soft real-time code in C#?
I'm writing a soft real-time application in C#. Certain tasks, like responding to hardware requests coming in from a network, needs to be finished within a certain amount of milliseconds; however it is not 100% mission-critical to do so (i.e. we can tolerate it being on time most of the time, and the 1% is undesirable but not a failure), hence the "soft" part.

Now I realize that C# is a managed language, and managed languages aren't particularly suited for real-time applications. However, the speed in which we can get things done in C#, as well as the language features, like reflection and memory management, make the task of building this application much easier.

Are there any optimizations or design strategies one can take to reduce the amount of overhead and increase determinism? Ideally I would have the following goals

Delay the garbage collection until it is "safe"

Allow the garbage collector to work without interfering with real-time processes

Thread/process priorities for different tasks

Are there any ways to do these in C#, and are there any other things to look out for with regards to real-time when using C#?

The platform target for the application is .NET 4.0 Client Profile on Windows 7 64-bit, with. I've set it currently to Client profile but this was just the default option and wasn't chosen for any particular reason.

答:
Delay the garbage collection until it is "safe"

You can do that, by setting the GC latency mode to LowLatency. For some more info, see this answer on SO.


问:
Tweaking a ranking algorithm from a few variables
I'm going to have a mySQL table with elements in it and would like to rank them in the same manner than Reddit but not quite. I'd like to know how to add or remove importance to a variable in my ranking algorithm.

For instance, what I have is a time (a timestamp, so a huge value) and a number of upvotes (a smallish value, under 50). How do I give more importance to the upvotes and less to the time?

答: Multiply each value with a weight, the timestamp will be small while the number of upvotes will be large. </p>


答:
A standard is a technical document specifying how a technology behaves. (For some technologies, it may be some other kind of technical standard.) That's all they are and why they exist: they are documents, and they describe the technology.

These documents are authored by a governing body which has the authority and trust necessary for them to be able to decide how that technology works, and for people to care when they release a specification document as a standard. A governing body could produce many standards, for different technologies or different versions of a technology. The governing body could also be known as maintainers, authors, custodians, etc of the standards.

(Contrast to what Mathew describes, a standard is not the governing body nor the technology itself. It's a document describing the technology, or a particular version of it.)

Some example standards for technologies you've mentioned (and others):

The SOAP standard, maintained by W3C.

The URI standard, defined in STD66, maintained by the Internet Engineering Task Force (IETF), who also work on...

The HTTP 1.1 Specifications, authored by the HTTP Working Group. These are Requests For Comment (RFCs), but nevertheless specify how HTTP works. These standards are actually very new, only having been released in June 2014. HTTP 1.1 was previously defined in RFC 2616, by the IETF Network Working Group.

HTML's specifications, defined in the HTML Living Standard. It's authored by the Web Hypertext Application Technology Working Group (WHATWG). W3C republishes and forks various versions of this standard, releasing them as HTML 4, XHTML 1.0, and HTML5 among other versions. WHATWG is unhappy about them doing this.

Java has a standard, maintained by Oracle. Its various versions have different standards, and you can download the Java EE 7 standard yourself.

The C# Language Specification 5.0, authored by a team at Microsoft. Previous versions have their own separate specification documents.

HTML is a good example of the fact that different versions of a language will often have different standards. The various versions have different documents describing how various versions of the language ought to be handled.

HTTP, meanwhile, is one of the many examples of a standard moving between groups: first by the Network Working Group, then to the HTTP Working Group, though both groups were part of the IETF. Other technologies have moved between companies, such as HTML (again), version 2 of which was authored by the IETF in RFC1866.

Why do standards exist?

They exist to give us a guarantee of how things will work.

The HTML5 specification tells me how the various browsers will handle and display the HTML5 markup I write, assuming they implement the standard correctly (which has historically been a problem). The C++11 standard will tell me things about what various C++11 code I write will or won't do.

Likewise, if I'm writing a browser, the HTML5 standard will tell me how I need to handle various pieces of HTML5 markup so that people get what they expect. If I'm writing a C++11 compiler, the C++11 standard will tell me what I need to do to implement the language correctly and get peoples' code working the way they expect it to work.

For instance, Microsoft authors C#. You can download the C# Language Specification 5.0 for yourself. This document is a promise that the C# code you write ought to behave the way it's described in the specification, in any compiler that actually implements the specification correctly.

(If you do things outside the specification, you're in undefined territory and there's no guarantee whatsoever about what will or won't happen.)

Historically, standards go back to things like screw threads, so that I can have some guarantee that if I order a screw of type X, it will fit in the hole I've drilled, and will be interchangeable with other screws of type X.

Which brings us back to the definition of the word "standard":

an accepted or approved example of something against which others are judged or measured — Collins Dictionary

An acknowledged measure of comparison for quantitative or qualitative value; a criterion. — The American Heritage® Stedman's Medical Dictionary

i.e. the thing you compare your stuff to to make sure you'll get what you expect.

Title: What does it mean when some technology is a "standard"?

Body:
I started learning Java EE 7 and I am frequently coming across this term "standard", and I don't understand what it means.

So, for example, here is a quotation from this book:

Contrary to SOAP and the WS-* stack, which rely on W3C standards, REST
  has no standard and is just a style of  architecture with design
  principles. REST applications rely heavily on many other standards:
  HTTP, URI, URL...

I have some idea of what that might mean, but I'm not sure.

The best explanation that I have come across is the definition from here.


问:
What's wrong with comments that explain complex code?
A lot of people claim that "comments should explain 'why', but not 'how'". Others say that "code should be self-documenting" and comments should be scarce. Robert C. Martin claims that (rephrased to my own words) often "comments are apologies for badly written code".

My question is the following:

What's wrong with explaining a complex algorithm or a long and convoluted piece of code with a descriptive comment?

This way, instead of other developers (including yourself) having to read the entire algorithm line by line to figure out what it does, they can just read the friendly descriptive comment you wrote in plain English.

English is 'designed' to be easily understood by humans. Java, Ruby or Perl, however, have been designed to balance human-readability and computer-readability, thus compromising the human-readability of the text. A human can understand a piece of English much faster that he/she can understand a piece of code with the same meaning (as long as the operation isn't trivial).

So after writing a complex piece of code written in a partly human-readable programming language, why not add a descriptive and concise comment explaining the operation of the code in friendly and understandable English?

Some will say "code shouldn't be hard to understand", "make functions small", "use descriptive names", "don't write spaghetti code".

But we all know that's not enough. These are mere guidelines - important and useful ones - but they do not change the fact that some algorithms are complex. And therefore are hard to understand when reading them line by line.

Is it really that bad to explain a complex algorithm with a few lines of comments about it's general operation? What's wrong with explaining complicated code with a comment?

答:
In layman's terms:

There's nothing wrong with comments per se. What's wrong is writing code that needs those kind of comments, or assuming that it's OK to write convoluted code as long as you explain it friendly in plain English.

Comments don't update themselves automatically when you change the code. That's why often times comments are not in sync with code.

Comments don't make code easier to test.

Apologizing is not bad. What you did that requires apologizing for (writing code that isn't easily understandable) is bad.

A programmer that is capable of writing simple code to solve a complex problem is better than one that writes complex code and then writes a long comment explaining what his code does.

Bottom line:

Explaining yourself is good, not needing to do so is better.

ContentLicense: CC BY-SA 4.0


答:
But we all know that's not enough.

Really? Since when?

Well designed code with good names is more than enough in the vast majority of cases. The arguments against using comments are well known and documented (as you refer to).

But these are guidelines (like anything else). In the rare case (in my experience, a about once every 2 years) where things would be worse when refactored into smaller legible functions (due to performance or cohesion needs) then go ahead - put in some lengthy comment explaining what the thing is actually doing (and why you're violating best practices).

Title: What's wrong with comments that explain complex code?

Body:
A lot of people claim that "comments should explain 'why', but not 'how'". Others say that "code should be self-documenting" and comments should be scarce. Robert C. Martin claims that (rephrased to my own words) often "comments are apologies for badly written code".

My question is the following:

What's wrong with explaining a complex algorithm or a long and convoluted piece of code with a descriptive comment?

This way, instead of other developers (including yourself) having to read the entire algorithm line by line to figure out what it does, they can just read the friendly descriptive comment you wrote in plain English.

English is 'designed' to be easily understood by humans. Java, Ruby or Perl, however, have been designed to balance human-readability and computer-readability, thus compromising the human-readability of the text. A human can understand a piece of English much faster that he/she can understand a piece of code with the same meaning (as long as the operation isn't trivial).

So after writing a complex piece of code written in a partly human-readable programming language, why not add a descriptive and concise comment explaining the operation of the code in friendly and understandable English?

Some will say "code shouldn't be hard to understand", "make functions small", "use descriptive names", "don't write spaghetti code".

But we all know that's not enough. These are mere guidelines - important and useful ones - but they do not change the fact that some algorithms are complex. And therefore are hard to understand when reading them line by line.

Is it really that bad to explain a complex algorithm with a few lines of comments about it's general operation? What's wrong with explaining complicated code with a comment?


问:
Algorithms for making image mosaics - is there a quicker way than this?
I've been playing with making image mosaics.  My script takes a large number of images, scales them down to thumbnail size and then uses them as tiles to approximate a target image.

The approach is actually quite pleasing:

I compute the mean square error for every thumb in every tile position.

At first I just used a greedy placement: put the thumb with the least error on the tile it best fits, and then the next and so on.

The problem with greedy is that it leaves you eventually placing the most different thumbs on the least popular tiles, whether they match closely or not.  I show examples here:
http://williamedwardscoder.tumblr.com/post/84505278488/making-image-mosaics

So I then do random swaps until the script is interrupted.  The results are quite OK.

A random swap of two tiles is not always an improvement, but sometimes a rotation of three or more tiles results in a global improvement i.e. A <-> B may not improve, but A -> B -> C -> A1 may..

For this reason, after picking two random tiles and discovering they do not improve, I pick a bunch of tiles to evaluate if they can be the third tile in such a rotation.  I do not explore if any set of four tiles can be profitably rotated, and so on; that'd be super-expensive real soon.

But this takes time.. A lot of time!

Is there a better and faster approach?

Bounty Update

I tested out various Python implementations and bindings of the Hungarian Method.

By far the fastest was the pure-Python https://github.com/xtof-durr/makeSimple/blob/master/Munkres/kuhnMunkres.py

My hunch is that this approximates the optimal answer; when run on a test image, all other libraries agreed on the result but this kuhnMunkres.py, whilst being orders of magnitude faster, only got very very very close to the score the other implementations agreed on.

Speed is very data-dependent; Mona Lisa rushed through kuhnMunkres.py in 13 minutes, but the Scarlet Chested Parakeet took 16 minutes.

Results were much the same as random swaps and rotations for the Parakeet:

(kuhnMunkres.py on the left, random swaps on the right; original image for comparision)

However, for the Mona Lisa image I tested with, the results were noticeably improved and she actually had her defined 'smile' shining through:

(kuhnMunkres.py on the left, random swaps on the right)

答:
I'm reasonably sure that's an NP-hard problem. To find a 'perfect' solution you have to try every possibility exhaustively, and that is exponential.

One approach would be to use the greedy fit and then try to improve it. That could be by taking a badly placed image (one of the last ones) and finding another place to put it, then taking that image and moving it and so on. You are done when you (a) run out of time (b) the fit is 'good enough'.

If you introduce a probabilistic element it might yield to a simulated annealing approach, or a genetic algorithm. Perhaps all you're trying to achieve is to spread the errors evenly. I suspect this is getting close to what you're already doing so the answer is: with the right algorithm you may get a better result faster but there is no magic shortcut to Nirvana.

Yes, this is similar to what you're already doing. The point is to forget a magic answer and to think in terms of 2 algorithms: first fill, then optimise.

The fill could be: random, best available, first best, good enough, some kind of hot spot.

The optimise could be random, fix the worst, or (as I suggested) simulated annealing or genetic algorithm.

You need a metric of 'goodness' and an amount of time you're prepared to spend on it and just experiment. Or find someone who has actually done it.


答:
So what's wrong with explaining complicated code with a comment?

It's not a question of right or wrong, but of the 'best practice', as defined in Wikipedia article:

A best practice is a method or technique that has consistently shown
  results superior to those achieved with other means, and that is used
  as a benchmark.

So the best practice is to try to improve the code first, and to use English if that is not possible.

It's not a law, but it's much more common to find commented code that requires refactoring than refactored code that requires comments, the best practice reflects this.


问:
On concatenating adjacent string literals
C and C++ compiles adjacent string literals as a single string literal. For example this:

```<code>"Some text..." "and more text"
</code>```

is equivalent to:

```<code>"Some text...and more text"
</code>```

In other C-family languages like C# or Java, this is a syntax error (which is perfectly fine BTW).

What is the rationale/historical reason for C and C++ to do this?

答:
C has no specific string concatenation operator (+) like C# and Java. In C# or Java, when the compiler sees

```<code>"a" + "b"
</code>```

it can compile the code exactly as if

```<code>"ab"
</code>```

were written in the source code. In C, however, there is no similarly easy syntax for describing concatenation of strings that the compiler can recognise and pre-calculate. So the designers of C decades ago chose that

```<code>"a" "b"
</code>```

would mean exactly the same thing as

```<code>"ab"
</code>```

Naturally C++ inherited the same convention. While the standard C++ library overloads + on std::string to mean string concatenation, the compiler does not attempt to coalesce "a" + "b" because that is actually an error (you can't add two const char * pointers together).

Body:
C has no specific string concatenation operator (+) like C# and Java. In C# or Java, when the compiler sees

"a" + "b"

it can compile the code exactly as if

"ab"

were written in the source code. In C, however, there is no similarly easy syntax for describing concatenation of strings that the compiler can recognise and pre-calculate. So the designers of C decades ago chose that

"a" "b"

would mean exactly the same thing as

"ab"

Naturally C++ inherited the same convention. While the standard C++ library overloads + on std::string to mean string concatenation, the compiler does not attempt to coalesce "a" + "b" because that is actually an error (you can't add two const char * pointers together).


答:
Does the second code have some problem?

Yes, two.

You are making it into the equivalent of a public field and thereby fixing and revealing the implementation. It breaks encapsulation and locks you in.

You miss the opportunity to ensure that your object's state is always valid, especially on the setter.

In my view the only legitimate reason to use a setter is that it should be viewed as an instruction to the object: "Please change your name to be XXX". The object should actively participate in the change, by (for example) parsing the name, checking it for validity, checking that it is consistent with other internal state, and perhaps by raising an exception if it is invalid. In debug mode you can also run extended validation checks on both getter and setter. When you expose the object itself you lose all that.

But of course getters and setters are evil. Really you should change object state only by asking the object to carry out some function, to which the internal state is merely incidental.

In response to your amended question, yes your example is a breach of encapsulation. Any time you ask an object for access to some other object you assume knowledge and you violate tell-dont-ask. Whether that matters depends on the semantics and in your example, it matters.

Title: Is this a good design in C++?

Body:
Is it a good idea to replace getters and setters with a single function returning a reference?
For example, instead of this,

```<code>class Person {
  std::string name;
public:
  std::string GetName() { return this->name; }
  void SetName(std::string& toSet) { this->name = toSet; }
};
</code>```

Is this a good idea,

```<code>class Person {
  std::string name;
public:
  std::string& Name() { return this->name; }
};
...
...
Person p;
p.Name() = "Joe"; // Write.
std::string local = p.Name(); // Read.
</code>```

Does the second code have some problem?

But in C#, methods return object by reference. For example,

```<code>class Person
{
    string name;
    public Person(string _name) { this.name = _name;  }
    public string GetName()
    {
        return this.name;
    }
    public void SetName(string _name)
    {
        this.name = _name;
    }
};

class Company
{
    Person manager;
    public Company()
    {
        this.manager = new Person("Mr. K");
    }

    // The Person object is returned by reference.
    // This is equivalent to "Person& GetManager()" in C++.
    public Person GetManager()
    {
        return this.manager;
    }
};
...
...
Company comp = new Company();

// Equivalent to,
// Person& p = comp.GetManager();
Person p = comp.GetManager(); // p is a reference to comp.manager
p.SetName("Mr. L");  // This statement changes comp.manager.name

Console.WriteLine(comp.GetManager().GetName()); // Prints "Mr. L"
</code>```

In the above code, comp.manager.name wouldn't have changed if the method GetManager() returned Person by value. So, this code isn't dependent on return value optimization.
Isn't this code a violation of encapsulation?


问:
Separation of concerns between objects
I have two objects which work together to provide interaction with HIDs on a machine.  One object is responsible for the communication (read/write) to the HID and the other object is responsible for modelling the HID.  Information is read and written to the HID as byte arrays.

As a contrived example:

```<code>class Hid
{
  private HidComms comms;

  public DateTime? GetPropertyB()
  {
    return comms.GetPropertyB();
  }
}

class HidComms
{
  public DateTime? GetPropertyB()
  {
    // request property B from HID
    // get 1 or more byte[] in response
    return new DateTime();
  }
}
</code>```

Which of these two objects should be responsible for encoding/decoding the byte arrays, or should a third object be responsible for this?  Meaning the Hid object only knows about state and the HidComms object only knows how to read/write with a third object responsible for the conversion?

答:
The usual principle of encapsulation (that implementation detail should be confined to as little code as practical) applies here. The information about encoding and decoding the byte arrays should be restricted to one class without a good reason to share it further.

The more obvious way to arrange this is for HidComms to translate the byte arrays to and from some higher-level representation.

The less obvious way is for HidComms to handle (but not understand) byte arrays going to and from the HID, while Hid (or a third class) does the encoding and decoding.

Both approaches are equally valid. They differ mainly in how you treat encoding/decoding errors.

Title: Separation of concerns between objects


答:
The principal purpose of code is commanding a computer to do something, so a good comment is never a substitute for good code because comments can't be executed.

That being said, comments in the source are one form of documentation for other programmers (including yourself). If the comments are about more abstract issues than what the code is doing at every step, you're doing better than average. That level of abstraction varies with the tool you're using. Comments accompanying assembly language routines generally have a lower level of "abstraction" than, for example, this APL A←0⋄A⊣{2⊤⍵:1+3×⍵⋄⍵÷2}⍣{⍺=A+←1}⎕. I think that would probably merit a comment about the problem it's intended to solve, hmmm?


问:
Parameterized Java Types (Generics)
Consider this "legacy" code:

```<code>public interface IPersistentCollection {
    IPersistentCollection cons(Object o);
}
</code>```

Genericized in Java, it could become something like this:

```<code>public interface IPersistentCollection<T> {
    IPersistentCollection<T> cons(T o);
}
</code>```

Clearly adding a new item to a mutable Java collection shouldn't change the type of the existing collection.  But unlike the Java collections, cons() returns a completely new, immutable collection, leaving the old collection unchanged, opening the possibility that it could meaningfully take on a different type than the original collection had.

Obviously, you should be able to cons an object of type Ford to a collection of Cars and get a collection of Cars back (covariance).  I think this is covered by the above generic example.

If Car and Train both extended a Vehicle class, it would be handy to be able to cons a Train to a collection of Cars and get a collection of Vehicles back (contravariance).  How would I even write that?  I thought by declaring new bounded type variables, S and E for "Vehicle" and "Train" in this example:

```<code>// Illegal because of <S super T>
<S super T, E extends S> IPersistentCollection<S> cons(E o);

// Simpler, but still Illegal because java disallows <S super T>
<S super T> IPersistentCollection<S> cons(S o);
</code>```

If we want to assume that the programmer knows what they are doing, you should be allowed to cons something totally unrelated to a collection and get a collection of Objects back.  I think this is the extreme case of contravariance, but I'm not sure there is even a name for it ("Dynamic Language" maybe?).

I think that if #2 were legal, it would cover cases #1 and #3.

My questions are:

A. To what degree is it possible to do #2 in Java?

B. Is #2 possible/easier in other languages?  Scala?  Haskell? ML?

C. In theory, a type system that preferred the most specific version of S in example 2 could handle a definition like this.  What book can I read about type systems without a PHD in math?  Is "Types and Programming Languages" by Pierce the best place to start?

Sample code would be appreciated.  If I'm using terms like covariance and contravariance incorrectly, I would appreciate being politely corrected.

答:
Angelika Langer is my new hero.  She has an incredible Java Generics FAQ
http://www.angelikalanger.com/GenericsFAQ/FAQSections/TypeParameters.html#FAQ107

She had the insight "class Box<T super Number> {...} is not permitted"... and "conjunctions with method declarations, type parameters with a lower bound would occasionally be useful."  Wow!  A.) I'm not wasting my time trying the impossible and B.) there is a chance that what I'm trying to do might be useful!

She suggests the workaround of using a static method as follows:

```<code>static <A, B, X extends A, Y extends B>
        B addToMap(Pair<X,Y> pair, Map<A,B> map) {
    return map.put(pair.first,pair.second);
}
</code>```

I was able to apply that directly to a static method in my interface, which worked!

```<code>@SuppressWarnings("unchecked")
static <S, E extends S, T extends S> Consable<S> cons(Consable<T> cs, E e) {
    return Consable3.of((S) e, (Consable<S>) cs);
}
</code>```

For a short time I thought that this same technique can be applied to an instance method, but it cannot:

```<code>public static interface Consable<T> {
    // T is the type of our existing collection (defined above)
    // E is the new element being cons-ed with our collection
    // S is a super-type of both T and E and therefore the
    //   type of our new collection.
    <S, E extends S, T extends S> Consable<S> cons(E e);
}

...

class Animal {}
class Mammal extends Animal {}

...

// Consable<Vehicle> vehicles = cars.cons(new Train());
Consable<Animal> vehicles = cars.cons(new Mammal());
</code>```

Commenting out cons-ing things to the vehicles, That compiles!  Eek!  And runs!

```<code>$ javac -Xlint JavaConsSignature.java
$ java JavaConsSignature
JavaConsSignature$Mammal@15db9742
JavaConsSignature$Car@6d06d69c
JavaConsSignature$Chevy@7852e922
JavaConsSignature$Chevy@4e25154f
JavaConsSignature$Chevy@70dea4e
</code>```

So static method: Good.  Instance method: Bad.  It doesn't support fluent interface building, but at least you can have this particular kind of type safety on some kind of method in Java.

Title: Parameterized Java Types (Generics)

Body:
Angelika Langer is my new hero.  She has an incredible Java Generics FAQ
http://www.angelikalanger.com/GenericsFAQ/FAQSections/TypeParameters.html#FAQ107

She had the insight "class Box<T super Number> {...} is not permitted"... and "conjunctions with method declarations, type parameters with a lower bound would occasionally be useful."  Wow!  A.) I'm not wasting my time trying the impossible and B.) there is a chance that what I'm trying to do might be useful!

She suggests the workaround of using a static method as follows:

static <A, B, X extends A, Y extends B>
        B addToMap(Pair<X,Y> pair, Map<A,B> map) {
    return map.put(pair.first,pair.second);
}

I was able to apply that directly to a static method in my interface, which worked!

@SuppressWarnings("unchecked")
static <S, E extends S, T extends S> Consable<S> cons(Consable<T> cs, E e) {
    return Consable3.of((S) e, (Consable<S>) cs);
}

For a short time I thought that this same technique can be applied to an instance method, but it cannot:

public static interface Consable<T> {
    // T is the type of our existing collection (defined above)
    // E is the new element being cons-ed with our collection
    // S is a super-type of both T and E and therefore the
    //   type of our new collection.
    <S, E extends S, T extends S> Consable<S> cons(E e);
}

...

class Animal {}
class Mammal extends Animal {}

...

// Consable<Vehicle> vehicles = cars.cons(new Train());
Consable<Animal> vehicles = cars.cons(new Mammal());

Commenting out cons-ing things to the vehicles, That compiles!  Eek!  And runs!

$ javac -Xlint JavaConsSignature.java
$ java JavaConsSignature
JavaConsSignature$Mammal@15db9742
JavaConsSignature$Car@6d06d69c
JavaConsSignature$Chevy@7852e922
JavaConsSignature$Chevy@4e25154f
JavaConsSignature$Chevy@70dea4e

So static method: Good.  Instance method: Bad.  It doesn't support fluent interface building, but at least you can have this particular kind of type safety on some kind of method in Java.


答:
There's a bunch of different reasons for code to be complicated or confusing.  The most common reasons are best addressed by refactoring the code to make it less confusing, not by adding comments of any kind.

However, there are cases where a well-chosen comment is the best choice.

If it is the algorithm itself that is complicated and confusing, not just its implementation—the kind that get written up in math journals and are ever after referred to as Mbogo's Algorithm—then you put a comment at the very beginning of the implementation, reading something like "This is Mbogo's Algorithm for refrobnicating widgets, originally described here: [URL of paper].  This implementation contains refinements by Alice and Carol [URL of another paper]."  Don't try to go into any more detail than that; if someone needs more detail they probably need to read the entire paper.

If you have taken something that can be written as one or two lines in some specialized notation and expanded it out into a big glob of imperative code, putting those one or two lines of specialized notation in a comment above the function is a good way to tell the reader what it's supposed to do.  This is an exception to the "but what if the comment gets out of sync with the code" argument, because the specialized notation is probably much easier to find bugs in than the code.  (It's the other way around if you wrote a specification in English instead.)  A good example is here: https://dxr.mozilla.org/mozilla-central/source/layout/style/nsCSSScanner.cpp#1057 ...

```<code>/**
 * Scan a unicode-range token.  These match the regular expression
 *
 *     u\+[0-9a-f?]{1,6}(-[0-9a-f]{1,6})?
 *
 * However, some such tokens are "invalid".  There are three valid forms:
 *
 *     u+[0-9a-f]{x}              1 <= x <= 6
 *     u+[0-9a-f]{x}\?{y}         1 <= x+y <= 6
 *     u+[0-9a-f]{x}-[0-9a-f]{y}  1 <= x <= 6, 1 <= y <= 6
</code>```

If the code is straightforward overall, but contains one or two things that look excessively convoluted, unnecessary, or just plain wrong, but have to be that way because of reasons, then you put a comment immediately above the suspicious-looking bit, in which you state the reasons.  Here's a simple example, where the only thing that needs explaining is why a constant has a certain value.

```<code>/* s1*s2 <= SIZE_MAX if s1 < K and s2 < K, where K = sqrt(SIZE_MAX+1) */
const size_t MUL_NO_OVERFLOW = ((size_t)1) << (sizeof(size_t) * 4);
if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
    nmemb > 0 && SIZE_MAX / nmemb < size)
  abort();
</code>```

Body:
There's a bunch of different reasons for code to be complicated or confusing.  The most common reasons are best addressed by refactoring the code to make it less confusing, not by adding comments of any kind.

However, there are cases where a well-chosen comment is the best choice.

If it is the algorithm itself that is complicated and confusing, not just its implementation—the kind that get written up in math journals and are ever after referred to as Mbogo's Algorithm—then you put a comment at the very beginning of the implementation, reading something like "This is Mbogo's Algorithm for refrobnicating widgets, originally described here: [URL of paper].  This implementation contains refinements by Alice and Carol [URL of another paper]."  Don't try to go into any more detail than that; if someone needs more detail they probably need to read the entire paper.

If you have taken something that can be written as one or two lines in some specialized notation and expanded it out into a big glob of imperative code, putting those one or two lines of specialized notation in a comment above the function is a good way to tell the reader what it's supposed to do.  This is an exception to the "but what if the comment gets out of sync with the code" argument, because the specialized notation is probably much easier to find bugs in than the code.  (It's the other way around if you wrote a specification in English instead.)  A good example is here: https://dxr.mozilla.org/mozilla-central/source/layout/style/nsCSSScanner.cpp#1057 ...

/**
 * Scan a unicode-range token.  These match the regular expression
 *
 *     u\+[0-9a-f?]{1,6}(-[0-9a-f]{1,6})?
 *
 * However, some such tokens are "invalid".  There are three valid forms:
 *
 *     u+[0-9a-f]{x}              1 <= x <= 6
 *     u+[0-9a-f]{x}\?{y}         1 <= x+y <= 6
 *     u+[0-9a-f]{x}-[0-9a-f]{y}  1 <= x <= 6, 1 <= y <= 6

If the code is straightforward overall, but contains one or two things that look excessively convoluted, unnecessary, or just plain wrong, but have to be that way because of reasons, then you put a comment immediately above the suspicious-looking bit, in which you state the reasons.  Here's a simple example, where the only thing that needs explaining is why a constant has a certain value.

/* s1*s2 <= SIZE_MAX if s1 < K and s2 < K, where K = sqrt(SIZE_MAX+1) */
const size_t MUL_NO_OVERFLOW = ((size_t)1) << (sizeof(size_t) * 4);
if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
    nmemb > 0 && SIZE_MAX / nmemb < size)
  abort();


答:
I think you're reading a little bit too much in to what he's saying. There are two distinct parts to your complaint:

What's wrong with explaining (1) a complex algorithm or (2) a long and convoluted piece of code with a descriptive comment?

(1) is inevitable. I don't think that Martin would disagree with you. If you're writing something like the fast inverse square root, you're going to need some comments, even if it's just "evil floating point bit level hacking." Barring something simple like a DFS or binary search, it's unlikely that the person reading your code will have experience with that algorithm, and so I think there should be at least a mention in the comments about what it is.

Most code isn't (1), however. Rarely will you write a piece of software that's nothing but hand-rolled mutex implementations, obscure linear algebra operations with poor library support, and novel algorithms known only to your company's research group. Most code consists of library/framework/API calls, IO, boilerplate, and unit tests.

This is the kind of code that Martin is talking about. And he addresses your question with the quote from Kernighan and Plaugher at the top of the chapter:

Don’t comment bad code—rewrite it.

If you have long, convoluted sections in your code, you have failed to keep your code clean. The best solution to this problem isn't to write a paragraph-long comment at the top of the file to help future developers muddle through it; the best solution is to rewrite it.

And this is exactly what Martin says:

The proper use of comments is to compensate for our failure to express ourself in code...Comments are always failures. We must have them because we cannot always figure out how to express ourselves without them, but their use is not a cause for celebration.

This is your (2). Martin agrees that long, convoluted code does need comments -- but he puts the blame for that code on the shoulders of the programmer who wrote it, not some nebulous idea that "we all know that's not enough." He argues that:

Clear and expressive code with few comments is far superior to cluttered and complex code with lots of comments. Rather than spend your time writing the comments that explain the mess you’ve made, spend it cleaning that mess.


答: For legal product liability the defect are classed as design, manufacture or documentation. A design is not defective if it is based on a standard, whether or not that standard is defective. The standard that applies is that in place when the product was created. A standard may be a published standard (ISO) or an accepted industry standard that is not published by the standards association. So TCP/IP with all its inherent defects like spoofing is a standard and if you create a new technology like VOIP and don't do anything to protect the user from known problems with the underlying technology then you are safe to continue the mayhem. Or I may be wrong and have a documentation defect here...</p>


问:
Redundancy caused by polymorphism
I have two chat rooms, one has administration behaviour, and one doesn't.  I have factored out all of the common code into a base chat room, but the AdministerChatroom behaviour I have pulled out into an interface called IAdministrable and it sits on the base chatroom class.

My issue is that because the interface is on the base class, which allows for the behaviour to polymorphic, the NonAdministratableChatroom chatroom class must implement that behaviour even though it will do nothing.

I have seen some developers put the interface on only one subclass: the class that has the behaviour, in this case the AdministerChatroom method, and when a chatroom is being used, they simply check the existence of the the IAdministrable interface, something like if(Chatroom is IAdministrable){ // do something }, which seems like a violation of the "tell don't ask" principle.

I seem to have two choices: I stick to the polymorphic strategy pattern, or I test the instance for an interface; the former seems preferable but I am wondering if there are any other options?

The code for the classes is as follows:

```<code>public interface IAdministrable
{
    void AdministerChatroom();
}

public abstract class BaseChatRoom : IAdministrable
{
    public void Close()
    {
    }

    public abstract void AdministerChatroom();
}

public class AdministrableChatroom : BaseChatRoom
{
    private readonly Administrator _administrator;

    public AdministrableChatroom(Administrator administrator)
    {
        _administrator = administrator;
    }

    public override void AdministerChatroom()
    {
        _administrator.DoSomethingSpecial();
    }
}

public class NonAdministratableChatroom : BaseChatRoom
{
    public override void AdministerChatroom()
    {
        // do nothing as this is not administrable
    }
}

public class Participant
{

}

public class Administrator : Participant
{
    public void DoSomethingSpecial()
    {
        // implement something special here
    }
}
</code>```

答:
It annoys me that object-oriented design education focuses almost exclusively on designing object hierarchies and almost completely neglects the structure of the other, often larger, side of object-oriented programs:  the calling code.

The answer is to put the interface on only one subclass, and structure the calling code so all the calling code either doesn't care which subclass it is acting against, or always already knows it implements your administrable interface.

In other words, at some point some of your code will want to call AdministerChatroom.  That should either be from within another method of the AdministrableChatroom object, or from a collection or event handler somewhere that only has a reference to an IAdministrable.  If your calling code isn't structured that way, it needs refactoring.  If you need help with the refactoring, you need to post more details of your calling code.

OwnerDisplayName: nickbw

Title: Redundancy caused by polymorphism


问:
How to let the outside world decorate my private field?
Imagine a simple Controller  (as in process control) interface. I have some concrete classes, say PIDController, that implement it. I also have some decorator classes that extend these classes somehow, say ITAETuningDecorator.

Now imagine that a FloodGate class has a private Controller field. I would like, from the outside and at runtime, to attach to the Controller in FloodGate an ITAETuningDecorator. How can I do it? I have no access to the field from the outside and obviously the decorator needs a reference to the original controller to be built.

答:
The question is: Who instantiates the Controller?

If it's created outside the FloodGate instance, you can wrap it there and pass the wrapped instance into the FloodGate.

If it's created by the FloodGate internally (which seems strange to me, but I'm not into your domain), you could either change that and pass it in (e.g. as a constructor parameter) or add a method addControllerDecorator(Controller c) to the FloodGate. The latter implies that you can instantiate the wrapper and later set the instance it wraps, which looks like a poor design choice to me...


答:
The "outside world" code could use reflection (the nasty kind) to access and / or update the private field.

But a better idea (IMO) would modify your APIs to provide access to the fields that you want to decorate.  This could take the form of a getters and / or setters, or it could be more specialized methods that add and (if necessary) remove the decorations.  In short "decoratibility" should be part of the API.

Title: How to let the outside world decorate my private field?

Body:
Imagine a simple Controller  (as in process control) interface. I have some concrete classes, say PIDController, that implement it. I also have some decorator classes that extend these classes somehow, say ITAETuningDecorator.

Now imagine that a FloodGate class has a private Controller field. I would like, from the outside and at runtime, to attach to the Controller in FloodGate an ITAETuningDecorator. How can I do it? I have no access to the field from the outside and obviously the decorator needs a reference to the original controller to be built.


问:
Long Keywords like `function` and `namespace`
In many English-based programming languages like C++ and JavaScript, there exist long keywords like function, namespace, exception (in OCaml languages) and such. Do you think shorter keywords like func should replace them? Why or why not? What about replacing them with digraph operators?

The long keywords we will be mainly talking about, but not limited to, are mainly from curly-brace imperative languages: function, namespace, implements, instanceof and synchronized (I always misspell that).
You should also show the examples from your favourite programming language.

答:
I accept keywords like func and cons in functional languages, because functional languages tend to be math-like and more symbolic.

But in imperative, object oriented languages, where you are telling the computer how to do something as well as what to do,  I prefer that the identifiers and keywords be whole words.

Any fool can write code that a computer can understand.  Good programmers write code that humans can understand.  ~Martin Fowler


问:
Single responsibility: how does this code cause problems?
Given the following interface

```<code>interface Modem {
    public void Dial(string pno);
    public void Hangup();
    public void Send(char c);
    public char Recv();
}
</code>```

Uncle Bob writes

However, there are two responsibilities being shown here. The first responsibility is
  connection management. The second is data communication.

...

Should these two responsibilities be separated? That depends upon how the application
  is changing. If the application changes in ways that affect the signature of the connection
  functions, then the design will smell of Rigidity because the classes that call send
  and read will have to be recompiled and redeployed more often than we like.

Can anyone explain to me how is the highlighted statement true? Why would I have to recompile code that calls the sending/receiving methods if the connection signature changes? I could have injected a ready made connection to the code using it.

答:
Let's say that for some reason we'd like to extend the Dial method to accept a structure

```<code>struct Endpoint
{
    public string pno;
    ...
}

class Modem
{
    public void Dial(Endpoint ep);
    ...
}
</code>```

This would cause the whole class to be recompiled - depending on the language and compiler - hence the Send and Recv are. If you'd adhere to the SRP you could - for example - change you modem class to

```<code>class Modem
{
    void Dial(Endpoint ep);
    void Hangup();
    Stream ConnectionStream();
}
</code>```

with a stream that is responsible for sending and receiving data. This avoids to recompile Send and Recv whenever Modem changes, but only the - very simple - method that returns our stream.

Anyway, I think the main advantage of the SRP is not the fact that some code is not recompiled under some circumstances - I'd gues that it does not really matter that much with the computational power available nowadays - but cleaner and more concise code.

Body:
Let's say that for some reason we'd like to extend the Dial method to accept a structure

struct Endpoint
{
    public string pno;
    ...
}

class Modem
{
    public void Dial(Endpoint ep);
    ...
}

This would cause the whole class to be recompiled - depending on the language and compiler - hence the Send and Recv are. If you'd adhere to the SRP you could - for example - change you modem class to

class Modem
{
    void Dial(Endpoint ep);
    void Hangup();
    Stream ConnectionStream();
}

with a stream that is responsible for sending and receiving data. This avoids to recompile Send and Recv whenever Modem changes, but only the - very simple - method that returns our stream.

Anyway, I think the main advantage of the SRP is not the fact that some code is not recompiled under some circumstances - I'd gues that it does not really matter that much with the computational power available nowadays - but cleaner and more concise code.


答:
instead of other developers (including yourself) having to read the
  entire algorithm line by line to figure out what it does, they can
  just read the friendly descriptive comment you wrote in plain English.

I would consider this a slight abuse of "comments". If the programmer wants to read something instead of the entire algorithm, then that's what function documentation is for. OK, so the function documentation might actually appear in comments in the source (perhaps for extraction by doc tools), but although syntactically it's a comment as far as your compiler is concerned, you should consider them separate things with separate purposes. I don't think "comments should be scarce" is necessarily intended to mean "documentation should be scarce" or even "copyright notices should be scarce"!

Comments in the function are for someone to read as well as the code. So if you have a few lines in your code that are difficult to understand, and you can't make them easy to understand, then a comment is useful for the reader to use as a placeholder for those lines. This could be very useful while the reader is just trying to get the general gist, but there are a couple of problems:

Comments aren't necessarily true, whereas the code does what it does. So the reader is taking your word for it, and this is not ideal.

The reader doesn't understand the code itself yet, so until they come back to it later they still aren't qualified to modify or re-use it. In which case what are they doing reading it?

There are exceptions, but most readers will need to understand the code itself. Comments should be written to assist that, not to replace it, which is why you're generally advised that comments should say "why you're doing it". A reader who knows the motivation for the next few lines of code has a better chance of seeing what they do and how.


问:
Mobile App Development-Architecture/Platform: Main performance concern: device/UI responsiveness
I am currently investigating different alternatives for building a mobile instant messaging application for iOS and Android, using an XMPP server (probably ejabberd) as the back-end. Main requirements are a nice UI and of course good performance on most devices.

I have identified three different alternatives, two of which include using the Marmalade SDK

Option A): Use Marmalade C++, creating the UI with Marmalade Libraries such as IwNUI/INUI. In this option, the UI is created in C++ code. My assumption is that this should be good in performance, however I am not sure how easy it is to achieve a nice, custom UI that has a good/modern feel to it, such as other high-quality apps. Another advantage: This would target iOS/Android with one code base.

Option B): Also Marmalade, using the C++ s3eWebView api to load local web pages packaged in the application package. UI would be designed in these web pages using HTML/CSS/JavaScript. For the application logic, JavaScript or C++ can be used, as there is a JavaScript Bridge (http://docs.madewithmarmalade.com/display/MD/The+Javascript+interface) to communicate between C++ and JavaScript code. Would also target iOS/Android in one go.

Option C): Non-Marmalade: Go with two code bases. Use Objective-C (i.e. "standard way") for iOS, and Google Android SDK for Android. Build the app twice.

I am currently leaning towards Option B, as this would allow for use of one code base, and leverage existing HTML5/CSS/JavaScript technologies (nice especially for UI), together with the ability to use C++. However, my concern is whether device/UI responsiveness will be acceptable with this. I have run some preliminary tests for simple things such as loading CSS3 dropdown menus into an s3eWebView via C++, and this seems fairly responsive (i.e. menu drops down quickly and smoothly).

答:
What do you prefer, using a single codebase for multiple platforms, or fully merge with each platform design requirements and features? Directly use the performance of a native application or deal with the webkit speed and limitations (compared to fully native code)? In my opinion:

A) I haven't tried Marmalade, so I don't know about the performance or anything related IwNUI, but if both interfaces are designed the same way, it may look weird to see interface decisions typical from iOS in Android and viceversa.

B) Similar to A, but with the lack of performance. HTML is easy, yes, but this means adding another layer to application execution. I have tried Cordova and there's no real way you can truly match a native app, neither performance nor design.

C) Do you know Android and iOS enough to code both of them? If you only know one of these two, do that app, monetize and get paid help from one that knows.

If you want to boost a single codebase, go for C++ (Android has NDK, and I guess you can do it your way with iOS too, maybe Marmalade would be enough), but make sure to give true differences to each interface. Otherwise, it may look a poorly designed interface in one of the platforms (or maybe both, if you want to take design decisions from both)