问:
How to rotate an array of bits

I currently have a PIL Image object which I store as an array of bits (1's and 0's). However I now would like to be able to rotate that image 45 degrees. One way to do it is take the original PIL image, apply a transform matrix on it, then convert that to an array of bits. Problem with this approach is that it's computationally expensive, especially if I want to start doing more than just one rotation. It would be faster to just modify the array of bits directly.

I tried using numpy.roll:

```<code>numpy.roll(bits, 45) # rotate 45 degrees
</code>```

Unfortunately, this just does a circular shift, not an actual angular rotation.

What algorithm can I use on the array of bits to give me the desired output without having to go through the original image? Even though my application is in Python, your answer can be in whatever language you feel comfortable with, I'm more interested in the algorithm itself not the syntax :)

答:
To see that it can't be just a question of shifting points around, just draw a frame around your image: In the rotated version, the image will have diagonal edges and so won't even fit in the dimensions of the original image.

So, to rotate it you'll have to compute where each pixel goes. Note that the top left point (0,1) will not end up at (1,1) but at a point on the diagonal whose distance from the origin is 1: namely, at (sqrt(2)/2, sqrt(2)/2). Since sin(45) = cos(45) = sqrt(2)/2, the algorithm you're looking for is multiplication of each point's coordinates by this transformation matrix:

```<code>|  sqrt(2)/2  sqrt(2)/2 |
| -sqrt(2)/2  sqrt(2)/2 |
</code>```

See the wikipedia page on Transformation Matrices for the details. So, you have to do a lot of multiplications but you don't have to calculate any sines or cosines (I just did that for you from memory). You can take some other shortcuts, as the other answers suggested, but one way or another you have to compute where each pixel must go.

Of course you'll also have to crop or pad to create a normal rectangular image.

PS. Better yet, instead of implementing this solution, outsource it to a graphics library that does rotations. Or check out this SO question and the solution suggested in the comments under the question:

Consider scipy.ndimage.interpolation.shift() and rotate() or skimage.transform.fast_homography() for interpolated translations and rotations of 2D numpy arrays.

Title: How to rotate an array of bits

Body:
To see that it can't be just a question of shifting points around, just draw a frame around your image: In the rotated version, the image will have diagonal edges and so won't even fit in the dimensions of the original image.

So, to rotate it you'll have to compute where each pixel goes. Note that the top left point (0,1) will not end up at (1,1) but at a point on the diagonal whose distance from the origin is 1: namely, at (sqrt(2)/2, sqrt(2)/2). Since sin(45) = cos(45) = sqrt(2)/2, the algorithm you're looking for is multiplication of each point's coordinates by this transformation matrix:

|  sqrt(2)/2  sqrt(2)/2 |
| -sqrt(2)/2  sqrt(2)/2 |

See the wikipedia page on Transformation Matrices for the details. So, you have to do a lot of multiplications but you don't have to calculate any sines or cosines (I just did that for you from memory). You can take some other shortcuts, as the other answers suggested, but one way or another you have to compute where each pixel must go.

Of course you'll also have to crop or pad to create a normal rectangular image.

PS. Better yet, instead of implementing this solution, outsource it to a graphics library that does rotations. Or check out this SO question and the solution suggested in the comments under the question:

Consider scipy.ndimage.interpolation.shift() and rotate() or skimage.transform.fast_homography() for interpolated translations and rotations of 2D numpy arrays.


问:
Suggested Web Application Framework and Database for Enterprise, “Big-Data” App?
I have a web application that I have been developing for a small group within my company over the past few years, using Pipeline Pilot (plus jQuery and Python scripting) for web development and back-end computation, and Oracle 10g for my RDBMS. Users upload experimental genomic data, which is parsed into a database, and made available for querying, transformation, and reporting.

Experimental data sets are large and have many layers of metadata.  A given experimental data record might have a foreign key relationship with a table that describes this data point's assay. Assays can cover multiple genes, which can have multiple transcript, which can have multiple mutations, which can affect multiple signaling pathways, etc.  Users need to approach this data from any point in those layers in the metadata. Since all data sets for a given data type can run over a billion rows, this results in some large, dynamic queries that are hard to predict.

New data sets are added on a weekly basis (~1GB per set).  Experimental data is never updated, but the associated metadata can be updated weekly for a few records and yearly for most others.  For every data set insert the system sees, there will be between 10 and 100 selects run against it and associated data.  It is okay for updates and inserts to run slow, so long as queries run quick and are as up-to-date as possible.

The application continues to grow in size and scope and is already starting to run slower than I like.  I am worried that we have about outgrown Pipeline Pilot, and perhaps Oracle (as the sole database). Would a NoSQL database or an OLAP system be appropriate here? What web application frameworks work well with systems like this? I'd like the solution to be something scalable, portable and supportable X-years down the road.

Here is the current state of the application:

Web Server/Data Processing: Pipeline Pilot on Windows Server + IIS

Database: Oracle 10g, ~1TB of data, ~180 tables with several billion-plus row tables

Network Storage: Isilon, ~50TB of low-priority raw data

答:
Since the data is mostly immutable, have you looked into possible denormalizations? The goal would be to find values that could be essentially duplicated but reduce query complexity.

If queries regulary chain joins to connect to pieces of data, you can create a duplicate foreign key relationship directly between the two tables.

If there is a calculation performed by several queries, perform it once and save the result in the appropriate table. For example, some property of the assays that is calculated when needed can be calculated when inserted and added the the assay table.

This is ultimately what a Data Warehouse type solution does, but on a much smaller scale.

ContentLicense: CC BY-SA 3.0


答:
The requirement of searching for arbitrary data and dynamic queries is a good use case for an in memory database.

Disclaimer for the rest of the answer: I work for SAP, so I am most familiar with SAP's products.

SAP already solved a similar use case (genome analysis) already with it's in memory database HANA, so it works. Read more about it here:
http://www.saphana.com/docs/DOC-1799

Programming in HANA is mostly done using stored procedures. HANA has a build in Javascript runtime to implement the application layer. Or you can expose the stored procedures as services and use any other app server on top (e.g. Java).

You can find tutorials and trial development environments here:
http://scn.sap.com/community/developer-center/cross-technology
More information:
http://scn.sap.com/community/hana-in-memory

Title: Suggested Web Application Framework and Database for Enterprise, “Big-Data” App?

Body:
I have a web application that I have been developing for a small group within my company over the past few years, using Pipeline Pilot (plus jQuery and Python scripting) for web development and back-end computation, and Oracle 10g for my RDBMS. Users upload experimental genomic data, which is parsed into a database, and made available for querying, transformation, and reporting.

Experimental data sets are large and have many layers of metadata.  A given experimental data record might have a foreign key relationship with a table that describes this data point's assay. Assays can cover multiple genes, which can have multiple transcript, which can have multiple mutations, which can affect multiple signaling pathways, etc.  Users need to approach this data from any point in those layers in the metadata. Since all data sets for a given data type can run over a billion rows, this results in some large, dynamic queries that are hard to predict.

New data sets are added on a weekly basis (~1GB per set).  Experimental data is never updated, but the associated metadata can be updated weekly for a few records and yearly for most others.  For every data set insert the system sees, there will be between 10 and 100 selects run against it and associated data.  It is okay for updates and inserts to run slow, so long as queries run quick and are as up-to-date as possible.

The application continues to grow in size and scope and is already starting to run slower than I like.  I am worried that we have about outgrown Pipeline Pilot, and perhaps Oracle (as the sole database). Would a NoSQL database or an OLAP system be appropriate here? What web application frameworks work well with systems like this? I'd like the solution to be something scalable, portable and supportable X-years down the road.

Here is the current state of the application:

Web Server/Data Processing: Pipeline Pilot on Windows Server + IIS

Database: Oracle 10g, ~1TB of data, ~180 tables with several billion-plus row tables

Network Storage: Isilon, ~50TB of low-priority raw data


问:
Favoring Immutability in Database Design
One of the items in Joshua Bloch's Effective Java is the notion that classes should allow mutation of instances as little as possible, and preferably not at all.

Oftentimes, the data of an object is persisted to a database of some form. This has led me to thinking about the idea of immutability within a database, especially for those tables that represent a single entity within a larger system.

Something I have been experimenting with recently is the idea of trying to minimize the updates I do to table rows representing these objects, and trying to perform inserts instead as much as I can.

A concrete example of something I was experimenting with recently. If I know I might append a record with additional data later on, I'll create another table to represent that, sort of like the following two table definitions:

```<code>create table myObj (id integer, ...other_data... not null);
create table myObjSuppliment (id integer, myObjId integer, ...more_data... not null);
</code>```

It is hopefully obvious that these names are not verbatim, but just to demonstrate the idea.

Is this a reasonable approach to data persistence modeling? Is it worth trying to limit updates performed on a table, especially for filling in nulls for data that might not exist when the record is originally created? Are there times when an approach like this might cause severe pain later on?

答:
If you are interested in the benefits you can get from immutability in a database, or at least a database that offers the illusion of immutability, check Datomic.

Datomic is a Database invented by Rich Hickey in alliance with Think Relevance, there are plenty of videos where they explain the architecture, the goals, the data model. Search infoq, one in particular is titled Datomic, Database as a Value. In confreaks you can find a keynote Rich Hickey gave at the euroclojure conference in 2012. confreaks.com/videos/2077-euroclojure2012-day-2-keynote-the-datomic-architecture-and-data-model

There is a talk in vimeo.com/53162418 which is more development oriented.

Here is another from stuart halloway
at.pscdn.net/008/00102/videoplatform/kv/121105techconf_close.html

Datomic is a database of facts in time, called datums, in 5-tuples [E,A,V,T,O]

E Entity id

A Attribute name in the entity (can have namespaces)

V Value of the attribute

T Transaction ID, with this you have notion of time.

O One operation of assertion (present or current value), rejection (past value);

Uses it's own data format, called EDN (Extensible Data Notation)

Transactions are ACID

Uses datalog as query language, wich is declarative as SQL +
recursive queries. Queries are represented with data structures, and extended with your jvm language, you don't need to use clojure.

The database is decoupled in 3 separate services (processes,machines):

Transaction

Storage

Query Engine.

You can separately, scale each service.

It's not open source, but there is free (as in beer) version of Datomic.

You can state a flexible schema.

set of attributes is open

add new attributes anytime

no rigidity in definition or query

Now, since the info is stored as facts in time:

all you do is add facts to the database, you never delete them
(except when is required by law)

you can cache everything forever. Query Engine, lives in the application server as an in memory database (for jvm languages non-jvm languages have access through a REST API.)

you can query as of time in the past.

The database is a value, and a parameter to the query engine, the QE manages the connection and the caching. Since you can see the db as a value, and immutable data structure in memory, you can merge it with another data structure made from values "in the future" and pass that to the QE & query with future values, without changing the actual database.

There is an open source project from Rich Hickey, called codeq, you can find it in github Datomic/codeq, which extends the git model, and stores references to git objects in a datomic-free database, and make queries of your code, you can see an example of how to use datomic.

You can think of datomic as a ACID NoSQL, with datums you can model tables or documents or Kv-stores or graphs.


问:
Independency and estimation of user stories that rely on shared predecessor
Lest's say I have user stories about using product catalog in shop:

