问:
Enterprise application object oriented modeling for user and role
Generally in the Enterprise Applications like ERP or ERM, CRM, BP etc. we see two things a lot, one of them is Role and the other one is User. What happens is that in the real world we have some persons as the Audiences of the Organization and also we have some roles that each person do his duty as that role. Actually each person has his own information in his file, dependent on the role that he has. Notice that one person can has more than one role.

The question is that How can we model this topic as the OO (Object Oriented) viewpoint?

One way is that we have an Inheritance Hierarchy of Users which each one has his own data and his own behaviors (for example in one clinic we have doctor, patient and Secretary that all of them are derived of the user.) User has list of roles. In this case roles are more likely to Enum and does not have any behavior and the main use of them is Access Control.

The problem of this method is that if a real person wants to have different roles and this issue is completely dynamic, modeling of this wouldn’t be clear.

Second method is that we have one user and an Inheritance Hierarchy   of roles that each role has his own duty. We assign this roles to the users. Actually we see the roles in the program and the main operant for us are the roles.

The problem of this method is that for some roles it is necessary that users have other personal information (for example about the doctor the field of study should be defined.) and it is not clear that where we should store these data.

The third method that is not obvious for us is a combination of the two method above.

答:
Firstly, congratulations on recognising that inheritance is a poor choice in this situation. You are 100% correct. Changing the type of an entity at run-time is definitely code smell!

@Doc Brown's answer is getting to the heart of the matter, especially the comment about using Person rather than User, and allowing a 1:many between Person and roles.

What is missing here is the period for which the role is valid. For instance, a doctor may also become a patient in middle age, and the patient role may be valid after he retires as a doctor. Similarly, a person may be an employee several times, and may be a manager for one or more periods. The take-out is that roles are time constrained, and as such require their own entity in the model.

I see you are concerned about complexity, and that is natural. My experience has been that if you get the data modelling 100% correct, then there is little complexity. The special cases that require tens of lines of code just disappear - the model reflects reality. For instance it will be able to answer quite complex queries like "what doctors are still on staff that were staff doctors during the Ebola epidemic in 2014?"

The guru in this modelling area is Peter Coad. I suggest http://www.step-10.com/SoftwareDesign/ModellingInColour/ as a suitable introduction to his ideas.


问:
Making sure loaden (non default) config is valid
I'm writing a device Software in which the device must handle much data. Therefore it has a database, either on NV-Ram (Non-volatile memory) or a SD-Card.

Due there's a DB which I can use, I also use it to store configurations which should survive restarts or power loss.

Everything is working fine so far, but how can I prevent corrupted configs?
Using SQLite3, I can be relatively sure, that changes either aren't saved, or are correct.
But what happens if wrong data is stored? This is a viable scenario.

Which techniques are good to check a set of data for coherency?

So far:
By (re-)start of the device, I check if DB holds a config and if not, I'm writing the hard-codet default config to the DB.
There are multiple problems with that, it does only check if there IS an existing config table in the DB, but not if the table is validt.

One Idea I had so far, is to iterate through default-config and check every entry in config if it has the specific entrie, if yes check for datatype, if not throw error. Still, this would not prevent invalid data.

Example:

Entry "reader-port" (hardware-port on which an specific device is connected)

Expected datatype -> String (example: "\ttys\com2" )
Given    data     -> String ("paoghsfodgvfnamox33" )

As you can guess, this is wrong.

Note: This question is not language specific. But beside of this, I'm working with Lua.

答:
To protect yourself against garbage input, you should validate the input as the user enters it. In the large majority of cases, your garbage input won't be as bad as "paoghsfodgvfnamox33" for a com-port, but rather clumsy typing, like "\ttys\comn2". If you catch these errors as soon as possible, while the user is still editing the configuration, then the user can immediately correct the error.

As for the database being modified outside your application, there are two lines of thought here:

The user isn't supposed to access/modify the database directly. If they do so anyway, then they have broken the warranty seal of the product (figuratively speaking) and they are themselves responsible for the consequences.

If you follow this line of though, there is no point in validating the configuration any further than you currently do, as your testing will have proven that the approved methods of changing the configuration can't corrupt it.

The user is allowed to do whatever they want with the database and we have to be robust against it.

If you follow this line of thought, then you should have additional measures against incorrect configuration values. This can be as simple as first trying the value read from the database and if that doesn't work, falling back to a hard-coded default value.

Or you can add a checksum column to the database table with the configuration values. That way you can immediately detect that a configuration value has changed outside your control.

ContentLicense: CC BY-SA 3.0


问:
Code maintenance: Is it better to develop in English or my mother tongue?
Suppose I develop an application for a given company of my own country. Is is better to code in English or with the language of my country ? I mean, if it is better to comment in French and name the variables and functions, classes in French ...

I ask this question in terms of code maintenance in the future.

答:
The answer, in my experience is, short and consistently: English!

When you develop for yourself, there's really nothing holding you back to comment or name things in your native language (although you shouldn't!), but code that you write for a company:

Doesn't belong to you

Might be maintained by anyone in the future

To allow yourself and others the best possibility to quickly get up to speed with a growing code base, you'd do well to make it a habit to write variable, class and method names as well as comments in English.

It is, after all, the convention and common ground that we all share (including this site!) so we can more easily understand and learn from one another. There is, in my opinion, no room for (well-meant) chauvinism or laziness in this.

I don't use these words lightly and certainly by no means imply, that you in your case would choose to use your native language to write comments because of such, but I have seen blatant displays of both in production environments, with loss of productivity as a result, having myself knowledge of very costly projects that have gone south because of the inability to translate the comments and method names.

For the record, I'm not a native English speaker either.


答:
I'd recommend English.

Our own, Dutch speaking company bought out a French company. Having to deal with code that's written in French isn't much fun for non native speakers. And that's for people who understand some French. Our Irish/Indian colleagues wouldn't understand a word of it.

Title: Code maintenance: Is it better to develop in English or my mother tongue?

Body:
Suppose I develop an application for a given company of my own country. Is is better to code in English or with the language of my country ? I mean, if it is better to comment in French and name the variables and functions, classes in French ...

I ask this question in terms of code maintenance in the future.


问:
Should a web developer know how to do slicing?
I am a web developer. I'm doing all kinds of web-sites and web applications.

It's very strange for me that a lot of customers do not know the difference between a web developer and a slicer. They just want to "give you the PSD" and expect you to give them a web site with a DB back-end and so on...

I'm just asking here: am I wrong in my thinking?

Of course, a web developer MUST know html and css but I don't think that he should slice the PSD and do all the work a css guru can do...

I would like to hear your opinions on this.

答:
Developing a website obviously includes developing the HTML and CSS, because basically that is the web page. If developing a website doesn't include that, what does it include?

So if you have a project where there happens to be a design in PSD, and that design has to be transformed into HTML and CSS, and you call that transformation "slicing", then yes slicing is part of developing a website.

Of course website development also includes lots of other stuff, from a dynamic user interface to all the backend stuff, databases, task servers, backup solution, as broad as you like. Projects that are done by teams can split up the work any way they like, there is no standard way.

If you work on your own, then you need to know everything, or not advertise yourself as an all-round web developer (I'm a backend web developer, not an all-round web developer). If you work in a team, it depends on how that team is setup.


问:
When is Singleton appropriate?
There is a widely accepted opinion that Singleton is an anti-pattern. As usual, there are always exceptions to the rule. Can you explain why Singleton is a bad choice in general and give an example of some valid use cases for it?</p>

答:
Personally I will use singletons when I need 1, 2, or 3, or some limited amount of the objects for the particular class in question.  Or I want to convey to the user of my class that I do not want multiple instances of my class being created for it to function properly.

Also I will only use it when I need to use it almost everywhere in my code and I don't want to pass an object as a parameter to each class or function that needs it.

In addition I will only use a singleton if it does not break another function's referential transparency.  Meaning given some input it will always produce the same output.  I.e. I don't use it for global state.  Unless possibly that global state is initialized once and never changed.

As for when not to use it, see the above 3 and change them to the opposite.

ContentLicense: CC BY-SA 4.0

Title: When is Singleton appropriate?

ContentLicense: CC BY-SA 2.5


问:
Naming conventions: camelCase versus underscore_case ? what are your thoughts about it?
I've been using underscore_case for about 2 years and I recently switched to camelCase because of the new job (been using the later one for about 2 months and I still think underscore_case is better suited for large projects where there are alot of programmers involved, mainly because the code is easier to read).

Now everybody at work uses camelCase because (so they say) the code looks more elegant .

What are you're thoughts about camelCase or underscore_case

p.s. please excuse my bad english

Edit

Some update first:

platform used is PHP (but I'm not expecting strict PHP platform related answers , anybody can share their thoughts on which would be the best to use , that's why I came here in the first place)

I use camelCase just as everibody else in the team (just as most of you recomend)

we use Zend Framework which also recommends camelCase

Some examples (related to PHP) :

Codeigniter framework recommends underscore_case , and honestly the code is easier to read .

ZF recomends camelCase and I'm not the only one who thinks ZF code is a tad harder to follow through.

So my question would be rephrased:

Let's take a case where you have the platform Foo which doesn't recommend any naming conventions and it's the team leader's choice to pick one. You are that team leader, why would you pick camelCase or why underscore_case?

p.s. thanks everybody for the prompt answers so far

答: I read several years ago that programmers who don't speak English as a first language tend to find underscore case easier to understand that camel case- but I can't find the reference, and I have no idea whether it's true. </p>


问:
Software architecture confusion App-Server/Client
i have a question about the following software architecture:

So, there is one database, an app server, which provide a restful service, a client and a framework, used by the app server and the client.

Now i have some problems with the data access in the Core Framework. On the one hand, the Client uses some functions from the core framework and all data has to be transfered over the HTTP-Protocol. On the other hand, the app-server uses the same functions, but should use our O/R-Mapper for reading and writing the datas.

Or do i have to devide API (in the client) and the Core Framework? But in this case, i have to write the same methods, multiple times, for example:

Example for user creation:

Create a method for the Restful service (GET/POST/...)

Write the method in the Core Framework

Write the method in the API

I think, i have some major architecture failures in my plan, do some one has had similar problems and found a solution?

Thank you!

答:
Yes, this is a very common architecture so the problem does pop up frequently.

What I would do is that I would introduce a new level of abstraction by defining a "model" for my project which contains and presents the classes that my project deals with irrespective of how they are obtained (via HTTP or ORM.)

On the server, this model would be implemented to fetch data using the ORM.

On the client, the model would be implemented to fetch the data using HTTP.

Then, as much as possible of the functionality of the framework would be built on top of the model, so that the same code can be used both on the client and on the server.


问:
How to hide a honeypot ( excluding external CSS and JS )
I am adding spam protection to my personal php framework and I think honeypots are a great way to block spam. Unfortunately they weren't invented yesterday and probably most bots do fetch CSS and can figure out whether the field is real or not. For example if I were designing a spam bot it would be highly intuitive for me to make my bot miss fields with display: none in their style attribute or fields that have relatively large style attributes such as width:0; height:0; border:none; background:none; position:absolute; cursor:defualt which is by the way what I'm currently using. Furthermore if all other fields lack a style attribute it's highly possible that the only one that doesn't is a honeypot.

In other words it seems to me that honey pots are not that difficult to spot. Can anyone with practice tell me which is the best way to hide a honeypot?

And JavaScript is not really an option because I'm building this, as I said, as part of a framework, so I can't really hardcode some JS into a php function.

And finally, there's no spam tag so I'm tagging this as security.

答:
If you are building a web framework, this implies you can serve resources including HTML, CSS and JS files. If it has to be, you could even inline all resources into HTML. You can therefore use CSS- and JavaScript-based techniques to make it arbitrarily difficult to spam your form.

To each form field, you can apply a different class. Only one of these will be used to designate the honeypot, and you can use CSS to hide that input. This requires spam bots to include a complete CSS parser and to find out whether a given input will be visible. This is fairly non-trivial. Using inline style attributes does not afford similar protection, since using a regex such as /\bdisplay:\s*none\b/ could be used to detect them. Using CSS like this is the 20% effort, 80% success solution that's actually worth doing.

You can easily improve this protection, e.g. by applying the necessary classes via JavaScript. This requires bots to run a JavaScript interpreter, but that turns out to be much easier than resolving CSS rules. You can obfuscate your CSS rules to require bots to implement CSS fully. Think about rules such as .the-next-one-is-spam + .field { display: none }. You can autogenerate class identifiers on each page load, so that hardcoding special rules for your site would be pointless for a bot. Or you could give up trying to throw together your own solution, and simply use an existing captcha provider.

The problem with honeypots is that on the one hand, they have to be indistinguishable from real input fields. On the other hand, there may be users with text-based browsers or users relying on assistive technologies. Other users might substitute their own style sheets. You can not rely on all your users to have JS and CSS enabled, and it would be nice if your site would still be usable despite that. Depending on your jurisdiction and type of project, you might be legally required to support users of assistive technologies.

Also, honeypots do not offer protection against human spammers which use real browsers. Honeypots can be one layer of defence, but on their own they cannot offer total protection. They are only useful to weed out the hordes of low-effort bots on the prowl for unsecured comment forms written with a 90's script kiddie's understanding of security.


问:
Bridging the gap between abstract machines and computer achitectures?
I always feel disconnected between abstract machines (such as Turing machines) and computer architectures (including virtual machines' architectures, Von Neumann's achitecture).
So I would like to know how they are related? How do one influence the other?
References are also appreciated. Thanks.</p>

答:
It is important to know that the definition of computation is not "those things which computers do".  Computation predates computers.  Computers were given their name because they were created to assist the task of computation, not because they define it.

So the Turing Machine is not about how computers work.  It is about whether or not a problem is computable - that is, solvable by a formal logical/mathematical process.  It says nothing about how that process might be implemented.  If it is computable, it can be solved by human beings with pencils and paper, given enough time, or with computers or (this is the important thing) with any system that can be shown to be Turing complete.

So the Turing Machine does two very important things:

Provides a test for the computability of any problem/task.

Provides a test for any system to show if it can compute any computable task.

The first point enables us to think about problems without being distracted by real world implementations.  This is a good thing because the real hardware often distract people with irrelevant detail (like, "what happens if we run out of memory or storage space?", since Turing Machines have infinite resource).  A provable theoretical solution can be developed for a Turing Machine and then all somebody needs to do is translate it into something that will work on a given architecture.

The second point allows us to verify the capability of any implementation without having to run lots of different tests on it. If it can simulate a Turing Machine, it can do anything the Turing Machine can do.  Since Turing Machines can compute anything computable, so can it.

Which means that the relationship between the Turing Machine and any genuinely practical computer architecture (even virtual ones) is just one thing: they can compute.

Von Neumann's architecture was an attempt to create a design template for effective general purpose electronic digital computers. Turing's work provided the proof of its validity


问:
When would dynamic scoping be useful?
With dynamic scoping, a callee can access the variables of its caller. Pseudo C code:

```<code>void foo()
{
    print(x);
}

void bar()
{
    int x = 42;
    foo();
}
</code>```

Since I have never programmed in a language that supports dynamic scoping, I wonder what some real world use cases for dynamic scoping would be.

答: Exception handling in most languages utilizes dynamic scoping; when an exception occurs control will be transferred back to the closest handler on the (dynamic) activation stack.</p>

Title: When would dynamic scoping be useful?


问:
number of strings, when each character must occur even times
I've been bashing my skull at this problem for some time now, and its really starting to frustrate me. The problem is:

I have a set of characters, A, B, C, and D. I have to tell in how many ways a string can be built from those characters, when the length is n and each character must occur even times.

For example, the answer for n = 2 is 4:

```<code>AA
BB
CC
DD
</code>```

The answer for n = 4 is 40. Some of those valid strings are:

```<code>AAAA
AABB
CACA
DAAD
BCCB
</code>```

I'm stuck at coming up with a logic. I feel like there could be a DP solution for this. Brute-forcing my way through this is out of the question: the number of solutions rapidly grow into huge numbers.

I've tried drawing all kinds of ideas on paper, to no avail. Almost all of those ideas I had to discard as their complexity was too big. The solution should be efficient for n = 10^4.

One of my ideas was to never keep track of the actual strings, but only whether each character has appeared even or odd times. I couldn't come up with a way to apply this logic.

Can anyone help me?

答:
Set up f(n,d) as a function giving the number of permutations of (even) length n using d distinct characters (i.e d=4 in your case).

Clearly f(0,d) = 1 and f(n,1) = 1 as there's only one arrangement when you have only one character, or zero spaces.

Now the induction step:

To make a valid string using d characters, take any shorter even-length string using d-1 characters and make it up to length by adding in an even multiple of this new character. The number of arrangements is choose(n,n_newdigits) because you can choose n_newdigit places out of the total string length to have the new digit, and the rest are filled by the original string in order.

To implement this using naive recursion in R, I did:

```<code>f <- function(n,d)
{
  if(n==0) return(1)
  if(d==1) return(1)
  retval=0
  for (i in seq(from=0, to=n, by=2)) retval=retval+f(n-i,d-1)*choose(n,i)
  return(retval)
}

f(4,4)
# 40

f(500,4)
# 1.339386e+300 takes about 10 secs
</code>```

for the sort of numbers you're interested I'd have thought that it'd be more efficient to store numbers in a two dimensional array, and iterate over increasing d, but this may depend on your choice of language.

Body:
Set up f(n,d) as a function giving the number of permutations of (even) length n using d distinct characters (i.e d=4 in your case).

Clearly f(0,d) = 1 and f(n,1) = 1 as there's only one arrangement when you have only one character, or zero spaces.

Now the induction step:

To make a valid string using d characters, take any shorter even-length string using d-1 characters and make it up to length by adding in an even multiple of this new character. The number of arrangements is choose(n,n_newdigits) because you can choose n_newdigit places out of the total string length to have the new digit, and the rest are filled by the original string in order.

To implement this using naive recursion in R, I did:

f <- function(n,d)
{
  if(n==0) return(1)
  if(d==1) return(1)
  retval=0
  for (i in seq(from=0, to=n, by=2)) retval=retval+f(n-i,d-1)*choose(n,i)
  return(retval)
}

f(4,4)
# 40

f(500,4)
# 1.339386e+300 takes about 10 secs

for the sort of numbers you're interested I'd have thought that it'd be more efficient to store numbers in a two dimensional array, and iterate over increasing d, but this may depend on your choice of language.


问:
What is the difference between a variable and a parameter?
Its a conceptual question. But I would like to use the right term at the right place. That is why I would like to read some other views on this.</p>

答: Parameters can be used as a special type of variable, but the basic difference is scope: that a variable is local (it only exists within the current method), whereas a parameter is external: it is passed in to the method from the caller.  This means that, if the parameter is passed by reference (including essentially any object type), changes to the parameter will be reflected in the calling code once the method exits, whereas anything done to a local variable does not live beyond the method. (Unless it gets passed elsewhere and stored, of course.)


答: Parameters are variables that only exist within a method, and are initialized automatically with the values passed to the method.</p>

Title: What is the difference between a variable and a parameter?

Body: Its a conceptual question. But I would like to use the right term at the right place. That is why I would like to read some other views on this.</p>


答:
In layman's words:

Imagine a function as a black box.

You don't know how the black box works

You only know what the black box does, but not how

The black box needs something to work on, that you must provide

The black box gives you something in return

That thing you provide the black box is a parameter

The pieces of information you don't know of, that the black box uses to do it's work, are variables

But hey!, for you (the caller), the thing you give the black box can be a variable of your own, that you use to do your own work.

You can also give the black box a literal, i.e, instead of passing it the variable personName you could pass it "Peter". The black box doesn't know whether you passed it a variable or a literal. Once inside the black box, it's a variable as seen from the perspective of the black box.

Finally the black box gives you something back, which is called a "return value", which you can put in a variable or your own, or not, or you can pass to another box as a parameter.

Some black boxes don't need you to pass them anything.

Some black boxes don't return anything, and people call them "methods".

Some people call parameters "arguments".


问:
"Read user input": Could it be a step of an algorithm?
Based on this definition of algorithm from Wikipedia:

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.

An algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state.

Is "Wait for user input" or simply read() counted an step of algorithm?

I thought for the following reasons it may not fit in the definition:

It seems it's not an step which can be executed as an operation is executed.

It should wait for an external signal to get finished, it could be against of the self-contained in the definition.

Moreover the definition talks about an initial input, so I suppose the input should be already provided.

Am I correct?

Update: If it's not an step, then how would you represent the following sequence, is it an algorithm?

X = 5

Y = X + 4

if ( Y > 10) Z = Read() // get the user input

else Z = 1

if (Z > 2) Z = Z + X

Please note reading occurs conditionally, then we may not suppose the input should be already provided.

答:
I think answering this question depends on our definition of "algorithm"

According to the given definition of the algorithm (in mathematics) the answer is "No"

I think in a general definition, the algorithm is just a recipe (set of instructions). We sometimes, confuse the algorithm with its execution. Execution of algorithm depends on its executor. Then the validity or feasibility (computability in the term of mathematics) of an algorithm depends on the executor.

A cooking recipe is also an algorithm, but you don't expect to give it to a computer and wait for your meal to be ready.

But computer can understand and perform the read() instruction then it is a valid instruction for it, and from this perspective the answer is "Yes". We shouldn't confuse this instruction with it's execution. the matter that the user will enter a data or not is not important, now every thing is just on paper (recipe).

But that read() instruction is usually used for a computer not for a computing algorithm (the algorithms we usually are familiar with and are supposed to be executed by Turing Machine). Computing algorithms are about calculation of functions or data processing and transforming, then read() is not a mathematical operator or is not important for it.

However, the example algorithm could be a computation which can not be written as a computing algorithm (a closed computation), the read() here occurs during computation. it's a type of interactive computation

In computer science, interactive computation is a mathematical model for computation that involves input/output communication with the external world during computation.


答:
I use a mix sometimes: module_FunctionName. All (non-static) functions in my modules start with a module abbreviation.

For example a function for sending a buffer's content on the I2C bus:

```<code>i2c_BufferSend()
</code>```

The alternative i2c_buffer_send does not show a big enough separation between prefix and function name. i2cBufferSend mixes in the prefix too much (there are quite a number of I2C functions in this module).

i2c_Buffer_send might have been an alternative, though.

My answer being that you adapt to what works best for your project (your language, your SW architecture, ...), and I wanted to point out that mixing these styles might be useful.

myGeneralOpinionIsThatNamesAreMuchHarderToReadInCamelCase. I_respect_the_fact_that_some_could_think_otherwise_but_I_do_not_really_understand_why.

Title: Naming conventions: camelCase versus underscore_case ? what are your thoughts about it?

Body:
I've been using underscore_case for about 2 years and I recently switched to camelCase because of the new job (been using the later one for about 2 months and I still think underscore_case is better suited for large projects where there are alot of programmers involved, mainly because the code is easier to read).

Now everybody at work uses camelCase because (so they say) the code looks more elegant .

What are you're thoughts about camelCase or underscore_case

p.s. please excuse my bad english

Edit

Some update first:

platform used is PHP (but I'm not expecting strict PHP platform related answers , anybody can share their thoughts on which would be the best to use , that's why I came here in the first place)

I use camelCase just as everibody else in the team (just as most of you recomend)

we use Zend Framework which also recommends camelCase

Some examples (related to PHP) :

Codeigniter framework recommends underscore_case , and honestly the code is easier to read .

ZF recomends camelCase and I'm not the only one who thinks ZF code is a tad harder to follow through.

So my question would be rephrased:

Let's take a case where you have the platform Foo which doesn't recommend any naming conventions and it's the team leader's choice to pick one. You are that team leader, why would you pick camelCase or why underscore_case?

p.s. thanks everybody for the prompt answers so far

Body:
I use a mix sometimes: module_FunctionName. All (non-static) functions in my modules start with a module abbreviation.

For example a function for sending a buffer's content on the I2C bus:

i2c_BufferSend()

The alternative i2c_buffer_send does not show a big enough separation between prefix and function name. i2cBufferSend mixes in the prefix too much (there are quite a number of I2C functions in this module).

i2c_Buffer_send might have been an alternative, though.

My answer being that you adapt to what works best for your project (your language, your SW architecture, ...), and I wanted to point out that mixing these styles might be useful.

myGeneralOpinionIsThatNamesAreMuchHarderToReadInCamelCase. I_respect_the_fact_that_some_could_think_otherwise_but_I_do_not_really_understand_why.


问:
Best OOP pattern to use for creating a commandline SQL API for a proprietary json based company datastore
We need to create a SQL commandline tool for querying a proprietary  json based datastore. I'll be using java. Any suggestions on the primary OOP design pattern I should use for building this API?

I've thought about using the builder pattern in the backend that would compose the json nodes based on statements built up by the builder but that doesn't seem very ground breaking for this use-case.

Could you suggest any other pattern you think would be more useful for this use-case? Also please provide the reason why you think the particular pattern applies.

答:
Primarily Adapter to adapt native datastore commands to SQL dialect.

IMHO I would advise you against exposing SQL API in such case. You are better off delivering native datastore-like commands (possibly wrapped somehow) that are supported by datastore developers. Simply - do you create costly overhead that won't deliver much value?


问:
Number of strings containing a specific substring
I've seen numerous questions (and answers) concerning the number of binary strings (e.g "10010" containing some binary substring (e.g "00"). I'd like to know if there is a way to generalize this:

Given a length n and a string s (may contain any letters A...Z), how many different strings of length n, that contain the substring s at least once, are there?

These kinds of questions are often solvable with combinatorics, but I'd like to find a dynamic-programming solution (and so I posted this question here instead of mathexchange).

Personally, I'm running on cold steam here. Of course, I tried some combinatorial methods:

```<code>n = 5
s = CAR
? = unknown character

all possibilities:

CAR??
?CAR?
??CAR
</code>```

This basically boils down to 26^0*26^2 + 26^1*26^1 + 26^2*26^0 = 3 * 26^2 = 2028 possibilities, which I assume is correct. Consider however the following case:

```<code>n = 7
s = CAR
? = unknown character

all possibilities:

CAR????
?CAR???
??CAR??
???CAR?
????CAR
</code>```

What's the problem? Well, there's 3 positions that can produce duplicate results:

```<code>CARCAR?
CAR?CAR
?CARCAR
</code>```

Now the number of possible strings is

(2 * 26^7) + (2 * 26^1 * 26^6) + (2 * 26^2 * 26^5) + (2 * 26^3 * 26^4) - (3 * 26)

I can't generalize this.

Did I catch anyone's interest? Any help is appreciated.

答:
[Edit: realized what I previously answered doesn't work in all cases, so editing to fix it as per https://meta.stackexchange.com/questions/186689/editing-answers ]

First of all I think there is a slight mix-up in your math (the case for n=7 has some math in it for n=10)

```<code>(2 * 26^7) + (2 * 26^1 * 26^6) + (2 * 26^2 * 26^5) + (2 * 26^3 * 26^4) - (3 * 26)
</code>```

should be

```<code>(2 * 26^4) + (2 * 26^1 * 26^3) + (26^2 * 26^2)  - (3 * 26)
</code>```

or just plain

```<code>(5*26^4)-(3*26)
</code>```

Anyway, framed as a dynamic programming problem, I think you can look at it like this:

1) Place s at some index, i in the resulting string. There are n - length(s) + 1 possibilities.

2) For each possibility, we simply need to count the possibilities for filling in the remaining indexes. As you have noticed, we run into problems with duplicates. This can be avoided by only counting possibilities where s occurs first at i. So when we place CAR at i=0, and get CARCAR?, we count, but when we place CAR at index i=3 we don't count CARCAR? . If we only count possibilities where s occurs first at i we never count duplicates. The part of the resulting string after our s at i (call it the suffix) can be filled in in any way. For the part before s at i (call it the prefix) we need to take care not to insert occurrences of s.

2a) What we can do here is count all possibilities of filling in the prefix and then subtract the possibilities where s is in. Counting this later part comes down to our original problem: getting the "Number of strings (of length n) containing a specific substring" only for a smaller length (now the length of our prefix, instead of the length of the entire string). So now we have a reduction of our problem to a smaller problem and hence a dynamic solution.

This works for strings like CAR, but not for strings that can overlap with themselves (place LOL at index 3 of a string of length 7. Then we can create ?LOLOL?, containing 2 occurrences of LOL, where the first isn't (completely) in the prefix, because it overlaps).

2b) This can be fixed by considering a slightly broader problem. We don't count the number of arbitrary strings that we can make containing some substring, but we count the number of strings of a specific form (that might already have characters fixed at some indices) that we can make containing the substring. When we do this, we can do the same thing as before. Again, we place s at some index, i in the form string (now there aren't necessarily n - length(s) + 1 possibilities to place s, since some indices in our form might have fixed characters on them and s might not fit everywhere). We still count all possibilities of filling in the prefix. But then not subtract the possibilities where s is in the prefix, but where s is in the prefix plus the s we put at index i save the last letter. So, when we have ???LOL?, we not only see that we need to subtract because we can create LOLLOL?, but since we check for possibilities to fill in LOL in the string ???LO, we also see that we need to subtract because we can create ?LOLOL?. Now, since we considered a broader problem, that can account for forms that might already have characters fixed at some indices, this again is a reduction of our problem to the same problem of smaller size.

Quick code would look like:

import java.util.*;

public class StringsInStrings {
    //use arrays of CustomCharacter as strings/forms, use nulls when a index is not yet filled in
    enum CustomCharacter {
        A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
    };

    public static void main(String[] args) {
        CustomCharacter[] string = new CustomCharacter[] { null, null, null, null, null, null, null };
        CustomCharacter[] substring = new CustomCharacter[] { CustomCharacter.L, CustomCharacter.O, CustomCharacter.L };
        System.out.println(countPossibilities(string, substring));
    }

    static int countPossibilities(CustomCharacter[] form, CustomCharacter[] substring) {
        int possibilities = 0;
        //put our substring at any index in the form
        for (int index = 0; index <= form.length - substring.length; index++) {
            //see if the substring fits at that index
            if (fits(form, substring, index)) {
                //count the possibilities for filling in the prefix
                CustomCharacter[] prefix = Arrays.copyOfRange(form, 0, index);
                int prefixPossibilities = (int) Math.pow(CustomCharacter.values().length, countNulls(prefix));
                //count the possibilities for filling in the suffix
                CustomCharacter[] suffix = Arrays.copyOfRange(form, index+substring.length, form.length);
                int suffixPossibilities = (int) Math.pow(CustomCharacter.values().length, countNulls(suffix));

                //count the possibilities where we fill the prefix such that our index is not the first occurence of the substring anymore
                //these need to be subtracted
                CustomCharacter[] reducedForm = Arrays.copyOfRange(insert(form,substring,index), 0, index + substring.length - 1);
                int invalidPrefixPossibilities = countPossibilities(reducedForm, substring);

                possibilities += (prefixPossibilities - invalidPrefixPossibilities) * suffixPossibilities;
            }

        }

        return possibilities;
    }

    private static boolean fits(CustomCharacter[] form, CustomCharacter[] substring, int index) {
        boolean result = true;
        for (int subStrIndex = 0; subStrIndex < substring.length; subStrIndex++) {
            if (!(form[index + subStrIndex] == null || form[index + subStrIndex] == substring[subStrIndex])) {
                result = false;
            }
        }
        return result;
    }

    private static int countNulls(CustomCharacter[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == null) {
                result++;
            }
        }
        return result;
    }

    private static CustomCharacter[] insert(CustomCharacter[] form, CustomCharacter[] substring, int index) {
        CustomCharacter[] result = Arrays.copyOf(form, form.length);
        for (int i = 0; i < substring.length; i++) {
            result[index + i] = substring[i];
        }
        return result;
    }
}
```

<p>So yeah, fun problem. I think this is a correct solution, maybe there is an easier one?</p>

<p>[One more edit: version with memoization and BigInteger. Making it more efficient and making use of the efficiency by having it support large examples...  as discussed in the comments]</p>

<pre class="lang-java prettyprint-override"><code>import java.math.BigInteger;
import java.util.*;

public class StringsInStringsCached {
    //use arrays of CustomCharacter as strings/forms, use nulls when a index is not yet filled in
    enum CustomCharacter {
        A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
    };

    static HashMap<List<CustomCharacter>, BigInteger> cache;

    public static void main(String[] args) {
        List<CustomCharacter> string = customCharListWithNulls(100);
        List<CustomCharacter> substring = customCharListFromString("ABCDABD");

        cache = new HashMap<List<CustomCharacter>, BigInteger>();

        System.out.println(countPossibilities(string, substring));
    }

    static BigInteger countPossibilities(List<CustomCharacter> form, List<CustomCharacter> substring) {
        if(!cache.containsKey(form)){
            BigInteger possibilities = BigInteger.ZERO;
            //put our substring at any index in the form
            for (int index = 0; index <= form.size() - substring.size(); index++) {
                //see if the substring fits at that index
                if (fits(form, substring, index)) {
                    //count the possibilities for filling in the prefix
                    List<CustomCharacter> prefix = copyOfRange(form, 0, index);
                    BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(prefix));
                    BigInteger.valueOf(countNulls(prefix));

                    BigInteger prefixPossibilities = BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(prefix));
                    //count the possibilities for filling in the suffix
                    List<CustomCharacter> suffix = copyOfRange(form, index+substring.size(), form.size());
                    BigInteger suffixPossibilities = BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(suffix));

                    //count the possibilities where we fill the prefix such that our index is not the first occurence of the substring anymore
                    //these need to be subtracted
                    List<CustomCharacter> reducedForm = copyOfRange(insert(form,substring,index), 0, index + substring.size() - 1);
                    BigInteger invalidPrefixPossibilities = countPossibilities(reducedForm, substring);

                    possibilities = possibilities.add((prefixPossibilities.subtract(invalidPrefixPossibilities)).multiply(suffixPossibilities));
                }

            }

            cache.put(form, possibilities);
        }
        return cache.get(form);
    }

    private static boolean fits(List<CustomCharacter> form, List<CustomCharacter> substring, int index) {
        boolean result = true;
        for (int subStrIndex = 0; subStrIndex < substring.size(); subStrIndex++) {
            if (!(form.get(index + subStrIndex) == null || form.get(index + subStrIndex) == substring.get(subStrIndex))) {
                result = false;
            }
        }
        return result;
    }

    private static int countNulls(List<CustomCharacter> l) {
        int result = 0;
        for (int i = 0; i < l.size(); i++) {
            if (l.get(i) == null) {
                result++;
            }
        }
        return result;
    }

    private static List<CustomCharacter> insert(List<CustomCharacter> form, List<CustomCharacter> substring, int index) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>(form);
        for (int i = 0; i < substring.size(); i++) {
            result.set(index + i, substring.get(i));
        }
        return result;
    }

    private static List<CustomCharacter> copyOfRange(List<CustomCharacter> l, int from, int to){
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(int i = from; i < to; i++){
            result.add(l.get(i));
        }
        return result;
    }

    private static List<CustomCharacter> customCharListWithNulls(int size) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(int i = 0; i < size; i++){
            result.add(null);
        }
        return result;
    }

    private static List<CustomCharacter> customCharListFromString(String s) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(char c : s.toCharArray()){
            result.add(CustomCharacter.valueOf(String.valueOf(c)));
        }

        return result;
    }
}
</code>```

Body:
[Edit: realized what I previously answered doesn't work in all cases, so editing to fix it as per https://meta.stackexchange.com/questions/186689/editing-answers ]

First of all I think there is a slight mix-up in your math (the case for n=7 has some math in it for n=10)

(2 * 26^7) + (2 * 26^1 * 26^6) + (2 * 26^2 * 26^5) + (2 * 26^3 * 26^4) - (3 * 26)

should be

(2 * 26^4) + (2 * 26^1 * 26^3) + (26^2 * 26^2)  - (3 * 26)

or just plain

(5*26^4)-(3*26)

Anyway, framed as a dynamic programming problem, I think you can look at it like this:

1) Place s at some index, i in the resulting string. There are n - length(s) + 1 possibilities.

2) For each possibility, we simply need to count the possibilities for filling in the remaining indexes. As you have noticed, we run into problems with duplicates. This can be avoided by only counting possibilities where s occurs first at i. So when we place CAR at i=0, and get CARCAR?, we count, but when we place CAR at index i=3 we don't count CARCAR? . If we only count possibilities where s occurs first at i we never count duplicates. The part of the resulting string after our s at i (call it the suffix) can be filled in in any way. For the part before s at i (call it the prefix) we need to take care not to insert occurrences of s.

2a) What we can do here is count all possibilities of filling in the prefix and then subtract the possibilities where s is in. Counting this later part comes down to our original problem: getting the "Number of strings (of length n) containing a specific substring" only for a smaller length (now the length of our prefix, instead of the length of the entire string). So now we have a reduction of our problem to a smaller problem and hence a dynamic solution.

This works for strings like CAR, but not for strings that can overlap with themselves (place LOL at index 3 of a string of length 7. Then we can create ?LOLOL?, containing 2 occurrences of LOL, where the first isn't (completely) in the prefix, because it overlaps).

2b) This can be fixed by considering a slightly broader problem. We don't count the number of arbitrary strings that we can make containing some substring, but we count the number of strings of a specific form (that might already have characters fixed at some indices) that we can make containing the substring. When we do this, we can do the same thing as before. Again, we place s at some index, i in the form string (now there aren't necessarily n - length(s) + 1 possibilities to place s, since some indices in our form might have fixed characters on them and s might not fit everywhere). We still count all possibilities of filling in the prefix. But then not subtract the possibilities where s is in the prefix, but where s is in the prefix plus the s we put at index i save the last letter. So, when we have ???LOL?, we not only see that we need to subtract because we can create LOLLOL?, but since we check for possibilities to fill in LOL in the string ???LO, we also see that we need to subtract because we can create ?LOLOL?. Now, since we considered a broader problem, that can account for forms that might already have characters fixed at some indices, this again is a reduction of our problem to the same problem of smaller size.

Quick code would look like:

import java.util.*;

public class StringsInStrings {
    //use arrays of CustomCharacter as strings/forms, use nulls when a index is not yet filled in
    enum CustomCharacter {
        A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
    };

    public static void main(String[] args) {
        CustomCharacter[] string = new CustomCharacter[] { null, null, null, null, null, null, null };
        CustomCharacter[] substring = new CustomCharacter[] { CustomCharacter.L, CustomCharacter.O, CustomCharacter.L };
        System.out.println(countPossibilities(string, substring));
    }

    static int countPossibilities(CustomCharacter[] form, CustomCharacter[] substring) {
        int possibilities = 0;
        //put our substring at any index in the form
        for (int index = 0; index <= form.length - substring.length; index++) {
            //see if the substring fits at that index
            if (fits(form, substring, index)) {
                //count the possibilities for filling in the prefix
                CustomCharacter[] prefix = Arrays.copyOfRange(form, 0, index);
                int prefixPossibilities = (int) Math.pow(CustomCharacter.values().length, countNulls(prefix));
                //count the possibilities for filling in the suffix
                CustomCharacter[] suffix = Arrays.copyOfRange(form, index+substring.length, form.length);
                int suffixPossibilities = (int) Math.pow(CustomCharacter.values().length, countNulls(suffix));

                //count the possibilities where we fill the prefix such that our index is not the first occurence of the substring anymore
                //these need to be subtracted
                CustomCharacter[] reducedForm = Arrays.copyOfRange(insert(form,substring,index), 0, index + substring.length - 1);
                int invalidPrefixPossibilities = countPossibilities(reducedForm, substring);

                possibilities += (prefixPossibilities - invalidPrefixPossibilities) * suffixPossibilities;
            }

        }

        return possibilities;
    }

    private static boolean fits(CustomCharacter[] form, CustomCharacter[] substring, int index) {
        boolean result = true;
        for (int subStrIndex = 0; subStrIndex < substring.length; subStrIndex++) {
            if (!(form[index + subStrIndex] == null || form[index + subStrIndex] == substring[subStrIndex])) {
                result = false;
            }
        }
        return result;
    }

    private static int countNulls(CustomCharacter[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == null) {
                result++;
            }
        }
        return result;
    }

    private static CustomCharacter[] insert(CustomCharacter[] form, CustomCharacter[] substring, int index) {
        CustomCharacter[] result = Arrays.copyOf(form, form.length);
        for (int i = 0; i < substring.length; i++) {
            result[index + i] = substring[i];
        }
        return result;
    }
}

So yeah, fun problem. I think this is a correct solution, maybe there is an easier one?

[One more edit: version with memoization and BigInteger. Making it more efficient and making use of the efficiency by having it support large examples...  as discussed in the comments]

import java.math.BigInteger;
import java.util.*;

public class StringsInStringsCached {
    //use arrays of CustomCharacter as strings/forms, use nulls when a index is not yet filled in
    enum CustomCharacter {
        A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
    };

    static HashMap<List<CustomCharacter>, BigInteger> cache;

    public static void main(String[] args) {
        List<CustomCharacter> string = customCharListWithNulls(100);
        List<CustomCharacter> substring = customCharListFromString("ABCDABD");

        cache = new HashMap<List<CustomCharacter>, BigInteger>();

        System.out.println(countPossibilities(string, substring));
    }

    static BigInteger countPossibilities(List<CustomCharacter> form, List<CustomCharacter> substring) {
        if(!cache.containsKey(form)){
            BigInteger possibilities = BigInteger.ZERO;
            //put our substring at any index in the form
            for (int index = 0; index <= form.size() - substring.size(); index++) {
                //see if the substring fits at that index
                if (fits(form, substring, index)) {
                    //count the possibilities for filling in the prefix
                    List<CustomCharacter> prefix = copyOfRange(form, 0, index);
                    BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(prefix));
                    BigInteger.valueOf(countNulls(prefix));

                    BigInteger prefixPossibilities = BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(prefix));
                    //count the possibilities for filling in the suffix
                    List<CustomCharacter> suffix = copyOfRange(form, index+substring.size(), form.size());
                    BigInteger suffixPossibilities = BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(suffix));

                    //count the possibilities where we fill the prefix such that our index is not the first occurence of the substring anymore
                    //these need to be subtracted
                    List<CustomCharacter> reducedForm = copyOfRange(insert(form,substring,index), 0, index + substring.size() - 1);
                    BigInteger invalidPrefixPossibilities = countPossibilities(reducedForm, substring);

                    possibilities = possibilities.add((prefixPossibilities.subtract(invalidPrefixPossibilities)).multiply(suffixPossibilities));
                }

            }

            cache.put(form, possibilities);
        }
        return cache.get(form);
    }

    private static boolean fits(List<CustomCharacter> form, List<CustomCharacter> substring, int index) {
        boolean result = true;
        for (int subStrIndex = 0; subStrIndex < substring.size(); subStrIndex++) {
            if (!(form.get(index + subStrIndex) == null || form.get(index + subStrIndex) == substring.get(subStrIndex))) {
                result = false;
            }
        }
        return result;
    }

    private static int countNulls(List<CustomCharacter> l) {
        int result = 0;
        for (int i = 0; i < l.size(); i++) {
            if (l.get(i) == null) {
                result++;
            }
        }
        return result;
    }

    private static List<CustomCharacter> insert(List<CustomCharacter> form, List<CustomCharacter> substring, int index) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>(form);
        for (int i = 0; i < substring.size(); i++) {
            result.set(index + i, substring.get(i));
        }
        return result;
    }

    private static List<CustomCharacter> copyOfRange(List<CustomCharacter> l, int from, int to){
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(int i = from; i < to; i++){
            result.add(l.get(i));
        }
        return result;
    }

    private static List<CustomCharacter> customCharListWithNulls(int size) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(int i = 0; i < size; i++){
            result.add(null);
        }
        return result;
    }

    private static List<CustomCharacter> customCharListFromString(String s) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(char c : s.toCharArray()){
            result.add(CustomCharacter.valueOf(String.valueOf(c)));
        }

        return result;
    }
}


问:
Is throwing an exception an anti-pattern here?
I just had a discussion over a design choice after a code review. I wonder what your opinions are.

There's this Preferences class, which is a bucket for key-value pairs. Null values are legal (that's important). We expect that certain values may not be saved yet, and we want to handle these cases automatically by initializing them with predefined default value when requested.

