问:
Is MVC just the SEO of PHP programming?
There's around a zillion "PHP frameworks". And most of them bill themselves as following the MVC pattern. While it's welcome to overcome osCommerce coding style (processing logic heavily intermixed with SQL and HTML), there are certainly simpler and easier to follow approaches to get a maintainable application design.

The original MVC concept was targetted at GUI applications. And for Gtk/Python it seems feasible to follow it accordingly. But PHP web apps don't operate on live Views (GUI elements) and a persistent Controller runtime. It's quite certainly a misnomer if it just describes the used code + directory grouping or class naming.

"MVC" seems to be used like a buzzword for PHP frameworks. And I've actually seen one or two mature PHP frameworks admit it, but redefining the phrase anyway to match interna.

So is it generally snake oil? Why isn't better terminology used, and a more sensible concept for maintainable PHP propagated?

Some elaborative reasoning

Why I suspect that PHP implementations don't follow the real MVC pattern:

Models: in theory, Models should be fat and contain business logic, and controllers should be thin handlers (input->output). In reality the PHP frameworks advocate shallow Models. CI and Symfony for example equate Model == ORM. Even HTTP input is handled by the controller, isn't treated as model.

Views: workarounds with AJAX discounted, there can't be Views on web pages. PHP frameworks still pump out pages. The interface still effectively follows the ordinary HTTP model, there's no advantage over non-MVC applications. (And lastly, none of the widespread php frameworks can factually output to GUI Views instead of HTML. I've seen a PHP library that can operate Gtk/Console/Web, but the frameworks don't.)

Controller: I'm unsure. Controllers probably don't need to be long-running and persistently active in the MVC model. In PHP framework context, they're however mostly request handlers. Not really something to get argumentative about, but it just feels slightly buzzwordish.

Would there be better descriptors? I've seen acronyms like PMVC or HMVC thrown around. Though descriptions get more ambigous there, maybe these would describe the current web frameworks less hokey?

答:
But PHP web apps don't operate on live Views (GUI elements) and a persistent Controller runtime.

No, they sure do!

Think of AJAX applications, then the view asks something to the controller and gets a partial view back,

this view or data is then filled in somewhere in the page and thus live updated.

The Controller is also persistent because you can use cookies/sessions.

"MVC" seems to be used like a buzzword for PHP frameworks.

MVC is a Software Architecture, some frameworks might use it as a buzz, but others do it properly...

See a list of some frameworks on Wikipedia.

is MVC just the SEO of php programming?

MVC and SEO are two things apart, but yes... MVC is getting more popular.

Title: Is MVC just the SEO of PHP programming?


问:
Is outsourcing code more expensive in the long term? Does it harm code quality?
I am aware of a company that owns the intellectual property of a decent software product and makes an excellent income from licensing per annum. However, the director (non technical) complains about the cost of maintaining the development team, as it eats significantly into the profit margins, and is considering outsourcing development of specific modules to other countries that charge at a lower rate.

Personally, I don't think this will be a more cost effective solution in the long term. This can lead to communication breakdowns when there are problems, additionally the specifications will need to be water tight which can end up taking taking more time anyway. In my opinion, when working in teams communication is key - or is there an effective way of making this work?

答:
If you are working with a quality outsourcing team, and the management is willing to communicate and enforce acceptance criteria.

Then the cost will be about the same rate as an in-house developed product.

You may also get the same quality, too, if you're lucky.

I may be a little biased because my company keeps an in-house development staff, and has not outsourced any product development.  I suspect the experiences we've had with integration partners who have outsourced development had something to do with that decision.

ContentLicense: CC BY-SA 3.0

ContentLicense: CC BY-SA 2.5


答:
Well planned/done open source software could be your answer, because it can be highly profitable and the maintainance gets somewhat delegated to a community, but there is no recipe for success. The best advice I can give is recommending several talks about what really is open source and its shenanigans:

"How to Start an Open Source Project" by Jeremy Ruston (BT) http://vimeo.com/856110

"Open Source is Magic" by Chris DiBona (Google) http://www.youtube.com/watch?v=hmZyyBVbkOQ

"The Engines Of Community" by Jono Bacon (Canonical) http://www.youtube.com/watch?v=zKOrWubmzAY

"Open Source Projects and Poisonous People" Ben Collins-Sussman & Brian Fitzpatric (Google) http://www.youtube.com/watch?v=ZSFDm3UYkeE

"What's In It for Me? Benefits from Open Sourcing Code" Ben Collins-Sussman & Brian Fitzpatric (Google) http://www.youtube.com/watch?v=ZtYJoatnHb8&feature=related

And perhaps also:

"How to Choose a Business Model" by Roan Lavery (FreeAgent) http://vimeo.com/5588154

The thing about open source, in my opinion, is to build something of value and interest not only to you but to all, the power of open source lies within communities.

Also, if your boss/company is reluctant to open up the software, just isolate the specifics of your own business logic and know-how. So, what you would be doing:

Incubate an open source project with your resources

Grow a community

???

Profit =)

Yeah, I'm serious, and "???" involves what ever strategies you want to pursue after you gather enough interest. With today's tools such as Github and twitter you can spread the word easier, but mind that your first impression should be interesting enough.

If you don't actually want open source (which you must understand as a business model before implementing it, if you want to succeed), you can always launch it as a service, for that check the Carsonified video, but that implies a whole lot of other things for your company.

In the end, being open source or launching it as a service are ways of making the project sustainable on the long run.

Title: Is outsourcing code more expensive in the long term? Does it harm code quality?

Body:
I am aware of a company that owns the intellectual property of a decent software product and makes an excellent income from licensing per annum. However, the director (non technical) complains about the cost of maintaining the development team, as it eats significantly into the profit margins, and is considering outsourcing development of specific modules to other countries that charge at a lower rate.

Personally, I don't think this will be a more cost effective solution in the long term. This can lead to communication breakdowns when there are problems, additionally the specifications will need to be water tight which can end up taking taking more time anyway. In my opinion, when working in teams communication is key - or is there an effective way of making this work?


答:
In my experience, outsourcing a project aint the best solution when trying to get better margins.

At work we had something like that going on and well, as others also said, we ended up re-doing the hole thing and maintaining what was on a production server. Conclusion on the matter, it costed twice as much.

My opinion on the matter is that if you are thinking about trying to make a difference about margins outsourcing developments, you might be throwing away your investment. If you think about it, the product success is a matter of things working as spected, so if you change dev-team , things could turn ugly.


问:
Is there a good site to hire programmers for little projects?
I need to a piece of php code that goes beyond my abilities so I need to hire somebody to do it. It's not really something too long or complex so I wanted to know if there was a straightforward way to post my request and find somebody to do it for a certain amount. Does such a website exists or what's the best alternative? Anyway thanks a lot</p>

答:
There's a number of such sites, however, with the experiences that myself and some friends have had as a programmer on these sites, I can't in good conscience recommend any of them.

My suggestion is to get better at what you do: ask questions on StackOverflow if you can't immediately figure it out.

OwnerDisplayName: Lisandro