As an administrator I can add/modify/delete catalog items (one or more user story, doesn't matter here)

As a customer I can search product catalog

As a customer I  can view product details

Each of this stories rely on predecessor: design and create database to store product information.

I can express db creation as:

another story: As a shop owner I want to store information about products I sell

Task to be done in story which will be firstly chosen to do

In first case I create story dependency, in second I wondering where estimate this additional task. Let's say it adds additional two story points. To which story should add this points? All (and re-estimate remaining stories in the future), none? I think that second option also can hinder estimation - I have to remember to add this story points to  dependent stories and then possibly remove it.

How to deal with such situations?

答:
Setting up the database has no customer value by itself, so preferably it is not a story of its own. The database implementation should be part of the first story that needs it. Or ideally, the database is implemented in phases: with Every story you implement the part that is needed to make that story work.

(That doesn't mean you can't do the design in advance. You probably should)

In general: Dependencies between user stories are very common. The team will estimate a certain story in the assumption that some other story is already done. (Best to take note of these kind of prerequisites). This happens all the time. If the planning changes, and the prerequisites of a story no longer apply, then the team should get the opportunity to re-estimate.


问:
Examples of UNIX Domain Socket Usage
Can anyone give an example of instances in which the AF_UNIX i.e unix domain sockets are used for process communication in a unix-based system</p>

答: X windows uses unix sockets when you run application locally (on the same host as the X server) and tcp for remote application. MySQL programs also uses unix sockets to connect to a local server.</p>

Title: Examples of UNIX Domain Socket Usage


答:
I've run into this problem a number of times and never found a perfect solution.

But I have found that the least imperfect solution is to have a separate story. The difficulty is in how to word it. You need to do this in conjunction with the user, so that they know this story doesn't produce anything visible, but it does allow you, the programmer, to provide other useful stories for them.

"As a shop owner I want to store information about products I sell" doesn't really convey that point very well. It implies that the end user will be able to store those details.

If your stakeholders are good at understanding that developers are also stakeholders in the product, you can put it to them that a story such as "As a programmer, I want to store and retrieve information about products that my customer sells, so that I can complete tasks #132, #133, #134."

When a user sees this in the current iteration but not tasks 132, 133 or 134, they're going to know that this isn't something you can demonstrate to them at the end of the iteration, but they will be satisfied that, next iteration, they'll be able to get those tasks done, cheaply. This is usually enough.

You should, as a matter of course, demonstrate such tasks to each other, at the end of an iteration, as you are the primary stakeholders for the task.

As a bonus, this mentality leads nicely onto conversations about technical debt stories like "As a programmer, I need an improved API for the XYZ services, so that I can develop against them more rapidly."

Note that I've added a "so that" clause to each of my story examples. This is a good practice for stories, even when they're more clear-cut than the example we're discussing. The business value of a task is at least as important as what the user needs to be able to do to gain that value. This becomes exponentially true as the number of stakeholders grows.

Title: Independency and estimation of user stories that rely on shared predecessor

Body:
Lest's say I have user stories about using product catalog in shop:

As an administrator I can add/modify/delete catalog items (one or more user story, doesn't matter here)

As a customer I can search product catalog

As a customer I  can view product details

Each of this stories rely on predecessor: design and create database to store product information.

I can express db creation as:

another story: As a shop owner I want to store information about products I sell

Task to be done in story which will be firstly chosen to do

In first case I create story dependency, in second I wondering where estimate this additional task. Let's say it adds additional two story points. To which story should add this points? All (and re-estimate remaining stories in the future), none? I think that second option also can hinder estimation - I have to remember to add this story points to  dependent stories and then possibly remove it.

How to deal with such situations?


答:
The correct solution is number 2.

Agile estimation is by design much less precise than waterfall:

stories are "reminders to have a conversation" and they are incomplete and negotiable by definition

the only purpose of estimating stories is to determine, more or less, what can be accomplished in an iteration, if you are using iterations

estimates are basically useless in agile methodologies like Kanban, as long as the stories are small enough.

there is no point estimating when a set of stories is precisely going to be done: stories will change, so detailed estimates must be avoided for long term goals.

In particular, creating the database is a task, an implementation detail, in the first story you are going to play. Tasks will be estimated (if you so choose) in hours, not in points, and they are estimated during the sprint and not during sprint planning.

Points measure the complexity of a story - not the amount of work, or even less the time it takes - and in my experience they are best seen as a "prize" that the team wins when they complete the story. Adding a database table does not really increase the overall complexity. Adding a database table is a detail which appears because of the specific point in time the story is played.

Asking "where do the 2 points go?" is meaningless. There are no "2 points" to go anywhere. The story is still the same whether you need to create the table or not, and it's perfectly normal and unavoidable not to know which all the tasks that need to be executed in order to complete the story are.

When I estimate, I don't know when a story will be played and what bit of the database will be in place when I play it, so there's no way out of this lack of precision. Again, let me stress that this is normal and unavoidable.

To be more specific, you say:

As an administrator I can add/modify/delete catalog items (one or more user story, doesn't matter here)

As a customer I can search product catalog

As a customer I can view product details

Each of this stories rely on predecessor: design and create database to store product information.

But this is not true in general. You don't need a database at all. You could use, say, a service. You could install an open source component that takes care of it. You could decide to use a document database which doesn't require table creation. You could use a pre-packaged search service, etc. etc.

What you are doing is conflating the implementation details with the stories. Stories are not requirements. They must be more high-level than that! A customer will benefit from searching the product catalog, and the team should be expected to provide the simplest solution that satisfies the story (and the definition of done that you've set), which may or may not include a product database.


问:
Why do we use story points instead of man days when estimating user stories?
In agile methodologies (e.g. SCRUM), the complexity/effort needed for user stories are measured in Story points. Story points are used to calculate how many user stories a team can take in an iteration.

What is the advantage of introducing an abstract concept (story points), where we can just use a concrete measurement, like estimated man-days? We can also calculate velocity, estimate coverage of an iteration, etc. using estimated man-days.

In contrast, story points are harder to use (because the concept is abstract), and also harder to explain to stakeholders. What advantage does it offer?

答:
Man days estimate the time it takes to do something. They are best used when the items you are estimating are very precise and measurable. Specific, well known, repeatable tasks are estimable in man days.

For example, if a sales person can make 20 customer calls per day, on average, we can calculate how much time each call takes and from that we can estimate how many man days it will take to make 1000 calls.

In this example one can concretely think in statistical terms about the median length of a call because all calls can be assumed to be effectively the same thing.

Story points determine which combination of stories can be done in an iteration. They are used to combine heterogeneous goals with fuzzy boundaries and to measure how many can be done in a fixed time frame. They estimate the complexity of chunks of work compared to each other so to be able to add them together.

For example, your team developed 5 stories for a total of 23 points in iteration 1, and 8 stories for 20 points in iteration 2. From this you can estimate that in iteration two your team will do a few stories whose total is around 20 points in iteration 3.

Note that we do not need to determine the size of one point and in particular there is no assumption whatsoever that each story of the same size will take the same time to be developed! We only work on sums and on points per iteration. I didn't even mention how long the iteration is.


问:
Which algorithms typify Lisp's power?
Similar question here (but not the same) because I am interested in which specific algorithms work particularly well in Lisp.

Lisp tutorials always give the example of finding factorials, but wanting to find factorials is not a good enough motivation to use Lisp.

I've heard that Quicksort has a particularly elegant implementation in Lisp. Can you give examples (and code samples too) of examples of algorithms that are best implemented in a language like Lisp?

答:
Lisp is not a one-trick pony, not even a two or ten thousand trick pony.

“Please don't assume Lisp is only useful for Animation and Graphics, AI, Bioinformatics, B2B and Ecommerce, Data Mining, EDA/Semiconductor applications, Expert Systems, Finance, Intelligent Agents, Knowledge Management, Mechanical CAD, Modeling and Simulation, Natural Language, Optimization, Research, Risk Analysis, Scheduling, Telecom, and Web Authoring just because these are the only things they happened to list.” (kmp)

If you want to see many algorithms implemented in Lisp, get a book (e.g., SICP or PCL).

See also Why is Lisp used for AI?

Title: Which algorithms typify Lisp's power?


问:
Is Java (still) the cross platform language of choice?
When I started using Java in the nineties, it was all "Write once, run anywhere!" from day one. That was probably all true then and I was a part of the choir as well.

I am not sure what to think about that anymore, considering all the other languages using multi platform runtimes (python, flash, perl, html, php...). But I am still seeing lots of arguments that says you should use Java because it is supposedly better for cross platform development.

So, Is that still true today? Is Java still the language of choice for multi platform development?

Please be specific with focus on cross platform aspects.

I am not asking for general language feature comparisons.

Update: Great responses so far! Most answers seems to be favoring Java or web. Any input from the script crowd?

答:
It's as true today as it was back then - that is to say not entirely.  Java is write once, test and debug everywhere.  Sure that's a lot less work than a completely fresh port but it's generally more work than the initial hype had us believe.

Our product has a Java server which will run on either Windows or Linux but we have seen OS specific issues with it and make sure we have both Linux and Windows servers available for support / testing if needed.  Java UIs tend to have more issues than the servers (though many are cosmetic and therefore potentially can be ignored depending on the application).

While not strictly a language for me the web is the cross platform platform of choice.  An HTML / JavaScript front end means that your application will run on pretty much any client platform and in most instances that was the real goal - not having to worry whether it was a Mac or a PC, which OS version and so on.

Of course you'll generally still be dictating the server platform but when it's just that people become a lot more flexible, particularly these days when most companies already support a mix of Windows and Linux servers.

ContentLicense: CC BY-SA 2.5


答:
I don't see how your scheme can be called "immutable".

What happens when a value stored in the supplementary table changes? It looks like you would need to perform an update on that table.

For a database to be truly immutable it would need to be maintained solely by "INSERTS". For this you need some method of identifying the "current" row. This nearly always end up being horribly inefficient. You either have to copy all the previous unchanged values over, or, piece together the current state from several records when you query. The selection of the current row usually needs some horribly messy SQL like (where updTime = (SELECT max(updTime) from myTab where id = ?).

This problem comes up a lot in DataWarehousing where you need to keep a history of the data over time, and, be able to select the state for any given point in time. The solution is usually "dimensional" tables. However while they solve the DW "who was the sales rep last January" problem. They do not provide any of the advantages that Javas immutable classes do.

On a more philosophical note; databases exist to store "state" (you bank balance, your electricity consumption, your brownie points on StackOverflow etc. etc. ) trying to come up with a "stateless" database seems a rather pointless exercise.

Title: Favoring Immutability in Database Design

Body:
One of the items in Joshua Bloch's Effective Java is the notion that classes should allow mutation of instances as little as possible, and preferably not at all.

Oftentimes, the data of an object is persisted to a database of some form. This has led me to thinking about the idea of immutability within a database, especially for those tables that represent a single entity within a larger system.

Something I have been experimenting with recently is the idea of trying to minimize the updates I do to table rows representing these objects, and trying to perform inserts instead as much as I can.

A concrete example of something I was experimenting with recently. If I know I might append a record with additional data later on, I'll create another table to represent that, sort of like the following two table definitions:

```<code>create table myObj (id integer, ...other_data... not null);
create table myObjSuppliment (id integer, myObjId integer, ...more_data... not null);
</code>```

It is hopefully obvious that these names are not verbatim, but just to demonstrate the idea.

Is this a reasonable approach to data persistence modeling? Is it worth trying to limit updates performed on a table, especially for filling in nulls for data that might not exist when the record is originally created? Are there times when an approach like this might cause severe pain later on?


问:
Where to learn graph theory applications
I am completely new to designing algorithms with graphs. I am following CLRS and other video lectures in Youtube, notably from IIT/MIT. They are pretty good, and I currently have decent idea about graph data structures, search, spanning-tree, etc. However, I am completely clueless as to how to identify a coding problem (the likes of which you see in Topcoder/Codechef) that requires a graph-based approach. In which problem, shall I need to use a minimum spanning tree? Where do I need to use Prim's Algorithm?

Is there ay book/resource which covers lots of problems on graphs, explaining (well, kind of spoon feeding) how to identify that this problem requires a graph-based solution, and finally how to do it?

答:
Very good question, but very tough to answer. I highly doubt, that such a book exists, because graphs are just another formalism and whether you apply it to your problem or not is a matter of two things:

Knowledge about its existence. People who do not know about graphs and the corresponding algorithms for some very strange reason never come up with graph-based solutions to their problems.

Being the most suitable formalism for your problem.

As for 1. you are well on your way already. Point 2 is much harder due to the genericity of graphs. If you take it to the extreme, do remember that every list or array is nothing but a graph in disguise. Now you could consider looping through a linked list in order to find a certain element as a depth-first search on a directed acyclic graph, but there's really no point in it apart from the mental masturbation.

On the other hand, there are myriads of problems which naturally lend themselves to graph-based solutions. The more experience you have with graphs, the more you will see them wherever you go, but it takes even more experience to decide when the time is right to pull out that full-blown graph library, or even roll your own algorithm.

If you are looking for a problem that requires a graph-based solution, then my guess is you won't find one, as it all could be solved in a different way as well. But if you're looking for problems for which graph-based solutions are a good fit, then your best bet might be to look at an abstraction of the problem.

Abstraction is the one thing that brings out graph datastructures the best. Try to translate your problem domain into nodes and figure out what the meaning of an edge between these nodes would be. If you cannot do that easily, chances are you are better off without graphs. However, most of the times everything just falls into place naturally.

Here are a few examples and how abstraction leads you to the corresponding graph algorithms:

Buildsystem: you have a lot of projects/libraries which depend on each other. You must ensure that one is built before another, oh and of course, if possible, you want to build them in parallel. Now do the abstraction: library = node and edge = dependency and voila.. you have a graph. Next question: what structure does this graph have? is it directed or undirected? has to be directed, as you have a direct relation that one library needs to be built before the other. Is it acyclic? indeed, you cannot have cyclic dependencies, or you would not have a place to start your build - but you may have to account for your tool being able to stop on detecting cycles, because someone configured something wrong. Ops, cycle-detection algorithm.. should be in your toolbox. Next up: determine the execution order for builds, or in other words: find a traversal through your graph that visits nodes only after all nodes from incoming edges have been visited. Check your toolbox, as this is the topological sort algorithm. And so on, and so on...

Power net: You have a city/country and several power plants and places where you can redirect power and of course, everyone needs to be supplied. Nodes are the homes and power plants, edges are the power lines, and if you want to find the minimal length of power lines you need to build, it comes down to the minimal amount of edges required to connect all of your nodes together.. or in toolbox-speech: minimum spanning tree.

Piping system: You have an elaborate setup of pipes through which you can run water. At several points you have the option to open/close valves to allow the water to pass through your system in different ways. However, the pipes differ in diameter, so that the throughput varies and you wonder: how much water can we get pumped through this system at most (in a given unit of time)? Abstraction leads you to model the tap, sink, and valves as nodes and pipes as edges. Edge weights will be involved due to the diameters affecting the throughput and now you want to find quite literally the maximum flow. Luckily, the graph toolbox has algorithms for just that.

Routing wires on a chip (example proposed by @jk.) : When you have to do wiring, you have the limitation, that wires must not cross due to the electrical charges. Abstraction is straight-forward at first, because you have components and wires between them, hence, nodes and edges. The next step is to identify the problem in graph-based terms, which in this case means you have to layout the edges on a plane. Whether or not a graph can be drawn on a plane without intersecting the edges is again checkable via an algorithm from the graph toolbox - keyword: planar graphs.

As for the spoon-feeding book: This is actually not a good idea. Let me stress again, that graphs can be applied to almost every problem if you force your mind around it. A book that shows you problems and how they are solved with graph algorithms is pretty much useless, because you will have to deal with other problems in your daily work. All it comes down to is experience with this kind of abstraction, because you have to adapt everything to the current situation at hand.


问:
User session timeout handling in SaaS apps - discussing several approaches
I know this has a great chance of being marked as duplicate, but couldn't find exactly what I'm looking for

This is a common problem and I'm sure it has some well defined best practice solution

Background

A single page SaaS app, has lot's of drag and drop, user can
interact with it without much server communication for periods of
time

Server session only holds user object, using a non persistent session cookie

Session expires on the server after X hours

Some things are loaded only during log-in

Problem

User works on the app, when done, user doesn't log out, just keeps the browser open

User comes back after more than X hours (session is invalidated on server)

User interacts with the app without needing a server connection (drags and drops things, text edits...)

Only on the next server interaction (let's assume there is no auto save) user is thrown to login page and loses some of their work

Possible solutions

Here are some solutions I have in mind, would like to hear if there are any others, and if there is anything fundamentally wrong with any of them.

1. Never log the user out

How? either keep a long session, keep a persistent cookie, or javaScript "keep alive" ping

Pros: user doesn't need to worry about anything, fixes the problem for them

Cons: not PCI compliant, not secure, and needs development changes, e.g. things loaded to session only on user log in need to move to either a pub sub model (listening on event changes) or have cache timeout.

2. Local Storage

How? use new local storage to temporarily store state if logged out, redirect to login page, persist once logged in

Pros: Also base for "work offline" support, not just handling session timeout

Cons: harder to implement, need to do state merge of data tree, not all browsers support

3. Auto save

Every user action that changes the model, should persist immediately (or via some sort of a client side queue), e.g. if they check a checkbox,  change a text field, or drag and drop something, once they are done, persist the changes.

How? Use an MV** framework (Backbone.js / Knockout.js / Ember.js / Angular.js etc) to bind the model, and persist on changes.

Pros: Seems like a clean solution, session is active as long as user is active, no client side work is done without persisting it.

Cons: The last action user is doing after a session timeout is lost.

4. Log the user out after session expires

this can have several approaches

Ask the server "has session expired" - this is a bit of a catch 22 / Schrodinger's cat, as the mere question to the server extends the session (restarts the timeout),

How? Either have a server that supports such question (I don't know of any, but I come form Java land)  or, one can just keep a table of session IDs, and last access time manually, and ask the server by passing the session ID as a parameter instead of the cookie, I'm not sure if this is even possible, but it sounds dangerous, insecure and bad design whatsoever.login page, persist once logged in

Pros: If there was such native support in servers, sounds like a clean, legitimate question (asking if user X still has a session or not without renewing it if they do)

Cons: If the server doesn't support it (and again, I don't know if any server or framework has this functionality) then the workaround has huge security risks potentially.

One workaround I've heard is have a short session on the server side, and a keep alive client side ping, that has a maximum number of pings

How? Short session on server, client pings every sessionTimeOut/2, has max retries of Y.

Pros: Kind of fixes the problem, quick and dirty

Cons: Feels like a hack, handling the session renewal yourself instead of letting the server do it

Client side timer

How? Have a timer on the client side and sync it with the server one by restarting it on every request to be equal to the max server session timeout minus some padding, after user is not sending any request to the server, UI shows a "sessions is about to time out, do you want to continue?" (like you have on online banking )

Pros: Fixes the problem

Cons: Can't think of any except the need to make sure the sync works

The Question

I'm probably missing something in the above analysis, might have some silly mistakes, and I would like your help to correct them. What other solutions I can have for this?

答:
I'm actually creating an application that deals with this.

I started by creating a RESTful service using Django, Guradian and Tastypie.
It authenticates using APIKEY only, authorisation to objects is handled by Guardian.

The django app only has one template view urlconf that loads the base.html which is ...

On the client side I created an application using Angular.

As far as authentication goes, there is a http-auth-interceptor that listens for  401 responses.

When a 401 is recieved it buffers the outgoing request and fires off an event "login-required". This might occur several times.

I have a modal popup containing a login form that is presented when the "login-required" event is heard, and it performs a login that returns a User resource ( a JSON bundle) which would also contain the APIKEY.

All buffered requests that previously resulted in a 401 response are replayed with the APIKEY now included in the Authorisation http header.

I use another angular service/factory to manage localstorage json data, and that's where I store the username and apikey.

The only piece of the puzzle left to solve is how to secure that information, and how to enforce a timeout on that information.

Perhaps use a timestamp check from last valid http request.


问:
How to create different paths for users to take through the pages in my site?
I have a website where users are directed to go through a sequence of pages to perform a sequence of work tasks (transcribe a paragraph, answer a survey, interact with another user, etc). For short, let's call these tasks A, B, C, etc. I'm using Django, and each task is currently implemented as a view function (or method), e.g. def A(request). Currently, each view function has the next step hardcoded in an HTTP redirect, e.g. HttpResponseRedirect(reverse(B)).

My challenge is that I will soon have a requirement to create various permutations of the sequence of tasks. Sometimes I will want users to do A, B, C; for others, B, C, D; for others, A, B, D, F. How can I architect this so that I can define these permutations elegantly and concisely in my code? Intuitively, I feel like I need to genericize the HTTP redirect calls with a variable, like: HttpResponseRedirect(reverse(next_view_function)), but I struggle to figure out where next_view_function should be defined, and how the definition of the sequence (e.g. A, B, D) should be persisted across requests.

Can anyone lead me down the right path with a suggestion or idea? I'm happy to provide more details.

Edit in response to Bart's questions:

The order of tasks is predetermined. Once we have defined it, we send the users a URL that takes them to the first page. They should then be routed through the tasks. One group of users might get a URL that takes them through steps A,B,C, while another group of users gets a URL that takes them through steps A,B,D. We decide in advance which users should get which URL.

Since the order is predetermined, the next step does not depend on the results of the current task. The only requirement is for them to complete the task (we of course validate the POST data they submit as a precondition to the HTTP redirect).

Edit 2, my solution so far:

A central concept in my code architecture is that of a "Treatment" (defined in my models.py). A Treatment is a specification of the experience a user has when they use my site, such as what UI is presented to them. I split my users into groups and assign each group to a different treatment by emailing them a URL that contains the PK of their treatment.

(There are also different subclasses of Treatment, since some Treatments are totally different from others. SoccerTreatment and HockeyTreatment have little in common, so it makes sense to subclass them.)

So, the class definition for a Treatment seems like the sensible place to store the sequence of views as a Python list, as follows:

```<code># in soccer/models.py
class SoccerTreatment(BaseTreatment):

    world_cup = models.BooleanField()
    ....

    def views(self, request):
        seq = [soccer.views.ViewClassA]
        if self.world_cup:
            seq.append(soccer.views.ViewClassWorldCup)

        return seq

# in shared/models.py
class BaseTreatment(models.Model):
    def next_view(self, request):
        seq = self.views() # views() method implemented by descendant classes
        if request.session.get('current_view_index'):
            request.session['current_view_index'] += 1
        else:
            request.session['current_view_index'] = 0
        # [handle boundary cases, code snipped...]
        # ...
        return seq[request.session['current_view_index']]

    # ...

# in views.py, at the end of a view function
# ...
HttpResponseRedirect(reverse(user.treatment.next_view()))
</code>```

However, the design above wouldn't work, since then models.py would have to import views.py, creating a circular import. So the list elements would have to be strings (either URLs, or a the name of the view class as a string), which could be brittle since renaming my classes or URLs won't automatically rename these strings.

Maybe I am being too picky, but I wonder if there is a better design.

答:
I came across a situation like this in an Application I helped create.

I called it the User Sanity Test, because I was testing the User model and the possible states it could be in with regards to its relations to other models.

Things I would test were, Had they set an email address, Did they have valid billing details, have they created their first Thing(tm), etc.

I approached this by creating a Middleware that performed these tests on authenticated users, which took the UserSanityTest class and feeds in the current User.

If a test fails, then it returns an url that the middleware will redirect the user to.

The Sanity check is in effect on all urls except those in the SanityCheck.

If the user is visiting a SanityCheck Url that they've already satisfied then it either sends them to the users dashboard or checks for other SanityChecks and processes them.

Normal URLS described in your UrlConf can only be visited when all SanityChecks are completed.


答:
I've only skimmed the requirements, but I'd be thinking something simple like this:

Give each task a letter.

Generate a task sequence string (eg, EBDFA) for a user.

Look at the first letter to decide what task to do next.

Carry out that task.

Strip the first letter off, pass the rest in the URL.

Go to step 3.

Keep it simple. Don't create models you don't need, don't store local state you don't need.

Title: How to create different paths for users to take through the pages in my site?

Body:
I have a website where users are directed to go through a sequence of pages to perform a sequence of work tasks (transcribe a paragraph, answer a survey, interact with another user, etc). For short, let's call these tasks A, B, C, etc. I'm using Django, and each task is currently implemented as a view function (or method), e.g. def A(request). Currently, each view function has the next step hardcoded in an HTTP redirect, e.g. HttpResponseRedirect(reverse(B)).

My challenge is that I will soon have a requirement to create various permutations of the sequence of tasks. Sometimes I will want users to do A, B, C; for others, B, C, D; for others, A, B, D, F. How can I architect this so that I can define these permutations elegantly and concisely in my code? Intuitively, I feel like I need to genericize the HTTP redirect calls with a variable, like: HttpResponseRedirect(reverse(next_view_function)), but I struggle to figure out where next_view_function should be defined, and how the definition of the sequence (e.g. A, B, D) should be persisted across requests.

Can anyone lead me down the right path with a suggestion or idea? I'm happy to provide more details.

Edit in response to Bart's questions:

The order of tasks is predetermined. Once we have defined it, we send the users a URL that takes them to the first page. They should then be routed through the tasks. One group of users might get a URL that takes them through steps A,B,C, while another group of users gets a URL that takes them through steps A,B,D. We decide in advance which users should get which URL.

Since the order is predetermined, the next step does not depend on the results of the current task. The only requirement is for them to complete the task (we of course validate the POST data they submit as a precondition to the HTTP redirect).

Edit 2, my solution so far:

A central concept in my code architecture is that of a "Treatment" (defined in my models.py). A Treatment is a specification of the experience a user has when they use my site, such as what UI is presented to them. I split my users into groups and assign each group to a different treatment by emailing them a URL that contains the PK of their treatment.

(There are also different subclasses of Treatment, since some Treatments are totally different from others. SoccerTreatment and HockeyTreatment have little in common, so it makes sense to subclass them.)

So, the class definition for a Treatment seems like the sensible place to store the sequence of views as a Python list, as follows:

```<code># in soccer/models.py
class SoccerTreatment(BaseTreatment):

    world_cup = models.BooleanField()
    ....

    def views(self, request):
        seq = [soccer.views.ViewClassA]
        if self.world_cup:
            seq.append(soccer.views.ViewClassWorldCup)

        return seq

# in shared/models.py
class BaseTreatment(models.Model):
    def next_view(self, request):
        seq = self.views() # views() method implemented by descendant classes
        if request.session.get('current_view_index'):
            request.session['current_view_index'] += 1
        else:
            request.session['current_view_index'] = 0
        # [handle boundary cases, code snipped...]
        # ...
        return seq[request.session['current_view_index']]

    # ...

# in views.py, at the end of a view function
# ...
HttpResponseRedirect(reverse(user.treatment.next_view()))
</code>```

However, the design above wouldn't work, since then models.py would have to import views.py, creating a circular import. So the list elements would have to be strings (either URLs, or a the name of the view class as a string), which could be brittle since renaming my classes or URLs won't automatically rename these strings.

Maybe I am being too picky, but I wonder if there is a better design.


问:
Do I have to learn html and javascript to create web applications?
I am an experienced Java programmer, and I want to create a complex web application requiring dynamic pages, drawings, etc (take SO as an example). Do I have to learn javascript/html in order to create such an application?

It is not that I don't want to learn another language (I've done this before), but technology on the javascript environment seems to change so fast that when you finish learning one framework it is already obsolete. I have checked a number of java framework for web development (spring, play), but not deeply. So can these frameworks (or other possible java frameworks that I'm not aware of) be used without learning html/javascript? I also have some python experience. So if I can do the app in python it is also an option.

答:
Knowing Javascript is a plus as it helps you creating web apps. I think HTML is the best to have a good solid knowledge on and HTML5 is nice because it integrates well with CSS3 and JavaScript. I would recommend browsing through the courses at Microsoft Virtual Academy.

They have over 200 different course options and they’re all free and expert led. I personally benefited from their course on app development training with HTML5. Good luck!


答:
There are web application frameworks that abstract away HTML and JavaScript, but honestly the cure is often worse than the disease. (eg, Google Web Toolkit).

Do yourself a favour though, and learn jQuery, CoffeeScript and/or other javascript frameworks to spare some of the most tedious details. Similarly, consider using something like Haml or HamlPy to work with a nicer version of HTML.

Title: Do I have to learn html and javascript to create web applications?

Body:
I am an experienced Java programmer, and I want to create a complex web application requiring dynamic pages, drawings, etc (take SO as an example). Do I have to learn javascript/html in order to create such an application?

It is not that I don't want to learn another language (I've done this before), but technology on the javascript environment seems to change so fast that when you finish learning one framework it is already obsolete. I have checked a number of java framework for web development (spring, play), but not deeply. So can these frameworks (or other possible java frameworks that I'm not aware of) be used without learning html/javascript? I also have some python experience. So if I can do the app in python it is also an option.


问:
Determining the cost of impediments (waste)
For some time now our Scrum teams have experienced recurring impediments caused by external factors to the team. The teams have discussed the impediments in their retrospectives and also brought it up on "Scrum of Scrums". It seems that the impediments may require involvement by management as it requires some rather significant changes in that way we do things and the way our technical environments have been configured. In a small setting these kind of issues would probably have been easy to deal with because the team would have more control, but in this setting there are multiple teams, stakeholders and parties. I’d like to hear your experience in making waste and costs visible. Do you simply estimate the hours wasted on the recurring impediments (such as, “we waste 10 hours every sprint waiting on the build server) or do you have a more systematic way of gathering and showing the waste?

I would like to collect waste based on Six Sigma (and Lean Software Development) and estimate the waste cost in terms of story points. E.g. at every retrospective highlight the waste in seven categories with the number of story points wasted in each category. The seven categories would be: Partially Done work, Extra Features, Relearning, Handoffs, Task Switching, Delays, and Defects.

In the end of the Retrospective, there would then be a clear indication of the cost of external impediments that management would easily be able to act on. What do you think?

答:
Perhaps you'd get more buy-in from management if you completely turned your problem around and presented it like this; "If we fix this problem, what can we gain?". Approach the problem from the positive side, and in my experience you'll get a better response all round. So, rather than highlighting problems (which we can all do until we're blue in the face), point out solutions, and benefits to change.

You could make a list of the things your team sees as impediments, and make yourselves a separate 'improvements' backlog. Estimate each item as you would any other user story. Then in your planning meeting with your stakeholders, you can present your varous proposals with a clear cost-benefit to them.

"So Gary, if we include this 'fix the build server' story in this weeks sprint, which we have estimated as having 6 points, we think that in the future, we will be able to improve velocity by around 4 points per sprint."

A couple of extra notes on this approach;

1) these stories are effectively crud that need to happen (I've completely forgotten the 'scrummy' term for this); and the story points shouldn't contribute to your sprint velocity, as they are a cost, and do not in themselves progress the real project

2) if you succeed with a small impediment story first, you might get more buy in for the bigger items on your impediments list


答: If you bring mobile platforms into the mix then you'd also at least need to include recompile. E.g. android, j2me.</p>

Title: Is Java (still) the cross platform language of choice?

Body:
When I started using Java in the nineties, it was all "Write once, run anywhere!" from day one. That was probably all true then and I was a part of the choir as well.

I am not sure what to think about that anymore, considering all the other languages using multi platform runtimes (python, flash, perl, html, php...). But I am still seeing lots of arguments that says you should use Java because it is supposedly better for cross platform development.

So, Is that still true today? Is Java still the language of choice for multi platform development?

Please be specific with focus on cross platform aspects.

I am not asking for general language feature comparisons.

Update: Great responses so far! Most answers seems to be favoring Java or web. Any input from the script crowd?


问:
Sorting and averaging the highest values of pixel data
Currently, I am using Android/Java.  I am looking for the most efficient means to determine the average of the highest 100 pixel values taken from a greyscale preview.

The preview part I am more or less okay with; however, it determining which sorting methodology is the most efficient.  The other option is to apply a threshold, which will eliminate most of the data.

Which sorting algorithm would be most efficient for an unsorted data set of over 3 million values?

答:
Assuming that you want the average of the highest 100 greyscale values:  Observe that greyscale values have a much smaller range than raw (RGB) pixels, usually 0.255.  (Also note that averages of RGB pixels are not likely to yield anything interesting.)</p>

```<code>   unsigned char image[NROWS][NCOLS];
   unsigned hist[256];
   bzero(hist, sizeof(hist));
   // compute histogram of greyscale values
   for(unsigned r = 0; r < NROWS; r++) {
      for(unsigned c = 0; c < NCOLS; c++) {
         hist[image[r][c]]++;
      }
   }
   unsigned counter;
   unsigned bin;
   bin = 255;
   while ((bin > 0) && (counter < 100)) {
      while (bin > 0) && (hist[bin] == 0)) {
         bin--;
      }
   #ifdef WEIGHTED_AVERAGE
      sum += (bin * hist[bin]);
   #else
      sum += bin;
   #endif
      // handle pathological case where there are < 100 nonzero bins
      if (hist[bin] > 0) counter++;
   }
   double average_value;
   average_value = ((double)sum)/counter;
</code>```

Body:
Assuming that you want the average of the highest 100 greyscale values:  Observe that greyscale values have a much smaller range than raw (RGB) pixels, usually 0.255.  (Also note that averages of RGB pixels are not likely to yield anything interesting.)

   unsigned char image[NROWS][NCOLS];
   unsigned hist[256];
   bzero(hist, sizeof(hist));
   // compute histogram of greyscale values
   for(unsigned r = 0; r < NROWS; r++) {
      for(unsigned c = 0; c < NCOLS; c++) {
         hist[image[r][c]]++;
      }
   }
   unsigned counter;
   unsigned bin;
   bin = 255;
   while ((bin > 0) && (counter < 100)) {
      while (bin > 0) && (hist[bin] == 0)) {
         bin--;
      }
   #ifdef WEIGHTED_AVERAGE
      sum += (bin * hist[bin]);
   #else
      sum += bin;
   #endif
      // handle pathological case where there are < 100 nonzero bins
      if (hist[bin] > 0) counter++;
   }
   double average_value;
   average_value = ((double)sum)/counter;


问:
SQL Table Design Modification based on data roles or implementation convenience?
I've got an existing SQL table structure that looks like this:

```<code>Orders
- order_id
- organisation_id
- [all the rest of the order data]

Organisations
- organisation_id
- [all the rest of the organisation data]

Users
- user ID
- [all the rest of the user data]
</code>```

I'm trying to change the Orders table so that an Order can be linked to either an Organisation or a User. I've got two ideas:

Option A

Add field orders.user_id, and then set either user_id or organisation_id to null for each order, indicating whether the order was placed by a user or organisation.

Option B

Add a table orderers (or similar) and then add fields organisations.orderer_id and users.orderer_id. Then, users and organisations are both orderers, and orderers place orders.

Evaluation

Option B's role-based approach seems to make good sense and seems to be more extensible, but I just can't help but think about the hassle the extra JOINs are going to cause, in terms of performance and SQL complexity.

What is the best way to go about this?

答:
Option B will actually cause you extra work on building the joins, but not necessarily worst performance, depending on your situation.

Consider this scenario:

- 1k organisations

- 20k users

- 1M orders

With scenario A you will have to take into consideration:

- you will have one more column on a 1M rows table

- you will probably want one index for user_id and one for organisation_id so if you want to find all the orders belonging to each you can find them faster.
This means your inserts/deletes would be slower than on scenario B which needs only, in reference to your largest table:

- only one index on orderer_id.

I think best choice will end up depending on your specific situation, but take this into consideration.


问:
How to write integration tests for a component oriented software platform
Initial situation:

We are developing a software platform where products can be generated by configuring different components and adding additional ones. The platform is developed several years by a little developer team. Now the platform is more and more used, we get new developers as well as testers. We are currently developing a concept for developer. Cause is, that we do not have much developer tests for our components.

The tester team uses automated UI testing tools to test the products emitted by the platform.

Our goal:

We want to motivate our team members to write more tests to achive

shorten feedback cycles

reduce bug count for new features

reduce regressions

The question:

We want to begin figuring out brittle components. After we have found them, we want to write integration tests for the component which describes expected features. Now we have the following problem: We can test the component for itself and mock all dependencies to other components. We can test the component with all directly depend components. We can test the component with the completely dependency structure of it - so its dependencies and their dependencies... We can test the component in the context of different product configurations.

Which one would be the best to achieve our goals and at the same time minimize the effort needed by our team members to configure the tests?

答:
You will probably need some of both.

Integration tests are against real dependencies. They are usually easier to write, but require more time and resources to run. Some bugs will only be found by integration tests, because you will be affected by real bugs of the dependencies and you'll never think of the same bugs when mocking. They also test all the components involved, so few tests for the downstream components will give you a lot of coverage.

Unit tests are against mock. Writing the mocks takes time, but the tests than run faster and it is the only way to test robustness against various failures, because you can't make the real dependency fail in whatever way you think of. They are also much easier to debug on.

I suggest you start with integration tests. Create some scripts to set up all necessary test data so it is easy to run. Start with big, realistic setups. That should help you identify the brittle components. You can than create smaller setups to narrow down sources of the problems. Than create mocks and unit tests mainly as tool to make debugging the faults you found in integration tests easier. And keep them around as regression tests.


问:
What is the name of λx.λf.fx (like reverse apply) in lambda calculus? Does the corresponding function have a standard name in programming?
What is the name of λx.λf.fx in lambda calculus?

Does the corresponding function have a standard name in functional programming languages, like Haskell?

In object oriented programming, is there a usual name for a method foo which takes a function as an argument, such that x.foo(f) returns f(x)?

答:
In the original Alonzo Church's "The calculi of lambda-conversion", he denotes this combinator by T.

In the context of Church numerals, it is called exp.
This matches the "shorthand" notation used by Church for the "application" of a term N to a term M: "[MN]" stands for "(NM)".

I haven't heard yet of a standard name for an analogous function in programming.


问:
Copyright in a database schema using a licenced windows application
I work for a company that has bought a licence for a windows client software that allows only 20 running clients per company.  I am trying to find a way around this 20 user restriction by programming a PHP web front end that connects to the existing database. This will allow unlimited users to access the database.

The problem I have is that the licence states that no CRM type interface is allowed to be used with the package.

Since I will not be using the windows binary in any way, what is to stop me from studying the database schema and developing my own front end? I would have thought that a schema that uses common tables, for example, customer addresses, materials, parts, orders etc could not be copyrighted by law otherwise a single company could have a monopoly over it.

What makes a database general or distinct enough to warrant copyright?

Any thoughts on this?

答:
The easiest, cheapest, safest, most ethically defensible way around the 20 client limit is to contact the vendor and pay them more money.

Your employer is (most likely) going to spend a LOT more time and money trying to program around the limit than they'd spend by buying more licenses.

You can always shop around for another product/vendor or write your own solution from scratch.

If you choose to write your own solution but base it on the current vendor's database structure, you'll need to find a local lawyer who can address your particular situation.

I strongly suspect the amount the lawyer would have to charge to provide a well-reasoned answer may be more than what it would cost to come up with your own database schema from scratch.

You may even come up with a better design.


问:
A few clarifications about the DOM
I have been trying to understand the DOM, and although I have a fair idea of what it is, there are certain ideas I just cannot pin down. I will list down what I think the DOM is and my questions will be inline.

The DOM is a fully object-oriented representation of the web page. The W3C DOM standard forms the basis of the DOM implemented in most modern browsers.

So does the DOM talk about how an XML/HTML document is represented as an object model?

The DOM does not specify that documents must be implemented as a tree or a grove, nor does it specify how the relationships among objects be implemented.

In what other ways can the document be represented?

When you do something like this -

```<code>document.write('welcome to my home page!');
</code>```

the document object is provided by the DOM. The write methods are the interfaces that are exposed to JavaScript by the DOM.

So the objects and its methods are created as JavaScript objects by the DOM parser and then presented to the JavaScript engine? Or are the objects and methods within the DOM parsing engine in their own native language? And is exposed to the JavaScript engine? If this is so, then what is responsible for translating from JavaScript to the native language?

What are language bindings ?

The language binding is the set of objects native to the language in question that implements each of the interfaces in the DOM specification.

Developers can create language bindings from the DOM to their language simply by following the IDL (Interface Definition Language) in the DOM specification.

So if the DOM parsing engine is implemented in say C++, does that mean that when you create language bindings by following the IDL, you are just creating objects in the specific language, i.e C++ that your DOM parsing engine is built with?

答:
What follows is my best reading of the relevant specifications and references. (I found Mozilla' abstracts about DOM levels and associated links especially helpful.) I encourage corrections or clarifications from others.

So does the DOM talk about how an XML/HTML document is represented as an object model?

Yes. There are two parts to DOM Level 1 specification -- Core and HTML. The Core DOM specification describes a general DOM that could be used to represent any structured document. The HTML DOM specification describes how to use the Core DOM to describe HTML documents specifically and includes HTML-specific interfaces.

The DOM does not specify that documents must be implemented as a tree or a grove, nor does it specify how the relationships among objects be implemented. In what other ways can the document be represented?

DOM Core does assume that the document is a tree. The Node interface is the "...primary datatype for the entire [DOM]. It represents a single node in the document tree." Node has several properties for accessing children, sibling, and parent nodes (e.g., parentNode, frstChild, etc.) that implies a tree structure. You could use a flat tree or a linear tree (e.g., a linked list), but it's still going to be some form of tree.

As George Mauer points out in the comments, perhaps you mean that the underlying model of an particular implementation does not need to be a tree. That much is true; as long as your implementation provides the functionality promised in the DOM specification, you can use whatever structure you like to provide that functionality.

Are the objects and methods within the DOM parsing engine in their own native language?

Generally, yes. In most browsers, the DOM is implemented in a lower-level language like C, and the browser supplies bindings to the JavaScript environment that can manipulate the actual representations. In fact, if you look at the question Meaning of “Moving DOM into Javascript”?, you'll see that Google is interested in switching to a native JavaScript DOM implementation (likely to avoid needing both a C++ function and a duplicate JavaScript wrapper for that C++ function; possibly also for performance gains).

what is responsible for translating from JavaScript to the native language?

I'm a little bit hazier on this subject, but my understanding is that when a JavaScript DOM binding is invoked, the JavaScript execution environment (which is itself implemented in a lower-level language like C) makes a call to the relevant DOM function (written in C/C++) to manipulate the DOM.

If you want to go deeper than that, you'll need to talk to someone who actually makes browsers.

does that mean that when you create language bindings by following the IDL, you are just creating objects in the specific language, i.e C++ that your DOM parsing engine is built with?

Yes. The DOM's IDL is language-agnostic, so that you can implement it in any language. "Writing a DOM implementation" means writing code (in a particular language) to conform to the IDL interfaces described in the DOM specifications.

Title: A few clarifications about the DOM


问:
I use an IDE (Eclipse) to develop software.  Why should I switch to vim or emacs?
My day job is  java/web developer. I have been using eclipse for ~5years. I think its excellent and I also use Webstorm for javascript and html/jsp.

I do on occasion need to ssh into server and mess around with config files; for this I use vi and it pains me. I have to get up a webpage listing the syntax/commands : press escape, then asterix, turn around three times and the text will be entered two lines above your cursor. Its so unintuitive to me, and I imagine anyone who grew up in the late eighties nineties.

Here are the main reasons I think eclipse is brilliant(and I assume other IDE's), and do not switch to emacs and/or vim.

Error highlighting with no need to
recompile project.

Code assist.

Refactoring.

Opening call hiearchy/Opening
declaration.

Fully integrated with source control.

Debugger is included.

availablity of 3rd party plugins - eg
findbugs/checkstyle.

One of the arguments I hear is that with emacs/vim you can create your own plugins - well OK, but you can do that in eclipse too. But you don't need to as everything is already there!  Its like saying buy this half built car, you can build the rest yourself.

Why are people using emacs/vim ? Do people who use it actually work on complex object-oriented projects in large organisations ?

What are the reasons to switch to vim/emacs. How would my productivity increase if I did switch?

答:
As a long-time user of emacs, I find emacs quite comfortable as an editing and development environment (and to some extent, it also integrates with build process, version control, quick context-sensitive search and the like, so I guess that qualifies it as an "IDE").

I'm also realtively comfortable with using vi and vi-like editors (I started out using ed, because I thought emacs was too complex; in retrospect that is backwards, but it did give me a solid foundation for future learning of vi). I use vi primarily for "small quick edits", primarily on remote machines where emacs isn't installed.

For your "I do on occasion need to ssh into server and mess around with config files; for this I use vi" scenario, I'd recommend a small set of commands and some general thoughts around vi:

Vi isn't modal, it has "a" (append), "A" (append at end of line), "i" (insert) and "I" (insert at start of line) commands, taking the text to insert as an argument and signalling "end-of-command" with Esc

h, j, k and l are movement keys. It MAY work using the arrow keys, but as the typical VT-style "I am an arrow key" sequence starts with Esc, this will break the text-insertion command you're not thinking of

:linenum moves you to line linenum, line 1 is the top-most line and line $ is the bottom-most one

. is the "repeat last command" command (see the first bullet point)

It shouldn't take more than an hour or two of playing around with vi to be at the "I can confidently edit a text file, but I may not be efficient with it" and that's as good as you'll probably need to be. Failing that, any editor that doesn't faff about auto-converting between tabs and spaces should be "good enough" for your purposes. If Eclipse is installed on all your remote servers, I don't see using that as a big problem, really.


问:
Is this pattern bad?
I notice that when I code I often use a pattern that calls a class method and that method will call a number of private functions in the same class to do the work. The private functions do one thing only. The code looks like this:

```<code>public void callThisMethod(MyObject myObject) {
    methodA(myObject);
    methodB(myObject);  // was mehtodB before
}

private void methodA(MyObject myObject) {
    //do something
}

 private void methodB(MyObject myObject) {
    //do something
}
</code>```

Sometimes there are 5 or more private methods, in the past I have moved some of the private methods into another class, but there are occasions when doing so would be creating needless complexity.

The main reason I don't like this pattern is that is not very testable, I would like to be able to test all of the methods individually, sometimes I will make all of the methods public so can I can write tests for them.

Is there a better design I can use?

答:
I believe that the pattern in question is known as composed method and it is mentioned in Kent Becks Smalltalk Best practice patterns [1]. Further, he mentions that each method does one identifiable thing and that the methods called within a method should all be at the same level of abstraction.

[1] http://www.amazon.com/Smalltalk-Best-Practice-Patterns-Kent/dp/013476904X

Title: Is this pattern bad?


问:
Should you reward based on overall project completeness or velocity?
The development team I'm in has been working on a VERY large project for months now and we recently started to implement a kanban board with agile practices into our process. We have seen MASSIVE improvement in our throughput! Its so exciting! But we have one struggle right now. We have a total ticket count for the project and our supervisor has given us incentive(candy and popcorn boxes) for when we get down to 100 and 50 tickets. It at first felt like a great idea but it feels like new tickets are created just as fast as we can resolve them, and its making the team feel worse about our progress. So heres my question:

Should you reward based on overall project completeness or velocity? And if completeness how do you make that feel more reachable?

答:
Ah, you're shooting a moving target and expecting people to pretend it was standing!

You should make up your mind on a target. If remaining ticket count is a metric, it's unfair to add tickets, especially externally, in a forced way.

In SCRUM when a sprint is planned the team commits to its content at the start, unanimously. From that point the content can only be changed by the team itself (or the sprint cancelled). Otherwise you kick the team out of control, and kill all hope of true commitment.

You may adopt some similar idea. Or drop that targeting system, and just reward healthy effort put to solve problems, accepting that you had X amount of progress, but in the meantime might have extended the project scope by more than that.

On the other hand I do suggest preventing scope creep by using milestones: add new stuff to the next milestone and you may even keep the original metric score. After the milestone is done you can plan the next one.


问:
What are non-programming mistakes that a programmer should avoid?
People make mistakes, even in the real life... Which should we, geeky programmers, avoid?</p>

答: Never eat anything larger than your own head</p>


答:
First and foremost, get a lawyer to review any license/contract you have with the software provider, as there can be (and I would expect) limitations on usage.

IANAL, but I think copyright is the wrong issue to investigate.  The schema is likely to be considered intellectual property and while maybe not copyrightable, certainly covered by any licensing or contract.  The database design, including schema, stored procedures, etc., is as much a part of the application as the Windows UI.  You have a usage license for 20 users that may very well include usage of the database in any form (if it was my company I certainly would).  If that is the case, writing your own front end expressly to get  more than 20 users will likely provide cause for the company to void your license entirely.  This would cause much more hardship to your company than the cost of a new license with a higher user count.

Title: Copyright in a database schema using a licenced windows application

Body:
I work for a company that has bought a licence for a windows client software that allows only 20 running clients per company.  I am trying to find a way around this 20 user restriction by programming a PHP web front end that connects to the existing database. This will allow unlimited users to access the database.

The problem I have is that the licence states that no CRM type interface is allowed to be used with the package.

Since I will not be using the windows binary in any way, what is to stop me from studying the database schema and developing my own front end? I would have thought that a schema that uses common tables, for example, customer addresses, materials, parts, orders etc could not be copyrighted by law otherwise a single company could have a monopoly over it.

What makes a database general or distinct enough to warrant copyright?

Any thoughts on this?


问:
In languages that don't allow underscores in integer constants, is it a good practice to create a constant for 1 billion?
In languages that don't allow underscores in integer literals, is it a good idea to create a constant for 1 billion?  e.g. in C++:

```<code>size_t ONE_BILLION = 1000000000;
</code>```

Certainly, we shouldn't create constants for small numbers like 100.  But with 9 zeros, it's arguably easy to leave off a zero or add an extra one in code like this:

```<code>tv_sec = timeInNanosec / 1000000000;
tv_nsec = timeInNanosec % 1000000000;
</code>```

答:
Do not create a constant for your big literals. You would need a constant for each such literal, which is (in my opinion) a complete joke. If you desperately need to make your literals clearer without the help of things like syntax highlighting, you could (though I would not) create functions or macros to make your life "easier":</p>

```<code>#define SPLIT3(x, y, z) x##y##z

int largeNumber1 = SPLIT3(123,456,789);
int largeNumber2 = 123456789;
</code>```

Body:
Do not create a constant for your big literals. You would need a constant for each such literal, which is (in my opinion) a complete joke. If you desperately need to make your literals clearer without the help of things like syntax highlighting, you could (though I would not) create functions or macros to make your life "easier":

#define SPLIT3(x, y, z) x##y##z

int largeNumber1 = SPLIT3(123,456,789);
int largeNumber2 = 123456789;


问:
Developing wheel reinventing tendencies into a skill as opposed to reluctantly learning wheel-finding skills?
I am more of a high-level wheel reinventor.  I definitely prefer to make use of existing API features built into a language and popular third-party frameworks that I know can solve the problem, however when I have a particular problem that I feel capable of solving within a reasonable time I am very reluctant to find someone else's solution.

Here are a few reasons why I reinvent:

It takes time to learn a new API

API restrictions might exist that I don't know about

Avoiding re-work of unfamiliar code

I am conflicted between doing what I know and shifting to a new technique I don't feel comfortable with.

On one hand I feel like following my instincts and getting really good at solving problems, especially ones that I would never challenge myself with if all I did was try to find answers. And on the other hand I feel like I might be missing out on important skills like saving time by finding the right framework and expanding my knowledge by learning how to use a new framework.

I guess my question comes down to this:

My current attitude is to stick to the built-in API and APIs I know well* and to not spend my time searching github for a solution to a problem I know I can solve myself within a reasonable amount of time.
Is that a reasonable balance for a successful programmer?

*Obviously I will still look around for new frameworks that save time and solve/simplify difficult problems.

答:
External libraries are, in a sense, a form of YAGNI.  You aren't going to need them, until and unless you actually do.

Here's why.  Every widely-used library out there is designed to satisfy a broad array of programmer needs.  It is generalized, in other words.  That generalization adds a lot of internal complexity and a learning curve.

Unless the nature your problem justifies that additional complexity and learning curve, you're better off writing the solution yourself, because you'll get a better fit to your application, less code overall, and in many cases better performance.

Naturally, there are all sorts of exceptions to this rule.  If you find a single class out there with a "do whatever you want with it" license that perfectly solves your problem, you'd be foolish to write that yourself.  If you need a framework that allows you to write lightweight web applications with excellent control over markup, a clean organizational structure, and a "get out of your way" philosophy, you'd be foolish to re-invent MVC.

To put it trivially, you don't need a 100,000 line math library to solve for 2 + 2.  But you might, if you're doing extensive statistical analysis.  Nor would you necessarily need a power drill with a Phillips bit if you're just taking the license plate off your car (even though that would probably work).  Use the tool that is the best fit for the job.


问:
How should I manage short-term user preferences, to simplify data cleanup?
When rolling out a new feature, sometimes it makes sense to notify the end user what it is, and give them an opportunity to provide feedback whether the software should get them to 'try something new' or 'put it off'.

In a cloud software, how should user preference data such as this be managed? A small piece of information would have to be stored to save the preference, but eventually, it becomes irrelevant. (The old way is phased out.) The simple thing to do is just leave that data there. After all, it doesn't take much space.

Eventually, as more features and changes come and go, and more messages are added, dismissed, and removed; there would be many items in the data storage that is no longer used, and there would be cost in the form of programmer hours in preserving or separating that data.

Are there coding and software maintenance patterns that would make sense to get rid of old data structures along with removal of old features? Is there a common solution to this data cleanup?

答:
In the version that phases out the old way, I'd add code to delete the obsolete data.  In the next version, I'd delete the code to delete the data. Hopefully this doesn't happen too often.

As an alternative, store your config data with an expiration date and update the expiration every time that particular bit of data is used.  Anything that's older than 6 months can probably be deleted.

Alternative #3 is to ignore the problem and hope it never comes back to haunt you.  I'm not a fan of this, but in some situations it's the right answer.


问:
IDE Generated Code
Many IDEs have the ability to spit out automatically written pieces of code. For example, it might generate a getter/setter pair for you. I wonder whether it isn't an attempt to work around some flaws in the language. If your IDE can figure out what the code should be without your help, why can't the compiler?

Are there cases where this is a really good idea? What kind of code generation does your IDE provide? Would the same thing be better provided as a feature of the language?

答:
Code generation from a Domain-Specific Language, to let you focus on writing what matters, is good.

Code generation from an IDE, to create boiler-plate code, is a sign the language sucks.

Your specific example - generating getters and setters* certainly shows a language problem.

You should only be writing a getter/setter if it does something - but if it's generic that doesn't mean you let the IDE generate it, it means you don't need it in the code at all. (Don't waste developer brain power figuring out if a function is generic or if it has a subtle difference - just leave the 'empty' functions out.)

Oh, and whilst technically IDE-based code generation, snippets/templates, - i.e. typing fpubstr and getting public string function( ) or equivalent - is also a form of immediate DSL-based generation, and thus a good thing (an actual language which had commands like fpubstr/fpubint/fprvint would be horrible to read).

* Ignoring temporarily that getters and setters are more than likely a sign of bad OO design.

Title: IDE Generated Code


答:
Next time you go for a walk, try counting all the different implementations you see of the wheel concept. The fact that some caveman long ago invented the wheel doesn't people from creating new versions of wheels for various purposes all the time. In the programming world, libraries and frameworks are not like the wheel concept, they're like wheel implementations. In programming lingo, wheel is a design pattern.

So no, of course there's nothing wrong with creating your own tools, libraries, frameworks, whatever. That may be the most expedient approach, and you're sure to get exactly what you want.

On the other hand, you should really get over your reluctance to use things that other people have written. Reusing code is often better than writing your own because you get a tool that has already been written, tested, debugged, and improved, and all you have to do to use it is learn a little bit about its interface. That can save you a lot of time and money. It's not always the right choice, but it's not one that you should automatically reject.

If a set of stock wheels will fit the vehicle you're building, machining a set of custom rims and fabricating your own tires is often overkill. But if stock wheels don't fit, or cost too much, or don't work quite right, building your own may be the best option.

Title: Developing wheel reinventing tendencies into a skill as opposed to reluctantly learning wheel-finding skills?

Body:
I am more of a high-level wheel reinventor.  I definitely prefer to make use of existing API features built into a language and popular third-party frameworks that I know can solve the problem, however when I have a particular problem that I feel capable of solving within a reasonable time I am very reluctant to find someone else's solution.

Here are a few reasons why I reinvent:

It takes time to learn a new API

API restrictions might exist that I don't know about

Avoiding re-work of unfamiliar code

I am conflicted between doing what I know and shifting to a new technique I don't feel comfortable with.

On one hand I feel like following my instincts and getting really good at solving problems, especially ones that I would never challenge myself with if all I did was try to find answers. And on the other hand I feel like I might be missing out on important skills like saving time by finding the right framework and expanding my knowledge by learning how to use a new framework.

I guess my question comes down to this:

My current attitude is to stick to the built-in API and APIs I know well* and to not spend my time searching github for a solution to a problem I know I can solve myself within a reasonable amount of time.
Is that a reasonable balance for a successful programmer?

*Obviously I will still look around for new frameworks that save time and solve/simplify difficult problems.


答:
The simplest approach is to just stick a cookie on the user's machine with a short expiration.  When you kill the setting, remove the code that handles it.

This solution has numerous disadvantages, but it does removes data cleanup concerns.

Title: How should I manage short-term user preferences, to simplify data cleanup?

Body:
When rolling out a new feature, sometimes it makes sense to notify the end user what it is, and give them an opportunity to provide feedback whether the software should get them to 'try something new' or 'put it off'.

In a cloud software, how should user preference data such as this be managed? A small piece of information would have to be stored to save the preference, but eventually, it becomes irrelevant. (The old way is phased out.) The simple thing to do is just leave that data there. After all, it doesn't take much space.

Eventually, as more features and changes come and go, and more messages are added, dismissed, and removed; there would be many items in the data storage that is no longer used, and there would be cost in the form of programmer hours in preserving or separating that data.

Are there coding and software maintenance patterns that would make sense to get rid of old data structures along with removal of old features? Is there a common solution to this data cleanup?


问:
Which could be a good design pattern for complex numeric calculations between three or more different data models?
The source code I'm working on at the moment performs numeric calculations between a bunch of different properties belonging to different data models. All the calculations are  coded in a big method with a lot of If statements than make it very complex, difficult to change and it contains some bugs.

I have not found a design pattern that fits into this problem that I think is very common in any financial application. Any help with this?

The source code is c# with .NET fw 4.

答:
Well, I don't believe there is a design pattern which can help you here, but maybe some "tactics". Honestly, it is hard to give you a good answer with so few bits of information. Here are my thoughts, based on some guessing how your code may look like:

start by refactoring that (too) big method into smaller methods. Make the structure transparent, introduce variables for intermediate results, decouple independent parts of the calculation, make sure the same calculation does not exist redundantly in two places of your source code. Also, introduce data structures for attributes which belong together

visualize your data flow (for example, by drawing a data flow diagram). This will help you to understand the dependencies better and probably help you by further refactoring into indenpendent parts or components. It will also help you to understand where you have to change something when a new requirement arises.

check if you really need a "push model" for your calculations (a change in one attribute triggers a sequence of calculations, you have to update a lot of intermediate variables, perhaps have to deal with unwanted side effects), or if you can switch to a more functional "pull model" (only when a specific value is needed the related calculations are triggered, calculating all the intermediate results from the current state of your input variables). A "pull model" works like an SQL view in a relational DB, a "push model" like an utility table in a relational database which has to be filled with redundant data.

it may be also a good idea to decouple your program from that "3 different data models" by introducing an intermediate layer which gives your calculation code a view upon the data which is suited for its needs. But with so few information how you calculation may look like, I am unsure if thats the right decision in your case, you have to decide that by yourself.


问:
Is SQL declarative?
I ask because so many of the questions I see in SQL amount to: "This is slow. How do I speed it up"? Or are tutorials stating "Do this this way and not that way as it's faster".

It seems to me that a large part of SQL is knowing just how an expression would be performed and from that knowledge chosing expression styles that perform better. This doesn't square with one aspect of declaritive programming - that of leaving the system to decide how best to perform the calculation with you just specifying what the calculation should produce.

Shouldn't an SQL engine not care about if you used in, exists or join if it is truly declarative shouldn't it just give you the correct answer in reasonable time if possible by any of the three methods? This last example is prompted by this recent post which is of the type mentioned in my opening paragraph.

Indexes

I guess the easiest example I could have used relates to creating an index for a table. The gumph here on w3schools.com even tries to explain it as something unseen by the user that is there for performance reasons. Their description seems to put SQL indices in the non-declarative camp and they are routinely added by hand for purely performance reasons.

Is it the case that their is somewhere an ideal SQL DB that is much more declarative than all the rest but because it is that good one doesn't hear about it?

答:
SQL is theoretically declarative.  But you know what they say about the difference between theory and practice...

At its core, the concept of "declarative programming" has never been truly effective, and likely never will until we have an AI-based compiler that's capable of looking at code and answering the question "what is the intention of this code?" intelligently, in the same way that the person who wrote it would.  At the heart of every declarative language is a whole bunch of imperative code trying frantically to solve that problem without the help of an AI.

Often it works surprisingly well, because the most common cases are common cases, which the people who wrote the language's implementation knew about and found good ways to handle.  But then you  run up against an edge case that the implementor didn't consider, and you see performance degrade quickly as the interpreter is forced to take the code much more literally and handle it in a less efficient manner.

Title: Is SQL declarative?


问:
Solo developer vs. team developer : should I move on?
I work as a solo developer in a small company. There's more than enough work, but the same does not apply for money. Thus, I won't be seeing any new colleagues in the near future.

I am responsible for absolutely everything that has do to with IT operations. This involves development and maintenance of software used in-house, development and maintenance of various websites which our clients use, website infrastructure, local network infrastructure including maintenance of several servers and in-house support to mention the most immediate things.

I really enjoy 95% of what I do, and I've got a high degree of flexibility in my work. I get to decide what do when, and no one really tells me what do to except that I now and then sit down with my colleagues to create a roadmap for what I need to get done. I do consider myself to have a high work ethic and being above average focused on what I do, so things get done.

However, I've come to the point where I really miss having other people around me who work with the same. Even though I need to get familiar with a wide range of technologies as I am a solo developer, I have the feeling that I am missing out one the "knowledge sharing" which other "like minded" people who work in bigger companies are taking part in. I don't really have anyone to discuss programming obstacles and design decisions with - and I am starting to miss that. Also, I'm worried about what future employers might think of this "hermit" who has been working on his own for too long to ever be able to take part in a team.

However, on the other side, I'm thinking that I won't get my current degree of flexibility in a larger company. I'll be seeing a lot more strict deadlines, late hours and specialized areas of work. Also; I'm not sure if this idea of "knowledge sharing" will ever take take place?

Has anyone else been in this situation? Is it a good idea seen from a career perspective and a personal development perspective? Should I consider moving on to a bigger place to (maybe) become a part of a larger group of developers and "like minded" people? In other words, will the grass be greener on the other side?

答: If you are enjoying your work and only missing knowledge sharing, consider joining an open source project instead of changing the job. Unless you already know the people you will be working with, you have no idea whether the grass will be greener on the other side.</p>