The discussed solution used following pattern (NOTE: this is not the actual code, obviously - it's simplified for illustrative purposes):

```<code>public class Preferences {
    // null values are legal
    private Map<String, String> valuesFromDatabase;

    private static Map<String, String> defaultValues;

    class KeyNotFoundException extends Exception {
    }

    public String getByKey(String key) {
        try {
            return getValueByKey(key);
        } catch (KeyNotFoundException e) {
            String defaultValue = defaultValues.get(key);
            valuesFromDatabase.put(key, defaultvalue);
            return defaultValue;
        }
    }

    private String getValueByKey(String key) throws KeyNotFoundException {
        if (valuesFromDatabase.containsKey(key)) {
            return valuesFromDatabase.get(key);
        } else {
            throw new KeyNotFoundException();
        }
    }
}
</code>```

It was criticized as an anti-pattern - abusing exceptions to control the flow. KeyNotFoundException - brought to life for that one use case only - is never going to be seen out of the scope of this class.

It's essentially two methods playing fetch with it merely to communicate something to each other.

The key not being present in the database isn't something alarming, or exceptional - we expect this to occur whenever a new preference setting is added, hence the mechanism that gracefully initializes it with a default value if needed.

The counterargument was that getValueByKey - the private method - as defined right now has no natural way of informing the public method about both the value, and whether the key was there. (If it wasn't, it has to be added so that the value can be updated).

Returning null would be ambiguous, since null is a perfectly legal value, so there's no telling whether it meant that the key wasn't there, or if there was a null.

getValueByKey would have to return some sort of a Tuple<Boolean, String>, the bool set to true if the key is already there, so that we can distinguish between (true, null) and (false, null). (An out parameter could be used in C#, but that's Java).

Is this a nicer alternative? Yes, you'd have to define some single-use class to the effect of Tuple<Boolean, String>, but then we're getting rid of KeyNotFoundException, so that kind of balances out. We're also avoiding the overhead of handling an exception, although it's not significant in practical terms - there are no performance considerations to speak of, it's a client app and it's not like user preferences will be retrieved millions of times per second.

A variation of this approach could use Guava's Optional<String> (Guava is already used throughout the project) instead of some custom Tuple<Boolean, String>, and then we can differentiate between Optional.<String>absent() and "proper" null. It still feels hackish, though, for reasons that are easy to see - introducing two levels of "nullness" seem to abuse the concept that stood behind creating Optionals in the first place.

Another option would be to explicitly check whether the key exists (add a boolean containsKey(String key) method and call getValueByKey only if we have already asserted that it exists).

Finally, one could also inline the private method, but the actual getByKey is somewhat more complex than my code sample, thus inlining would make it look quite nasty.

I may be splitting hairs here, but I'm curious what you would bet on to be closest to best practice in this case. I didn't find an answer in Oracle's or Google's style guides.

Is using exceptions like in the code sample an anti-pattern, or is it acceptable given that alternatives aren't very clean, either? If it is, under what circumstances would it be fine? And vice versa?

答:
Yes, your colleague is right: that is bad code. If an error can be handled locally, then it should be handled immediately. An exception should not be thrown and then handled immediately.

This is much cleaner then your version (the getValueByKey() method is removed) :

```<code>public String getByKey(String key) {
    if (valuesFromDatabase.containsKey(key)) {
        return valuesFromDatabase.get(key);
    } else {
        String defaultValue = defaultValues.get(key);
        valuesFromDatabase.put(key, defaultvalue);
        return defaultValue;
    }
}
</code>```

An exception should be thrown only if you do not know how to resolve the error locally.

Body:
Yes, your colleague is right: that is bad code. If an error can be handled locally, then it should be handled immediately. An exception should not be thrown and then handled immediately.

This is much cleaner then your version (the getValueByKey() method is removed) :

public String getByKey(String key) {
    if (valuesFromDatabase.containsKey(key)) {
        return valuesFromDatabase.get(key);
    } else {
        String defaultValue = defaultValues.get(key);
        valuesFromDatabase.put(key, defaultvalue);
        return defaultValue;
    }
}

An exception should be thrown only if you do not know how to resolve the error locally.


答:
I wouldn't call this use of Exceptions an anti-pattern, just not the best solution to the problem of communicating a complex result.

The best solution (assuming you're still on Java 7) would be to use Guava's Optional; I disagree that it's use in this case would be hackish. It seems to me, based on Guava's extended explanation of Optional, that this is a perfect example of when to use it. You're differentiating between "no value found" and "value of null found".

Title: Is throwing an exception an anti-pattern here?

Body:
I just had a discussion over a design choice after a code review. I wonder what your opinions are.

There's this Preferences class, which is a bucket for key-value pairs. Null values are legal (that's important). We expect that certain values may not be saved yet, and we want to handle these cases automatically by initializing them with predefined default value when requested.

The discussed solution used following pattern (NOTE: this is not the actual code, obviously - it's simplified for illustrative purposes):

```<code>public class Preferences {
    // null values are legal
    private Map<String, String> valuesFromDatabase;

    private static Map<String, String> defaultValues;

    class KeyNotFoundException extends Exception {
    }

    public String getByKey(String key) {
        try {
            return getValueByKey(key);
        } catch (KeyNotFoundException e) {
            String defaultValue = defaultValues.get(key);
            valuesFromDatabase.put(key, defaultvalue);
            return defaultValue;
        }
    }

    private String getValueByKey(String key) throws KeyNotFoundException {
        if (valuesFromDatabase.containsKey(key)) {
            return valuesFromDatabase.get(key);
        } else {
            throw new KeyNotFoundException();
        }
    }
}
</code>```

It was criticized as an anti-pattern - abusing exceptions to control the flow. KeyNotFoundException - brought to life for that one use case only - is never going to be seen out of the scope of this class.

It's essentially two methods playing fetch with it merely to communicate something to each other.

The key not being present in the database isn't something alarming, or exceptional - we expect this to occur whenever a new preference setting is added, hence the mechanism that gracefully initializes it with a default value if needed.

The counterargument was that getValueByKey - the private method - as defined right now has no natural way of informing the public method about both the value, and whether the key was there. (If it wasn't, it has to be added so that the value can be updated).

Returning null would be ambiguous, since null is a perfectly legal value, so there's no telling whether it meant that the key wasn't there, or if there was a null.

getValueByKey would have to return some sort of a Tuple<Boolean, String>, the bool set to true if the key is already there, so that we can distinguish between (true, null) and (false, null). (An out parameter could be used in C#, but that's Java).

Is this a nicer alternative? Yes, you'd have to define some single-use class to the effect of Tuple<Boolean, String>, but then we're getting rid of KeyNotFoundException, so that kind of balances out. We're also avoiding the overhead of handling an exception, although it's not significant in practical terms - there are no performance considerations to speak of, it's a client app and it's not like user preferences will be retrieved millions of times per second.

A variation of this approach could use Guava's Optional<String> (Guava is already used throughout the project) instead of some custom Tuple<Boolean, String>, and then we can differentiate between Optional.<String>absent() and "proper" null. It still feels hackish, though, for reasons that are easy to see - introducing two levels of "nullness" seem to abuse the concept that stood behind creating Optionals in the first place.

Another option would be to explicitly check whether the key exists (add a boolean containsKey(String key) method and call getValueByKey only if we have already asserted that it exists).

Finally, one could also inline the private method, but the actual getByKey is somewhat more complex than my code sample, thus inlining would make it look quite nasty.

I may be splitting hairs here, but I'm curious what you would bet on to be closest to best practice in this case. I didn't find an answer in Oracle's or Google's style guides.

Is using exceptions like in the code sample an anti-pattern, or is it acceptable given that alternatives aren't very clean, either? If it is, under what circumstances would it be fine? And vice versa?


答:
You're basically writing a compiler, which translates from SQL to whatever your datastore understands. In the end, you'll probably have the following parts:

a Parser which takes SQL and produces an Abstract Syntax Tree

a bunch of Visitors which do semantic analysis and/or rewriting on the AST

an Interpreter which finally executes the (processed) query against the datastore

a REPL which reads input and formats output

But before you even start implementation, you should consider that SQL is defined on relations (tables), which are fundamentally unlike document collections. First, each row in a table has the same columns as all other rows in that table, and nothing else. Second, each row is a flat tuple, while a document is a tree.

If I were you, I'd first solve this mapping problem by taking something like PostgreSQL, defining the tables you expect to have, and then solving how to map your data into said tables (by actually doing it). You can use the result as a prototype for whomever wishes to have SQL, it will give you some ideas on how to implement the compiler, because semantics will be known, and you will have a solid reference for testing/verification purposes.

You may also end up deciding that copying data to an actual RDBMS is good enough; SQL queries are a fairly complex thing to implement efficiently, with joins, subqueries, aggregation, projections and whatnot.. It is even more difficult if you have to do it "from outside" of data store..

Title: Best OOP pattern to use for creating a commandline SQL API for a proprietary json based company datastore

Body:
We need to create a SQL commandline tool for querying a proprietary  json based datastore. I'll be using java. Any suggestions on the primary OOP design pattern I should use for building this API?

I've thought about using the builder pattern in the backend that would compose the json nodes based on statements built up by the builder but that doesn't seem very ground breaking for this use-case.

Could you suggest any other pattern you think would be more useful for this use-case? Also please provide the reason why you think the particular pattern applies.


答:
Miff's answer is definitely elegant. Since I had mine nearly finished anyway I provide it nevertheless. The good thing is that I get the same result for n=500 :-)

Let d be the number of different characters that are allowed, d=4 in your case.

Let n be the length of the string, ultimately you will be looking at even values of n.

Let u be the number of unpaired characters in a string.

Let N(n,d,u) be the number of strings of length n, built from d different characters and having u unpaired characters. Lets try to compute N.

There are quite a few corner cases to observe:

u>d or u>n => N=0

u<0 => N=0

n%2 != u%2 => N=0.

When stepping from n to n+1, u must either increase by 1 or decrease by 1, so we have a recursion according to

N(n,d,u) = f(N(n-1,d,u-1), N(n-1,d,u+1))

How many ways are there to reduce u by one. This one is easy, because we have to pair one of the u unpaired characters, which makes it just u. So the 2nd part of f will read (u+1)*N(n-1,d,u+1), with the caveat of course that we must observe that N=0 if u+1>n-1 or u+1>d.

Once we have understood this, it is easy to see what the first part of f is: in how many ways can we increase u when there are u-1 unpaired characters. Well, we have to pick one of the (k-(u-1)) characters which are paired.

So taking into account all corner cases, the recursive formula for N is

N(n,d,u) = (d-(u-1))*N(n-1,d,u-1) + (u+1)*N(n-1,d,u+1)

I am not going to read up in http://en.wikipedia.org/wiki/Concrete_Mathematics how to solve the recursion.

Instead I wrote some Java code. Again a little bit more clumsy, as is Java anyway due to its verbosity. But I had the motivation not to use recursion, since it breaks far to early, at least in Java, when the stack overflows at 500 or 1000 nesting levels.

The result for n=500, d=4 and u=0 is:

N(500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

computed in 0.2 seconds, due to memorizing intermediate results. N(40000,4,0) computes in less than 5 seconds. Code also here: http://ideone.com/KvB5Jv

```<code>import java.math.BigInteger;

public class EvenPairedString2 {
  private final int nChars;  // d above, number of different chars to use
  private int count = 0;
  private Map<Task,BigInteger> memo = new HashMap<>();

  public EvenPairedString2(int nChars) {
    this.nChars = nChars;
  }
  /*+******************************************************************/
  // encodes for a fixed d the task to compute N(strlen,d,unpaired).
  private static class Task {
    public final int strlen;
    public final int unpaired;

    Task(int strlen, int unpaired) {
      this.strlen = strlen;
      this.unpaired = unpaired;
    }
    @Override
    public int hashCode() {
      return strlen*117 ^ unpaired;
    }
    @Override
    public boolean equals(Object other) {
      if (!(other instanceof Task)) {
        return false;
      }
      Task t2 = (Task)other;
      return strlen==t2.strlen && unpaired==t2.unpaired;
    }
    @Override
    public String toString() {
      return "("+strlen+","+unpaired+")";
    }
  }
  /*+******************************************************************/
  // return corner case or memorized result or null
  private BigInteger getMemoed(Task t) {
    if (t.strlen==0 || t.unpaired<0 || t.unpaired>t.strlen || t.unpaired>nChars
        || t.strlen%2 != t.unpaired%2) {
      return BigInteger.valueOf(0);
    }

    if (t.strlen==1) {
      return BigInteger.valueOf(nChars);
    }
    return memo.get(t);
  }

  public int getCount() {
    return count;
  }

  public BigInteger computeNDeep(Task t) {
    List<Task> stack = new ArrayList<Task>();
    BigInteger result = null;
    stack.add(t);

    while (stack.size()>0) {
      count += 1;
      t = stack.remove(stack.size()-1);
      result = getMemoed(t);
      if (result!=null) {
        continue;
      }

      Task t1 = new Task(t.strlen-1, t.unpaired+1);
      BigInteger r1 = getMemoed(t1);
      Task t2 = new Task(t.strlen-1, t.unpaired-1);
      BigInteger r2 = getMemoed(t2);
      if (r1==null) {
        stack.add(t);
        stack.add(t1);
        if (r2==null) {
          stack.add(t2);
        }
        continue;
      }
      if (r2==null) {
        stack.add(t);
        stack.add(t2);
        continue;
      }
      result = compute(t1.unpaired, r1, nChars-t2.unpaired, r2);
      memo.put(t,  result);
    }
    return result;
  }
  private BigInteger compute(int u1, BigInteger r1, int u2, BigInteger r2) {
    r1 = r1.multiply(BigInteger.valueOf(u1));
    r2 = r2.multiply(BigInteger.valueOf(u2));
    return r1.add(r2);
  }
  public static void main(String[] argv) {
    int strlen = Integer.parseInt(argv[0]);
    int nChars = Integer.parseInt(argv[1]);

    EvenPairedString2 eps = new EvenPairedString2(nChars);

    BigInteger result = eps.computeNDeep(new Task(strlen, 0));
    System.out.printf("%d: N(%d, %d, 0) = %d%n",
                      eps.getCount(), strlen, nChars,
                      result);
  }
}
</code>```

Title: number of strings, when each character must occur even times

Body:
I've been bashing my skull at this problem for some time now, and its really starting to frustrate me. The problem is:

I have a set of characters, A, B, C, and D. I have to tell in how many ways a string can be built from those characters, when the length is n and each character must occur even times.

For example, the answer for n = 2 is 4:

```<code>AA
BB
CC
DD
</code>```

The answer for n = 4 is 40. Some of those valid strings are:

```<code>AAAA
AABB
CACA
DAAD
BCCB
</code>```

I'm stuck at coming up with a logic. I feel like there could be a DP solution for this. Brute-forcing my way through this is out of the question: the number of solutions rapidly grow into huge numbers.

I've tried drawing all kinds of ideas on paper, to no avail. Almost all of those ideas I had to discard as their complexity was too big. The solution should be efficient for n = 10^4.

One of my ideas was to never keep track of the actual strings, but only whether each character has appeared even or odd times. I couldn't come up with a way to apply this logic.

Can anyone help me?

Body:
Miff's answer is definitely elegant. Since I had mine nearly finished anyway I provide it nevertheless. The good thing is that I get the same result for n=500 :-)

Let d be the number of different characters that are allowed, d=4 in your case.

Let n be the length of the string, ultimately you will be looking at even values of n.

Let u be the number of unpaired characters in a string.

Let N(n,d,u) be the number of strings of length n, built from d different characters and having u unpaired characters. Lets try to compute N.

There are quite a few corner cases to observe:

u>d or u>n => N=0

u<0 => N=0

n%2 != u%2 => N=0.

When stepping from n to n+1, u must either increase by 1 or decrease by 1, so we have a recursion according to

N(n,d,u) = f(N(n-1,d,u-1), N(n-1,d,u+1))

How many ways are there to reduce u by one. This one is easy, because we have to pair one of the u unpaired characters, which makes it just u. So the 2nd part of f will read (u+1)*N(n-1,d,u+1), with the caveat of course that we must observe that N=0 if u+1>n-1 or u+1>d.

Once we have understood this, it is easy to see what the first part of f is: in how many ways can we increase u when there are u-1 unpaired characters. Well, we have to pick one of the (k-(u-1)) characters which are paired.

So taking into account all corner cases, the recursive formula for N is

N(n,d,u) = (d-(u-1))*N(n-1,d,u-1) + (u+1)*N(n-1,d,u+1)

I am not going to read up in http://en.wikipedia.org/wiki/Concrete_Mathematics how to solve the recursion.

Instead I wrote some Java code. Again a little bit more clumsy, as is Java anyway due to its verbosity. But I had the motivation not to use recursion, since it breaks far to early, at least in Java, when the stack overflows at 500 or 1000 nesting levels.

The result for n=500, d=4 and u=0 is:

N(500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

computed in 0.2 seconds, due to memorizing intermediate results. N(40000,4,0) computes in less than 5 seconds. Code also here: http://ideone.com/KvB5Jv

import java.math.BigInteger;

public class EvenPairedString2 {
  private final int nChars;  // d above, number of different chars to use
  private int count = 0;
  private Map<Task,BigInteger> memo = new HashMap<>();

  public EvenPairedString2(int nChars) {
    this.nChars = nChars;
  }
  /*+******************************************************************/
  // encodes for a fixed d the task to compute N(strlen,d,unpaired).
  private static class Task {
    public final int strlen;
    public final int unpaired;

    Task(int strlen, int unpaired) {
      this.strlen = strlen;
      this.unpaired = unpaired;
    }
    @Override
    public int hashCode() {
      return strlen*117 ^ unpaired;
    }
    @Override
    public boolean equals(Object other) {
      if (!(other instanceof Task)) {
        return false;
      }
      Task t2 = (Task)other;
      return strlen==t2.strlen && unpaired==t2.unpaired;
    }
    @Override
    public String toString() {
      return "("+strlen+","+unpaired+")";
    }
  }
  /*+******************************************************************/
  // return corner case or memorized result or null
  private BigInteger getMemoed(Task t) {
    if (t.strlen==0 || t.unpaired<0 || t.unpaired>t.strlen || t.unpaired>nChars
        || t.strlen%2 != t.unpaired%2) {
      return BigInteger.valueOf(0);
    }

    if (t.strlen==1) {
      return BigInteger.valueOf(nChars);
    }
    return memo.get(t);
  }

  public int getCount() {
    return count;
  }

  public BigInteger computeNDeep(Task t) {
    List<Task> stack = new ArrayList<Task>();
    BigInteger result = null;
    stack.add(t);

    while (stack.size()>0) {
      count += 1;
      t = stack.remove(stack.size()-1);
      result = getMemoed(t);
      if (result!=null) {
        continue;
      }

      Task t1 = new Task(t.strlen-1, t.unpaired+1);
      BigInteger r1 = getMemoed(t1);
      Task t2 = new Task(t.strlen-1, t.unpaired-1);
      BigInteger r2 = getMemoed(t2);
      if (r1==null) {
        stack.add(t);
        stack.add(t1);
        if (r2==null) {
          stack.add(t2);
        }
        continue;
      }
      if (r2==null) {
        stack.add(t);
        stack.add(t2);
        continue;
      }
      result = compute(t1.unpaired, r1, nChars-t2.unpaired, r2);
      memo.put(t,  result);
    }
    return result;
  }
  private BigInteger compute(int u1, BigInteger r1, int u2, BigInteger r2) {
    r1 = r1.multiply(BigInteger.valueOf(u1));
    r2 = r2.multiply(BigInteger.valueOf(u2));
    return r1.add(r2);
  }
  public static void main(String[] argv) {
    int strlen = Integer.parseInt(argv[0]);
    int nChars = Integer.parseInt(argv[1]);

    EvenPairedString2 eps = new EvenPairedString2(nChars);

    BigInteger result = eps.computeNDeep(new Task(strlen, 0));
    System.out.printf("%d: N(%d, %d, 0) = %d%n",
                      eps.getCount(), strlen, nChars,
                      result);
  }
}


答:
Since there's no performance considerations and it's an implementation detail, it ultimately doesn't matter which solution you choose. But I have to agree it's bad style; the key being absent is something that you know will happen, and you don't even handle it more than one call up the stack, which is where exceptions are most useful.

The tuple approach is a bit hacky because the second field is meaningless when the boolean is false. Checking if the key exists beforehand is silly because the map is looking up the key twice. (Well, you're already doing that, so in this case thrice.) The Optional solution is a perfect fit for the problem. It might seem a bit ironic to store a null in an Optional, but if that's what the user wants to do, you can't say no.

As noted by Mike in the comments, there's an issue with this; neither Guava nor Java 8's Optional allow storing nulls. Thus you'd need to roll your own which -- while straightforward -- involves a fair amount of boilerplate, so might be overkill for something that will only be used once internally. You could also change the map's type to Map<String, Optional<String>>, but handling Optional<Optional<String>>s gets awkward.

A reasonable compromise might be to keep the exception, but acknowledge its role as an "alternative return". Create a new checked exception with the stack trace disabled, and throw a pre-created instance of it which you can keep in a static variable. This is cheap -- possibly as cheap as a local branch -- and you can't forget to handle it, so the lack of stack trace isn't an issue.


问:
Software cost estimation
I've seen on my work place (a University) most students making the software estimation cost of their final diploma work using COCOMO. My guessing is that this way of estimating costs is somewhat old (COCOMO dates of 1981), hence my question:

```<code>How do you estimate costs in your software?
</code>```

I've seen things like :

Cost = ( HoursOfWork + EstimatedIddle ) * HourlyRate

That's not what I want, I'm looking for a properly (scientifically) defined cost model

EDIT I've found some related questions on SO:

What are some of the software cost estimation methods and models?

How do you estimate the cost of developing software requirements?

答:
What we normally do is dividing full work scope into major modules / elements which could be considered as sub-project. In other words they are those work parts which client consider as separate parts of the project and which client wants to get estimated separately.

Once it is done we divide each module into tasks, sub-tasks and even smaller sub-sub-tasks so that each one can be estimated quite easy and the estimation take from one to ten man-hours. That way we get detailed breakdown of work scope for the project.

Last step is distributing tasks between milestones. We do it the way so that after each milestone client gets visible results. That helps to pass one milestone and move to another one.
So finally we get something like:

Module 1

```<code>    <ol>
        <li>
            Primary task 1 - 5 hrs
            <ol>
                <li>Subtask 1.1 – 3 hrs</li>
                <li>Subtask 1.2 – 2 hrs</li>
            </ol>
        </li>
        <li>
            Primary task 2 - 9 hrs
            <ol>
                <li>Subtask 2.1 – 1 hrs</li>
                <li>Subtask 2.2 – 2 hrs</li>
                 <li>Subtask 2.2 – 5 hrs</li>
            </ol>
</code>```

Initially we did it just using excel sheet. But more than two years ago we started to use software tool for that. There are few similar products which helps with it www.evenflow.com, www.swproposal.com and a few others. I don't remember all list. We did research long time ago. Hope that may help.

Good question is how to estimate precisely. There is no 100% correct estimation as we believe. The only way is to divide full work scope into as small tasks as possible. The smaller tasks you have the more detailed review and analysis of the project you do. So that anyway increases accuracy.

Title: Software cost estimation

Body:
What we normally do is dividing full work scope into major modules / elements which could be considered as sub-project. In other words they are those work parts which client consider as separate parts of the project and which client wants to get estimated separately.

Once it is done we divide each module into tasks, sub-tasks and even smaller sub-sub-tasks so that each one can be estimated quite easy and the estimation take from one to ten man-hours. That way we get detailed breakdown of work scope for the project.

Last step is distributing tasks between milestones. We do it the way so that after each milestone client gets visible results. That helps to pass one milestone and move to another one.
So finally we get something like:

Module 1

    <ol>
        <li>
            Primary task 1 - 5 hrs
            <ol>
                <li>Subtask 1.1 – 3 hrs</li>
                <li>Subtask 1.2 – 2 hrs</li>
            </ol>
        </li>
        <li>
            Primary task 2 - 9 hrs
            <ol>
                <li>Subtask 2.1 – 1 hrs</li>
                <li>Subtask 2.2 – 2 hrs</li>
                 <li>Subtask 2.2 – 5 hrs</li>
            </ol>

Initially we did it just using excel sheet. But more than two years ago we started to use software tool for that. There are few similar products which helps with it www.evenflow.com, www.swproposal.com and a few others. I don't remember all list. We did research long time ago. Hope that may help.

Good question is how to estimate precisely. There is no 100% correct estimation as we believe. The only way is to divide full work scope into as small tasks as possible. The smaller tasks you have the more detailed review and analysis of the project you do. So that anyway increases accuracy.


答:
There's this Preferences class, which is a bucket for key-value pairs. Null values are legal (that's important). We expect that certain values may not be saved yet, and we want to handle these cases automatically by initializing them with predefined default value when requested.

The problem is exactly this. But you already posted the solution yourself:

A variation of this approach could use Guava's Optional (Guava is already used throughout the project) instead of some custom Tuple, and then we can differentiate between Optional.absent() and "proper" null. It still feels hackish, though, for reasons that are easy to see - introducing two levels of "nullness" seem to abuse the concept that stood behind creating Optionals in the first place.

However, don't use null or Optional. You can and  should use Optional only. For your "hackish" feeling, just use it nested, so you end up with Optional<Optional<String>> which makes it explicit that there might a key in the database (first option layer) and that it might contain a predefined value (second option layer).

This approach is better than using exceptions and it is quite easy to understand as long as Optional is not new to you.

Also please note that Optional has some comfort functions, so that you don't have to do all the work yourself. These include:

static static <T> Optional<T> fromNullable(T nullableReference) to convert your database input to the Optional types

abstract T or(T defaultValue) to get the key value of the inner option layer or (if not present) get your default key value


答:
Though I think @BЈовић's answer is fine in case getValueByKey is needed nowhere else, I don't think your solution is bad in case your program contains both use cases:

retrieval by key with automatic creation in case the key does not exist beforehand, and

retrieval without that automatism, without changing anything in the database, repository, or key map (think of getValueByKey beeing public, not private)

If this is your situation, and as long as the performance hit is acceptable, I think your proposed solution is fully ok. It has the advantage of avoiding duplication of the retrieval code, it does not rely on third party frameworks, and it is pretty simple (at least in my eyes).

In fact, in such a situation, in depends on the context if a missing key is an "exceptional" situation or not. For a context where it is, something like getValueByKey is needed. For a context where automatic key creation is expected, providing a method which reuses the already available function, swallows the exception and provides a different failure behaviour, makes perfectly sense. This can be interpreted as an extension or "decorator" of getValueByKey, not so much as a function where the "exception is abused for flow of control".

Of course, there is a third alternative: create a third, private method returning the Tuple<Boolean, String>, as you suggested, and reuse this method both in getValueByKey and getByKey. For a more complicated case that might be indeed the better alternative, but for such a simple case as shown here, this has IMHO a smell of overengineering, and I doubt the code gets really more maintainable that way. I am here with the topmost answer here by Karl Bielefeldt:

"you shouldn't feel bad about using exceptions when it simplifies your code".


问:
How should I unit test mathematical formulae?
I have a number of functions that are pretty close to the mathematical definition of a function. For example, a simplified version of one of these functions may look like:

```<code>int function foo(int a, int b) {
    return a * b;
}
</code>```

I'd like to unit test them, but I'm not sure what the best way to approach those tests, as these functions have very large ranges for parameter values. Every approach I've come up with feels lacking:

If I test with a discrete pre-defined subset of possible values, I fear the set I choose may not be representative of the whole, leading to a potentially endless cycle of adding new values to the subset every time an unexpected value is found. This seems like defeating the point of having a unit test in the first place.

If I test with a discrete subset of possible values that's randomly determined, I inherit all of the problems of picking the subset manually as well as the real chance that tests will fail randomly every run.

If I test with every possible value (e.g. 0 to 264), the tests will take forever.

My final thought on how to approach the problem was to avoid testing the implementation of the function entirely, either by:

Only testing that the function accepts two integers and returns an integer, or

Not testing the function at all

But if I'm not testing the functions at all—either in practice or in principle—I'm not sure how I can guarantee the correctness of the functions in the case of an eventual refactor.

What is the best way to test functions that have completely deterministic output, but can operate on a large range of possible inputs?

答:
Perfect is definitely the enemy of good when it comes to testing. Testing is rarely easy. You have to really understand what your function/formula is supposed to do. Even something as simple as multiplying two numbers has several properties we can check.

You may find that some of them will hold up only if you don't consider some of the edge cases.

// False assumption that when numbers are multiplied, the result is greater

foo(a,b) > a + b

* fails on 2,2

// Update bad assumption

foo(a, b) >= a + b

// A negative times a negative is a possitive

isneg(a) and isneg(b) and ispos(foo(a,b))

// Test for zero

foo(a, 0) = 0

// Test for 1

foo(a, 1) = a

// Commutative property

foo(a, b) = foo(b,a)

// Associative property

foo(a, b) * c = a * foo(b,c)

Being able to do this means you don't have to test every single parameter combination.

These kinds of things get caught manually in the business world all the time. Anyone with enough domain knowledge can help with making these assumptions. I may not know the quarterly report figures but it's a safe bet they will never exceed the year to date figures.


答:
You mention the dilemma of testing a fixed set of cases (which might just happen to "miss" the values which your function fails on) or testing many randomly generated cases (which can pass one time and fail the next, and is slow to boot).

Both of these techniques are useful, and they are not mutually exclusive. It can be useful to have one (fast) test suite which uses a fixed set of cases, and another (slow) suite which generates many, many random cases and 1) checks whether the outputs obey certain invariants, as well as 2) seeing if you hit a failed assertion, or throw an uncaught exception.

Run the fast suite on every commit. Run the slow (randomized, generative) suite as often as you want to, perhaps before each release. If the slow suite discovers an input which "breaks" your function, add that input as a new test case in the fast suite.

When the randomized suite starts, it should generate a new random seed and print it to the console. It should also provide a way to manually set the seed, for cases where you want to repeat a previous run exactly.

Title: How should I unit test mathematical formulae?

Body:
I have a number of functions that are pretty close to the mathematical definition of a function. For example, a simplified version of one of these functions may look like:

```<code>int function foo(int a, int b) {
    return a * b;
}
</code>```

I'd like to unit test them, but I'm not sure what the best way to approach those tests, as these functions have very large ranges for parameter values. Every approach I've come up with feels lacking:

If I test with a discrete pre-defined subset of possible values, I fear the set I choose may not be representative of the whole, leading to a potentially endless cycle of adding new values to the subset every time an unexpected value is found. This seems like defeating the point of having a unit test in the first place.

If I test with a discrete subset of possible values that's randomly determined, I inherit all of the problems of picking the subset manually as well as the real chance that tests will fail randomly every run.

If I test with every possible value (e.g. 0 to 264), the tests will take forever.

My final thought on how to approach the problem was to avoid testing the implementation of the function entirely, either by:

Only testing that the function accepts two integers and returns an integer, or

Not testing the function at all

But if I'm not testing the functions at all—either in practice or in principle—I'm not sure how I can guarantee the correctness of the functions in the case of an eventual refactor.

What is the best way to test functions that have completely deterministic output, but can operate on a large range of possible inputs?


问:
Writing Unit Tests in the Middle
Is unit testing a 100% or not at all kind of deal?

I was browsing through my old projects and started adding features, this time with unit testing.  However, is this ultimately worthless if I'm going to be re-using past components that do not have unit tests?

Do I need to write unit tests for all the previous classes and not bother at all, or is it OK to only write unit tests for the new stuff I'm adding?

答:
Any unit tests are better than none. So it's not an all-or-nothing deal.

In your case, since Test Driven Development has not been the norm - you'll wonder how the tests are of any use.

You want to ensure that any future code you write doesnt break any (current) functionality - and that's where your sub-cases come in handy. If the well-written tests pass, you most likely have not damaged anything.
The next developer who comes along will thank you for the tests and documentation.

What you can start with is if you have a well split up layered architecture, pick up the data access tiers and work upwards (towards UI tier) with the tests. If the project has a domain model its the most likely candidate for TDD as its likely to have most of the logic. If the service (or business logic) tier is just making a call to Domain/Data Access tier no point in doing Service tier in TDD fashion. Those are fluffy tests and not of much value.

Added to a code coverage tool like Emma - and you can steadily monitor the improvement in overall test coverage.

Title: Writing Unit Tests in the Middle


答:
Learn from the framework that learned from all Java's pain points:

.NET provides two far more elegant solutions to this problem, exemplified by:

Dictionary<TKey, TValue>.TryGetValue(TKey, out TValue)

Nullable<T>.GetValueOrDefault(T default)

The latter is very easy to write in Java, the former just requires a "strong reference" helper class.