问:
Refactoring in domain driven design
I've just started working on a project and we're using domain-driven design (as defined by Eric Evans in Domain-Driven Design: Tackling Complexity in the Heart of Software.  I believe that our project is certainly a candidate for this design pattern as Evans describes it in his book.

I'm struggling with the idea of constantly refactoring.

I know refactoring is a necessity in any project and will happen inevitably as the software changes.  However, in my experience, refactoring occurs when the needs of the development team change, not as understanding of the domain changes ("refactoring to greater insight" as Evans calls it).  I'm most concerned with breakthroughs in understanding of the domain model.  I understand making small changes, but what if a large change in the model is necessary?

What's an effective way of convincing yourself (and others) you should refactor after you obtain a clearer domain model?  After all, refactoring to improve code organization or performance could be completely separate from how expressive in terms of the ubiquitous language code is. Sometimes it just seems like there's not enough time to refactor.

Luckily, SCRUM lends it self to refactoring.  The iterative nature of SCRUM makes it easy to build a small piece and change and it.  But over time that piece will get larger and what if you have a breakthrough after that piece is so large that it will be too difficult to change?

Has anyone worked on a project employing domain-driven design? If so, it would be great to get some insight on this one.  I'd especially like to hear some success stories, since DDD seems very difficult to get right.

Thanks!

答:
I've been a big fan of DDD for a while (with and without the safety net of a test framework).

The whole concept and lifecycle of refactoring doesn't change because you're now using a new design methodology. If it will take significant time, it has to have proportional benefit to the project in order to get that time from management.

With respect to doing it: in one instance, I partook in a 3 month major refactoring because of a 'breakthrough' in the understanding of the domain model. It required tests to verify the current behaviour, tests to verify the expected behaviour and changes to calling code. The benefits were significant however, and allowed the business to do many more things that it needed to do before but just wasn't able to. In essence, the refactoring was essentially a 'feature'.

Title: Refactoring in domain driven design


答:
The director wants to replace some of his experienced local developers with people in a distant country whose expertise he's not competent to judge, who have no experience with the code at all, and who can't be directly supervised or mentored by anybody who does know the code.

I've been through that twice. In both cases, the inexpensive foreign firms failed to deliver on-time with adequate quality. When the local developers heard work was heading overseas, they found other jobs rather than wait to be made redundant. As the expertise hemorrhage continued, schedules slipped, critical bugs weren't fixed, customers got angry and switched to competitors, and eventually both companies folded.

There were also strange problems with communication, expectations, and culture. For instance, a foreign team wasn't checking in much code or responding to email promptly. It turned out the local IT manager got a bonus for keeping costs down, so he had the entire office on a low-speed Internet connection. Another time, third-world QA testers routinely put several wildly different bugs in the same bug report; their manager was afraid of running out of bug numbers.

Some teams in inexpensive places are fine. From what I hear, Red Hat seems to have a very competent team in Beijing. But they already had years of experience with people working from around the world via telecommute before they started doing that, and the folks in Beijing are Red Hat employees, not an outsourcing firm.


答:
Check out the following sites:

oDesk

eLance

scriptlance

vWorker (originally rent a coder)

Rent A Coder

Code Monkey For Hire

FreeLancer

I know someone that reasonable success with oDesk.

Title: Is there a good site to hire programmers for little projects?

Body: I need to a piece of php code that goes beyond my abilities so I need to hire somebody to do it. It's not really something too long or complex so I wanted to know if there was a straightforward way to post my request and find somebody to do it for a certain amount. Does such a website exists or what's the best alternative? Anyway thanks a lot</p>


问:
Why does it matter that HTML and CSS are not programming languages?
Example here:

What languages should I know if I'm interested in building web applications?

Yes, I understand that HTML and CSS are not Turing-complete.  Yes, I understand that they are declarative, not imperative languages.  But why are people always clubbed over the head with this pedantic (and arguably obvious) fact when they ask a question about these languages?

答:
It might not be an "important" distinction, since arguably as much work goes in the html/css part of some websites as in the programming part.

But it is a significant distinction, since anybody that doesn't know what does it mean has no place in a team that does web development.

If a designer believes HTML is programming, let him stay designing with Adobe tools and do print-related designs; but don't believe a thing he might say about web apps.

If a developer thinks he's above designers because 'his' languages are Turing-complete, don't expect him to work well with designer, or that his code can be 'prettified' after it's done.


问:
Contract / Freelance Programming, The initial communication process / sending documents to them (terms, etc)
I've been searching around for info on contract / freelance programming as far as steps to take in the initial communication with a client (someone who has contacted me regarding a project). I am wondering if anyone has links to good resources as far as what I should send them (should I send them a document outlining "my process", etc?).

Often the initial requirements that they send are vague and I want to immediately "take charge" of the process and starting asking them questions, talking about price, etc but I don't want to be too overbearing so I'm just curious if there is much out there written about this, my google searches aren't turning up much that is good about this sort of thing.

答:
Alec the Geek's answer is great, but I'd like to add a few things.

A lot of the documents he mentions apply to fixed-price projects, and I haven't used them since I switched to only working by the hour eight years ago. For instance, I don't use change order documents. If somebody wants a change, I just give them a ballpark estimate, and proceed if they agree.

If the prospect doesn't bring it up first, I insist on signing a non-disclosure agreement very early, usually after the first or second phone conversation. I also have a standard NDA if the prospect doesn't have one. Depending on what you do, that may not be important for you.

While I have a process, I don't talk about it that way with prospects - I think it sounds pretentious. Also, sometimes clients have their own processes, and if they do, you need to fit in with those.

Take version control, for example. I ask, "What do you do for version control?" Sometimes they say, "We use X and we'll give you VPN access and a login," and then we're good to go. Or sometimes they ask, "Version control? What's that" and then I say, "Okay, never mind, I'll send you code drops. How often do you want them?" Then I use my own version control server, and they don't need to know anything more.

In many ways, the most important thing is just promoting good communication. Try to be relaxed in talking with your prospect, ask lots of questions, and be genuinely concerned about helping them meet whatever need led them to contact you. Most people will value that personal touch much more than paperwork.


答:
You hit it on the head when you said "declarative, not imperative".  Markup (be it HTML, CSS, or whatever) describes things.  The whole point of programming is to do things.

The skill set required to use markup is completely different than the skill set required to program.

The types of problems solved by writing markup are completely different from the types of problems solved by programming.

Title: Why does it matter that HTML and CSS are not programming languages?

Body:
Example here:

What languages should I know if I'm interested in building web applications?

Yes, I understand that HTML and CSS are not Turing-complete.  Yes, I understand that they are declarative, not imperative languages.  But why are people always clubbed over the head with this pedantic (and arguably obvious) fact when they ask a question about these languages?


答:
Here's my two cents.  HTML and CSS are clearly not programming languages.  For that reason, when I see HTML or CSS on somebody's resume under "Programming Languages", that simply tells me that this person does not know what he is talking about.

Other than that, no, it does not really matter.

By the way, programmers generally tend to be pedantic.  That simply comes with the job.


问:
What's the most important feature of quality software?
This question is along the same lines as this one, but instead of talking about quality of code, I'm talking about the final product from the users' perspective. If you had limited time / budget, and could only guarantee one attribute of the software (other than the basic requirements) that take it from decent software to good quality software, what would you consider most important?

Is it having as few bugs as possible? An intuitive interface? Helpful error messages? Good technical support and documentation? If we don't want our software looking like cheap crap to our users, what should we always remember to include?

答:
Intuitive and attractive user interface.  It may seem clichéd, but there's some truth to the statement "beautiful things work better."

Edit 9/18/2013:

It's been years now but Morten's question below has been stuck in my head all this time.  Yes, I do judge SQL servers by their user interface.  Everything has a user interface.  Well, almost everything anyway.  Shells, config files, commands, log files, they all are an interface for users.  Even most linux kernel modules have some UI exposed as files in /sys and /proc.  Yes, those are user interfaces.  Just because it isn't graphical doesn't make it any less important.

Example: I know Postgres is an excellent database.  I'm sad sometimes I don't use it more. I use MySQL more.  Why?  Part of it is that the shell commands are easier to use.  show databases; says what it does and does what it says. I looked that up once, the first time. Never did again. When I use psql, I can rarely remember. Is it \dl or just \l? No wait, isn't \dl something else? Huh, do I really want \dn? Shoot, ok, what's the command for help? \help? No, that's a list of SQL commands.  Where is the list of shell commands? Ah. \? has the list. WHY is \? different from \help?

Yeah if I used it all the time I'd get used to it. That's not the point. The point is that well designed software shouldn't require "getting used to."

I know that seems like a silly example but it does have an effect.


答:
For a software company, this is just plain stupid. The closest they could get to a reasonably intelligent decision would be to move the company to another location that has cheaper talent.

A software company outsourcing their software development isn't a software company anymore. I would argue that any gains earned will be short-lived, because you are creating your own competition. Once they realize that they know the product better than you, then they also realize that they don't need you anymore.


答:
IMO, providing a platform to evolve the program is the best feature a program can have. Firefox is a good example of this. They deliver a decent working product and as and when bugs are fixed, the software get updated automatically. This is very helpful for the enduser as he has the latest build always. This will also help in your case because when you get more budget and time, you can push new features easily.

I think the other best quality of a software product is how it handles exceptions and respond to exceptional scenarios. Most programs fails to handle this gracefully. They either get killed by unhandled excpetions or they produce meaningless error messages which confuses the user.

Creating bug free software is not a simple job. It will happen eventually as and when the program evolves. But it is programmers duty to make sure enough information is available to debug the issue. One good example of how to produce excellent error messages to user is VirtualBox. On any unexpected errors, it informs user what could have possible gone wrong with an option to contact the developers with the detailed log file for more help.

Title: What's the most important feature of quality software?

Body:
This question is along the same lines as this one, but instead of talking about quality of code, I'm talking about the final product from the users' perspective. If you had limited time / budget, and could only guarantee one attribute of the software (other than the basic requirements) that take it from decent software to good quality software, what would you consider most important?

Is it having as few bugs as possible? An intuitive interface? Helpful error messages? Good technical support and documentation? If we don't want our software looking like cheap crap to our users, what should we always remember to include?


答:
Programming language is a bit of an inexact term because it's a common term that is used by practitioners and the lay person as well.  Practitioners have a nuanced meaning of that term where lay person usually doesn't.  Normally their definition is if it has funny words/syntax that I don't immediately understand and programmers use it then that must be a programming language.  Not completely off the mark, but we can agree it's inexact.

Words like declarative, imperative, and turing complete are more precise terms with very specific meanings.  When you ask a question like why is HTML/CSS not a programming language you're asking for a more precise definition of what a programming language really is.  We aren't being pedantic, but trying to answer your question.  Are they the best terms to use when even if you google them it's hard to understand what they mean?  Depends.  Did you want the short or long answer. :-)

Programming languages are typically thought of being Turning-complete by programmers, but what does that mean?  It means the language can describe behavior or how to do things.  We formally call it logic.  HTML/CSS can describe there is a button located in the top right corner, or there is a table with 4 columns 5 rows, first two rows are yellow, and the bottom row has green text, and each cell in the table has 5 pixels of blank space around the content.

What HTML/CSS can't do is express the behavior or logic of what happens when you click the button.  It can't say when I click that button get the values out of that table and add them up, and write that value to a new row at the bottom of the table.  Describing behavior is roughly equivalent to Turning-complete without getting overly pedantic.

More precisely Turing-complete means that you could implement the language in itself.  That would mean I could write a javascript program that takes a string of javascript and it could execute it (and not using the eval() function).  In fact, I can write a javascript program that could take a program written in any Turing complete language and evaluate it.  That's what it means to be Turing complete.  All languages that are Turning complete are equivalent in what programs can be expressed.  Pretty amazing revelation if you think about it.


答:
Usability

Any other essential feature is just an attribute of or contributes to usability (bug-free, functionality, attractiveness, etc.)

This is the #1 most important feature because it is what proves that your software has value. If it has value, it makes money.


问:
Is using YouTube a good, inexpensive solution to building a website that requires users to post videos?
I'm diving into web development after ten years of desktop development and I have an idea for a Rails website that will rely on users posting short videos (5 -15 mins) they've recorded.  The website will be ad-supported and probably won't generate enough revenue to support hosting video based on how expensive I understand it to be, so the idea I had was to allow users to specify a link to the video they recorded and have posted on Youtube.  This way, YouTube funds all the resources (storage, bandwidth, etc.) needed for the videos and I simply embed them in my website.  My questions are...

Is it worth the poor design choice to separate the user's content service provider (in this case, YouTube) from my website in order to save the money it would cost me to host the videos myself?

Is there an inexpensive way for me to host the videos myself if the answer to my first question is "No!"?

If it's not a bad idea, do you see any other potential problems with this approach?

I apologize if this question is absurd in any way, I'm still getting familiar with the workings of web businesses.  Thanks so much in advance for your wisdom, I'm going to continue researching my questions right now.

答:
It's definitely a good idea to offload as much hosting as you can to sites that you know will still be around long after your website is gone (or until you make enough money to host content yourself). Your real issue is: how do you make it transparent to your users?

I haven't really done any research into this myself but it might be worth seeing if you can embed the youtube video upload form on your own page so that the user never has to leave your site. Depending on the assumed computer competency of your users, making them create a youtube account, upload the video and then submit the link to your site is probably a bad idea.


答:
If your talking about Business software it's all about Ease of Management. At my company we work hard to get rid of any piece of software the requires too many admins.

For desktop software for me it's all about Stability.  I hate software that crashes on me.


问:
What languages should I know if I'm interested in building web applications?
I'm interested in developing for the web and I'm curious what languages should I know besides html, css, javascript, php/python/ruby. I don't know much about c# or java to make a decision whether to learn them or not, are they used much in the field I'm interested in?
What other technologies should I look into ?</p>

答:
Just because no one has mentioned it yet, Flash with ActionScript 3 is a rather wide-spread solution for rich-media client-side applications. It always depends on what you want to develop.

I would rather suggest that learning Java or C# now from scratch would be a bit too much and probably couldn't really help your profile. With the languages you already know, you could in theory do everything you want (with the help of a little SQL, certainly.)

On the other hand, if you're at home in the Microsoft world, some ASP.NET stuff can't be wrong. And with C# and SilverLight, you can also do the things that you can do with Flash.

OwnerDisplayName: webguy


问:
Is it possible to speed up a hash table by using binary search trees for separate chaining?
I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and if yes then how? It would be easier to understand if solution is step by step, implementation of the logic.

I want to reduce the Search time in the hashtable (build using separate chaining), but at the same time I do not want the insert time to increase. For my project i cannot change the hash function to reduce collisions. But due to scalability, collision are happening. I am trying to find a work around, so that i can somehow work with the best access and insert time in case a collision occurs... i.e. to manage the current state of thing than to restructure the entire algorithm. If it does not pan out then will have to restructure. So any ideas?

答:
What you are asking for is possible given your constraints.

Analysis

A hash table's strength is its fast lookup and insertion speed. To get that speed, one must forsake any semblance of order in the table: i.e. entries are all jumbled up. A list is acceptable to use as a table entry because while traversal is O(n), the lists tend to be short assuming the hash table is sufficiently large and the objects stored in the table are hashed using a good quality hashing algorithm.

A binary search tree (BST) has fast insertion and lookup at O(log2 n). It also imposes a restriction on the elements it stores: there must be some way to order the elements. Given two elements A and B stored in the tree, it must be possible to determine if A comes before B or if they have equivalent order.

A hash table imposes no such restriction: elements in a hash table must have two properties. First, there must be a way to determine if they are equivalent; second, there must be a way to calculate a deterministic hash code. Order is not a requirement.

If your hash table elements do have an order, then you can use a BST as a hash table entry to hold objects with the same hash code (collisions). However, due to a BST having O(log2 n) lookup and insertion, that means the worst case for the whole structure (hash table plus BST) is technically better than using a list as a table entry. Depending on the BST implementation it will require more storage than a list, but likely not much more.

Please note that normally the overhead and behavior of a BST brings nothing to the table in real world situations as hash table buckets, which is why the theoretical poor performance of a list is acceptable. In other words, the hash table compensates for the list's weakness by placing fewer items in each list (bucket). However: the problem specifically stated that the hash table cannot increase in size, and collisions are more frequent than is typical in a hash table.

Implementation

I am not going to put code here because honestly it is not really necessary and you did not give a language anyway.

What I would do is simply copy whatever standard hash table your language's standard library contains into a new class, then change the table bucket type from a list to a tree. Depending on the language and its standard library this may be a very trivial thing to do.

Normally I would not advocate copy and paste coding like this. However, it is an easy way to get a battle-tested data structure very quickly.


答:
Using a binary tree for collision handling in a hash table isn't just possible - it has been done.

Walter Bright is best known as the inventor of the D programming language, but also wrote an ECMAScript variant called DMDScript. In the past, a headline claim of DMDScript (or possibly an ancestor - I seem to remember the name DScript) was that its hashtables tended to outperform those in a lot of similar languages. The reason - collision handling using binary trees.

I don't remember exactly where this is from, but the trees used were naive binary trees, with no partial balance scheme (not AVL, red-black or whatever) which makes sense as assuming the hashtable itself gets resized when it gets overfull and you don't get absurdly improbable rates of hash collisions, the binary trees should always be small. Basically, the worst case is still the same as using a linked list for collision handling (except you pay the price of two pointers per node instead of one) but the average case reduces the amount of searching within each hash bucket.

Title: Is it possible to speed up a hash table by using binary search trees for separate chaining?

Body:
I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and if yes then how? It would be easier to understand if solution is step by step, implementation of the logic.

I want to reduce the Search time in the hashtable (build using separate chaining), but at the same time I do not want the insert time to increase. For my project i cannot change the hash function to reduce collisions. But due to scalability, collision are happening. I am trying to find a work around, so that i can somehow work with the best access and insert time in case a collision occurs... i.e. to manage the current state of thing than to restructure the entire algorithm. If it does not pan out then will have to restructure. So any ideas?


问:
Picking m number in the best possible time
Imagine we want to pick m numbers from n numbers so that the difference of the maximum and minimum of the m numbers be minimum, for example if

m = 4

  n =6

  numbers: 10 12 10 7 5 22

The minimum difference is 5, picking 5, 7, 10, 10 from the numbers.

the first thing that pops into mind is to sort the numbers and pick the n number which has the minimum difference through looping on an m sized window on the n numbers.

I was wondering if there would be a way to do this in a time order less than O(nlogn), maybe through dynamic programming?

EDIT : The m numbers doesn't matter, the only thing the problem wants is the minimum difference (e.g. 5 for the provided example)

答:
Answer:

The element distinctness problem for lists of numbers is Θ(n log n) and you can reduce it to your problem in constant time by setting m=2 and checking whether the result is 0. So no, O(n log n) is optimal. (See the comments for a caveat, though)

More explanation:

A bit more explanation for those unfamiliar with the reduction idea: In the mentioned element distinctness problem, you get a list of numbers and you must find out whether they're distinct, i.e., whether there are no duplicates. So given some numbers, how do you solve that task? You could simply give the numbers, along with m=2, to any algorithm that solves Amen's problem. If that tells you "0", then you know there's a duplicate, and if it tells you something larger, then you know there isn't. So if there were an algorithm for Amen's problem faster than n log n, then by using it, you could also solve the distinctness problem faster than n log n. But that problem is already known to not be solvable faster than n log n, meaning Amen's problem isn't, either.

For good measure, here's a Python implementation of the algorithm Amen already mentioned. Sort, find the best window, and output it:

m, n, numbers = 4, 6, [10, 12, 10, 7, 4, 22]

numbers.sort()
i = min(range(n-m+1), key=lambda i: numbers[i+m-1] - numbers[i])
print numbers[i:i+m]
```
<p>You can see it in action at ideone. For finding just the difference, it gets even simpler:</p>
<pre class="lang-python prettyprint-override"><code>numbers.sort()
print min(high-low for low, high in zip(numbers, numbers[m-1:]))
</code>```

(yeah I love to advertise Python)

Body:
Answer:

The element distinctness problem for lists of numbers is Θ(n log n) and you can reduce it to your problem in constant time by setting m=2 and checking whether the result is 0. So no, O(n log n) is optimal. (See the comments for a caveat, though)

More explanation:

A bit more explanation for those unfamiliar with the reduction idea: In the mentioned element distinctness problem, you get a list of numbers and you must find out whether they're distinct, i.e., whether there are no duplicates. So given some numbers, how do you solve that task? You could simply give the numbers, along with m=2, to any algorithm that solves Amen's problem. If that tells you "0", then you know there's a duplicate, and if it tells you something larger, then you know there isn't. So if there were an algorithm for Amen's problem faster than n log n, then by using it, you could also solve the distinctness problem faster than n log n. But that problem is already known to not be solvable faster than n log n, meaning Amen's problem isn't, either.

For good measure, here's a Python implementation of the algorithm Amen already mentioned. Sort, find the best window, and output it:

m, n, numbers = 4, 6, [10, 12, 10, 7, 4, 22]

numbers.sort()
i = min(range(n-m+1), key=lambda i: numbers[i+m-1] - numbers[i])
print numbers[i:i+m]

You can see it in action at ideone. For finding just the difference, it gets even simpler:

numbers.sort()
print min(high-low for low, high in zip(numbers, numbers[m-1:]))

(yeah I love to advertise Python)

ContentLicense: CC BY-SA 4.0


问:
What characteristics does software have that's easily modified by other developers 6+ months after initial release?
One of the measures of maintainable software is its acceptance of changes later on by developers other than the one(s) who wrote it. But what characteristics does software have when it has been in production for awhile and the client wants a new developer to add a feature or fix a bug? What activities, attitudes, techniques, and/or practices contribute to software being "maintainable" 6 months later?</p>

答:
Automated testing

A comprehensive suite of automated tests is perhaps the most useful feature of a code-base when it comes to enabling someone with no prior familiarity to make substantial changes.

Usually when entering a new code-base you have low confidence that changes won't have unintended effects, so you start small and as you become more confident in your understanding of how the system works you make bigger changes.

Automated testing can really speed up this period of confidence building by ensuring you have the same understanding of what "correct" behaviour is, and that you haven't deviated from that.

Self-documenting code

External documentation and code-level documentation is great, but often it's a band-aid solution to code which is difficult to read.

Prioritise making your code easier to read, then if that's not enough consider where additional documentation would help.

Typically a high level system description or overview to find which code to start reading is helpful, but even then naming your directories and files so people can easily guess where things are is preferable.

Reliable automated build tools and dev environment

Make sure the process to get started developing on the code-base is quick, automated and reliable.

This particularly applies to running the application - don't make them have to update 10 different paths or click through 20 different IDE menus just to get it running, and make sure they can easily match the production environment.

No matter how good your instructions for building or deploying the project are, automating as much as possible for them will save the very likely possibility of someone new missing a step.


答:
In addition to existing answers, I would like to add:

Being simple, small, well-defined and limited.

Justification:

When each of these descriptions are negated and applied to a piece of software, it will imply an increasing difficulty of understanding its source code.

Being modular, and conforms to (1) LSP as well as (2) POLA.

LSP: Liskov substitution principle

POLA: Principle of least astonishment

These are the necessary (but not sufficient) conditions for preventing what is known as leaky abstractions.

Leaky abstractions are unavoidable, but violations of modularity, LSP and POLA will increase the amount of details that software programmers must juggle with when working with the software, thus increasing the mental burden.

The coding style is familiar to the programmer.

Justification:

This lowers the learning burden on the programmer.

The code is highly navigable.

Given task:

The customer would like to make a small change to a software feature. The customer describes the change request, using terminology and mental models which the customer has learned from the user interface. The software programmer must now figure out the different parts of source code that corresponds to what the user has described.

Evaluation criteria:

The terminology, mental model, and organizations of software features are highly similar between the user interface and the application source code. Furthermore, the source code is organized according to well-established software application architecture principles, which speeds up the programmer's understanding and navigation to the relevant parts of source code.

The software is traceable.

Given task:

A customer discovers a bug in the software that can be triggered when the user performs a sequence of steps on the user interface. Please investigate and fix the bug.

Evaluation criteria:

For a software application to be traceable, a programmer must be able to trace out its execution when the user performs a sequence of steps. It is hopeful that once the execution has been traced out, a follow-up investigation on the execution path will provide clues for the root cause and a resolution to the bug.

Typical ways to achieve traceability:

Tracing / Logging

Being compatible with debuggers

Writing out execution snapshots so that the software's internal states can be examined.

Built-in software code that can verify its consistency of states during runtime.

Title: What characteristics does software have that's easily modified by other developers 6+ months after initial release?

Body: One of the measures of maintainable software is its acceptance of changes later on by developers other than the one(s) who wrote it. But what characteristics does software have when it has been in production for awhile and the client wants a new developer to add a feature or fix a bug? What activities, attitudes, techniques, and/or practices contribute to software being "maintainable" 6 months later?</p>


问:
Design of actions handlers requiring some order
I have a REST application where 'actions' can be executed to perform anything in the system. For example: user.save, user.get, etc...

I also have pre and post execution 'handlers'.  For example a post execution handler is used to add tags to the users; it's an AddOn module that handles the tags of the users (and other entities). I also have another module (called Rules) that can, for example, validate the user information and do something based on that (eg, send an email).

The problem I'm facing now is that in general the execution order of those modules is not important, but sometimes it is. Take the following cases:

Example 1:

Action: Save user

Handler: Tag the user as "VIP"

Handler: Send an email if user is tagged as "VIP"

=> The email gets send.

Example 2:

Action: Save user

Handler: Send an email if user is tagged as "VIP"

Handler: Tag the user as "VIP"

=> The email won't be send.

All the operations (action and handlers) are executed inside a single transaction.

What would be a good solution to make sure the "Send email" handler is executed after the "Tag user" one?

Some ideas:
 - Have post-action handlers and post-(post-action) handlers. But how many post-post-post would I end up adding?
 - Add a weight or priority index to each handler. But when you end up having several handlers, the priorities tend to be confusing as each module doesn't know about the other modules and handlers.

What would you recommend? Thanks.

In case anyone finds it important: it's C# 4.5, ASP.NET, IIS.

答:
The general approach for ensuring a list of handlers getting executed in the right order is to not make every handler as being ready to execute, but to only make the first such handler as being ready, and pass on the remaining list of handlers to the first handler, so that the first handler can execute the next one on the list as the first one finishes. Each handler will then pop one off and execute the next, until the list becomes empty.

(This is not specific to ASP.NET; it is just a general approach in software.)

Another possibility is that you will need to have someone review your source code and implementation, to see whether you are using IHttpModule and IHttpHandler in the correct (intended) way. If your code did not achieve the desired effect because you are not using them according to the framework design, it will be futile to ask such questions on Programmers.
(This should not be done on Programmers.SE nor CodeReview.SE; you should seek someone from your own software department.)

OwnerDisplayName: Diego Jancic


答: In my opinion using MVC in php brings programmers to the web. It's easier to get from for example Java to PHP when you know how to work with MVC. </p>

Title: Is MVC just the SEO of PHP programming?

Body:
There's around a zillion "PHP frameworks". And most of them bill themselves as following the MVC pattern. While it's welcome to overcome osCommerce coding style (processing logic heavily intermixed with SQL and HTML), there are certainly simpler and easier to follow approaches to get a maintainable application design.

The original MVC concept was targetted at GUI applications. And for Gtk/Python it seems feasible to follow it accordingly. But PHP web apps don't operate on live Views (GUI elements) and a persistent Controller runtime. It's quite certainly a misnomer if it just describes the used code + directory grouping or class naming.

"MVC" seems to be used like a buzzword for PHP frameworks. And I've actually seen one or two mature PHP frameworks admit it, but redefining the phrase anyway to match interna.

So is it generally snake oil? Why isn't better terminology used, and a more sensible concept for maintainable PHP propagated?

Some elaborative reasoning

Why I suspect that PHP implementations don't follow the real MVC pattern:

Models: in theory, Models should be fat and contain business logic, and controllers should be thin handlers (input->output). In reality the PHP frameworks advocate shallow Models. CI and Symfony for example equate Model == ORM. Even HTTP input is handled by the controller, isn't treated as model.

Views: workarounds with AJAX discounted, there can't be Views on web pages. PHP frameworks still pump out pages. The interface still effectively follows the ordinary HTTP model, there's no advantage over non-MVC applications. (And lastly, none of the widespread php frameworks can factually output to GUI Views instead of HTML. I've seen a PHP library that can operate Gtk/Console/Web, but the frameworks don't.)

Controller: I'm unsure. Controllers probably don't need to be long-running and persistently active in the MVC model. In PHP framework context, they're however mostly request handlers. Not really something to get argumentative about, but it just feels slightly buzzwordish.

Would there be better descriptors? I've seen acronyms like PMVC or HMVC thrown around. Though descriptions get more ambigous there, maybe these would describe the current web frameworks less hokey?


问:
MVC, pagination, and massive search criteria
I am currently working on a project that has a fairly large search form - the form is 30 or fields or more.

Now I can of course map this out for routing by having my application pull the parameters and handle it as usual - but as you can imagine having that many fields can grow the URL to the near max character limit and becomes difficult to manage.

My question is this I suppose - what mechanism do people generally deploy for this? Should I store search criteria in the session and have it expire?  That is the only way I can see getting around forcing the pagination to "post" variables (via javascript etc. to continue the search criteria).

I'm looking to keep this as manageable as possible.  This search criteria is in a private application so I do have room for flexibility.

This is being built in PHP, JavaScript, CSS and isn't using any specific flavor of framework - although it is using the traditional MVC design pattern.

Any thoughts, help, past experiences handling this is appreciated.

答:
Practical URL length limit is around 2000 characters - think about whether you could optimize you filters to fit into it.

It this is not possible I'd probably implement this as a POST request. Disadvantages:

although this is in line with HTTP semantics of POST request (POST can be used for almost anything), it's not a best fit - it's effectively nullipotent request which could be cached by proxies, but now it can't be cached because it is POST. In practice I don't think this is very important, especially if it's some kind of internal application.

you can't copy & paste the URL from the browser to e.g. send the filter settings to a colleague

there's a bit weird behavior when you want to refresh the page - refreshing POST request causes the browser to ask you whether you want to re-submit the POST request. Workaround for this is that result page itself is GET which loads the data from the backend using AJAX POST.

Using session introduces state into the interactions which kind of violates one of the basic principles of HTTP. If you use GET to fetch the data, results can be cached, but this can actually produce wrong results because it depends on a state stored in backend. You should make sure that your GET pages with dependence on state can't be cached. Doing stateful interactions is also more complex in general, you need to always think in what state you are now and into what state you want to go which isn't always easy.

I actually implemented filtering using session few years ago, but for a different reason - filter settings will not be erased if you go to different pages and then come back. This is useful for a lot of applications.

But if you don't need this filter settings "persistence", I'd recommend you to use POST, as it is just simpler to use (correctly).


问:
How to concurrently write data in Java without locking?
How to implement a multi-threaded program in which each thread needs to write/output some data (in any order of course) but without the locking overhead that is involved with files or a particular data structure.

Is each thread writing to a separate file a feasible option? (wrt to locking overhead)

Can we use System.out.print or BufferWriter instead of files? Or is there any other elegant solution?

答:
If you have multiple threads generating data independently from each other, writing to separate files may be indeed a good option. There will still be some locking under the hood since the Operating System needs to keep the filesystem consistent, but it should be better than writing to a single file with manual locking or writing to standard output (which has internal synchronization). Similarily if you have access to some online storage which you can access via the network, you could send the data independently from each thread.

But there is a big "but". If you write out a lot of data (more than several MB/s, depending on machine specs), your file system may not be able to keep up. In such a situation, the bottleneck will be your file system and not locks in the app. If this happens, you might actually be better off with a single file and locking since concurrent writes to multiple locations may put more load on the filesystem and disk than writing at a single spot. So it all depends and any number of concurrent writes between one and many may be optimal. Your best bet would be to make the number of concurrent writes parametrizable and then to compare the final performance of the application for several different values.


问:
How to properly license open source software
I have a project I've been working on which I would like to push into a new, public Github repository as open source. After searching on StackExchange for the right license to use I've settled on the BSD license.

My question is: now what? Do I just need to copy the BSD license text into a file called LICENSE in the root of my repository and call it good? Is that the general rule for how all open source licenses work? Or do I need to notify some other organization that I'm using this license so I can 'enforce' it if necessary?

答:
If you have decided on a particular license suits your needs, then putting a License.txt file in a prominent place in the distro should be sufficient.  Also, you should make sure that the github metadata for your project, Maven POM files and so on also declare the licensing in the appropriate way.

Or do I need to notify some other organization that I'm using this license so I can 'enforce' it if necessary?

It is not necessary.  Enforcement of the license is entirely your responsibility.  (Not that there is a lot to enforce .... with a BSD license.)

However, if you were prepared to use a GNU license and assign copyright to the FSF (and your project is worth protecting), they would take care of enforcement of the license.


问:
Write Once - Use Many for server return values?
Well, I was wondering how I could do this or how this is done.

Having a server that accepts HTTP Requests and maintains a database for a mobile app, it is supposed to provide data for Android and iOS - or let's say - for more than one client.

Now that I write the Android client in Java and the iOS client in Objective-C I cannot simply have a shared project between my clients and the server for them to know how the objects returned from the server as JSON are supposed to look like as runtime objects.

For example if my server returns a simple Java object that gets marshalled to JSON:

```<code>public class Person {
    public String name;
    public int age;
}

// ..

public Person[] getListOfPersons(int minAge, int maxAge) {
    // ..
    return personList[];
}
</code>```

How can I introduce this return value for all kind of clients without having to write every object over and over again?

答:
There are any number of solutions to this, but fundamentally what you're looking for is some way to provide a specification file for your API that can be used to create a client for that API.

If you create a "level 3" REST API (see: Richardson Maturity Model) then you can almost leave it to the client to figure out (although in fact implementations seem to rely on the API providing some structured data according to a standard to "help" the client). However there's a chunk about getting to that level that is hard - at both ends.

So more pragmatically you pick a api/schema definition and one that appears to be gaining significant traction is Swagger and on github.


问:
Where to keep persistent services in MVVM architecture?
In an MVVM application I need to use some services that are persistent, e.g. network services like P2P and WCF where the main "engine" or server endpoint must remain up and running during the lifetime of my application. Currently I have coded these into singletons that abstracts functionality, using the engine or server instance internally.

Another example is a central message queue (like a main loop/BlockingCollection) where I need to queue various tasks that need to be processed sequentially.

How should I define and access such services in an MVVM context? I have read about the service locator pattern but this and singletons are often described as an anti-patterns?

答:
My tip is to look into Dependency injection. Here is a real world example of what you wanna do

Inject your behavior into the VM

https://github.com/AndersMalmgren/FreePIE/blob/master/FreePIE.GUI/Shells/Curves/CurveSettingsViewModel.cs#L18

In this example I inject a ISettingsManager into the VM

```<code>public CurveSettingsViewModel(ISettingsManager settingsManager)
{
     this.settingsManager = settingsManager;
}
</code>```

And it happens to be configured as a singleton by the IoC (Nothing the VM is aware of though and should not care about)

https://github.com/AndersMalmgren/FreePIE/blob/master/FreePIE.Core/Services/ServiceBootstrapper.cs#L49

```<code>private static void BindPersistance(StandardKernel kernel)
{
    kernel.Bind<ISettingsManager>().To<SettingsManager>().InSingletonScope();
}
</code>```

Body:
My tip is to look into Dependency injection. Here is a real world example of what you wanna do

Inject your behavior into the VM

https://github.com/AndersMalmgren/FreePIE/blob/master/FreePIE.GUI/Shells/Curves/CurveSettingsViewModel.cs#L18

In this example I inject a ISettingsManager into the VM

public CurveSettingsViewModel(ISettingsManager settingsManager)
{
     this.settingsManager = settingsManager;
}

And it happens to be configured as a singleton by the IoC (Nothing the VM is aware of though and should not care about)

https://github.com/AndersMalmgren/FreePIE/blob/master/FreePIE.Core/Services/ServiceBootstrapper.cs#L49

private static void BindPersistance(StandardKernel kernel)
{
    kernel.Bind<ISettingsManager>().To<SettingsManager>().InSingletonScope();
}


答:
There are obviously dependencies between the handlers.

One possible way to do this is to assign priorities to the modules - good thing is that it is easy to implement, but (as Frank Hileman noted) this solution is not scalable. Essentially you hide the dependencies between modules from the system and solve these dependencies yourself by manually ordering the modules - you need to keep these dependencies in your head or in some non-formal way (comments, documentation). This is fine as long as there isn't a lot of modules and dependencies.

More scalable solution would be to express the dependencies direclty in the code and then have some engine which resolves them automatically and orders the execution of the handlers. For example each handler can have two properties:

prerequisites (e.g. TAGS) - what is necessary to be done for this handler to be executed (tag operations must be completed)

operatesOn (again TAGS) - what is this handler doing (modifies tags)

Rule is that handler can be executed only after all of its prerequisites have been already finished. "Finished" means that there's no other handler with given prerequisites in its "operatesOn" field which hasn't been already executed.

Example, you have two handlers:

Handler tagging the user as VIP:

prerequisites: none

operatesOn: TAGS

Handler sending the email:

prerequisites: TAGS

operatesOn: USER_EMAIL

First you execute handlers with no dependencies (VIP tagging one). Then you try to find handlers for which all dependencies have been completed. You look at handler sending the email, it has dependency TAGS. You check that all handlers which operate on TAGS have been finished so you can execute handler sending the email.

This will effectively create a tree of handlers which expresses the dependencies. As with any trees, you must be careful to not introduce circular dependencies - one handler depends on the result of different handler which again depends on the result of the first handler.

Of course this has quite an upfront cost of designing such system, so it's more useful for complex (and generalized) systems with a lot of handlers and dependencies.

Title: Design of actions handlers requiring some order

Body:
I have a REST application where 'actions' can be executed to perform anything in the system. For example: user.save, user.get, etc...

I also have pre and post execution 'handlers'.  For example a post execution handler is used to add tags to the users; it's an AddOn module that handles the tags of the users (and other entities). I also have another module (called Rules) that can, for example, validate the user information and do something based on that (eg, send an email).

The problem I'm facing now is that in general the execution order of those modules is not important, but sometimes it is. Take the following cases:

Example 1:

Action: Save user

Handler: Tag the user as "VIP"

Handler: Send an email if user is tagged as "VIP"

=> The email gets send.

Example 2:

Action: Save user

Handler: Send an email if user is tagged as "VIP"

Handler: Tag the user as "VIP"

=> The email won't be send.

All the operations (action and handlers) are executed inside a single transaction.

What would be a good solution to make sure the "Send email" handler is executed after the "Tag user" one?

Some ideas:
 - Have post-action handlers and post-(post-action) handlers. But how many post-post-post would I end up adding?
 - Add a weight or priority index to each handler. But when you end up having several handlers, the priorities tend to be confusing as each module doesn't know about the other modules and handlers.

What would you recommend? Thanks.

In case anyone finds it important: it's C# 4.5, ASP.NET, IIS.


问:
How to help you client into making better requirements for you?
One of the most difficult and critical part of a project is to get good requirements from your client (internal or otherwise).

I understand by 'good requirement' one that is not so high-level that's barely tangible to the system, and not so low-level that it'll constraint the system creation with really needing it (it happens when your client has some knowledge in programming).

So, firstly how to guide you client into giving precise information that will help you at specification/implementation?

And finally, how one can tell at Requirement gathering if you have a mature enough requirement?

答:
You don't, because gathering requirements is not the job of the customer.

It's up to you to figure out what the customer needs and to translate it into a formal spec. The usual problem is that you often don't know the business domain quite well to determine the actual needs, while your customer doesn't know what is technically doable, and what is not.

This is why requirements gathering should rely on regular communication between you and your customer, which makes it possible for you to understand better the actual needs.

In order to help the customer to realize what answers her needs better technically, prototypes (and mockups) are usually used.


问:
Algorithms for allocating N balls into M boxes
Every box has at least no balls and at most N balls. Of course the total number of balls in M boxes must equal to N.

For each allocation, I calculated a value based on the allocation: V=f(n_1,n_2,...n_m). I want to find out the maximum of V given N,M and f. I need to store the maximum V and the corresponding allocation results.

Using loops the complexity should be O(N^M), but loop isn't the way to go in this case.

Any hint or suggestion is greatly appreciated. Having few classical DP algorithm at hand but no luck.

Note: f = f1 + f2 + ... f_m, where f(i)'s are polynomials. f(i) only depends on n(i).

答:
If you need not strictly the global maximum but just a “fairly good” solution, you can approach this kind of problem by an approximation technique known as local search.  The idea is that you start with a given solution and try to improve it by making “simple small steps”.

In your case, such a step could be moving one ball from one box to another.  Here is then a simplistic local search algorithm:

amax ← ⊥

fmax ← –1

Repeat k times:

Generate a random allocation a ← (n1, …, nm)

While you can find i and j such that ni > 0, nj < N and moving one ball from box i to box j increases f(a):

Set a ← (n1, …, ni – 1, …, nj + 1, … nm)

If f(a) > fmax:

amax ← a

fmax ← f(a)

Output the best allocation amax found

If you only repeat the main loop once (k = 1), you'll get the local maximum from a random starting point.  This will often not be a globally good solution.  By repeating the local search a few times from different random starting points and finally taking the best local maximum, you increase your chances to reach something closer to the global maximum.

If you know more about your f, you might be able to design a better “small step” than simply moving one ball into another box.

The kind of algorithm like local search with multiple random restarts is known as a meta heuristic since it is applicable to a large number of problems without knowing much about them.  (This particular form is also sometimes referred to as the hill climber algorithm.)  If you search for meta heuristics, you'll find a wealth of approaches to choose from.


答:
I do not know what DP algorithms you tried, but here is one which solves your problem in  O(M * N²), which is certainly better than O(N^M).

The algorithm works inductively by increasing number of boxes. In each step, you store the maximum of f1+...+f_m, where m is the number of boxes in the particular step (0<=m<=M). For a given m, you solve the problem for every n between 0 and N, and you use the solutions for m-1 boxes to solve the problem for m boxes (also for every n between 0 and N).

For m=1, generate the solutions for 0<=n<=N  -> O(N)

For m=2 and each 0<=n<=N, use still "brute force" -> O(N²)

For m=3 and each 0<=n<=N, and 0<=k<=n, calculate f3(k) + max((f1(x1)+f2(x2)), where x1 + x2 = n-k (the maximum term is the result of the step m=2. For each n, keep the maximum value over all k.  -> still O(N²), which is the same as O((m-1)*N²)

Now continue that way: each step needs only N*(N+1)/2, thus O(N²), new calculations, and you have M-1 steps in total, so the overall complexity  is O(M * N²).

Title: Algorithms for allocating N balls into M boxes

Body:
Every box has at least no balls and at most N balls. Of course the total number of balls in M boxes must equal to N.

For each allocation, I calculated a value based on the allocation: V=f(n_1,n_2,...n_m). I want to find out the maximum of V given N,M and f. I need to store the maximum V and the corresponding allocation results.

Using loops the complexity should be O(N^M), but loop isn't the way to go in this case.

Any hint or suggestion is greatly appreciated. Having few classical DP algorithm at hand but no luck.

Note: f = f1 + f2 + ... f_m, where f(i)'s are polynomials. f(i) only depends on n(i).


问:
Should we define types for everything?
Recently I got into a problem with the readability of my code.

I had a function that did an operation and returned a string representing the ID of this operation for future reference (a bit like OpenFile in Windows returning a handle). The user would use this ID later to start the operation and to monitor its finish.

The ID had to be a random string because of interoperability concerns. This created a method that had a very unclear signature like so:

public string CreateNewThing()
```

<p>This makes the intent of the return type unclear. I thought to wrap this string in another type that makes its meaning clearer like thus:</p>

<pre class="lang-cs prettyprint-override"><code>public OperationIdentifier CreateNewThing()
</code>```

The type will contain only the string and be used whenever this string is used.

It's obvious that the advantage of this way of operation is more type safety and clearer intent, but it also creates a lot more code and code that isn't very idiomatic. On the one hand I like the added safety, but it also creates a lot of clutter.

Do you think it is a good practice to wrap simple types in a class for safety reasons?

答:
Do you think it is a good practice to wrap simple types in a class for safety reasons?

Sometimes.

This is one of those cases where you need to weigh the problems that may arise from using a string instead of a more concrete OperationIdentifier. What are their severity? What is their likeliness?

Then you need to consider the cost of using the other type. How painful is it to use? How much work is it to make?

In some cases, you'll save yourself time and effort by having a nice concrete type to work against. In others, it won't be worth the trouble.

In general, I think that this sort of thing should be done more than it is today. If you have an entity that means something in your domain, it is good to have that as its own type, since that entity is more likely to change/grow with the business.

Title: Should we define types for everything?


答:
As with all tips, knowing when to apply the rules is the skill. If you create your own types in a type-driven language you get type checking. So generally that is going to be a good plan.

NamingConvention is key to readability. The two combined can convey intention clearly.

But /// is still useful.

So yes, I would say create many own types when their lifetime is beyond a class boundary. Also consider the use of both Struct and Class, not always Class.

Title: Should we define types for everything?

Body:
Recently I got into a problem with the readability of my code.

I had a function that did an operation and returned a string representing the ID of this operation for future reference (a bit like OpenFile in Windows returning a handle). The user would use this ID later to start the operation and to monitor its finish.

The ID had to be a random string because of interoperability concerns. This created a method that had a very unclear signature like so:

public string CreateNewThing()
```

<p>This makes the intent of the return type unclear. I thought to wrap this string in another type that makes its meaning clearer like thus:</p>

<pre class="lang-cs prettyprint-override"><code>public OperationIdentifier CreateNewThing()
</code>```

The type will contain only the string and be used whenever this string is used.

It's obvious that the advantage of this way of operation is more type safety and clearer intent, but it also creates a lot more code and code that isn't very idiomatic. On the one hand I like the added safety, but it also creates a lot of clutter.

Do you think it is a good practice to wrap simple types in a class for safety reasons?


答:
Primitives, such as string or int, have no meaning in a business domain. A direct consequence of this is that you may mistakenly use an URL when a product ID is expected, or use quantity when expecting price.

This is also why Object Calisthenics challenge features primitives wrapping as one of its rules:

Rule 3: Wrap all primitives and Strings

In the Java language, int is a primitive, not a real object, so it obeys different rules than objects. It is used with a syntax that isn’t object-oriented. More importantly, an int on its own is just a scalar, so it has no meaning. When a method takes an int as a parameter, the method name needs to do all of the work of expressing the intent. If the same method takes an Hour as a parameter, it’s much easier to see what’s going on.

The same document explains that there is an additional benefit:

Small objects like Hour or Money also give us an obvious place to put behavior that would otherwise have been littered around other classes.

Indeed, when primitives are used, it's usually extremely difficult to track the exact location of the code related to those types, often leading to severe code duplication. If there is Price: Money class, it is natural to find the range checking inside. If, instead, a int (worse, a double) is used to store product prices, who should validate the range? The product? The rebate? The cart?

Finally, a third benefit not mentioned in the document is the ability to change relatively easy the underlying type. If today my ProductId has short as its underlying type and later I need to use int instead, chances are the code to change will not span the entire code base.

The drawback—and the same argument applies to every rule of Object Calisthenics exercise—is that if quickly becomes too overwhelming to create a class for everything. If Product contains ProductPrice which inherits from PositivePrice which inherits from Price which in turn inherits from Money, this is not clean architecture, but rather a complete mess where in order to find a single thing, a maintainer should open a few dozen files every time.

Another point to consider is the cost (in terms of lines of code) of creating additional classes. If the wrappers are immutable (as they should be, usually), it means that, if we take C#, you have to have, within the wrapper at least:

The property getter,

Its backing field,

A constructor which assigns the value to the backing field,

A custom ToString(),

XML documentation comments (which makes a lot of lines),

A Equals and a GetHashCode overrides (also a lot of LOC).

and eventually, when relevant:

A DebuggerDisplay attribute,

An override of == and != operators,

Eventually an overload of the implicit conversion operator to seamlessly convert to and from the encapsulated type,

Code contracts (including the invariant, which is a rather long method, with its three attributes),

Several converters which will be used during XML serialization, JSON serialization or storing/loading a value to/from a database.

A hundred LOC for a simple wrapper makes it quite prohibitive, which is also why you may be completely sure of the long-term profitability of such wrapper. The notion of scope explained by Thomas Junk is particularly relevant here. Writing a hundred LOCs to represent a ProductId used all over your code base looks quite useful. Writing a class of this size for a piece of code which makes three lines within a single method is much more questionable.

Conclusion:

Do wrap primitives in classes which have a meaning in a business domain of the application when (1) it helps reducing mistakes, (2) reduces the risk of code duplication or (3) helps changing the underlying type later.

Don't wrap automatically every primitive you find in your code: there are many cases where using string or int is perfectly fine.

In practice, in public string CreateNewThing(), returning an instance of ThingId class instead of string might help, but you may also:

Return an instance of Id<string> class, that is an object of generic type indicating that the underlying type is a string. You have your benefit of readability, without the drawback of having to maintain a lot of types.

Return an instance of Thing class. If the user only needs the ID, this can easily be done with:

```<code>var thing = this.CreateNewThing();
var id = thing.Id;
</code>```

Title: Should we define types for everything?

Body:
Primitives, such as string or int, have no meaning in a business domain. A direct consequence of this is that you may mistakenly use an URL when a product ID is expected, or use quantity when expecting price.

This is also why Object Calisthenics challenge features primitives wrapping as one of its rules:

Rule 3: Wrap all primitives and Strings

In the Java language, int is a primitive, not a real object, so it obeys different rules than objects. It is used with a syntax that isn’t object-oriented. More importantly, an int on its own is just a scalar, so it has no meaning. When a method takes an int as a parameter, the method name needs to do all of the work of expressing the intent. If the same method takes an Hour as a parameter, it’s much easier to see what’s going on.

The same document explains that there is an additional benefit:

Small objects like Hour or Money also give us an obvious place to put behavior that would otherwise have been littered around other classes.

Indeed, when primitives are used, it's usually extremely difficult to track the exact location of the code related to those types, often leading to severe code duplication. If there is Price: Money class, it is natural to find the range checking inside. If, instead, a int (worse, a double) is used to store product prices, who should validate the range? The product? The rebate? The cart?

Finally, a third benefit not mentioned in the document is the ability to change relatively easy the underlying type. If today my ProductId has short as its underlying type and later I need to use int instead, chances are the code to change will not span the entire code base.

The drawback—and the same argument applies to every rule of Object Calisthenics exercise—is that if quickly becomes too overwhelming to create a class for everything. If Product contains ProductPrice which inherits from PositivePrice which inherits from Price which in turn inherits from Money, this is not clean architecture, but rather a complete mess where in order to find a single thing, a maintainer should open a few dozen files every time.

Another point to consider is the cost (in terms of lines of code) of creating additional classes. If the wrappers are immutable (as they should be, usually), it means that, if we take C#, you have to have, within the wrapper at least:

The property getter,

Its backing field,

A constructor which assigns the value to the backing field,

A custom ToString(),

XML documentation comments (which makes a lot of lines),

A Equals and a GetHashCode overrides (also a lot of LOC).

and eventually, when relevant:

A DebuggerDisplay attribute,

An override of == and != operators,

Eventually an overload of the implicit conversion operator to seamlessly convert to and from the encapsulated type,

Code contracts (including the invariant, which is a rather long method, with its three attributes),

Several converters which will be used during XML serialization, JSON serialization or storing/loading a value to/from a database.

A hundred LOC for a simple wrapper makes it quite prohibitive, which is also why you may be completely sure of the long-term profitability of such wrapper. The notion of scope explained by Thomas Junk is particularly relevant here. Writing a hundred LOCs to represent a ProductId used all over your code base looks quite useful. Writing a class of this size for a piece of code which makes three lines within a single method is much more questionable.

Conclusion:

Do wrap primitives in classes which have a meaning in a business domain of the application when (1) it helps reducing mistakes, (2) reduces the risk of code duplication or (3) helps changing the underlying type later.

Don't wrap automatically every primitive you find in your code: there are many cases where using string or int is perfectly fine.

In practice, in public string CreateNewThing(), returning an instance of ThingId class instead of string might help, but you may also:

Return an instance of Id<string> class, that is an object of generic type indicating that the underlying type is a string. You have your benefit of readability, without the drawback of having to maintain a lot of types.

Return an instance of Thing class. If the user only needs the ID, this can easily be done with:

var thing = this.CreateNewThing();
var id = thing.Id;


答:
I would use the scope as a rule of thumb: The narrower the scope of generating and consuming such values is, the less likely you have to create an object representing this value.

Say you have the following pseudocode

```<code>id = generateProcessId();
doFancyOtherstuff();
job.do(id);
</code>```

then the scope is very limited and I would see no sense in making it a type.
But say, you generate this value in one layer and pass it to another layer (or even another object), then it would make perfect sense to create a type for that.

Title: Should we define types for everything?

Body:
I would use the scope as a rule of thumb: The narrower the scope of generating and consuming such values is, the less likely you have to create an object representing this value.

Say you have the following pseudocode

id = generateProcessId();
doFancyOtherstuff();
job.do(id);

then the scope is very limited and I would see no sense in making it a type.
But say, you generate this value in one layer and pass it to another layer (or even another object), then it would make perfect sense to create a type for that.


问:
Version controlling a database's contents
I'm working on a web project that involves user-editable content, and I'd like to be able to do version-tracking of the actual content, which lives in a database. Basically, I want to implement wiki-style change histories.

Doing some background research, I see a lot of documentation about how to version your database schema (mine is actually already controlled), but any existing strategies about how to track your database content changes are lost in the avalanche of schema versioning stuff, at least in my searches.

I can think of a few ways to implement my own change tracking, but they all seem rather crude:

Save the entire row on each change, relate row back to source id with a Primary key (what I'm leaning towards currently, it's the simplest). Lots of small changes could produce a lot of table bloat, though.

save before/after/user/timestamp for each change, with a column name to relate the change back to the relevant column.

save before/after/user/timestamp with a table for each column (would result in too many tables).

save diffs/user/timestamp for each change with a column (this would mean that you'd have to walk the entire intervening change history to go back to a certain date).

What is the best approach here? Rolling my own seems like I'm probably reinventing someone else's (better) codebase.

Bonus points for PostgreSQL.

答:
Well, I wound up just going with the simplest option, a trigger that copies the old version of a row to a per-table history log.

If I wind up with too much database bloat, I can look at possibly collapsing some of the minor history changes, if needed.

The solution wound up being rather messy, since I wanted to generate the trigger functions automatically. I'm SQLAlchemy, so I was able to produce the history table by doing some inheritance hijinks, which was nice, but the actual trigger functions wound up requiring some string munging to properly generate PostgreSQL functions properly, and map the columns from one table to another correctly.

Anyways, it's all on github here.


问:
How do you unit test \ use TDD methods for ETL's and reporting projects?
ETL projects are projects created using an ETL (Extract - Transform - Load) tool such as SSIS, PowerCenter,etc

These typically involve reading data from an external source, loading it to a staging database, performing certain transformations and loading it to a final database

A simple example would be to use SSIS to read excel files provided by schoolteachers using SSIS and load them into a database. Then write stored procedures or more SSIS packages to calculate the grades of each student and load that data into a data mart\warehouse

You then build stored procedures on top of the mart to generate output which is used by reporting tools (SSRS\Excel\etc) to generate visualizations.

I'm trying to understand how to perform TDD and proper unit testing in this scenario. Tests for ETL's are mostly about ensuring the data loaded in the staging tables matches is the right subset of the data from the source. So implementing a test for it leads to implementing a mini version of the ETL. The output of the report SP's depends on the data in the tables themselves, so one cannot have a stable set of output data without a maintenance nightmare even if you do create a database containing scrubbed test data

Example:

Sprint 1 : Student table contains Name, Age, Grade

You create test data for this table, and unit tests based on that

Sprint 2: A gender field is added to the table.

Now, if you refresh the data in the student field to populate the gender attribute, the test cases are invalidated since the data changed. And if you dont, you cant create test cases that require the gender column

答:
What I have done in the past is use Acceptance Test Driven Development. ETL code is often distributed across different stages/languages and technologies AND tightly coupled.  Most ETL process are dependent on the sequence of transformations in the pipeline.

The risk in using unit test only in ETL is that it won't cover the integrations. The sequencing of transformations is an equal part to the actual transformations in many ETLs. If I am spending resources on creating an automated test suite I would make sure it covered the sequencing as well.

I would focus on TDD for each unique transformation sequence or at least include these tests in a larger test suite. If there are too many combinations you may have to pick and choose which sequences to test.  The idea is to validate the ETL pipeline for the data set(s) it will be used on. As well as making sure you have test coverage on all your code.


问:
Behavior Driven Development and Unit Testing in Python
We might be interested in starting to incorporate a unit test suite to our project, which is coded in Python (and it uses Redis, PostgreSQL and some third-party libraries, if that bears into the solution).  The benefits we want to achieve are:

Once the project is up to speed, we want to be able to specify new behavior quickly and efficiently, to help improve communication and team productivity.  Read: We want BDD, but have already started coding without it.

Excellent textual support (i.e. the tests can be read almost as natural text), so as to make it easier to write and read tests.

Ability to automatically run tests (at the very least, to be able to include the running in a Bash script or something like that).  We use Windows and Linux for development, and Linux servers, so Linux support is our primary requirement.

Integration with github.  I don't know if it is possible, but I've seen some projects in github which have a "Passing" or "Failing" status on them and it would be great to have that for our project.

What are good tools / libraries that can help us do this, and, most importantly, what are good ways to incorporate BDD into a Python project?

Thank you very much!  Any suggestions are appreciated.

答:
I think you should try Morelia:
https://morelia.readthedocs.org/en/latest/

It passes your 4-point requirements list:

It's BDD tool built on Python's unittests module

Executed tests are textual description.

If you can automatically run traditional Unit Tests then Morelia can be run same way.

I think the most common CI for github is Travis-CI which can run unit tests so that it can run Morelia.


问:
What's the most important feature of quality software?
This question is along the same lines as this one, but instead of talking about quality of code, I'm talking about the final product from the users' perspective. If you had limited time / budget, and could only guarantee one attribute of the software (other than the basic requirements) that take it from decent software to good quality software, what would you consider most important?

Is it having as few bugs as possible? An intuitive interface? Helpful error messages? Good technical support and documentation? If we don't want our software looking like cheap crap to our users, what should we always remember to include?

答: it has to do what the user needs it to do easily and quickly.  it has to be easy to use.  </p>


问:
Sorting a large number of unknown items with multiple stacks
Here is a problem I'm trying to solve for a personal project. I'm not exactly sure how best to even approach it.

Problem:

I have a single stack already populated with several thousands of unknown items. (Not completely unique items, maybe 300 different values. So it's a stack with plenty of duplicates shuffled together in a random order.) I want to sort these items by moving them between a limited number of other stacks. (Maybe between 10-30 stacks at most.) An algorithm with less moves is ideal.

Limitations:

The initial stack is full of unknown values (except for the top item).

I can read the top item in a stack.

I can move the top item of a stack directly to the top of another stack.

I can check if a stack is empty.

I can remember and store all the items I have read and moved.

Based on the above limitations, all the items need to be moved once to another stack just so they can be read/scanned. Then I would know where and what everything is.

Once this is done I can do the real sorting. (This is the part I mainly need help with.) After I've read and moved all the items once, I can then calculate and queue up all the stack moves needed to actually sort the items.

Presorting and optimizing:

It might be too early to think about this, but I can potentially do some pre-sorting onto different stacks as the items are first read and moved.

I do have a overall idea about the distribution of all the items. For instance, if the items were sorted alphabetically, I might know that items values starting with "S" are five times more common then items that start with "V" and that "S" is also twice as common as items starting with "A". Is knowing this even useful here?

I'm not sure if this would be helpful for pre-sorting but in some instances I might also know all the possible values of the items. So I could calculate if the value of an item is "odd" or "even". Even other similar calculations can be done (like the remainder of a larger modulos operation). Maybe separating the items into "odd" or "even" stacks would make it easier to weave into the final sorted stacks. I'm just speculating here, since I haven't run any tests yet.

Desired Result:

Items don't need to be sorted back into a single stack, it would probably actually be more ideal if they were moved into several smaller stacks of somewhat equal size. For example, I might end with alphabetically sorted stacks as such: A-D, D-K, K-R, R-S, S-Z.

What kind of algorithms would be best given these limitations? Pseudo code?

答:
Do a "binning" of the initial black box stack into N groups of equal proportions (your A-D, D-K...). At that point you can use any O(n log n) algorithm to sort each group in turn.

Actually, you could pop items from the black-box stack directly into a group of N red-black trees.

But if you have lots of identical elements... could you not just store a counter into a single tree? If you only have 300 values, you might then store your several thousands values into a single tree of comparatively small height. When extracting values you'd just decrement the counter and delete the element when the counter eventually reached 0. And you could use the tree to fill the output stacks if you found that you still needed them.


答:
No, you should not define types (classes) for "everything".

But, as other answers state, it often is useful to do so. You should develop – consciously, if possible – a feeling or sense of too-much-friction due to the absence of a suitable type or class, as you write, test, and maintain your code. For me, the onset of too-much-friction is when I want to consolidate multiple primitive values as a single value or when I need to validate the values (i.e. determine which of all possible values of the primitive type correspond to valid values of the 'implied type').

I've found considerations such as what you've posed in your question to be responsible for too much design in my code. I've developed a habit of deliberately avoiding writing any more code than necessary. Hopefully you're writing good (automated) tests for your code – if you are, then you can easily refactor your code and add types or classes if doing so provides net benefits for the ongoing development and maintenance of your code.

Telastyn's answer and Thomas Junk's answer both make a very good point about the context and usage of the relevant code. If you're using a value inside a single block of code (e.g. method, loop, using block) then it's fine to just use a primitive type. It's even fine to use a primitive type if you're using a set of values repeatedly and in many other places. But the more frequently and widely you're using a set of values, and the less closely that set of values corresponds to the values represented by the primitive type, the more you should consider encapsulating the values in a class or type.

Title: Should we define types for everything?


问:
Shared database vs tightly coupled message model
We have an ASP.NET MVC application sitting on top of a MySQL database. Now we're thinking about creating a public REST API so that third parties may integrate their services with ours.

Now, I would much prefer not to have the API application access the same database directly. I like the idea of an application that "owns" it's own data. Making an internal change in the web app´s data model would inevitably affect the public API as well:

However, the only alternative I can think of, would be to set up a message bus and have the two applications communicate through that. So when some external client requests a piece of data from our public API, the API would then create a message on the service bus which is then handled by the web app, which then responds with the desired data. If we go with this design, the web app would be the only application that accesses the database. And we might use different patterns of information exchange over the service bus, such as request/response as in this examples, or pub-sub for stuff like "something has happened".

Now, to make sure the message types are consistent in both applications, I was thinking about putting them in a separate assembly, and have the two applications consume it as a Nuget package. However, this would kinda bring us back to square one, because now both applications are tightly coupled to this shared object model. And even If we use practices like semantic versioning, I fear it will be a source of much frustration and a lot of extra work.

Any comments on this? Perhaps there is a completely different architecture that would fit our needs better?

EDIT:

I should point out that the service bus I'm talking about would not be an ESB, but rather a simple message queue.

I must say I'm quite puzzled by the lack of articles and blog posts on this subject. It seems nowadays every SaaS out there has an outwards facing API, so there should have emerged some best practices by now.

答:
I agree that web app must be the only one accessing mysql. So web app must inevitably provide some sort of api that let your public web api access relevant data.
This API is a contract between web app and mysql that allow them to be developed separately without breaking.

The complexity and flexibility of this API must reflect your business needs but keep it as simple as possible.
If you can, stick to a simple REST API or whatever is easiest to integrate and document with your framework.


问:
Why does it matter that HTML and CSS are not programming languages?
Example here:

What languages should I know if I'm interested in building web applications?

Yes, I understand that HTML and CSS are not Turing-complete.  Yes, I understand that they are declarative, not imperative languages.  But why are people always clubbed over the head with this pedantic (and arguably obvious) fact when they ask a question about these languages?

答:
I think it comes down to this - HTML & CSS, while complicated enough to require some savvy, are presentation languages, most suited as the format for generated reports. Therefore, people who can only do these were not considered coders. Bearing in mind that some coders have been in computing long enough to remember when the average word-processor took more command syntax to style text than HTML.

I will temper this with the note that gatekeeping by saying who is a "real" programmer and not is less than helpful. Encouraging people learning HTML and CSS into learning javascript and finding a world of more interesting flexibility is a better way. CSS has also become complicated enough that animations, composition and other concepts are present, and it's declarative style is similar to languages like HCL.

What some would call a 'real' language is that which would process data in some way to generate a report. Or something that could be used to write a game. Knowing HTML & CSS inside and out is a valuable skill, but it is much more so combine with knowledge of JS for front end, and Java, PHP, Perl, Ruby, Python, C/C++ or C# at the back end.

Conversely, someone who only knows one of those 'real' languages without any web front end technologies, are very much limiting their own flexibility as a coder.


问:
How to represent a Rubik's Cube in a data structure
If I am attempting to simulate a Rubik's Cube, how would you create a data structure to store the cube's state in memory, with X number of tiles per side?

Things to consider:

the cube can be of any size

it is a Rubik's cube, so layers can be rotated

答:
Since you already received great answers, let me add just a detail.

Irrespective of your concrete representation, note that lenses are a very fine tool for "zooming in" on the various parts of a cube. For instance, look at the function cycleLeft in this Haskell code. It is a generic function which cyclically permutes any list of length 4. The code for performing the L move looks like this:

```<code>moveL :: Aut (RubiksCube a)
moveL =
    cong cube $ cong leftCols cycleLeft
              . cong leftSide rotateSideCW
</code>```

Thus cycleLeft operates on the view given by leftCols. Similarly, rotateSideCW, which is a generic function taking a side to a rotated version of it, operates on the view given by leftSide. The other moves can be implemented in similar ways.

The goal of that Haskell library is to create pretty pictures. I think it succeeded:

Body:
Since you already received great answers, let me add just a detail.

Irrespective of your concrete representation, note that lenses are a very fine tool for "zooming in" on the various parts of a cube. For instance, look at the function cycleLeft in this Haskell code. It is a generic function which cyclically permutes any list of length 4. The code for performing the L move looks like this:

moveL :: Aut (RubiksCube a)
moveL =
    cong cube $ cong leftCols cycleLeft
              . cong leftSide rotateSideCW

Thus cycleLeft operates on the view given by leftCols. Similarly, rotateSideCW, which is a generic function taking a side to a rotated version of it, operates on the view given by leftSide. The other moves can be implemented in similar ways.

The goal of that Haskell library is to create pretty pictures. I think it succeeded: